Kvadratni ostatak

Kvadratni ostatak po modulu [math]\displaystyle{ n }[/math] je neki cijeli broj [math]\displaystyle{ a }[/math] ako vrijedi [math]\displaystyle{ M(a, n) = 1 }[/math] i ako kongruencija [math]\displaystyle{ x^2 \equiv a \pmod n }[/math] ima rješenja, tj. ako postoji cijeli broj [math]\displaystyle{ x }[/math] čiji je kvadrat kongruentan s [math]\displaystyle{ a. }[/math]

U suprotnom kažemo da je [math]\displaystyle{ a }[/math] kvadratni neostatak modulo [math]\displaystyle{ n. }[/math] Uočimo da ako imamo neki [math]\displaystyle{ m \in \mathbb{Z} }[/math] takav da je [math]\displaystyle{ M(m, n) \gt 1 }[/math] tada [math]\displaystyle{ m }[/math] nije niti kvadratni ostatak niti kvadratni neostatak, a takav je primjerice broj nula. Uočimo zato da broj [math]\displaystyle{ x }[/math] također mora biti relativno prost s [math]\displaystyle{ n. }[/math]

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

Jasno je da za provjeriti je li neki broj [math]\displaystyle{ a }[/math] kvadratni ostatak modulo [math]\displaystyle{ n }[/math] dovoljno je naći njegov ostatak pri dijeljenju s [math]\displaystyle{ n }[/math] u reduciranom sustavu ostataka modulo [math]\displaystyle{ n }[/math] i vidjeti je li kvadrat nekog od brojeva u tom skupu kongruentan s [math]\displaystyle{ a. }[/math]

Isto tako, kongruencija [math]\displaystyle{ x^2 \equiv (x + kn)^2 \pmod n }[/math] je trivijalno zadovoljena pa će biti dovoljno promatrati skup relativno prostih brojeva s [math]\displaystyle{ n }[/math] u intervalu [math]\displaystyle{ [1, n - 1] }[/math] jer je [math]\displaystyle{ (1, n) = (n - 1, n) = 1. }[/math]

Kvadratni ostatci po prostom modulu

Kvadratni ostatci modulo [math]\displaystyle{ p }[/math] gdje je [math]\displaystyle{ p \gt 2 }[/math] prost broj poštuju određena jednostavna svojstva.

Ako želimo naći sve kvadratne ostatke modulo [math]\displaystyle{ p }[/math] dovoljno je izlistati kvadratne ostatke po modulu [math]\displaystyle{ p }[/math] iz skupa [math]\displaystyle{ \{1, 2, ..., p - 1\}. }[/math]

Dokazat ćemo da u tom skupu ima točno [math]\displaystyle{ \frac{p - 1}{2} }[/math] kvadratnih ostataka. Pitamo se koliko kvadratnih ostataka postižu brojevi [math]\displaystyle{ 1^2, 2^2, ..., (p - 1)^2. }[/math] Uočimo da vrijedi [math]\displaystyle{ x^2 \equiv (p - x)^2 \pmod p }[/math] pa se svaki kvadratni ostatak pastiže barem dva puta (jer očito [math]\displaystyle{ x \neq p - x }[/math]). Treba dokazati da se postižu točno dva puta.

U tu svrhu, pretpostavimo da je [math]\displaystyle{ x^2 \equiv y^2 \pmod p. }[/math] Tada [math]\displaystyle{ p|(x - y)(x + y) }[/math] pa prema Euklidovoj lemi slijedi [math]\displaystyle{ p|x - y }[/math] ili [math]\displaystyle{ p|x + y. }[/math] No kako su [math]\displaystyle{ x, y \in \{1, 2, ..., p - 1\} }[/math] slijedi [math]\displaystyle{ x = y }[/math] ili [math]\displaystyle{ x + y = p }[/math] pa se kvadratni ostatak postiže točno dva puta.

Broj rješenja čiste kvadratne kongruencije

