1. Conventies
2. Deler
3. Priemgetal
3.1. Zeef van Eratosthenes
3.2. Priemtweeling
3.3. Priemfactoren
3.4. Aantal priemgetallen
3.5. Mersenne priemgetal
4. GGD
4.1. Uit priemfactorisatie
4.2. Algoritme van Euclides
4.3. Diophantes van Alexandrië
4.4. KGV
5. (Ir)rationaal getal
5.1. Van decimaal naar breuk
5.2. Bewijs( ir)rationaliteit van een wortel
5.3. Kettingbreuk
5.4. Schema
6. Modulo
6.1. Modulo reduceren
1/6 © Peter Zomerdijk
, 1. Conventies
• voorbeelden zijn omkaderd
• k, n, p, q, r, t, x, y, z ∈ ℕ
• p is een priemgetal
• g∈ℝ
2. Deler
t
• n is een deler van deelgetal t en t is een veelvoud van n als er een x (∈ ℕ) bestaat zó dat n = x
• "n is een deler van deelgetal t" wordt genoteerd als n|t
• n is een "echte deler" van t als n ≠ 1 ꓥ n ≠ t
• n is een "flauwe deler" van t als n = t ꓦ n = 1
• getallen met een oneven aantal delers zijn kwadraten
• n|0 = 0
• n|t ꓥ n|r ⇒ n|(tx + ry) ꓥ n|tr
• ieder getal > 0 bestaat uit een product plus een rest:
n > 0 ⇒ x, y, r | n = x · y + r waarbij 0 ≤ r < max(x,y)
18 > 0 ⇒ 18 = 7 · 2 + 4 waarbij 0 ≤ 4 < 7
• [g] is het gehele deel van g
• g ‒ [g] is de rest van g
• g = [g] rest (g ‒ [g])
18 18 18 18 4
= [ ] rest ( − [ ]) = 2 rest
7 7 7 7 7
3. Priemgetal
• priemgetal : een natuurlijk getal > 1 zonder echte delers
• samengesteld getal : een natuurlijk getal dat geen priemgetal is
• Goldbach (1742) : elk even getal > 2 is een som van twee priemgetallen
• p|xy ⇒ p|x ꓦ p|y
3.1. Zeef van Eratosthenes (200 v. Chr.)
Selecteert de priemgetallen uit een lijst getallen van 2 tot x (= tot en met x ‒ 1)
veger = 2
herhaal
noteer veger als priemgetal
streep alle veger-vouden tot x door
veger wordt 1e niet doorgestreepte getal
tot veger > [√x]
noteer overige niet doorgestreepte getallen als priemgetal
3.2. Priemtweeling
• een priemtweeling bestaat uit 2 priemgetallen; p en p+2
11 en 13 vormen een priemtweeling
• het is onbekend of er oneindig veel priemtweelingen zijn
2/6 © Peter Zomerdijk
2. Deler
3. Priemgetal
3.1. Zeef van Eratosthenes
3.2. Priemtweeling
3.3. Priemfactoren
3.4. Aantal priemgetallen
3.5. Mersenne priemgetal
4. GGD
4.1. Uit priemfactorisatie
4.2. Algoritme van Euclides
4.3. Diophantes van Alexandrië
4.4. KGV
5. (Ir)rationaal getal
5.1. Van decimaal naar breuk
5.2. Bewijs( ir)rationaliteit van een wortel
5.3. Kettingbreuk
5.4. Schema
6. Modulo
6.1. Modulo reduceren
1/6 © Peter Zomerdijk
, 1. Conventies
• voorbeelden zijn omkaderd
• k, n, p, q, r, t, x, y, z ∈ ℕ
• p is een priemgetal
• g∈ℝ
2. Deler
t
• n is een deler van deelgetal t en t is een veelvoud van n als er een x (∈ ℕ) bestaat zó dat n = x
• "n is een deler van deelgetal t" wordt genoteerd als n|t
• n is een "echte deler" van t als n ≠ 1 ꓥ n ≠ t
• n is een "flauwe deler" van t als n = t ꓦ n = 1
• getallen met een oneven aantal delers zijn kwadraten
• n|0 = 0
• n|t ꓥ n|r ⇒ n|(tx + ry) ꓥ n|tr
• ieder getal > 0 bestaat uit een product plus een rest:
n > 0 ⇒ x, y, r | n = x · y + r waarbij 0 ≤ r < max(x,y)
18 > 0 ⇒ 18 = 7 · 2 + 4 waarbij 0 ≤ 4 < 7
• [g] is het gehele deel van g
• g ‒ [g] is de rest van g
• g = [g] rest (g ‒ [g])
18 18 18 18 4
= [ ] rest ( − [ ]) = 2 rest
7 7 7 7 7
3. Priemgetal
• priemgetal : een natuurlijk getal > 1 zonder echte delers
• samengesteld getal : een natuurlijk getal dat geen priemgetal is
• Goldbach (1742) : elk even getal > 2 is een som van twee priemgetallen
• p|xy ⇒ p|x ꓦ p|y
3.1. Zeef van Eratosthenes (200 v. Chr.)
Selecteert de priemgetallen uit een lijst getallen van 2 tot x (= tot en met x ‒ 1)
veger = 2
herhaal
noteer veger als priemgetal
streep alle veger-vouden tot x door
veger wordt 1e niet doorgestreepte getal
tot veger > [√x]
noteer overige niet doorgestreepte getallen als priemgetal
3.2. Priemtweeling
• een priemtweeling bestaat uit 2 priemgetallen; p en p+2
11 en 13 vormen een priemtweeling
• het is onbekend of er oneindig veel priemtweelingen zijn
2/6 © Peter Zomerdijk
