Inhoudsopgave Getaltheorie
1. Pythagorese drietallen (Week 1)
2. GGD en Algoritme van Euclides (Week 2)
3. Delers - stellingen en bewijzen - Pyth drietal eenheidscirkel (Week 2)
4. Diophantische vergelijkingen (Week 3)
5. Hoofdstelling (Week 4)
6. Modulorekenen (Week 4)
7. Stellingen van Wilson, Euler en Fermat (Week 5)
8. CRS - Eliminatie - Sommeren (Week 6)
9. Stelling van Euler vervolg en oneindig veel priemgetallen (Week 6 en 7)
10. Het aantal priemgetallen (Week 7)
11. Mersenne, sigma, tau en perfecte getallen (Week 8)
12. G-tallig rekenen en machtsverheffen (Week 9)
13. Worteltrekken en factorisatie Fermat (Week 9 en 10)
14. RSA (Week 10)
15. RSA (vervolg) en Polardontbinding (Week 10 en 11)
16. Fermat priemtest, Carmichaelgetallen en wortelpriemtest (Week 11)
17. Rabin-Miller-priemtest (Week 11)
18. Multiplicatief som phi en begrip orde (Week 13)
19. Orde en triviale stellingen (Week 14)
20. Orde efficient berekenen en primitieve wortels (Week 14)
21. Orde via machten en aantal primitieve wortels (Week 14)
22. Bewijs elk priemgetal heeft precies phi(p-1) primitieve wortels (Week 14)
23. Protocol Diffie-Helman (deel 1) (Week 15)
24. Protocol Diffie-Helman (deel 2) (Week 15)
,Pythagorese drietallen (Week 1)
Stelling 1: Een geheeltallige oplossing van 𝑎2 + 𝑏 2 = 𝑐 2 waarvoor geldt:
• 𝑔𝑔𝑑(𝑎, 𝑏) = 𝑔𝑔𝑑(𝑎, 𝑐) = 𝑔𝑔𝑑(𝑏, 𝑐) = 1 heet een primitief Pythagorees drietal.
Eigenschap 1: Als (𝑎, 𝑏, 𝑐) een primitief Pythagorees drietal is, dan geldt:
• 𝑎 oneven en 𝑏 even (of andersom) en is 𝑐 is oneven.
Lemma: Als (𝑎, 𝑏, 𝑐) een primitief Pythagorees drietal is, dan 𝑔𝑔𝑑(𝑐 − 𝑏, 𝑐 + 𝑏) = 1.
Stelling 2: Alle priemfactoren in het kwadraat hebben even exponenten.
Stelling 3: Elk primitief Pythagorees drietal (𝑎, 𝑏, 𝑐) met 𝑎 oneven en 𝑏 even is van de vorm:
𝑠2 −𝑡 2 𝑠2 +𝑡 2
𝑎 = 𝑠𝑡, 𝑏= 𝑐=
2 2
Waarbij 𝑠 > 𝑡 ≥ 1, 𝑠 en 𝑡 oneven en 𝑔𝑔𝑑(𝑠, 𝑡) = 1.
Slimme truc: (𝑎2 + 𝑏 2 )(𝑐 2 + 𝑑2 ) = 𝑎2 𝑐 2 − 2𝑎𝑏𝑐𝑑 + 𝑏 2 𝑑2 + 𝑎2 𝑑 2 + 2𝑎𝑏𝑐𝑑 + 𝑏 2 𝑐 2
= (𝑎𝑐 − 𝑏𝑑)2 + (𝑎𝑑 + 𝑏𝑐)2
Voorbeeld 1: Bepaal alle primitieve Pythagorese drietallen die het getal 65 bevatten.
65 is oneven, dus 65 moet a of c zijn.
• 𝑎 = 𝑠𝑡 = 65 → 𝐴𝑓𝑠𝑐ℎ𝑎𝑡𝑡𝑒𝑛 𝑔𝑒𝑒𝑓𝑡: 1 ≤ 𝑡 < 𝑠 < 65
→ 𝑡 = 1, 𝑑𝑎𝑛 𝑠 = 65 𝑂𝐹 𝑡 = 5, 𝑑𝑎𝑛 𝑠 = 13 .
652 −12 652 + 12
Optie 1: 𝑡 = 1 & 𝑠 = 65 Invullen geeft: 𝑎 = 65 en 𝑏 = en 𝑐 = .
2 2
𝑎 = 65 𝑒𝑛 𝑏 = 2112 𝑒𝑛 𝑐 = 2113. Dus (65, 2112, 2113).
132 −52 132 + 52
Optie 2: 𝑡 = 5 & 𝑠 = 13 Invullen geeft: 𝑎 = 65 en 𝑏 = en 𝑐 = .
2 2
𝑎 = 65 𝑒𝑛 𝑏 = 72 𝑒𝑛 𝑐 = 97. Dus (65, 72, 97).
𝑠2 +𝑡 2
• 𝑐= = 65 → 𝑠 2 + 𝑡 2 = 130 → Afschatten geeft: 1 ≤ 𝑡 < 𝑠 < 12
2
→ 𝑡 = 3, 𝑑𝑎𝑛 𝑠 = 11 𝑂𝐹 𝑡 = 7, 𝑑𝑎𝑛 𝑠 = 9 .
112 −32
Optie 1: 𝑡 = 3 & 𝑠 = 11 Invullen geeft: 𝑎 = 11 ∙ 3 en 𝑏 = en 𝑐 = 65 .
2
𝑎 = 33 𝑒𝑛 𝑏 = 56 𝑒𝑛 𝑐 = 65. Dus (33, 56, 65).
92 −72
Optie 2: 𝑡 = 7 & 𝑠 = 9 Invullen geeft: 𝑎 = 9 ∙ 7 en 𝑏 = en 𝑐 = 65.
2
𝑎 = 63 𝑒𝑛 𝑏 = 16 𝑒𝑛 𝑐 = 65. Dus (63, 16, 65).
Voorbeeld 2: Bepaal alle primitieve Pythagorese drietallen die het getal 20 bevatten.
20 is even, dus 20 moet b zijn. 2 ∙ (2 ∙ 2 ∙ 5) = 2 ∙ 20 OF (2 ∙ 2) ∙ (2 ∙ 5) = 4 ∙ 10 OF (2 ∙ 2 ∙ 2) ∙ 5 = 8 ∙ 5
𝑠2 −𝑡 2
• 𝑏= = 20 → 𝑠 2 − 𝑡 2 = 40 → (𝑠 − 𝑡)(𝑠 + 𝑡) = 40 𝑒𝑛 40 = 2 ∙ 2 ∙ 2 ∙ 5
2
LET OP: 𝑒𝑣𝑒𝑛 ∙ 𝑒𝑣𝑒𝑛 = 𝑒𝑣𝑒𝑛 , dus 𝑠 − 𝑡 𝑒𝑛 𝑠 + 𝑡 = 𝑒𝑣𝑒𝑛.
𝑠, 𝑡 = 𝑜𝑛𝑒𝑣𝑒𝑛, 𝑤𝑎𝑛𝑡 𝑔𝑔𝑑 (𝑠, 𝑡) = 1.
𝑠−𝑡 =2 𝑠 = 11
Optie 1: { → { → 𝑎 = 99 𝑒𝑛 𝑏 = 20 𝑒𝑛 𝑐 = 101. Dus (99, 20, 101).
𝑠 + 𝑡 = 20 𝑡=9
𝑠−𝑡 =4 𝑠=7
Optie 2: { → { → 𝑎 = 21 𝑒𝑛 𝑏 = 20 𝑒𝑛 𝑐 = 29. Dus (21, 20, 29).
𝑠 + 𝑡 = 10 𝑡=3
, GGD en Algoritme van Euclides (Week 2)
(GGD op HP Prime: MEM → CAS → 5. Geheel getal → 4. GGD.)
Stelling 1: De 𝑔𝑔𝑑 (𝑎, 𝑏) kan altijd berekend worden met het algoritme van Euclides.
Het algoritme van Euclides
Voorbeeld: Onderzoek wat de GGD van het getal 42 en 16 is met het algoritme van Euclides.
42 = 2 ∙ 16 + 10
Eerste stap snel op HP Prime:
16 = 1 ∙ 10 + 6
• Cijfer voor keer: MEM → CAS → 5. Geheel getal
10 = 1 ∙ 6 + 4 → 7. Deling → 1. Quotiënt → Enter
6= 1∙4+2 GGD • Rest: MEM → CAS → 5. Geheel getal
→ 7. Deling → 2. Rest → Enter
4= 2∙2+𝟎 STOP (Bij rest 0)
Stelling 2: Er is een 𝑥1 , 𝑦1 ∈ Ζ waarvoor geldt 𝑔𝑔𝑑(𝑎, 𝑏) = 𝑥1 𝑎 + 𝑦1 𝑏.
(Ook wel het uitgebreide algoritme van Euclides OF GGD als lineaire combinatie van a en b.)
Het uitgebreide algoritme van Euclides (Zie voorbeeld.)
Uit 42 = 2 ∙ 16 + 10 volgt → 10 = 42 − 2 ∙ 16
Uit 16 = 1 ∙ 10 + 6 volgt → 6 = 16 − 1 ∙ 10 → 6 = 16 − 1 ∙ (42 − 2 ∙ 16)
→ 6 = − 1 ∙ 42 + 3 ∙ 16
Uit 10 = 1 ∙ 6 + 4 volgt → 4 = 10 − 1 ∙ 6 → 4 = (42 − 2 ∙ 16) − 1 ∙ (− 1 ∙ 42 + 3 ∙ 16)
→ 4 = 2 ∙ 42 − 5 ∙ 16
Uit 6 = 1 ∙ 4 + 2 volgt → 2 = 6 − 1 ∙ 4 → 2 = (− 1 ∙ 42 + 3 ∙ 16) − 1 ∙ (2 ∙ 42 − 5 ∙ 16)
→ 2 = − 3 ∙ 42 + 8 ∙ 16
𝑥1 𝑥2
𝑔𝑔𝑑(42, 16) = − 3 ∙ 42 + 8 ∙ 16 . (Dit is de lineaire vergelijking.)
Stelling 3: 𝑔𝑔𝑑(𝑎, 𝑏) is de kleinste positieve waarde die 𝑎𝑥 + 𝑏𝑦 kan aannemen.
∎
Stelling 4: 𝑎|𝑏𝑐 ∧ 𝑔𝑔𝑑(𝑎, 𝑏) = 1 → 𝑎|𝑐.
∎
1. Pythagorese drietallen (Week 1)
2. GGD en Algoritme van Euclides (Week 2)
3. Delers - stellingen en bewijzen - Pyth drietal eenheidscirkel (Week 2)
4. Diophantische vergelijkingen (Week 3)
5. Hoofdstelling (Week 4)
6. Modulorekenen (Week 4)
7. Stellingen van Wilson, Euler en Fermat (Week 5)
8. CRS - Eliminatie - Sommeren (Week 6)
9. Stelling van Euler vervolg en oneindig veel priemgetallen (Week 6 en 7)
10. Het aantal priemgetallen (Week 7)
11. Mersenne, sigma, tau en perfecte getallen (Week 8)
12. G-tallig rekenen en machtsverheffen (Week 9)
13. Worteltrekken en factorisatie Fermat (Week 9 en 10)
14. RSA (Week 10)
15. RSA (vervolg) en Polardontbinding (Week 10 en 11)
16. Fermat priemtest, Carmichaelgetallen en wortelpriemtest (Week 11)
17. Rabin-Miller-priemtest (Week 11)
18. Multiplicatief som phi en begrip orde (Week 13)
19. Orde en triviale stellingen (Week 14)
20. Orde efficient berekenen en primitieve wortels (Week 14)
21. Orde via machten en aantal primitieve wortels (Week 14)
22. Bewijs elk priemgetal heeft precies phi(p-1) primitieve wortels (Week 14)
23. Protocol Diffie-Helman (deel 1) (Week 15)
24. Protocol Diffie-Helman (deel 2) (Week 15)
,Pythagorese drietallen (Week 1)
Stelling 1: Een geheeltallige oplossing van 𝑎2 + 𝑏 2 = 𝑐 2 waarvoor geldt:
• 𝑔𝑔𝑑(𝑎, 𝑏) = 𝑔𝑔𝑑(𝑎, 𝑐) = 𝑔𝑔𝑑(𝑏, 𝑐) = 1 heet een primitief Pythagorees drietal.
Eigenschap 1: Als (𝑎, 𝑏, 𝑐) een primitief Pythagorees drietal is, dan geldt:
• 𝑎 oneven en 𝑏 even (of andersom) en is 𝑐 is oneven.
Lemma: Als (𝑎, 𝑏, 𝑐) een primitief Pythagorees drietal is, dan 𝑔𝑔𝑑(𝑐 − 𝑏, 𝑐 + 𝑏) = 1.
Stelling 2: Alle priemfactoren in het kwadraat hebben even exponenten.
Stelling 3: Elk primitief Pythagorees drietal (𝑎, 𝑏, 𝑐) met 𝑎 oneven en 𝑏 even is van de vorm:
𝑠2 −𝑡 2 𝑠2 +𝑡 2
𝑎 = 𝑠𝑡, 𝑏= 𝑐=
2 2
Waarbij 𝑠 > 𝑡 ≥ 1, 𝑠 en 𝑡 oneven en 𝑔𝑔𝑑(𝑠, 𝑡) = 1.
Slimme truc: (𝑎2 + 𝑏 2 )(𝑐 2 + 𝑑2 ) = 𝑎2 𝑐 2 − 2𝑎𝑏𝑐𝑑 + 𝑏 2 𝑑2 + 𝑎2 𝑑 2 + 2𝑎𝑏𝑐𝑑 + 𝑏 2 𝑐 2
= (𝑎𝑐 − 𝑏𝑑)2 + (𝑎𝑑 + 𝑏𝑐)2
Voorbeeld 1: Bepaal alle primitieve Pythagorese drietallen die het getal 65 bevatten.
65 is oneven, dus 65 moet a of c zijn.
• 𝑎 = 𝑠𝑡 = 65 → 𝐴𝑓𝑠𝑐ℎ𝑎𝑡𝑡𝑒𝑛 𝑔𝑒𝑒𝑓𝑡: 1 ≤ 𝑡 < 𝑠 < 65
→ 𝑡 = 1, 𝑑𝑎𝑛 𝑠 = 65 𝑂𝐹 𝑡 = 5, 𝑑𝑎𝑛 𝑠 = 13 .
652 −12 652 + 12
Optie 1: 𝑡 = 1 & 𝑠 = 65 Invullen geeft: 𝑎 = 65 en 𝑏 = en 𝑐 = .
2 2
𝑎 = 65 𝑒𝑛 𝑏 = 2112 𝑒𝑛 𝑐 = 2113. Dus (65, 2112, 2113).
132 −52 132 + 52
Optie 2: 𝑡 = 5 & 𝑠 = 13 Invullen geeft: 𝑎 = 65 en 𝑏 = en 𝑐 = .
2 2
𝑎 = 65 𝑒𝑛 𝑏 = 72 𝑒𝑛 𝑐 = 97. Dus (65, 72, 97).
𝑠2 +𝑡 2
• 𝑐= = 65 → 𝑠 2 + 𝑡 2 = 130 → Afschatten geeft: 1 ≤ 𝑡 < 𝑠 < 12
2
→ 𝑡 = 3, 𝑑𝑎𝑛 𝑠 = 11 𝑂𝐹 𝑡 = 7, 𝑑𝑎𝑛 𝑠 = 9 .
112 −32
Optie 1: 𝑡 = 3 & 𝑠 = 11 Invullen geeft: 𝑎 = 11 ∙ 3 en 𝑏 = en 𝑐 = 65 .
2
𝑎 = 33 𝑒𝑛 𝑏 = 56 𝑒𝑛 𝑐 = 65. Dus (33, 56, 65).
92 −72
Optie 2: 𝑡 = 7 & 𝑠 = 9 Invullen geeft: 𝑎 = 9 ∙ 7 en 𝑏 = en 𝑐 = 65.
2
𝑎 = 63 𝑒𝑛 𝑏 = 16 𝑒𝑛 𝑐 = 65. Dus (63, 16, 65).
Voorbeeld 2: Bepaal alle primitieve Pythagorese drietallen die het getal 20 bevatten.
20 is even, dus 20 moet b zijn. 2 ∙ (2 ∙ 2 ∙ 5) = 2 ∙ 20 OF (2 ∙ 2) ∙ (2 ∙ 5) = 4 ∙ 10 OF (2 ∙ 2 ∙ 2) ∙ 5 = 8 ∙ 5
𝑠2 −𝑡 2
• 𝑏= = 20 → 𝑠 2 − 𝑡 2 = 40 → (𝑠 − 𝑡)(𝑠 + 𝑡) = 40 𝑒𝑛 40 = 2 ∙ 2 ∙ 2 ∙ 5
2
LET OP: 𝑒𝑣𝑒𝑛 ∙ 𝑒𝑣𝑒𝑛 = 𝑒𝑣𝑒𝑛 , dus 𝑠 − 𝑡 𝑒𝑛 𝑠 + 𝑡 = 𝑒𝑣𝑒𝑛.
𝑠, 𝑡 = 𝑜𝑛𝑒𝑣𝑒𝑛, 𝑤𝑎𝑛𝑡 𝑔𝑔𝑑 (𝑠, 𝑡) = 1.
𝑠−𝑡 =2 𝑠 = 11
Optie 1: { → { → 𝑎 = 99 𝑒𝑛 𝑏 = 20 𝑒𝑛 𝑐 = 101. Dus (99, 20, 101).
𝑠 + 𝑡 = 20 𝑡=9
𝑠−𝑡 =4 𝑠=7
Optie 2: { → { → 𝑎 = 21 𝑒𝑛 𝑏 = 20 𝑒𝑛 𝑐 = 29. Dus (21, 20, 29).
𝑠 + 𝑡 = 10 𝑡=3
, GGD en Algoritme van Euclides (Week 2)
(GGD op HP Prime: MEM → CAS → 5. Geheel getal → 4. GGD.)
Stelling 1: De 𝑔𝑔𝑑 (𝑎, 𝑏) kan altijd berekend worden met het algoritme van Euclides.
Het algoritme van Euclides
Voorbeeld: Onderzoek wat de GGD van het getal 42 en 16 is met het algoritme van Euclides.
42 = 2 ∙ 16 + 10
Eerste stap snel op HP Prime:
16 = 1 ∙ 10 + 6
• Cijfer voor keer: MEM → CAS → 5. Geheel getal
10 = 1 ∙ 6 + 4 → 7. Deling → 1. Quotiënt → Enter
6= 1∙4+2 GGD • Rest: MEM → CAS → 5. Geheel getal
→ 7. Deling → 2. Rest → Enter
4= 2∙2+𝟎 STOP (Bij rest 0)
Stelling 2: Er is een 𝑥1 , 𝑦1 ∈ Ζ waarvoor geldt 𝑔𝑔𝑑(𝑎, 𝑏) = 𝑥1 𝑎 + 𝑦1 𝑏.
(Ook wel het uitgebreide algoritme van Euclides OF GGD als lineaire combinatie van a en b.)
Het uitgebreide algoritme van Euclides (Zie voorbeeld.)
Uit 42 = 2 ∙ 16 + 10 volgt → 10 = 42 − 2 ∙ 16
Uit 16 = 1 ∙ 10 + 6 volgt → 6 = 16 − 1 ∙ 10 → 6 = 16 − 1 ∙ (42 − 2 ∙ 16)
→ 6 = − 1 ∙ 42 + 3 ∙ 16
Uit 10 = 1 ∙ 6 + 4 volgt → 4 = 10 − 1 ∙ 6 → 4 = (42 − 2 ∙ 16) − 1 ∙ (− 1 ∙ 42 + 3 ∙ 16)
→ 4 = 2 ∙ 42 − 5 ∙ 16
Uit 6 = 1 ∙ 4 + 2 volgt → 2 = 6 − 1 ∙ 4 → 2 = (− 1 ∙ 42 + 3 ∙ 16) − 1 ∙ (2 ∙ 42 − 5 ∙ 16)
→ 2 = − 3 ∙ 42 + 8 ∙ 16
𝑥1 𝑥2
𝑔𝑔𝑑(42, 16) = − 3 ∙ 42 + 8 ∙ 16 . (Dit is de lineaire vergelijking.)
Stelling 3: 𝑔𝑔𝑑(𝑎, 𝑏) is de kleinste positieve waarde die 𝑎𝑥 + 𝑏𝑦 kan aannemen.
∎
Stelling 4: 𝑎|𝑏𝑐 ∧ 𝑔𝑔𝑑(𝑎, 𝑏) = 1 → 𝑎|𝑐.
∎
