Wilsonov teorem: razlika između inačica
Izbrisani sadržaj Dodani sadržaj
Oznake: mobilni uređaj m.wiki |
Oznake: mobilni uređaj m.wiki |
||
Redak 13:
Kako je <math> (a, n) = 1, </math> prema [[Bezoutov identitet|Bezoutovom identitetu]] slijedi da postoje <math> k, l \in \mathbb{Z} </math> takvi da je <math> ak + nl = 1. </math> Odavde dobivamo <math> akb + nlb = b. </math> Sada zbog toga što he <math> n \mid nlb </math> vrijedi <math> akb = b \pmod n. </math> Stavljamo <math> x := kb, </math> što je rješenje početne kongruencije. Dakako, prema gornjoj napomeni, rješenja su i svi brojevi kongruentni <math> x </math> modulo <math> n. </math> No, trebamo pokazati da su to sva rješenja. U tu svrhu, pretpostavimo da postoji neko drugo rješenje, <math> y \not\equiv x \pmod n. </math> Imali bismo, <math> ax \equiv b \pmod n, ay \equiv b \pmod n, </math> no to povlači <math> ax = ay \pmod n. </math> Odatle (jer je <math> (a, n) = 1 </math>) dobivamo <math> x \equiv y \pmod n,</math> što je kontradikcija. Time je dokazana jedinstvenost rješenja.
Dakle, sva rješenja su u parovima kongruenta modulo <math> n. </math> Valja napomenuti da rješenje za <math> b = 1 </math> zovemo ''multiplikativnim inverzom broja'' <math> a </math> ''modulo'' <math> p.
Sada je lako dokazati Wilsonov teorem. Naime, svaki je od brojeva <math> \{1, 2, ..., p - 1\} </math> relativno prost s <math> p </math> pa nam prethodna lema može pomoći. Prema gornjoj lemi, svaki od faktora <math> (p - 1)! = 1 \cdot 2 \cdot ... \cdot (p - 1) </math> ima svoj multiplikativni inverz modulo <math> p, </math> osim brojeva koji su sami sebi inverzni modulo <math> p. </math> Nađimo sve takve faktore. Neka je <math> S = \{1, 2, ..., p - 1\} </math> te neka je <math> x \in S </math> za koji vrijedi <math> x^2 \equiv 1 \pmod n. </math> Tada <math> p \mid (x - 1)(x + 1) . </math> Kako je <math> p </math> prost i <math> p \leq x \leq p - 1 </math> slijedi (prema Euklidovoj lemi) da postoje samo dva takva broja <math> p = x - 1 \iff x = p + 1 </math> ili <math> p = x + 1 \iff x = p - 1. </math> No, <math> p + 1 \not\in S, </math> ali su prema gornjoj lemi rješenja svi brojevi kongruentni s <math> p + 1 </math> modulo <math> p. </math> Očito je onda i broj <math> 1 \in S, </math> uz <math> p - 1 \in S, </math> rješenje gornje kvadratne kongruencije. Sada je jasno da su svi parovi <math> (k, p - k), k \in \mathbb{N}</math> osim para <math> (1, p - 1), </math> kongruenti <math> 1 </math> modulo <math> p. </math> Prema tome, <math> (p - 1)! \equiv p - 1 \pmod p, </math> iz čega je konačno <math> (p - 1)! \equiv - 1 \pmod p, </math> što je i trebalo dokazati.
== Zanimljivosti ==
| |||