Kwadratische congruentievergelijking

Hoeveel oplossingen heeft de congruentievergelijking x²=103 (mod 331) ?
Eventuele oplossingen hoef ik niet te weten, alleen maar de manier waarop ik het aantal kan weten.
Alvast bedankt.

Henri
Student hbo - woensdag 12 november 2003

Antwoord

Hoi,

Bemerk eerst dat p=331 en a=103 priemgetallen zijn en dat daarom uiteraard ggd(103,331)=1. We veronderstellen dat er minstens één oplossing s bestaat voor x²=a (mod p) (of anders gezegd: dat a een kwadratisch residu is modulo p). Voor elke t die voldoet aan t²=1 (mod p), zal s.t een oplossing zijn van x²=a (mod p). Dit betekent dat x²=a (mod p) evenveel oplossingen heeft als x²=1 (mod p).
Welnu x²=1 (mod p) als p|(x-1)(x+1). Aangezien p2, is ggd(x-1,x+1)=1, zodat p|x-1 of p|x+1. De enige oplossingen voor x=1..p-1 zijn dus x-1=0 en x+1=p of x=1 en x=p-1. De vergelijking x²=1 (mod p) heeft dus 2 oplossingen. (Je kan dit resultaat veralgemenen tot een uitdrukking van de vorm 2^k, 2^k-1 of 2^k+1 waarbij k het aantal verschillende priemfactoren is van de modulo en afhankelijk van de multipliciteit van de priemfactor 2, maar dat zal ons te ver leiden).

Je vergelijking heeft dus 2 oplossingen op voorwaarde dat we minstens één oplossing vinden. Voor elke s met s²=103 (mod p) moet s^p-1=1 (mod p), dus moet 103^(p-1)/2=1 (mod p) (kleinde stelling Fermat). En dit klopt inderdaad... Voor 106 bijvoorbeeld klopt dit niet en dus is 106 geen kwadritisch residu. Je kan bewijzen dat dit een nodige en voldoende voorwaarde is (als je hier ook een bewijs van wil, laat je het maar weten - tip: een cyclische groep heeft generatoren..). Er bestaan dus inderdaad oplossingen voor x²=103 (mod p).

Anders kan ook. We nemen q=(p-1)/2=165, zodat q²=83 (mod p). We proberen een s te vinden van de vorm q+k. De voorwaarde is (q+k)²=103 (mod p), of q²+2qk+k²=103 of k²-k-20=0 of (k+4).(k-5)=0. En nu zien we dat k=-4 en k=5 tot oplossingen leiden.

Op de 'harde' manier (alles lijsten in Excel) kan je in elk geval ook ontdekken dat 161²=170²=103 (mod p).

Hoe je het ook bekijkt, er zijn dus 2 oplossingen.

Groetjes,
Johan

andros
donderdag 13 november 2003

©2001-2024 WisFaq