Resume
Samenvatting Getaltheorie
- Cours
- Établissement
Zonder Chinese reststelling.
[Montrer plus]
2 revues
Par: jb0318 • 2 année de cela
Par: aimee0044 • 3 année de cela
The summary is very clear and clear and there are good examples that make the substance more understandable.
Vendeur
S'abonner
cdenhollander
Avis reçus
Aperçu du contenu
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.
Les avantages d'acheter des résumés chez Stuvia:
Qualité garantie par les avis des clients
Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.
L’achat facile et rapide
Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.
Focus sur l’essentiel
Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.
Foire aux questions
Qu'est-ce que j'obtiens en achetant ce document ?
Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.
Garantie de remboursement : comment ça marche ?
Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.
Auprès de qui est-ce que j'achète ce résumé ?
Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur cdenhollander. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €2,99. Vous n'êtes lié à rien après votre achat.
Peut-on faire confiance à Stuvia ?
4.6 étoiles sur Google & Trustpilot (+1000 avis)
79373 résumés ont été vendus ces 30 derniers jours
Fondée en 2010, la référence pour acheter des résumés depuis déjà 14 ans