WisFaq!

Kwadraatrest modulo p

Hallo,

Ik heb laatst de volgende stelling ergens gelezen:

Het getal 19 is een kwadraatrest (mod 31), immers 9²=81=19+2*31. Het is ook een kwardaatrest (mod 59) want 14²=196=19+3*59. Maar 19 is geen kwadraatrest 23.

Het probleem: bepaal alle priemgetallen p waarvoor geldt dat 19 een kwadraatrest mod p is? Hoe kun je dit ook bewijzen.

koen
7-2-2004

Antwoord

Hallo,

Dit soort bewijzen gebruikt de 'quadratic reciprocity law'.
Notatie: (q/p)=1 als q een kwadraatrest is modulo p, anders geldt (q/p)=-1. (q en p zijn verschillende oneven priemen)

De vraag is dus: voor welke p is (19/p) gelijk aan 1?

De stelling zegt nu:
(q/p)=(-1)^{q-1/₂p-1/₂}(p/q)

Anders gezegd: (p/q)=(q/p) als p of q (1 mod 4) is.
q = 19 = -1 (mod 4).

Dus, als een p gegeven wordt: kijk of (p/19) 1 of -1 is; en kijk of p = 1 of -1 mod 4. Eens je dit weet, weet je ook of (19/p) 1 dan wel -1 is. Om een lijst op te stellen zal je de priemen moeten nakijken op hun waarde modulo 4, en nakijken op hun kwadraatzijn modulo 19, dus je zal een lijst moeten maken van priemen modulo 4*19=76, dus toch knap wat werk...

Vb p=5: (5/19)=1 want 5º81
5º1 mod 4
Dus (19/5) = 1*1 = 1 en inderdaad: 19º4 mod 5, dus 19 is een kwadraatrest mod 5.

Vb p=31: (31/19)=-1 (want de kwadraten modulo 19 zijn 1,4,9,16,6,17,11,7,5,5,7,11,17,6,16,9,4,1,0 en dus niet 12)
31º-1 mod 4
Dus (19/31)=(-1)(-1)=1

Groeten,

Christophe
8-2-2004