Wilsonov teorem

Wilsonov teorem je jedan od najvažnijih teorema elementarne teorije brojeva koji tvrdi da ako je [math]\displaystyle{ p }[/math] prost broj, vrijedi [math]\displaystyle{ (p - 1)! \equiv - 1 \pmod p. }[/math]

Teorem je prvi iskazao arapski matematičar Ibn al-Haytham još u 10. stoljeću, no ponovno je iskazan u 18. stoljeću od strane engleskih matematičara Johna Wilsona i Edwarda Waringa. Ipak, ovaj je teorem dokazao veliki talijanski matematičar Joseph-Louis Lagrange 1771. godine.

Dokaz

Ovdje ćemo iznijeti elementarni dokaz ovoga teorema koji koristi tzv. modularne multiplikativne inverze. No, prije svega ćemo dokazati sljedeću lemu.

Lema. Ako su [math]\displaystyle{ a, n }[/math] relativno prosti, tada za svaki cijeli broj [math]\displaystyle{ b }[/math] postoji jedinstveno rješenje kongruencije [math]\displaystyle{ ax \equiv b \pmod n. }[/math]

Napomenimo da je rješenje kongruencije svaki [math]\displaystyle{ x }[/math] oblika [math]\displaystyle{ qn + b, \forall q \in \mathbb{Z}. }[/math]

Kako je [math]\displaystyle{ M(a, n) = 1, }[/math] prema Bezoutovom identitetu slijedi da postoje [math]\displaystyle{ k, l \in \mathbb{Z} }[/math] takvi da je [math]\displaystyle{ ak + nl = 1. }[/math] Odavde dobivamo [math]\displaystyle{ akb + nlb = b. }[/math] Sada zbog toga što [math]\displaystyle{ n \mid nlb }[/math] vrijedi [math]\displaystyle{ akb \equiv b \pmod n. }[/math] Stavljamo [math]\displaystyle{ x := kb, }[/math] što je rješenje početne kongruencije. Dakako, prema gornjoj napomeni, rješenja su i svi brojevi kongruentni [math]\displaystyle{ x }[/math] modulo [math]\displaystyle{ n. }[/math] No, trebamo pokazati da su to sva rješenja. U tu svrhu, pretpostavimo da postoji neko drugo rješenje, [math]\displaystyle{ y \not\equiv x \pmod n. }[/math] Imali bismo, [math]\displaystyle{ ax \equiv b \pmod n, ay \equiv b \pmod n, }[/math] no to povlači [math]\displaystyle{ ax \equiv ay \pmod n. }[/math] Odatle (jer je [math]\displaystyle{ M(a, n) = 1 }[/math]) dobivamo [math]\displaystyle{ 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]\displaystyle{ n. }[/math] Valja napomenuti da rješenje za [math]\displaystyle{ b = 1 }[/math] zovemo multiplikativnim inverzom broja [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ p. }[/math]

Sada je lako dokazati Wilsonov teorem. Naime, svaki je od brojeva [math]\displaystyle{ \{1, 2, ..., p - 1\} }[/math] relativno prost s [math]\displaystyle{ p }[/math] pa nam prethodna lema može pomoći. Prema gornjoj lemi, svaki od faktora [math]\displaystyle{ (p - 1)! = 1 \cdot 2 \cdot ... \cdot (p - 1) = P }[/math] ima svoj multiplikativni inverz modulo [math]\displaystyle{ p, }[/math] osim faktora koji su sami sebi inverzni modulo [math]\displaystyle{ p. }[/math] Nađimo sve takve faktore. Neka je [math]\displaystyle{ S = \{1, 2, ..., p - 1\} }[/math] te neka je [math]\displaystyle{ x \in S }[/math] za koji vrijedi [math]\displaystyle{ x^2 \equiv 1 \pmod n. }[/math] Tada [math]\displaystyle{ p \mid (x - 1)(x + 1) . }[/math] Kako je [math]\displaystyle{ p }[/math] prost i [math]\displaystyle{ p \leq x \leq p - 1 }[/math] slijedi (prema Euklidovoj lemi) da postoje samo dva takva broja [math]\displaystyle{ p = x - 1 \iff x = p + 1 }[/math] ili [math]\displaystyle{ p = x + 1 \iff x = p - 1. }[/math] No, [math]\displaystyle{ p + 1 \not\in S, }[/math] ali su prema gornjoj lemi rješenja svi brojevi kongruentni s [math]\displaystyle{ p + 1 }[/math] modulo [math]\displaystyle{ p. }[/math] Očito je onda i broj [math]\displaystyle{ 1 \in S, }[/math] uz [math]\displaystyle{ p - 1 \in S, }[/math] rješenje gornje kvadratne kongruencije. (Ovo se moglo zaključiti i preko toga da je jedini element iz [math]\displaystyle{ S }[/math] koji zadovoljava [math]\displaystyle{ p \mid x - 1 }[/math] upravo broj [math]\displaystyle{ 1 }[/math] i slično jedino [math]\displaystyle{ p - 1 }[/math] zadovoljava [math]\displaystyle{ p \mid x + 1. }[/math])

Sada je jasno da brojeve [math]\displaystyle{ 2, 3, ..., p - 2 }[/math] možemo rasporediti u parove (na jedinstveni način) tako da je umnožak brojeva u svakom paru kongruentan [math]\displaystyle{ 1 }[/math] modulo [math]\displaystyle{ p. }[/math] Dakle, jedino faktori broja [math]\displaystyle{ P }[/math] koji ostanu nespareni su [math]\displaystyle{ 1, p - 1 }[/math] pa je [math]\displaystyle{ P \equiv 1 \cdot 1 \cdot (p - 1) \pmod p. }[/math] Prema tome, [math]\displaystyle{ (p - 1)! \equiv p - 1 \equiv - 1 \pmod p, }[/math] što je i trebalo dokazati.

Obrat Wilsonova teorema

Lako je pokazati da vrijedi i obrat Wilsonova teorema. Naime, neka je [math]\displaystyle{ (p - 1)! \equiv - 1 \pmod p }[/math] i pretpostavimo da [math]\displaystyle{ p }[/math] nije prost. Tada [math]\displaystyle{ p }[/math] ima djelitelj [math]\displaystyle{ d, 1 \lt d \lt p }[/math] pa [math]\displaystyle{ d }[/math] dijeli i broj [math]\displaystyle{ (p - 1)! }[/math]. No, tada [math]\displaystyle{ d }[/math] mora dijeliti i [math]\displaystyle{ - 1 }[/math], što je kontradikcija.

Zanimljivosti

Zbog obrata Wilsonova teorema, ovaj teorem može poslužiti i kao ispit prostosti nekog prirodnog broja, tj. moguće je pomoću Wilsonovog teorema dokazati je li neki prirodan broj prost ili nije. Ipak, unatoč tomu što ovo unikatno svojstvo prostih brojeva izgleda primamljivo, u praksi je rijetka pojava da je to svojstvo korisno koristiti kao test prostosti nekog većeg prirodnog broja.