Školjka

%V0 za $n = 2$, ovo je poznata lema. za slucaj da netko nezna lemu, evo leme i dokaza: [b] lema [/b] neka su $a$ i $b$ relativno prosti cijeli brojevi. tada postoje cijeli brojevi $k$ i $l$ takvi da je $ak + bl = 1$ [b] dokaz [/b] promotrimo brojeve $b, 2b, ..., ab$. u ovome skupu od $a$ brojeva, pojavljuju se svi moguci ostaci modulo $a$. zaista kada nebi bilo tako, onda se neki ostatak nebi pojavljivao, pa bi se nuzno neki ostatak morao javiti dva puta. drugim rjecima, bilo bi $ib \equiv jb ( \cdot a )$, za neke razlicite $i$ i $j$ iz skupa $\{1, 2, ..., a \}$. ali tada bi bilo $ a | (i-j)b $. no zbog toga sto su $a$ i $b$ po pretpostavci relativno prosti, znacilo bi da $ a | (i-j) $, sto ocito nije moguce s obzirom da su $i$ i $j$ iz skupa $\{1, 2, ..., a \}$, pa je njihova razlika po apsolutnoj rijednosti manja od $a$. dakle, medu pocetnih $a$ brojeva $b, 2b, ... , ab$, javljaju se svi moguci ostaci modulo $a$, pa tako posebno i ostatak $1$. neka je onda $nb \equiv 1 ( \cdot a )$. drugim rjecima, postoji cijeli broj $m$ tako da je $nb - 1 = ma$, tj $nb - ma = 1$. uz $k = -m$ i $l = n$, pronasli smo $k$ i $l$ koji zadovoljavaju uvete nase leme. dodatno, za potrebe naseg zadatka, postoje takvi $k$ i $l$ koji su oba razliti od $0$. zaista, cim je su i $a$ i $b$ razliciti od $1$, jasno je da nece ni $k$ ni $l$ biti jednaki $0$, jer u suprotnom bismo imali npr $ka = 1$, za $a \neq 1$, sto naravno ne moze vrijediti. s druge strane, ako je tocno jedan od brojeva, npr $b$ jednak $1$, lako se uzme $k=1, l = (a-1)$. naposlijetku, ako su oba jednaka $1$, naravno, uzme se $k=2$, $l=-1$, pa tvrdnja ponovo vrijedi. nastavljamo s dokazom koristeci indukciju. baza, za $n=2$, tvrdnja vrijedi. pretpostavimo da vrijedi za broj $n$, te dokazimo da vrijedi za $n+1$. pretpostavimo takoder da medu brojevima $a_1,...a_{n+1}$, postoji neki broj koji je razlicit od $1$, te BSO, neka je to bas broj $a_{n+1}$. u slucaju da su svi brojevi jednaki $1$, lako se vidi da npr $(\lambda_1,...\lambda_n, \lambda_{n+1}) = ( 1, 1, ..., 1, 1 - n )$ zadovoljavaju uvjet zadataka. kako vrijedi za $n$, pronadimo brojeve $\lambda_1', ... \lambda_n'$, takve da je $\lambda_1'a_1 + ... + \lambda_n'a_n = 1$. mnozeci ovu relaciju s $1 - a_{n+1} \neq 0$, te supstitucijom $c_i = \lambda_i' (1 - a_{n+1}) \neq 0 $, za $i = 1,...,n$, dobijamo $c_1a_1 + ... + c_na_n = 1 - a_{n+1}$, odnosno $c_1a_1 + ... + c_na_n + a_{n+1} = 1$, pa tvrdnja vrijedi uz $(\lambda_1, ... \lambda_n, \lambda_{n+1}) = (c_1, ..., c_n, 1)$