Neka je [math]\displaystyle{ p }[/math] prost i [math]\displaystyle{ a }[/math] neki cijeli broj.

Koristeći sada Legendreov simbol, broj rješenja kongruencije [math]\displaystyle{ x^2 \equiv a \pmod p }[/math] jednak je [math]\displaystyle{ 1 + \left(\frac{a}{p}\right) }[/math].

Naime, ako je [math]\displaystyle{ a }[/math] kvadratni ostatak, tada kongruencija ima 2 rješenja (ako je jedno rješenje [math]\displaystyle{ x_0 }[/math], drugo rješenje je [math]\displaystyle{ -x_0 }[/math]). Ako je pak [math]\displaystyle{ a }[/math] kvadratni neostatak, onda kongruencija nema rješenja, a ako [math]\displaystyle{ p|a }[/math] kongruencija ima točno jedno rješenje modulo [math]\displaystyle{ p }[/math], tj. sve brojeve kongruente [math]\displaystyle{ 0 }[/math] modulo [math]\displaystyle{ p }[/math].

Eulerov kriterij

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

Teorem tvrdi [math]\displaystyle{ a^{\frac{p - 1}{2}} \equiv \left(\frac{a}{p}\right) \pmod p. }[/math]

Naime, ako [math]\displaystyle{ p }[/math] dijeli [math]\displaystyle{ a }[/math] tvrdnja očigledno vrijedi. Zato prijeđimo na slučaj kada [math]\displaystyle{ p }[/math] ne dijeli [math]\displaystyle{ a. }[/math]

Ako je [math]\displaystyle{ a }[/math] kvadratni ostatak modulo [math]\displaystyle{ p }[/math], po definiciji postoji cijeli broj [math]\displaystyle{ x }[/math] takav da je [math]\displaystyle{ x^2 \equiv a \pmod p }[/math] pa budući da [math]\displaystyle{ x }[/math] nije djeljiv s [math]\displaystyle{ p }[/math], tada niti [math]\displaystyle{ x^2 }[/math] nije djeljiv s [math]\displaystyle{ p. }[/math] Prema Malom Fermatovom teoremu lagano slijedi [math]\displaystyle{ a^{\frac{p - 1}{2}} \equiv (x^2)^{\frac{p - 1}{2}} \equiv x^{p - 1} \equiv 1 \pmod p }[/math] pa tvrdnja u ovom slučaju vrijedi.

Slično se pokazuje ako [math]\displaystyle{ a }[/math] nije kvadratni ostatak modulo [math]\displaystyle{ p. }[/math] Nije teško dokazati da za svaki [math]\displaystyle{ x \in S = \{1, 2, ..., p - 1\} }[/math] postoji jedinstveni [math]\displaystyle{ y \in S }[/math] takav da je [math]\displaystyle{ xy \equiv a \pmod p }[/math]. Naime, ova tvrdnja slijedi iz Bézoutovog identiteta.

Dalje, prema pretpostavci, [math]\displaystyle{ a }[/math] nije kvadratni ostatak modulo [math]\displaystyle{ p }[/math] pa vrijedi [math]\displaystyle{ x \neq y. }[/math] Promotrimo li sve takve parove oblika [math]\displaystyle{ (x, y) }[/math] vidimo da smo skup [math]\displaystyle{ S }[/math] podijelili na [math]\displaystyle{ \frac{p - 1}{2} }[/math] parova ostataka koji u umnošku daju [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ p. }[/math] Koristeći još Wilsonov teorem zaključujemo da vrijedi [math]\displaystyle{ a^{\frac{p - 1}{2}} \equiv 1 \cdot 2 \cdot ... \cdot (p - 1) \equiv - 1 \pmod p, }[/math] čime je Eulerov kriterij dokazan.

Gaussov kvadratni zakon reciprociteta

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 [math]\displaystyle{ p, q }[/math] vrijedi [math]\displaystyle{ \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}. }[/math]

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