Samenvatting Getaltheorie

GETALTHEORIE

HOOFDSTUK 15: PRIEMGETALLEN EN HET ALGORITME VAN EUCLIDES

Definities
- Priemgetallen: een geheel getal die alleen deelbaar is door zichzelf en 1, ofwel wanneer een
getal geen echte delers heeft: 2, 3, 5, 7, 11, …
- Echte deler: een positieve deler van a ∈ ℤ die niet gelijk is aan 1 of a, zoals 5 en 3 van 15.
- Samengesteld getal: een getal a ∈ ℤ als het getal echte delers heeft.
- Priemdeler of priemfactor: ieder natuurlijk getal groter dan 2 heeft minstens één deler die een
priemgetal is. Denk aan het ontbinden in priemfactoren.
- Priemgetaltweeling: 𝑃 en 𝑃 + 2. Voorbeeld: 3 en 5, 29 en 31, etc. Het vermoeden is dat er
oneindig veel zijn.
- Priemgetaldrieling: 𝑃 en 𝑃 + 2 en 𝑃 + 4. Voorbeeld: 3, 5 en 7. Er is slechts één priemdrieling.

Stelling van Euclides Stelling 15.12
‘Er zijn oneindig veel priemgetallen.’

Bewijs (uit het ongerijmde):
Stel dat het priemgetal 𝑃𝑘 het grootste priemgetal is, dus 𝑃1 , 𝑃2 , … , 𝑃𝑘 .
Beschouw het getal 𝑃𝑛 = 𝑃1 ∙ 𝑃2 ∙ 𝑃3 ∙ … ∙ 𝑃𝑘 + 1.
𝑃𝑛 heeft altijd minstens één priemdeler (want het is een samengesteld getal wat je altijd kan
ontbinden in priemfactoren). Dat moet één van de priemgetallen 𝑃1 of 𝑃2 of … of 𝑃𝑘 zijn. We noemen
die priemdeler even 𝑃𝑖 .

Dan geldt: 𝑃𝑖 | 𝑃𝑛 en 𝑃𝑖 | 𝑃𝑛 − 1
Dit geldt omdat 𝑃𝑛 − 1 een vermenigvuldiging is van alle priemgetallen

Dan is 𝑃𝑖 | 𝑃𝑛 − (𝑃𝑛 − 1)
Als 𝑑 | 𝑎 ∧ 𝑑 |𝑏
Dan 𝑑 | 𝑎 + 𝑏 ∧ 𝑑 | 𝑎 − 𝑏


Dus 𝑃𝑖 | 1, maar een priemgetal dat groter is dan 1 is geen deler van 1.
De aanname was onjuist, dus er zijn oneindig veel priemgetallen.

Mersenne priemgetal
𝑀𝑝 = 2𝑝 − 1 , waarbij p een priemgetal is.
Maar 𝑀11 = 211 − 1 = 2047 = 23 ∙ 89 en dat is dus geen priemgetal. De formule wordt, ondanks
dat hij niet altijd werkt, nog wel gebruikt om een priemgetal te bepalen.

Definities
- Grootst gemene deler: de ggd van twee gehele getallen a en b is het grootste gehele getal d
waarvoor geldt: 𝑑 | 𝑎 en 𝑑 | 𝑏. Definitie 15.16
2 3
o Voorbeeld: 𝑔𝑔𝑑(18, 40) = 2 want 18 = 2 ∙ 3 en 40 = 2 ∙ 5.

, - Kleinst gemene veelvoud: de kgv van twee gehele getallen a en b is het kleinste positieve getal
k waarvoor geldt: 𝑎 | 𝑘 en 𝑏 | 𝑘. Definitie 15.17
3 2
o Voorbeeld: 𝑘𝑔𝑣(18, 40) = 2 ∙ 3 ∙ 5 = 360.
- Lineaire combinatie van a en b: een getal in de vorm 𝑢𝑎 + 𝑣𝑏, waarbij u en v gehele getallen
zijn. Definitie 15.18
o Voorbeeld: 𝑎 = 10 en 𝑏 = 16
68 = 2 ∙ 10 + 3 ∙ 16
22 = −1 ∙ 10 + 2 ∙ 16
22 = −9 ∙ 10 + 7 ∙ 16
Lemma Lemma 15.19
𝑎, 𝑏 ∈ ℤ en 𝑐 is een lineaire combinatie van a en b.
1) Ieder veelvoud van c is een lineaire combinatie van a en b.
2) Er zijn oneindig veel lineaire combinaties van a en b die gelijk aan c zijn.

Stelling Stelling 15.21
𝑎, 𝑏 ∈ ℤ en beide ongelijk aan 0.
De lineaire combinatie van a en b zijn precies de veelvouden van de 𝑔𝑔𝑑(𝑎, 𝑏). In het bijzonder is de
𝑔𝑔𝑑(𝑎, 𝑏) zelf een lineaire combinatie van a en b.

Voorbeeld: 𝑔𝑔𝑑(10, 16) = 2 want 10 = 21 ∙ 51 en 16 = 24
Alle lineaire combinaties zijn dus veelvouden van 2: 2 = −3 ∙ 10 + 2 ∙ 16
68 = 2 ∙ 10 + 3 ∙ 16
22 = −1 ∙ 10 + 2 ∙ 16
26 = 1 ∙ 10 + 1 ∙ 16
44 = 6 ∙ 10 − 1 ∙ 16

Stelling Stelling 15.22
𝑎, 𝑏 ∈ ℤ en beide ongelijk aan 0 en 𝑔𝑔𝑑(𝑎, 𝑏) = 𝑑.
𝑎 𝑏
1) 𝑔𝑔𝑑 (𝑑 , 𝑑) = 1.
2) 𝑑 is de enige gemeenschappelijke deler van a en b waarvoor het bovenstaande geldt.
3) Iedere gemeenschappelijke deler van a en b is een deler van 𝑔𝑔𝑑(𝑎, 𝑏).

Voorbeeld: neem 𝑎 = 32 en 𝑏 = 56.
Dan geldt 32 = 25 en 56 = 23 ∙ 71 , dus 𝑔𝑔𝑑(32, 56) = 23 = 8.
32 56
1) 𝑔𝑔𝑑 ( 8 , ) = 𝑔𝑔𝑑(4, 7) = 1.
8
32 56
2) 2 is ook een deler van 32 en 56, maar 𝑔𝑔𝑑 ( 2 , ) = 𝑔𝑔𝑑(16, 28) ≠ 1.
2
3) Gemeenschappelijke delers zijn: 2, 4 en 8.
8 is de ggd en 2 | 8 ∧ 4 | 8.

Defintie
- Relatief priem: twee getallen 𝑎, 𝑏 ∈ ℤ zijn relatief priem als 𝑔𝑔𝑑(𝑎, 𝑏) = 1. a en b zelf hoeven
niet per se priem te zijn. Definitie 15.24
o Voorbeeld: 𝑎 = 18 en 𝑏 = 7, dan 𝑔𝑔𝑑(18, 7) = 1.
Je kan dan een lineaire combinatie vinden voor de ggd: 1 = 2 ∙ 18 − 5 ∙ 7. Daarmee
geldt dan ook dat elk getal een lineaire combinatie is van deze twee getallen.