Kvadratni ostatak

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

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

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 $a$ kvadratni ostatak modulo $n$ dovoljno je naći njegov ostatak pri dijeljenju s $n$ u reduciranom sustavu ostataka modulo $n$ i vidjeti je li kvadrat nekog od brojeva u tom skupu kongruentan s $a.$

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

Kvadratni ostatci po prostom modulu

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

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

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

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

Broj rješenja čiste kvadratne kongruencije

Neka je $p$ prost i $a$ neki cijeli broj.

Koristeći sada Legendreov simbol, broj rješenja kongruencije $x^2\equiv a(\mathrm{mod}p)$ jednak je $1+\left(\frac{a}{p}\right)$.

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

Eulerov kriterij

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

Teorem tvrdi $a^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right)(\mathrm{mod}p).$

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

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

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

Dalje, prema pretpostavci, $a$ nije kvadratni ostatak modulo $p$ pa vrijedi $x\ne y.$ Promotrimo li sve takve parove oblika $(x,y)$ vidimo da smo skup $S$ podijelili na $\frac{p-1}{2}$ parova ostataka koji u umnošku daju $a$ modulo $p.$ Koristeći još Wilsonov teorem zaključujemo da vrijedi $a^{\frac{p-1}{2}}\equiv 1\cdot 2\cdot ...\cdot (p-1)\equiv -1(\mathrm{mod}p),$ č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 $p,q$ vrijedi $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{\frac{p-1}{2}\frac{q-1}{2}}.$

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