Točno
8. prosinca 2013. 17:17 (10 godine, 7 mjeseci)
Sakrij rješenje
Sakrij rješenje
Upozorenje: Ovaj zadatak još niste riješili!
Kliknite ovdje kako biste prikazali rješenje.
Kliknite ovdje kako biste prikazali rješenje.
za
, ovo je poznata lema. za slucaj da netko nezna lemu, evo leme i dokaza:
lema neka su
i
relativno prosti cijeli brojevi. tada postoje cijeli brojevi
i
takvi da je ![ak + bl = 1](/media/m/2/6/2/26209fbc4ef4ead81fc574cf1bbe41fb.png)
dokaz promotrimo brojeve
. u ovome skupu od
brojeva, pojavljuju se svi moguci ostaci modulo
. 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
, za neke razlicite
i
iz skupa
. ali tada bi bilo
. no zbog toga sto su
i
po pretpostavci relativno prosti, znacilo bi da
, sto ocito nije moguce s obzirom da su
i
iz skupa
, pa je njihova razlika po apsolutnoj rijednosti manja od
. dakle, medu pocetnih
brojeva
, javljaju se svi moguci ostaci modulo
, pa tako posebno i ostatak
. neka je onda
. drugim rjecima, postoji cijeli broj
tako da je
, tj
. uz
i
, pronasli smo
i
koji zadovoljavaju uvete nase leme.
dodatno, za potrebe naseg zadatka, postoje takvi
i
koji su oba razliti od
. zaista, cim je su i
i
razliciti od
, jasno je da nece ni
ni
biti jednaki
, jer u suprotnom bismo imali npr
, za
, sto naravno ne moze vrijediti. s druge strane, ako je tocno jedan od brojeva, npr
jednak
, lako se uzme
. naposlijetku, ako su oba jednaka
, naravno, uzme se
,
, pa tvrdnja ponovo vrijedi.
nastavljamo s dokazom koristeci indukciju. baza, za
, tvrdnja vrijedi. pretpostavimo da vrijedi za broj
, te dokazimo da vrijedi za
. pretpostavimo takoder da medu brojevima
, postoji neki broj koji je razlicit od
, te BSO, neka je to bas broj
. u slucaju da su svi brojevi jednaki
, lako se vidi da npr
zadovoljavaju uvjet zadataka. kako vrijedi za
, pronadimo brojeve
, takve da je
. mnozeci ovu relaciju s
, te supstitucijom
, za
, dobijamo
, odnosno
, pa tvrdnja vrijedi uz
![n = 2](/media/m/5/d/e/5de286c03f7be13a5a67f0265685173b.png)
lema neka su
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![b](/media/m/e/e/c/eec0d7323095a1f2101fc1a74d069df6.png)
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
![l](/media/m/e/e/9/ee975101080f37986f56baaf4c3cdcd2.png)
![ak + bl = 1](/media/m/2/6/2/26209fbc4ef4ead81fc574cf1bbe41fb.png)
dokaz promotrimo brojeve
![b, 2b, ..., ab](/media/m/1/2/3/123615b301ffec8d71094e3299eac564.png)
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![ib \equiv jb ( \cdot a )](/media/m/2/b/5/2b5e7304d1d553f6f52860ff1998985a.png)
![i](/media/m/3/2/d/32d270270062c6863fe475c6a99da9fc.png)
![j](/media/m/7/9/e/79ebb10f98eb80d16b0c785d9d682a72.png)
![\{1, 2, ..., a \}](/media/m/2/c/f/2cfd4896cd42883dc5b0a7d9d95ca486.png)
![a | (i-j)b](/media/m/0/0/8/0089988e7b5a5eb05728d290c4be5bcd.png)
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![b](/media/m/e/e/c/eec0d7323095a1f2101fc1a74d069df6.png)
![a | (i-j)](/media/m/5/3/b/53b73be7fd8b2dedddff3c303fa22319.png)
![i](/media/m/3/2/d/32d270270062c6863fe475c6a99da9fc.png)
![j](/media/m/7/9/e/79ebb10f98eb80d16b0c785d9d682a72.png)
![\{1, 2, ..., a \}](/media/m/2/c/f/2cfd4896cd42883dc5b0a7d9d95ca486.png)
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![b, 2b, ... , ab](/media/m/4/e/e/4ee1d3d13e1d3ca471a9e485c53831a2.png)
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
![nb \equiv 1 ( \cdot a )](/media/m/b/a/7/ba7275ad33313ca8da34d449eb75cd06.png)
![m](/media/m/1/3/6/1361d4850444c055a8a322281f279b39.png)
![nb - 1 = ma](/media/m/e/c/d/ecdf929b7e275c81ce72810f22b13ab7.png)
![nb - ma = 1](/media/m/d/1/5/d1543eff0f7a41606068e69a670d357b.png)
![k = -m](/media/m/b/8/0/b8084bb8ddacb19f978fc7e6d8e0af0a.png)
![l = n](/media/m/a/6/0/a601ac42f01ccd376a5d689fc1de2a6c.png)
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
![l](/media/m/e/e/9/ee975101080f37986f56baaf4c3cdcd2.png)
dodatno, za potrebe naseg zadatka, postoje takvi
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
![l](/media/m/e/e/9/ee975101080f37986f56baaf4c3cdcd2.png)
![0](/media/m/7/b/8/7b8b0b058cf5852d38ded7a42d6292f5.png)
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![b](/media/m/e/e/c/eec0d7323095a1f2101fc1a74d069df6.png)
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
![l](/media/m/e/e/9/ee975101080f37986f56baaf4c3cdcd2.png)
![0](/media/m/7/b/8/7b8b0b058cf5852d38ded7a42d6292f5.png)
![ka = 1](/media/m/7/c/e/7cea449a98ea06ebe7e2926db59601b0.png)
![a \neq 1](/media/m/7/f/3/7f3e0e7a5db3e2fdd18f4b5264104e8e.png)
![b](/media/m/e/e/c/eec0d7323095a1f2101fc1a74d069df6.png)
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
![k=1, l = (a-1)](/media/m/d/7/d/d7da410713561ee2168a25b33cc50451.png)
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
![k=2](/media/m/b/2/c/b2c85402c049e3e48f39c947b9411e8a.png)
![l=-1](/media/m/7/2/f/72f95f06607cd26e329da336fc8e5a77.png)
nastavljamo s dokazom koristeci indukciju. baza, za
![n=2](/media/m/e/8/2/e82e9f27692b705eb8b201ab32bd0a83.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![n+1](/media/m/2/a/7/2a7327e09a84d01a602088c9f045cbde.png)
![a_1,...a_{n+1}](/media/m/6/f/5/6f53230cfbd411305f6eb92db36071a3.png)
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
![a_{n+1}](/media/m/5/a/5/5a5045f99ae50b191e743cf02926d28c.png)
![1](/media/m/a/9/1/a913f49384c0227c8ea296a725bfc987.png)
![(\lambda_1,...\lambda_n, \lambda_{n+1}) = ( 1, 1, ..., 1, 1 - n )](/media/m/b/c/7/bc7ec481c67e51e4fcff9d4527212962.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![\lambda_1', ... \lambda_n'](/media/m/a/5/d/a5df8dc305ceb0ffee5e22b26e41044a.png)
![\lambda_1'a_1 + ... + \lambda_n'a_n = 1](/media/m/f/1/f/f1f07de374418afaa2512665ad5035db.png)
![1 - a_{n+1} \neq 0](/media/m/1/1/a/11a23992d252ee781255239e3d9b3a57.png)
![c_i = \lambda_i' (1 - a_{n+1}) \neq 0](/media/m/1/5/9/159a07cff27ec6c9606bfefa3e5e8ab4.png)
![i = 1,...,n](/media/m/9/7/4/9740af11bf473fafdcec6390fa078af5.png)
![c_1a_1 + ... + c_na_n = 1 - a_{n+1}](/media/m/2/0/2/20244686d56d124e0a13c8c9a95bbcb9.png)
![c_1a_1 + ... + c_na_n + a_{n+1} = 1](/media/m/7/4/0/74015ed2b4e2e9ea103242e166a2bd2e.png)
![(\lambda_1, ... \lambda_n, \lambda_{n+1}) = (c_1, ..., c_n, 1)](/media/m/8/6/b/86b1ba6aae4602ef54c1346e2210b7f4.png)