dokazat cemo cak nesto jacu tvrdnju:
Neka su
![(a_1,a_2,...,a_n)](/media/m/2/a/f/2afa3811e8421900767032ed4273e0de.png)
cijeli brojevi. Tada postoje cijeli brojevi
![(\lambda_1, \lambda_2, \dots , \lambda_n)](/media/m/c/d/a/cda8eb9286f19aa96ae68abc750c7b99.png)
, koji su svi razliciti od
![0](/media/m/7/b/8/7b8b0b058cf5852d38ded7a42d6292f5.png)
, takvi da je
![\lambda_1a_1+\lambda_2a_2 +...+\lambda_na_n=M(a_1, ..., a_n)](/media/m/a/e/b/aebff34a51e905ecbe239109f3d08b71.png)
za
![n = 2](/media/m/5/d/e/5de286c03f7be13a5a67f0265685173b.png)
, ovo je poznata lema. za slucaj da netko nezna lemu, evo leme i dokaza:
lema neka su
![c](/media/m/e/a/3/ea344283b6fa26e4a02989dd1fb52a51.png)
i
![d](/media/m/f/7/d/f7d3dcc684965febe6006946a72e0cd3.png)
cijeli brojevi. tada postoje cijeli brojevi
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
i
![l](/media/m/e/e/9/ee975101080f37986f56baaf4c3cdcd2.png)
takvi da je
dokaz neka je
![M(c,d) = r, c = ar, d = br](/media/m/3/4/7/34776c04f2125731ba8133f25f7ebf48.png)
. promotrimo brojeve
![b, 2b, ..., ab](/media/m/1/2/3/123615b301ffec8d71094e3299eac564.png)
. u ovome skupu od
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
brojeva, pojavljuju se svi moguci ostaci modulo
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
. 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 )](/media/m/2/b/5/2b5e7304d1d553f6f52860ff1998985a.png)
, za neke razlicite
![i](/media/m/3/2/d/32d270270062c6863fe475c6a99da9fc.png)
i
![j](/media/m/7/9/e/79ebb10f98eb80d16b0c785d9d682a72.png)
iz skupa
![\{1, 2, ..., a \}](/media/m/2/c/f/2cfd4896cd42883dc5b0a7d9d95ca486.png)
. ali tada bi bilo
![a | (i-j)b](/media/m/0/0/8/0089988e7b5a5eb05728d290c4be5bcd.png)
. no zbog toga sto su
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
i
![b](/media/m/e/e/c/eec0d7323095a1f2101fc1a74d069df6.png)
po pretpostavci relativno prosti, znacilo bi da
![a | (i-j)](/media/m/5/3/b/53b73be7fd8b2dedddff3c303fa22319.png)
, sto ocito nije moguce s obzirom da su
![i](/media/m/3/2/d/32d270270062c6863fe475c6a99da9fc.png)
i
![j](/media/m/7/9/e/79ebb10f98eb80d16b0c785d9d682a72.png)
iz skupa
![\{1, 2, ..., a \}](/media/m/2/c/f/2cfd4896cd42883dc5b0a7d9d95ca486.png)
, pa je njihova razlika po apsolutnoj vrijednosti manja od
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
. dakle, medu pocetnih
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
brojeva
![b, 2b, ... , ab](/media/m/4/e/e/4ee1d3d13e1d3ca471a9e485c53831a2.png)
, javljaju se svi moguci ostaci modulo
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
, pa tako posebno i ostatak
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
. neka je onda
![nb \equiv 1 ( \cdot a )](/media/m/b/a/7/ba7275ad33313ca8da34d449eb75cd06.png)
. drugim rjecima, postoji cijeli broj
![m](/media/m/1/3/6/1361d4850444c055a8a322281f279b39.png)
tako da je
![nb - 1 = ma](/media/m/e/c/d/ecdf929b7e275c81ce72810f22b13ab7.png)
, tj
![nb - ma = 1](/media/m/d/1/5/d1543eff0f7a41606068e69a670d357b.png)
. uz
![k = -m](/media/m/b/8/0/b8084bb8ddacb19f978fc7e6d8e0af0a.png)
i
![l = n](/media/m/a/6/0/a601ac42f01ccd376a5d689fc1de2a6c.png)
, pronasli smo
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
i
![l](/media/m/e/e/9/ee975101080f37986f56baaf4c3cdcd2.png)
koji zadovoljavaju
![ka + lb = 1](/media/m/9/0/b/90b73750ef4687bc8e078ecf533d3237.png)
, tj mnozeci s
![r](/media/m/3/d/f/3df7cc5bbfb7b3948b16db0d40571068.png)
,
![kc + ld = M(c,d)](/media/m/1/0/6/1062b7bf1506cf16f89650460cf29310.png)
, cime je lema dokazana.
dodatno, za potrebe naseg zadatka, postoje takvi
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
i
![l](/media/m/e/e/9/ee975101080f37986f56baaf4c3cdcd2.png)
koji su oba razliti od
![0](/media/m/7/b/8/7b8b0b058cf5852d38ded7a42d6292f5.png)
. zaista, cim su i
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
i
![b](/media/m/e/e/c/eec0d7323095a1f2101fc1a74d069df6.png)
razliciti od
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
, jasno je da nece ni
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
ni
![l](/media/m/e/e/9/ee975101080f37986f56baaf4c3cdcd2.png)
biti jednaki
![0](/media/m/7/b/8/7b8b0b058cf5852d38ded7a42d6292f5.png)
, jer u suprotnom bismo imali npr
![ka = 1](/media/m/7/c/e/7cea449a98ea06ebe7e2926db59601b0.png)
, za
![a \neq 1](/media/m/7/f/3/7f3e0e7a5db3e2fdd18f4b5264104e8e.png)
, sto naravno ne moze vrijediti. s druge strane, ako je tocno jedan od brojeva, npr
![b](/media/m/e/e/c/eec0d7323095a1f2101fc1a74d069df6.png)
jednak
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
, lako se uzme
![k=1, l = (a-1)](/media/m/d/7/d/d7da410713561ee2168a25b33cc50451.png)
. naposlijetku, ako su oba jednaka
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
, naravno, uzme se
![k=2](/media/m/b/2/c/b2c85402c049e3e48f39c947b9411e8a.png)
,
![l=-1](/media/m/7/2/f/72f95f06607cd26e329da336fc8e5a77.png)
, pa tvrdnja ponovo vrijedi.
nastavljamo s dokazom koristeci indukciju. baza, za
![n=2](/media/m/e/8/2/e82e9f27692b705eb8b201ab32bd0a83.png)
, tvrdnja vrijedi. pretpostavimo da vrijedi za broj
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
, te dokazimo da vrijedi za
![n+1](/media/m/2/a/7/2a7327e09a84d01a602088c9f045cbde.png)
. kako vrijedi za
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
, pronadimo brojeve
![\lambda_1', ... \lambda_n'](/media/m/a/5/d/a5df8dc305ceb0ffee5e22b26e41044a.png)
, takve da je
![\lambda_1'a_1 + ... + \lambda_n'a_n = M(a_1,...a_n)](/media/m/1/b/d/1bd51ade50018ba359cfa7b1d322fbae.png)
. ali sada ponovo upotrijebimo tvrdnju za
![n=2](/media/m/e/8/2/e82e9f27692b705eb8b201ab32bd0a83.png)
i brojeve
![M(a_1,...a_n)](/media/m/2/4/0/24030f895fbe5c6d623b8ca464b6473b.png)
i broj
![a_{n+1}](/media/m/5/a/5/5a5045f99ae50b191e743cf02926d28c.png)
. drugim rjecima, postoje
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
i
![l](/media/m/e/e/9/ee975101080f37986f56baaf4c3cdcd2.png)
, oba razliciti od
![0](/media/m/7/b/8/7b8b0b058cf5852d38ded7a42d6292f5.png)
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})](/media/m/d/e/2/de23e25554c22ec8846599d28ed189f7.png)
. dakle nasa tvrdnja vrijedi uz
![(\lambda_1,...,\lambda_n,\lambda_{n+1}) = (k \lambda_1',...,k \lambda_n', l)](/media/m/b/c/9/bc9b90a8f1e88dc5887aef9053ec32af.png)
, te je jasno da su svi ovi brojevi razlicti od
![0](/media/m/7/b/8/7b8b0b058cf5852d38ded7a42d6292f5.png)
.
posebno, za ovaj zadatak znamo da je
![M(a_1,...a_n) = 1](/media/m/0/0/b/00b9c832a2d2b101b91659c13d631eda.png)
, dakle, postoje
![(\lambda_1',...,\lambda_n')](/media/m/c/0/7/c079a8db2566bd8e00da69a664953edb.png)
za koje vrijedi
![\lambda_1'a_1 + ... + \lambda_n'a_n = 1](/media/m/f/1/f/f1f07de374418afaa2512665ad5035db.png)
, pa za
![(\lambda_1,...,\lambda_n) = (2013 \lambda_1',...,2013 \lambda_n')](/media/m/1/d/d/1dd2c8fbe433f7390ff7314407f60ae7.png)
vrijedi tvrdnja zadatka.
%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.