Algebra

Analyse

Bewijzen

De grafische rekenmachine

Discrete wiskunde

Fundamenten

Meetkunde

Oppervlakte en inhoud

Rekenen

Schoolwiskunde

Statistiek en kansrekenen

Telproblemen

Toegepaste wiskunde

Van alles en nog wat


\require{AMSmath}

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 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...

Groetjes,
Johan

andros
dinsdag 9 maart 2004

©2001-2024 WisFaq