Kvadratisk rest

Från Wikipedia
Hoppa till: navigering, sök

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, så är q en icke-kvadratisk rest. Om exempelvis p = 13, så ä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, så 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 Legendresymbolen kan man på ett förhållandevis enkelt sätt beräkna om kongruenser av ovanstående slag kan lösas.

Källor[redigera | redigera wikitext]

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