Wilsonov teorem

Izvor: Wikipedija
Prijeđi na navigaciju Prijeđi na pretraživanje

Wilsonov teorem je jedan od najvažnijih teorema elementarne teorije brojeva koji tvrdi da ako je prost broj, vrijedi

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.[1]

Dokaz[uredi | uredi kôd]

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

Lema. Ako su relativno prosti, tada za svaki cijeli broj postoji jedinstveno rješenje kongruencije

Napomenimo da je rješenje kongruencije svaki oblika

Kako je prema Bezoutovom identitetu slijedi da postoje takvi da je Odavde dobivamo Sada zbog toga što vrijedi Stavljamo što je rješenje početne kongruencije. Dakako, prema gornjoj napomeni, rješenja su i svi brojevi kongruentni modulo No, trebamo pokazati da su to sva rješenja. U tu svrhu, pretpostavimo da postoji neko drugo rješenje, Imali bismo, no to povlači Odatle (jer je ) dobivamo što je kontradikcija. Time je dokazana jedinstvenost rješenja.

Dakle, sva rješenja su u parovima kongruenta modulo Valja napomenuti da rješenje za zovemo multiplikativnim inverzom broja modulo

Sada je lako dokazati Wilsonov teorem. Naime, svaki je od brojeva relativno prost s pa nam prethodna lema može pomoći. Prema gornjoj lemi, svaki od faktora ima svoj multiplikativni inverz modulo osim faktora koji su sami sebi inverzni modulo Nađimo sve takve faktore. Neka je te neka je za koji vrijedi Tada Kako je prost i slijedi (prema Euklidovoj lemi) da postoje samo dva takva broja ili No, ali su prema gornjoj lemi rješenja svi brojevi kongruentni s modulo Očito je onda i broj uz rješenje gornje kvadratne kongruencije. (Ovo se moglo zaključiti i preko toga da je jedini element iz koji zadovoljava upravo broj i slično jedino zadovoljava )

Sada je jasno da brojeve možemo rasporediti u parove (na jedinstveni način) tako da je umnožak brojeva u svakom paru kongruentan modulo Dakle, jedino faktori broja koji ostanu nespareni su pa je Prema tome, što je i trebalo dokazati.[2]

Obrat Wilsonova teorema[uredi | uredi kôd]

Lako je pokazati da vrijedi i obrat Wilsonova teorema. Naime, neka je i pretpostavimo da nije prost. Tada ima djelitelj pa dijeli i broj . No, tada mora dijeliti i , što je kontradikcija.

Zanimljivosti[uredi | uredi kôd]

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.

Izvori[uredi | uredi kôd]

  1. https://artofproblemsolving.com/wiki/index.php/Wilson%27s_Theorem
  2. I. Matić, Uvod u teroju brojeva, Odjel za matematiku Sveučilišta J. J. Strossmayera u Osijeku, 2013, skripta.