Inhoud
Voordat u aan dit artikel begint is het raadzaam om eerst het artikel over bewijzen te lezen. In dit artikel gaan we kijken naar een eigenschap van gehele getallen die de meesten wel zullen kennen en voor de hand vinden liggen. Dat laatste is echte verre van waar; het ligt helemaal niet voor de hand. En daar gaan we hier op in. Waar hebben we het eigenlijk over? In wat meer wiskundige termen staat hier: Ieder natuurlijk (geheel, positief) getal kan op unieke wijze worden geschreven als het product (vermenigvuldiging) van priemgetallen. We moeten dus een aantal dingen weten: En daarna gaan we uitgebreid in op de zogenaamde hoofdstelling van de rekenkunde. En daarvoor hebben we een aantal andere stellingen nodig, die we ook zullen bewijzen. We beperken ons hierbij tot natuurlijke getallen, dat zijn dus positief gehele getallen. Hoe kunnen we 12 ontbinden? Dat wil zeggen: Kunnen we getallen vinden waarvan het product (de vermenigvuldiging) 12 oplevert. Ja, dat kunnen we zeker: 12 = 2 x 6. Maar ook: 12 = 3 x 4. We hebben dus 2 verschillende manieren gevonden om 12 te ontbinden. De vraag is echter: Zijn deze 2 producten echt verschillend? Kijken we naar 12 = 2 x 6, dan kan ik 6 ontbinden in 6 = 2 x 3 en dus 12 = 2 x 2 x 3. Kijken we naar 12 = 3 x 4, dan kan ik 4 ontbinden in 4 = 2 x 2 en dus 12 = 3 x 2 x 2. En behalve dat de volgorde van de factoren verschilt (2 x 2 x 3 tegenover 3 x 2 x 2) is de ontbinding hetzelfde. Ik kan de factoren 2 en 3 niet verder ontbinden, in ieder geval niet met natuurlijke getallen. De getallen 2 en 3 zijn zogenaamde priemgetallen. Een priemgetal is dus een natuurlijk getal dat niet te ontbinden is, anders dan met de factoren 1 en zichzelf. De formele, wiskundige, definitie van een priemgetal is: Een priemgetal is een getal met precies twee (verschillende) delers; namelijk 1 en zichzelf. Het getal 1 is daarom geen priemgetal want het heeft slechts 1 deler. He kleinste priemgetal is dus 2 (2 x 1) en is tevens het enige even priemgetal. En dat is logisch want ieder even getal heeft ook 2 als deler en dus meer dan twee verschillende delers. De eerste priemgetallen zijn: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, … Er zijn oneindig veel priemgetallen. Rekenkunde is een deelgebied van de wiskunde dat zich bezig houdt met verschillende eigenschappen van (meestal gehele) getallen en de bewerkingen die op getallen los gelaten kunnen worden. Deze bewerkingen zijn: optellen, aftrekken, vermenigvuldigen, delen, en machtsverheffen. Er wordt dan bijvoorbeeld gekeken naar deelbaarheid van getallen, het “open” of “gesloten” zijn van verzamelingen onder een bepaalde bewerking, de commutatieve en associatieve eigenschappen van bewerkingen etc. Zo is optellen commutatief omdat: a + b = b + a, ofwel dat de volgorde waarin je getallen optelt niet uitmaakt voor de uitkomst. Vermenigvuldigen is ook commutatief. Maar aftrekken en delen zijn dat niet: a – b ≠ b – 1 en a/b ≠ b/a. Optellen en vermenigvuldigen zijn ook associatief omdat: (a + b) + c = a + (b + c) en (a x b) x c = a x (b x c). Aftrekken en delen zijn niet associatief. Zo is bijvoorbeeld (4-2)-3 = -1 en 4-(2-3) = 5. Een verzameling heet gesloten voor een bepaalde bewerking als deze bewerking ook weer een element uit dezelfde verzameling oplevert, anders is de verzameling open voor deze bewerking. Voor alle bewerkingen geldt dat eindige verzamelingen altijd open zijn. De verzameling der natuurlijke getallen ℕ, is gesloten voor optellen en vermenigvuldigen. Met wiskundige symbolen ziet dat er zo uit: Voor de aftrekken en delen is ℕ open. Wanneer ik bijvoorbeeld 2-3)=-1) heb dan zit het verschil niet meer in ℕ. Wanneer een verzameling open is voor een bepaalde bewerkging gaan wiskundigen op zoek naar uitbreiding van zo’n verzameling waarin de betreffende bewerking dan wel gesloten is. Zo is de verzameling der gehele getallen een uitbreiding op de verzameling natuurlijke getallen zodat aftrekken in deze nieuwe verzameling gesloten is. Deze verzameling bestaat uit alle natuurlijke getallen uitgebreid met de negatieve gehele getallen (en eventueel 0 wanneer deze niet wordt meegerekend in ℕ). Deze verzameling wordt ℤ genoemd. Voor delen is ℤ (en dus ook ℕ) open. Deze verzamelingen zijn uitgebreid naar de verzameling der rationale getalen. Dat zijn alle getallen a/b waarbij a en b uit ℤ komen. Deze verzameling heet ℚ. Er geldt dus: ℕ ⊂ ℤ ⊂ ℚ. Binnen ℕ (inclusief 0) wordt 0 als “hoogste” getal aangemerkt omdat er geen enkel getal deelbaar is door 0. En zo is 1 het “laagste” getal omdat ieder getal deelbaar is door 1. De hoofdstelling van de rekenkunde luidt: Ieder natuurlijk getal groter dan 1 is op unieke wijze te ontbinden in priemfactoren. Dit geldt ook voor de gehele getallen getallen uitgezonderd -1, 0 en 1. Het bijzondere van deze stelling is het woordje “unieke”. Het bewijs van de hoofdstelling van de rekenkunde is een veel-traps-raket. Het bewijs zelf bestaat uit twee delen. In het bewijs maken we gebruik van het Lemma van Euclides, dat we ook zullen bewijzen. In het bewijs van het Lemma van Euclides maken we gebruik van het Lemma of Stelling van Bezout, dat we ook gaan bewijzen. In dat laatste bewijs maken we gebruik van het algoritme van Euclides dat we ook gaan bewijzen. We gaan dus zorgvuldig te werk en werken van onder naar boven. Met het algoritme van Euclides kan op eenvoudige wijze de Grootste Gemene Deler (ggd) van twee getallen worden gevonden. Een gemene deler van twee getallen is een deler die beide getallen deelt. Zo is 2 een deler van 12 en 32, ofwel 2 is een gemene deler van 12 en 32. We gaan nu kijken naar de grootste van al die gemene delers. Wat is de grootste gemene deler van 12 en 32, ofwel wat is de ggd(12, 32)? De delers van 12 zijn: 1, 2, 3, 4, 6 en 12. De grootste is dus 4. Nu is dit voor kleine getallen goed te doen, maar voor grote getallen is dit veel lastiger. Wat is bijvoorbeeld de ggd(120, 36)? Gelukkig heeft Euclides ons een algoritme gegeven dat snel naar het antwoord leidt en dat gaat als volgt (met de getallen 120 en 36): Kijk hoe vaak 36 (geheel) in 120 past en bepaal de rest: 120 = 3 x 36 + 12. Kijk nu hoe vaak 12 in 36 past en bepaal de rest: 36 = 3 x 12 + 0. Als de rest 0 is dan is de ggd de laatste rest die niet 0 is, dus 12. Nog een voorbeeld: Wat is de ggd(336, 44)? 336 = 7 x 44 + 28 De ggd is dus 4. We zullen dit algoritme nu bewijzen voor twee gehele getallen, dus twee getallen uit ℤ. Even wat notatie en uitleg vooraf: De absolute waarde van een (geheel) getal is de positieve variant van dat getal en wordt genoteerd tussen 2 verticale lijntjes. Dus |-2| = 2, maar ook |2| = 2. Als d een deler is van n dan is de notatie als volgt: d|n; de verticale streep tussen d en n betekent dus: “is deler van”. De wiskundige èn wordt weergegeven met ∧ en betekent dat aan alle voorwaarden voldaan moet worden. Met het symbool ∃ wordt bedoeld: “Er is” of “Er zijn” of “Er bestaat” of “Er bestaan”. Bewijs: Als m, n ∈ ℤ, |m| > |n| dan ggd(m, n) = ggd(n, r) met m = qn + r met q ∈ ℤ en 0 < r < |m| (In woorden: de ggd van m en n, m groter dan n, is gelijk aan de ggd van n en r waarbij m gelijk is aan q keer n plus een rest, waarbij de rest ligt tussen 0 en m; anders is q verkeerd gekozen) Te bewijzen: Als d|m ∧ d|n ⇔ d|n ∧ d|r (In woorden: als d een deler is van m èn van n dan is d ook een deler van n èn van r en omgekeerd!) 1) Eerst de weg van links naar rechts: a) Als d|n (linker kant), dan is (logisch) d|n (rechter kant); klaar. 2) De weg van rechts naar links a) Als d|n (rechter kant) dan is d|n (linker kant; klaar) En met 1a), 1b), 2a) en 2b) hebben we ons bewijs helemaal rond. Het leuke van het algoritme van Euclides is dat je heel snel van negatieve getallen kunt afkomen. Het moge duidelijk zijn dat wanneer d ∈ ℤ en d<0 en d|q met q ∈ ℤ dat |d| een grotere deler van q is dan d zelf. Voorbeeld: Wat is de ggd(-120, -36)? -120 = 4 x -36 + 24 (Je zou eerder 3 hebben gekozen, maar dan is de rest negatief en omdat we geen negatieve resten willen hebben nemen we er dus eentje meer) De stelling van Bezout luidt als volgt: Als m, n ∈ ℤ en d = ggd(m, n) dan ∃ z1, z2 ∈ ℤ: z1m + z2n = d. Ofwel de ggd(m, n) kun je schrijven als de som van m keer een geheel getal en n keer een geheel getal. En eigenlijk blijkt dat al uit het algoritme van Euclides. Voorbeeld: Wat is de ggd(36, 20)? a) 36 = 1 x 20 + 16 De ggd is dus 4. Uit b) volgt dat ik 4 kan schrijven als 4 = 20 – 16. Uit a) volgt dat ik 16 kan schrijven als 16 = 36 – 20. Overigens is de oplossing hierboven één van oneindig veel oplossingen. Alle oplossingen zitten in de verzameling: Bewijs: In het bewijs gaan we het voorbeeld van hierboven abstraheren. Dat levert een hoop letters op maar die doen er uiteindelijk niet zo veel toe. 1) m, n ∈ ℤ. Als |m| = |n| dan d = ggd(m, n) = |m| = |n|. Neem nu z1 = 0 en z2 = 1 (of -1 als n<0) en dan geldt: d = z1m + z2n; klaar. Uit al het bovenstaande blijkt dat de Stelling van Bezout waar is. Dat was een hele bevalling… Het Lemma van Euclides luidt als volgt: Als p|ab met a,b ∈ ℤ en p is priem dan p|a ∨ p|b. Met andere woorden: Als het product van twee (gehele) getallen een priemgetal als deler heeft dan heeft of het ene getal of het andere getal of beide getallen dezelfde priem als deler. Het symbool ∨ betekent of in de wiskundige betekenis, dus of de één of de ander òf allebei! Op de vraag: “Wilt u koffie of thee?” kan een wiskundige dus rustig “Ja” antwoorden… Bewijs: a) Als 2|a dan zijn we klaar. Uit a) en b) volgt hetgeen we bewijzen moesten. De hoofdstelling van de rekenkunde luidt: Als x ∈ ℕ, x ≥ 2, dan x is priem of x is samengesteld en kan op unieke wijze ontbonden worden als het product van priemfactoren, dus x = p1 x p2 x p3 x … x pn. Bewijs: Het bewijs bestaat uit twee delen. In deel 1) bewijzen we door middel van volledige inductie dat ieder getal te ontbinden is in priemfactoren. 1) Inductie: 2) Ieder natuurlijk getal heeft een unieke priemontbinding. Uit 1) en 2) volgt nu dat de Hoofdstelling van de Rekenkunde juist is. De uniciteit is een bijzonderheid. Er zijn genoeg andere oneindige verzamelingen te bedenken waarin dit niet zo is. Laten we eens kijken naar de verzameling ℕ3n+1 = {1, 4, 7, 10, 13, 16, …} ofwel de verzameling van alle positieve 3vouden+1. Bewijs Laat p,q ∈ ℕ3n+1. Dus p=3a+1 en q=3b+1 met a,b ∈ ℕ. Het getal 100 ∈ ℕ3n+1 is te ontbinden in 100 = 10 x 10 = 4 x 25. De getallen 4, 10, 25, 100 ∈ ℕ3n+1 maar 4, 10 en 25 zijn priemgetallen in ℕ3n+1, dus is de ontbinding in priemfactoren niet uniek! Nog een voorbeeld. Laten we eens kijken naar de verzameling a + b√6, met a, b ∈ ℤ. Dit is een uitbreiding van ℤ. Ook deze verzameling is gesloten voor vermenigvuldigen. Bewijs Zeg x = p + q√6 en y = r + s√6, dan xy = (p + q√6)(r + s√6) = pr + ps√6 + qr√6 + 6qs = (pr + 6qs) + (ps + qr)√6. Omdat alle letters uit ℤ komen kan ik zeggen dat a = pr + 6qs en b = ps + qr en aldus is xy = a + b√6. Kijken we nu eens naar de ontbinding van 6 dan krijgen we: 6 = 2 x 3 = √6 x √6. Maar we zijn er nog niet, want 2 en 3 zijn in deze verzameling geen priemgetallen, want ik kan ze ontbinden: 2 = (√6 + 2)(√6 – 2) en 3 = (3 + √6)(3 – √6) Dus 6 = √6 x √6 = (√6 + 2)(√6 – 2)(3 + √6)(3 – √6). Maar nu ook 6 = (12 + 5√6)(5√6 – 12). Er zijn dus veel verschillende ontbindingen van 6 in dit systeem. Merk op dat we de definitie van priem, impliciet, een beetje hebben aangepast: Een priem in dit systeem is een getal dat niet gefactoriseerd kan worden in dit systeem. We hebben veel werk moeten verzetten om de Hoofdstelling van de Rekenkunde te kunnen bewijzen. Merk op dat we alle lemma’s, het algoritme en stellingen voor de hoofdstelling hebben bewezen in ℤ, terwijl we ons hadden kunnen beperken tot ℕ, omdat daar de Hoofdstelling over gaat. Voornamelijk de video’s op YouTube van Elliot Nicholson (wat saai maar zeer informatief), te beginnen met: https://www.youtube.com/watch?v=oYuJXAKlQaA&list=PLAvgI3H-gclY1BRV_CPX4XQEzzggFzzih&index=1&ab_channel=ElliotNicholsonInleiding
Welnu, in simpele bewoordingen: “Ieder getal kan op unieke manier ontbonden worden in priemfactoren”.
Ontbinden van een getal
Priemgetallen
Rekenkunde
Commutatief en associatief
Open en gesloten verzamelingen
Het is dus alleen interessant om naar oneindige verzamelingen te kijken.
Dit betekent dat wanneer ik twee natuurlijke getallen bij elkaar optel of vermenigvuldig de uitkomst (som of product) ook weer in ℕ zit.
Hetzelfde geldt voor delen; zo zit 1/2 ook niet in ℕ.Hoogste en laagste getal
Hoofdstelling
Het bewijs
Het algoritme van Euclides
De delers van 32 zijn: 1, 2, 4, 8, 16 en 32.
Dat betekent dat ggd(12, 32) = 4.
44 = 1 x 28 + 16
28 = 1 x 16 + 12
16 = 1 x 12 + 4
12 = 3 x 4 + 0
b) Anders: m = qn + r (gegeven) → r = m – qn
Omdat d|m èn d|n geldt nu: m = z1d en n = z2d (z1, z2 ∈ ℤ).
Nu geldt: r = m – qn = z1d – qz2d = d(z1 – qz2). Daar z1, z2, q ∈ ℤ en ℤ gesloten is voor aftrekken en vermenigvuldigen geldt: z1 – qz2 ∈ ℤ, zeg k.
Dus r = kd, dus d|r; klaar.
b) m = qn + r (gegeven), n = z2d, r = z3d (rechter kant)
dan m = qz2d + z3d = d(qz2 + z3). Daar z2, z3, q ∈ ℤ en ℤ gesloten is voor optellen en vermenigvuldigen is qz2 + z3 ∈ ℤ, zeg k.
Dus m=dk, dus d|m; klaar.Ggd met negatieve getallen
Met het algoritme kunnen we er voor zorgen dat de resten altijd positief zijn.
-36 = -2 x 24 + 12 (En nu zijn we al van de negatieve getallen af)
24 = 2 x 12 + 0.
De ggd(-120, -36) is dus 12.De Stelling van Bezout
b) 20 = 1 x 16 + 4
c) 16 = 4 x 4 + 0
Dus kan ik 4 schrijven als 4 = 20 – 16 = 20 – 36 – 20 = -(1x)36 + 2 x 20. (z1 uit de stelling is dus -1 en z2 is dus 2).
Zo is 9 x 36 – 16 x 20 = 4 en -11 x 36 + 20 x 20 = 4.
Het gaat erom dat we vanuit de ggd van twee getallen de ggd kunnen schrijven als de som van de twee getallen met een gehele coëfficiënt.
2) m, n ∈ ℤ. Als |m|>|n|, dan m = q1n + r1.
a) Als r1 = 0 dan m = q1n -> d = |n|. Neem z1 = 0 en z2 = 1 (of -1 als n<0) en dan geldt: d = z1m + z2n; klaar.
b) Als r1>0 dan
i) m = q1n + r1, met 0<r1<|n|, dus ggd(m, n) = ggd(n, r1)
ii) n = q2r1 + r2, met 0<r2<|r1|, dus ggd(n, r1) = ggd(r1, r2)
iii) r1 = q3r2 + r3, met 0<r3<|r2|, dus ggd(r1, r2) = ggd(r2, r3)
.
.
.
iv) ri-2 = qiri-1 + ri ⇔ ri-2 = qiri-1 + d
We moeten d uitdrukken in m en n, dus gaan we substitueren…
ad i) m = q1n + r1 → r1 = m – q1n
ad ii) r2 = n – q2r1 = n – q2(m – q1n) = n – q2m + q1q2n = -q2m + (1 + q1q2)n
ad ii) r3 = r1 – q3r2 = (m – q1n) – q3((1 + q1q2)n – q2m) = … = (1 + q2q3)m + (-q1 – q3 – q1q2q3)n
Door steeds weer terug te substitueren kunnen we de resten uitdrukken in termen van m en n. De coëfficiënten van m en n zijn steeds weer getallen uit ℤ. Dit betekent dus dat:
.
.
.
ad iv) d = ri-2 = qiri-1 → d = z1m + z2n.Het Lemma van Euclides
b) Als 2∤a dan geldt: ggd(p, a) = 1.
Omdat p|ab geldt: ab = mp, met m ∈ ℤ.
Volgens de stelling van Bezout geldt ook: ∃ z1, z2 ∈ ℤ: z1p + z2a = 1.
Als we beide zijden met b vermenigvuldigen krijgen we:
z1pb + z2ab = b ⇔ z1pb + z2mp = b ⇔ b = (z1b + z2m)p.
Omdat z1, z2, b, m ∈ ℤ en omdat ℤ gesloten is voor vermenigvuldigen en optellen is z1b + z2m ∈ ℤ, zeg k.
Dus b = kp en derhalve p|b.Hoofdstelling van de rekenkunde
In deel 2) bewijzen we dat deze priemontbinding uniek moet zijn.
a) Start met x=2. 2 is priem; klaar.
b) Stel 2 ≤ x ≤ k, k ∈ ℕ dan x is priem of x is te ontbinden in priemfactoren.
Nu te bewijzen dat dit ook geldt voor k+1:
x=k+1
i) k+1 is priem; klaar.
ii) k+1 is samengesteld, dan k+1 = ab met a, b ∈ ℕ, 1 < a, b < k+1. Maar nu geldt (volgens de inductie aanname) 2 ≤ a ≤ k, dus a is te ontbinden in priemfactoren.
Hetzelfde geldt voor b.
Uit i) en ii) volgt 1b). Uit 1a) en 1b) volgt dat ieder natuurlijk getal een priemgetal is of te ontbinden is in priemfactoren.
Stel dat dit niet zo is, dus dat er een natuurlijk getal is (één of meerdere) dat twee verschillende priemontbindingen heeft, dan geldt:
a) x=p1p2p3…pn=q1q2q3…qm waarbij pi<>qi en n=m of n<>m.
p1|x → p1|q1q2q3…qm.
Volgens het Lemma van Euclides geldt: p1|ab met a=q1 en b=q2q3…qm dan p1|a=q1 of p1|b=q2q3…qm, dus p1=q1 of p1|q2q3…qm, maar dan geldt (Lemma van Euclides) p1|ab met a=q2 en b=q3q4…qm, dus p1=q2 of p1|q3q4…qm.
Dit principe kan herhaald worden tot qm-1.qm waaruit blijkt dat p1=qm-1 of qm.
In ieder geval zit p1 in q1q2q3…qm!
Maar nu kunnen we dus beide zijden p1p2p3..pn en q1q2q3…qm delen door p1.
Dan houden we over p2p3p4…pn en q1q2q3…qm met ergens een qi=p1 minder.
Maar nu kunnen we met p2 hetzelfde doen als in stap 2a).
Uiteindelijk zullen uit beide zijden alle pi’s verdwijnen zodat we overhouden: 1=qo1qo2…qom. Maar omdat alle qoi’s priemgetallen zijn en alle priemgetallen ≥ 2 kan deze vergelijking helemaal niet bestaan!
Dus moet gelden dat in p1p2p3..pn=q1q2q3…qm n=m en we hebben tevens aangetoond dat alle pi’s uitwisselbaar zijn met alle qj’s en dus moet de priemontbinding uniek zijn!
Ga zelf na dat deze verzameling gesloten is voor vermenigvuldigen.
Dan geldt: pq = (3a + 1)(3b + 1)=9ab + 3a + 3b + 1 = 3(3ab + a + b) + 1, dus ab is een drievoud plus 1.
Alle gehele getallen zitten erin; dan is b = 0.
En dit geldt voor √6, (√6 + 2), (√6 – 2), (3 + √6) en (3 – √6).Tot slot
Maar eigenlijk hebben we te veel gedaan.Bronnen
Hoofdstelling van de rekenkunde
\forall a,b \in \mathbb{N}: a\times b \in \mathbb{N}
\begin{Bmatrix}\left ( z_{1}+\frac{kn}{ggd(m,n)} \right ), & \left ( z_{2}\text{ - }\frac{km}{ggd(m,n)} \right )\left.\right|k \in\mathbb{Z}\end{Bmatrix}