Kvadratni ostatak

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

Kvadratni ostatak po modulu je neki cijeli broj ako vrijedi i ako kongruencija ima rješenja, tj. ako postoji cijeli broj čiji je kvadrat kongruentan s

U suprotnom kažemo da je kvadratni neostatak modulo Uočimo da ako imamo neki takav da je tada nije niti kvadratni ostatak niti kvadratni neostatak, a takav je primjerice broj nula. Uočimo zato da broj također mora biti relativno prost s [1]

Veliki matematičari poput Fermata, Eulera, Lagrangea, Legendrea (i mnogih drugih) su u 17. i 18. stoljeću iznijeli neke teoreme o kvadratnim ostatcima. Ipak, prvi koji ih je sistematično proučavao bio je Carl Friedrich Gauss u svojem čuvenom djelu Disquisitiones Arithmeticae izdanom 1801.

Pronalazak rješenja u reduciranom sustavu ostataka[uredi | uredi kôd]

Jasno je da za provjeriti je li neki broj kvadratni ostatak modulo dovoljno je naći njegov ostatak pri dijeljenju s u reduciranom sustavu ostataka modulo i vidjeti je li kvadrat nekog od brojeva u tom skupu kongruentan s

Isto tako, kongruencija je trivijalno zadovoljena pa će biti dovoljno promatrati skup relativno prostih brojeva s u intervalu jer je

Kvadratni ostatci po prostom modulu[uredi | uredi kôd]

Kvadratni ostatci modulo gdje je prost broj poštuju određena jednostavna svojstva.

Ako želimo naći sve kvadratne ostatke modulo dovoljno je izlistati kvadratne ostatke po modulu iz skupa

Dokazat ćemo da u tom skupu ima točno kvadratnih ostataka. Pitamo se koliko kvadratnih ostataka postižu brojevi Uočimo da vrijedi pa se svaki kvadratni ostatak pastiže barem dva puta (jer očito ). Treba dokazati da se postižu točno dva puta.

U tu svrhu, pretpostavimo da je Tada pa prema Euklidovoj lemi slijedi ili No kako su slijedi ili pa se kvadratni ostatak postiže točno dva puta.

Broj rješenja čiste kvadratne kongruencije[uredi | uredi kôd]

Neka je prost i neki cijeli broj.

Koristeći sada Legendreov simbol, broj rješenja kongruencije jednak je .

Naime, ako je kvadratni ostatak, tada kongruencija ima 2 rješenja (ako je jedno rješenje , drugo rješenje je ). Ako je pak kvadratni neostatak, onda kongruencija nema rješenja, a ako kongruencija ima točno jedno rješenje modulo , tj. sve brojeve kongruente modulo .

Eulerov kriterij[uredi | uredi kôd]

Ovaj se teorem prvi puta pojavljuje u Eulerovim radovima iz 1748.

Teorem tvrdi

Naime, ako dijeli tvrdnja očigledno vrijedi. Zato prijeđimo na slučaj kada ne dijeli

Ako je kvadratni ostatak modulo , po definiciji postoji cijeli broj takav da je pa budući da nije djeljiv s , tada niti nije djeljiv s Prema Malom Fermatovom teoremu lagano slijedi pa tvrdnja u ovom slučaju vrijedi.

Slično se pokazuje ako nije kvadratni ostatak modulo Nije teško dokazati da za svaki postoji jedinstveni takav da je .[2] Naime, ova tvrdnja slijedi iz Bézoutovog identiteta.

Dalje, prema pretpostavci, nije kvadratni ostatak modulo pa vrijedi Promotrimo li sve takve parove oblika vidimo da smo skup podijelili na parova ostataka koji u umnošku daju modulo Koristeći još Wilsonov teorem zaključujemo da vrijedi čime je Eulerov kriterij dokazan.

Gaussov kvadratni zakon reciprociteta[uredi | uredi kôd]

Kvadratni zakon reciprociteta je jedan od najdubljih rezultata elementarne teorije brojeva i jedan je od teorema s najviše poznatih dokaza, a tvrdi da za dva različita neparna prosta broja vrijedi

Kao korak u nekim dokazima ovog teorema se često koristi poznata Gaussova lema.

Izvori[uredi | uredi kôd]

  1. Andrej Dujella, Teorija brojeva, Školska knjiga, Zagreb, 2019.
  2. Za dokaz, preporuča se pogledati dokaz leme u članku o Wilsonovom teoremu