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 x2 = a mod p en c2 = 1 mod p (1/p is per definitie 1, dus deze bestaat). Dan bestaat er ook een y2 = (a+1) mod p, want, y2 - x2 = ( a+1 + l*p) - ( a + r*p) = 1 + (l-r)*p. Dus als y2 - x2 = 1 mod p = c2.
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 y2-x2=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+g2+g4+...+gp-3=(1-gp-1)/(1-g2)=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)2/4 en dit is niet deelbaar door p. Foute veronderstelling dus...
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.