Školjka

%V0 dokazat cemo cak nesto jacu tvrdnju: Neka su $(a_1,a_2,...,a_n)$ cijeli brojevi. Tada postoje cijeli brojevi $(\lambda_1, \lambda_2, \dots , \lambda_n)$, koji su svi razliciti od $0$, takvi da je $$\lambda_1a_1+\lambda_2a_2 +...+\lambda_na_n=M(a_1, ..., a_n)$$ za $n = 2$, ovo je poznata lema. za slucaj da netko nezna lemu, evo leme i dokaza: [b] lema [/b] neka su $c$ i $d$ cijeli brojevi. tada postoje cijeli brojevi $k$ i $l$ takvi da je $ck + dl = M(c,d)$ [b] dokaz [/b] neka je $M(c,d) = r, c = ar, d = br$. 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 vrijednosti 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 $ka + lb = 1$, tj mnozeci s $r$, $kc + ld = M(c,d)$, cime je lema dokazana. dodatno, za potrebe naseg zadatka, postoje takvi $k$ i $l$ koji su oba razliti od $0$. zaista, cim 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$. kako vrijedi za $n$, pronadimo brojeve $\lambda_1', ... \lambda_n'$, takve da je $\lambda_1'a_1 + ... + \lambda_n'a_n = M(a_1,...a_n)$. ali sada ponovo upotrijebimo tvrdnju za $n=2$ i brojeve $M(a_1,...a_n)$ i broj $a_{n+1}$. drugim rjecima, postoje $k$ i $l$, oba razliciti od $0$ takvi da je $kM(a_1,...a_n) + la_{n+1} = M ( M(a_1,...a_n), a_{n+1} ) = M(a_1,...a_{n+1})$. dakle nasa tvrdnja vrijedi uz $(\lambda_1,...,\lambda_n,\lambda_{n+1}) = (k \lambda_1',...,k \lambda_n', l)$, te je jasno da su svi ovi brojevi razlicti od $0$. posebno, za ovaj zadatak znamo da je $M(a_1,...a_n) = 1$, dakle, postoje $(\lambda_1',...,\lambda_n')$ za koje vrijedi $\lambda_1'a_1 + ... + \lambda_n'a_n = 1$, pa za $(\lambda_1,...,\lambda_n) = (2013 \lambda_1',...,2013 \lambda_n')$ vrijedi tvrdnja zadatka.