Samenvatting
Samenvatting Getaltheorie
- Vak
- Instelling
Zonder Chinese reststelling.
[Meer zien]Voorbeeld 2 van de 14 pagina's
Voorbeeld 2 van de 14 pagina's
In winkelwagen
In winkelwagen
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.
Verkoper
Volgen
cdenhollander
Ontvangen beoordelingen
Voorbeeld van de inhoud
GETALTHEORIEHOOFDSTUK 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.
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
√ Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, Bancontact of creditcard voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
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.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper cdenhollander. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €2,99. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 72042 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen