Wilsonov teorem

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

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 $a,n$ relativno prosti, tada za svaki cijeli broj $b$ postoji jedinstveno rješenje kongruencije $ax\equiv b{\pmod {n}}.$

Napomenimo da je rješenje kongruencije svaki $x$ oblika $qn+b,\forall q\in \mathbb {Z} .$

Kako je $M(a,n)=1,$ prema Bezoutovom identitetu slijedi da postoje $k,l\in \mathbb {Z}$ takvi da je $ak+nl=1.$ Odavde dobivamo $akb+nlb=b.$ Sada zbog toga što $n\mid nlb$ vrijedi $akb\equiv b{\pmod {n}}.$ Stavljamo $x:=kb,$ što je rješenje početne kongruencije. Dakako, prema gornjoj napomeni, rješenja su i svi brojevi kongruentni $x$ modulo $n.$ No, trebamo pokazati da su to sva rješenja. U tu svrhu, pretpostavimo da postoji neko drugo rješenje, $y\not \equiv x{\pmod {n}}.$ Imali bismo, $ax\equiv b{\pmod {n}},ay\equiv b{\pmod {n}},$ no to povlači $ax\equiv ay{\pmod {n}}.$ Odatle (jer je $M(a,n)=1$) dobivamo $x\equiv y{\pmod {n}},$ što je kontradikcija. Time je dokazana jedinstvenost rješenja.

Dakle, sva rješenja su u parovima kongruenta modulo Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n. } Valja napomenuti da rješenje za $b=1$ zovemo multiplikativnim inverzom broja Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a } modulo Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p. }

Sada je lako dokazati Wilsonov teorem. Naime, svaki je od brojeva Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{1, 2, ..., p - 1\} } relativno prost s Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p } pa nam prethodna lema može pomoći. Prema gornjoj lemi, svaki od faktora Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (p - 1)! = 1 \cdot 2 \cdot ... \cdot (p - 1) = P } ima svoj multiplikativni inverz modulo Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p, } osim faktora koji su sami sebi inverzni modulo Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p. } Nađimo sve takve faktore. Neka je $S=\{1,2,...,p-1\}$ te neka je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in S } za koji vrijedi Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^2 \equiv 1 \pmod n. } Tada $p\mid (x-1)(x+1).$ Kako je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p } prost i $p\leq x\leq p-1$ slijedi (prema Euklidovoj lemi) da postoje samo dva takva broja Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p = x - 1 \iff x = p + 1 } ili Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p = x + 1 \iff x = p - 1. } No, Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p + 1 \not\in S, } ali su prema gornjoj lemi rješenja svi brojevi kongruentni s Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p + 1 } modulo $p.$ Očito je onda i broj Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 \in S, } uz Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p - 1 \in S, } rješenje gornje kvadratne kongruencije. (Ovo se moglo zaključiti i preko toga da je jedini element iz $S$ koji zadovoljava Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p \mid x - 1 } upravo broj Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 } i slično jedino $p-1$ zadovoljava Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p \mid x + 1. } )

Sada je jasno da brojeve $2,3,...,p-2$ možemo rasporediti u parove (na jedinstveni način) tako da je umnožak brojeva u svakom paru kongruentan Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 } modulo $p.$ Dakle, jedino faktori broja Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P } koji ostanu nespareni su $1,p-1$ pa je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P \equiv 1 \cdot 1 \cdot (p - 1) \pmod p. } Prema tome, $(p-1)!\equiv p-1\equiv -1{\pmod {p}},$ što je i trebalo dokazati.

Obrat Wilsonova teorema

Lako je pokazati da vrijedi i obrat Wilsonova teorema. Naime, neka je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (p - 1)! \equiv - 1 \pmod p} i pretpostavimo da $p$ nije prost. Tada Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} ima djelitelj $d,1<d<p$ pa Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} dijeli i broj $(p-1)!$. No, tada Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} mora dijeliti i Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle - 1} , š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.