Kvadratisk rest

Inom talteorin kallas ett heltal q för kvadratisk rest modulo p, om det finns ett heltal x sådant att:

${x^{2}}\equiv {q}{\mbox{ (mod }}p{\mbox{)}}.$

Antingen finns ingen eller två icke kongruenta lösningar. Om kongruensen ovan inte har någon lösning är q en icke-kvadratisk rest. Om exempelvis p = 13, är de kvadratiska resterna 1, 3, 4, 9, 10 och 12.

Med hjälp av Eulers kriterium kan man avgöra om kongruenser av detta slag har någon lösning. Om till exempel p är ett udda primtal, finner man med detta kriterium att

${x^{2}}\equiv {-1}{\mbox{ (mod }}p{\mbox{)}}$

är lösbar, endast om p kan skrivas på formen 4n + 1. Om till exempel p = 17, så är x = 4 eller x = 13.

Vidare är exempelvis ett positivt heltal en kvadratisk rest (mod 10) om och endast om dess sista siffra är 0, 1, 4, 5, 6 eller 9.

Allmänt kan man säga, att en kvadratisk rest modulo p är ett tal, som har en kvadratrot i modulär aritmetik när modulen är p. Kvadratiska reciprocitetssatsen ger ett samband för när q är kvadratisk rest (mod p) och p är kvadratisk rest (mod q), för primtal p och q.

Med hjälp av reciprocitetssatsen kan man på ett förhållandevis enkelt sätt beräkna om kongruenser av ovanstående slag kan lösas.

Källor

• I.N. Herstein, Topics in Algebra, Blaisdell Publishing Company, 1964.