Hoeveel oplossingen heeft de congruentievergelijking x2=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 x2=a (mod p) (of anders gezegd: dat a een kwadratisch residu is modulo p). Voor elke t die voldoet aan t2=1 (mod p), zal s.t een oplossing zijn van x2=a (mod p). Dit betekent dat x2=a (mod p) evenveel oplossingen heeft als x2=1 (mod p). Welnu x2=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 x2=1 (mod p) heeft dus 2 oplossingen. (Je kan dit resultaat veralgemenen tot een uitdrukking van de vorm 2k, 2k-1 of 2k+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 s2=103 (mod p) moet sp-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 x2=103 (mod p).
Anders kan ook. We nemen q=(p-1)/2=165, zodat q2=83 (mod p). We proberen een s te vinden van de vorm q+k. De voorwaarde is (q+k)2=103 (mod p), of q2+2qk+k2=103 of k2-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 1612=1702=103 (mod p).
Hoe je het ook bekijkt, er zijn dus 2 oplossingen.
2, 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 x2=1 (mod p) heeft dus 2 oplossingen. (Je kan dit resultaat veralgemenen tot een uitdrukking van de vorm 2k, 2k-1 of 2k+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).