Samenvatting

Samenvatting Getaltheorie

Name: Samenvatting Getaltheorie
SKU: doc_1333249
Rating: 5.00 (2 reviews)
Author: cdenhollander

2 beoordelingen

2 keer verkocht

Vak
Getaltheorie

Instelling
Hogeschool Windesheim (HW)

Zonder Chinese reststelling.

[Meer zien]

Voorbeeld 2 van de 14 pagina's

Bekijk voorbeeld

Geupload op 12 oktober 2021
Aantal pagina's 14
Geschreven in 2021/2022
Type Samenvatting

2 beoordelingen

Door: jb0318 • 3 jaar geleden

Door: aimee0044 • 3 jaar geleden

De samenvatting is erg duidelijk en overzichtelijk en er staan goede voorbeelden in die de stof begrijpelijker maken.

Volgen

cdenhollander Lid sinds 8 jaar 595 documenten verkocht

€2,99

In winkelwagen

Opslaan

100% tevredenheidsgarantie
Direct beschikbaar na je betaling
Lees online óf als PDF
Geen vaste maandelijkse kosten

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.

Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:

Bewezen kwaliteit door reviews

Studenten hebben al meer dan 850.000 samenvattingen beoordeeld. Zo weet jij zeker dat je de beste keuze maakt!

In een paar klikken geregeld

Geen gedoe — betaal gewoon eenmalig met iDeal, creditcard of je Stuvia-tegoed en je bent klaar. Geen abonnement nodig.

Direct to-the-point

Studenten maken samenvattingen voor studenten. Dat betekent: actuele inhoud waar jij écht wat aan hebt. Geen overbodige details!

Veelgestelde vragen

Wat krijg ik als ik dit document koop?

Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.

Tevredenheidsgarantie: hoe werkt dat?

Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.