© h.hofstede (h.hofstede@hogeland.nl)

Kwadraatresten.
       
Eerst maar de definitie:

a is een kwadraatrest modulo b  als er een geheel getal x  bestaat  zodat  x2 ☰ a (mod b)

       
Een paar voorbeeldjes om er wat vertrouwd mee te raken:

Van sommige getallen kun je door te proberen laten zien dat ze een kwadraatrest zijn. Zo is bijvoorbeeld  21 is een kwadraatrest modulo 5, want  42 = 16 ☰ 21 (mod 5).

Maar 2 is géén kwadraatrest modulo 3. 
Hoe toon je aan dat een getal géén kwadraatrest is?
Als a ☰ b (mod 3)  dan is  a2 ☰ b2 (mod 3)
Maar  a (mod 3) kan alleen gelijk zijn aan 0, 1 of 2.
Dan is a2 (mod 3) ☰ 0, 1, 1  dus dat is nooit 2.

Dus door vanaf het getal 2 steeds stapjes van 3 omhoog te gaan kun je nooit op een kwadraat belanden. In de rij  2, 5, 8, 11, 14, 17, 20, 23, 26, .... komt geen kwadraat voor!

Wat zijn de mogelijke kwadraatresten modulo 4?
a(mod 4) is gelijk aan 0, 1, 2 of 3
a2 (mod 4) is dan  0, 1, 0, 1.  Dus de enige kwadraatresten modulo 4 zijn 0 en 1.

Stelling:  als p een oneven priemgetal is zijn er precies  (p + 1)/2  kwadraten mod p
Bewijs:
  a  mod p  kan gelijk zijn aan  (0, 1, ..., p - 1)
Dus alle kwadraatresten  kunnen gelijk zijn aan   (02, 12, ..., (p - 1)2 )
Welke uit deze lijst staan er (mod p) dubbel in?
Stel dat b = a + k   (met b en a uit deze lijst getallen)
Dan is  b2 = (a + k)2 = a2 + 2ak + k2  =  a2 + k(2a + k)
Dat is hetzelfde als a2 (mod p) als  2a + k deelbaar is door p
2a + k = a + a + k = a + b
Conclusie:  als  a + b  deelbaar is door p dan zijn hun kwadraatresten mod p gelijk.
Maar omdat a en b beiden kleiner dan p zijn (ze stonden immers beiden in de lijst) kan dat alleen maar als a + b = p.
De koppels dubbelen zijn dus  (1, p - 1)(2, p - 2) enz.
Dat zijn er  (p - 1)/2  dus er blijven  p - (p - 1)/2 = (p + 1)/2  over. 
q.e.d.

voorbeeld.  bereken alle kwadraatresten mod 11.
De lijst is  0, 1, 2, 3, 4, 5, 6, 7, 8, 9 10
De kwadraten daarvan zijn  0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100
Modulo 11 geeft dat  0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1   (inderdaad symmetrisch!!)
Zonder de dubbelen  0, 1, 4, 9, 5, 3  en dat zijn er  6.

       
Toepassing op Diophantische vergelijkingen.
       
Probleempje:
"Vind alle getallen m en n  zodat n2 + 1 = 4m(m + 1)"
       
Oplossinkje:
4m(m + 1) is deelbaar door 4, dus  n2 + 1 is ook deelbaar door 4.
Laten we de hele vergelijking modulo 4 bekijken.
n2 + 1 ☰ 0 (mod 4) 
Dus n2 ☰ 3  (mod 4)
De kwadraatresten (mod 4)  zijn 0 en 1 dus dat kan niet.
Er zijn geen oplossingen.
       
Oké, ik geef toe: je moet maar op het idee komen om de hele vergelijking modulo 4 te gaan bekijken. Misschien dat je door die 4 aan de rechterkant op dat idee kunt komen.
Je ziet dat je deze methode meestal zult gebruiken om aan te tonen dat er géén oplossingen zijn.
       
Probeer deze nu zelf:
"Vind alle gehele getallen  en n  waarvoor  2m2 + 1 = 5n2 + 2
(verrassing:  ze zijn er niet!).
     

oplossing
     

Neem de vergelijking (mod5)
5n2 + 2 ☰ 2 (mod 5)
2m2 + 1 ☰ 2 (mod 5)
2m2 ☰ 1  (mod 5)
Kwadraatresten (mod 5) zijn  0, 1, 4
2m2 is dus 0, 2, 8 ☰ 0, 2, 3  (mod 5)
1 is niet mogelijk.
       

© h.hofstede (h.hofstede@hogeland.nl)