Kvadratisk rest
Inom talteorin kallas ett heltal q för kvadratisk rest modulo p, om det finns ett heltal x sådant att:
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
ä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.