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{\pmod {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}{\pmod {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}{\pmod {p}}$ pa se svaki kvadratni ostatak pastiže barem dva puta (jer očito $x\neq p-x$). Treba dokazati da se postižu točno dva puta.

U tu svrhu, pretpostavimo da je $x^{2}\equiv y^{2}{\pmod {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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x^{2}\equiv a{\pmod {p}}} jednak je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p|a} kongruencija ima točno jedno rješenje modulo $p$, tj. sve brojeve kongruente Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 0} modulo $p$.

Eulerov kriterij

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

Teorem tvrdi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a^{\frac {p-1}{2}}\equiv \left({\frac {a}{p}}\right){\pmod {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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x^{2}\equiv a{\pmod {p}}} pa budući da $x$ nije djeljiv s $p$, tada niti $x^{2}$ nije djeljiv s Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p.} Prema Malom Fermatovom teoremu lagano slijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a^{\frac {p-1}{2}}\equiv (x^{2})^{\frac {p-1}{2}}\equiv x^{p-1}\equiv 1{\pmod {p}}} pa tvrdnja u ovom slučaju vrijedi.

Slično se pokazuje ako $a$ nije kvadratni ostatak modulo Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p.} Nije teško dokazati da za svaki Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x\in S=\{1,2,...,p-1\}} postoji jedinstveni Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle y\in S} takav da je $xy\equiv a{\pmod {p}}$. Naime, ova tvrdnja slijedi iz Bézoutovog identiteta.

Dalje, prema pretpostavci, $a$ nije kvadratni ostatak modulo $p$ pa vrijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x\neq y.} Promotrimo li sve takve parove oblika Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (x,y)} vidimo da smo skup $S$ podijelili na ${\frac {p-1}{2}}$ parova ostataka koji u umnošku daju $a$ modulo Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p.} Koristeći još Wilsonov teorem zaključujemo da vrijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a^{\frac {p-1}{2}}\equiv 1\cdot 2\cdot ...\cdot (p-1)\equiv -1{\pmod {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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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.