Opeenvolgende kwadraatresten

Volgens een stelling bestaat er voor iedere p 7 een paar opeenvolgende kwadraatresten, bijvoorbeeld 8 en 9 of 41 en 42. Een kennis van mij wilde dit eenvoudig als volgt bewijzen. Lees voor = daar waar nodig het congruent-teken.

Zij x² = a mod p en c² = 1 mod p (1/p is per definitie 1, dus deze bestaat). Dan bestaat er ook een y² = (a+1) mod p,
want, y² - x² = ( a+1 + l*p) - ( a + r*p) = 1 + (l-r)*p.
Dus als y² - x² = 1 mod p = c².

Ik vond dit bewijs kort door de bocht. Wat is het echte bewijs ?

Alvast bedankt.

Hans

Hans v
Student hbo - vrijdag 5 maart 2004

Antwoord

Hoi,

Een beetje uit de bocht zelfs... Hoe raak je aan y als je weet dat y²-x²=1 (mod p)? Ik veronderstel ook dat je het niet over 0 en 1 hebt, want dat zijn ook opeenvolgende kwadraatresten...

Alle restklassen zonder 0 vormen een multiplicatieve groep met generator g. Elke kwadraatrest (verschillend van 0) kan je dus schrijven als een even macht van g. Je gaat na dat er (p-1)/2 kwadraatresten zijn verschillend van 0. De som is dus 1+g²+g⁴+...+g^p-3=(1-g^p-1)/(1-g²)=0 (mod p). De som van alle kwadraatresten is dus deelbaar door p.

Welnu, stel dat er (p-1)/2 kwadraatresten zijn zodat er geen enkel paar opeenvolgende klassen is. Omdat 1 een kwadraatrest is, is de enige mogelijkheid dan dat {1,3,5,...,p-2} de hele set kwadraatresten vormt. De som hiervan is (p-1)²/4 en dit is niet deelbaar door p. Foute veronderstelling dus...

Groetjes,
Johan

andros
dinsdag 9 maart 2004

©2001-2024 WisFaq