WikiSysop: Bot: Automatski unos stranica

2021-12-09T18:27:54Z

Bot: Automatski unos stranica

Nova stranica

'''Wilsonov teorem''' je jedan od najvažnijih teorema elementarne [[Teorija brojeva|teorije brojeva]] koji tvrdi da ako je <math> p </math> [[Prosti broj|prost broj]], vrijedi <math> (p - 1)! \equiv - 1 \pmod p. </math>

[[Teorem]] je prvi iskazao [[Arabija|arapski]] [[Matematika|matematičar]] Ibn al-Haytham još u [[10. stoljeće|10. stoljeću]], no ponovno je iskazan u [[18. stoljeće|18. stoljeću]] od strane [[Engleska|engleskih]] matematičara Johna Wilsona i Edwarda Waringa. Ipak, ovaj je teorem dokazao veliki [[Italija|talijanski]] matematičar [[Joseph-Louis Lagrange]] [[1771.]] godine.<ref>https://artofproblemsolving.com/wiki/index.php/Wilson%27s_Theorem</ref>

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

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

Kako je <math> M(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 <math> n \mid nlb </math> vrijedi <math> akb \equiv 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 \equiv ay \pmod n. </math> Odatle (jer je <math> M(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. </math>

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)
= P </math> ima svoj multiplikativni inverz modulo <math> p, </math> osim faktora 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. (Ovo se moglo zaključiti i preko toga da je jedini element iz <math> S </math> koji zadovoljava <math> p \mid x - 1 </math> upravo broj <math> 1 </math> i slično jedino <math> p - 1 </math> zadovoljava <math> p \mid x + 1. </math>)

Sada je jasno da brojeve <math> 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> 1 </math> modulo <math> p. </math> Dakle, jedino faktori broja <math> P </math> koji ostanu nespareni su <math> 1, p - 1 </math> pa je <math> P \equiv 1 \cdot 1 \cdot (p - 1) \pmod p. </math> Prema tome, <math> (p - 1)! \equiv p - 1 \equiv - 1 \pmod p, </math> što je i trebalo dokazati.<ref>I. Matić, Uvod u teroju brojeva, Odjel za matematiku Sveučilišta J. J. Strossmayera u Osijeku, 2013, skripta.</ref>

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

== Zanimljivosti ==
Zbog obrata Wilsonova teorema, ovaj teorem može poslužiti i kao ispit ''prostosti'' nekog [[Prirodan broj|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.

==Izvori==
{{izvori}}

[[Kategorija:Matematika]]

Wilsonov teorem - Povijest promjena

WikiSysop: Bot: Automatski unos stranica