Getaltheorie

Beste Wisfaq,

Ik zit met het volgende probleem:

Ik moet aantonen dat het aantal oplossingen voor x²-y²=a (mod p) (waarbij p een oneven priemgetal is) p-1 is wanneer a ongelijk aan 0 (mod p) is en 2p-1 wanneer a = 0 (mod p)

Als hint is gegeven: wanneer a ongelijk is aan 0 (mod p), toon dan aan dat er voor elke c ongelijk 0 (mod p) een unieke oplossing (x,y) is waarvoor (x-y) = c (mod p).

Ik zie echter niet in hoe ik de hint moet relateren aan het gegeven probleem, of ik de hint moet aantonen.

Bij voorbaat dank voor de hulp,

Herman

Herman
Student universiteit - zondag 19 april 2009

Antwoord

Dag Herman,

De vorm x²-y² en de hint zouden je op de gedachte kunnen brengen x²-y² te schrijven in de vorm c·d met c=x-y en d=x+y.
1)
a=0
c·d=0 mod p betekent c=0 (mod p) of d=0 (mod p) (of beide)
Hieruit volgt gemakkeljk het gestelde voor a=0.

2)
a¹0.
Je moet nu de hint zo lezen: voor iedere a¹0 en c¹0 (mod p) bestaat precies een oplossing (x,y) (mod p).
Je kunt deze oplossing (x,y) als volgt bepalen:
Ga uit van de vergelijking c·d=a.
Bepaal nu het getal e zo, dat c·e=1 (mod p).
Dit getal e wordt wel de modulaire inverse van c (mod p) genoemd. Ook wel geschreven als c^-1 (mod p)
Dat kan met het uitgebreide euclidisch algoritme. Ik neem aan dat je niet hoeft te bewijzen dat c^-1 uniek (mod p) is als ggd(c,p)=1.

Dan:
Vermenigvuldig de vergelijking c·d=a links en rechts met e=c^-1.
Je krijgt dan:
c^-1·c·d=c^-1·a
Dus x+y=d=c^-1·a
Bij elke keuze van a en c=x-y bestat dus een unieke waarde van d=x+y.
Dan 2·x=c+d en 2·y=d-c.
Vermenigvuldig in beide gevallen met 2^-1 mod p en je hebt x en y.
(En hier komt om de hoek kijken waarom p een oneven priem moet zijn)

Uitgewerkt voorbeeld:
Neem p=7, a=5 en c=4.
Dan 4·d=5 mod 7.
4^-1 mod 7=2. (4·2=8=1 mod 7)
Dus 2·4·d=2·5 mod 7, dus d=10 (mod7)=3
c=x-y=4
d=x+y=3
2x=c+d=7=0 mod 7
2y=d-c=3-4=-1=6 mod 7
2^-1 mod 7=4.
x=4·0=0, y=4·6=24=3 mod 7.
0²-3²=0-9=-9=-2=5 mod 7.

maandag 20 april 2009

©2001-2024 WisFaq