Summary
Samenvatting Getaltheorie
- Course
- Institution
Zonder Chinese reststelling.
[Show more]
2 reviews
By: jb0318 • 3 year ago
By: aimee0044 • 3 year ago
The summary is very clear and clear and there are good examples that make the substance more understandable.
Seller
Follow
cdenhollander
Reviews received
Content preview
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.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller cdenhollander. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.23. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
67866 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now