Hoofdstelling van de rekenkunde

Inhoud

Inleiding

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?
Welnu, in simpele bewoordingen: “Ieder getal kan op unieke manier ontbonden worden in priemfactoren”.

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:

• Wat is eigenlijk ontbinden?
• Wat is een priemgetal?
• Wat is rekenkunde?

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.

Ontbinden van een getal

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.

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

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.

Commutatief en associatief

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.

Open en gesloten verzamelingen

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.
Het is dus alleen interessant om naar oneindige verzamelingen te kijken.

De verzameling der natuurlijke getallen ℕ, is gesloten voor optellen en vermenigvuldigen.
Dit betekent dat wanneer ik twee natuurlijke getallen bij elkaar optel of vermenigvuldig de uitkomst (som of product) ook weer in ℕ zit.

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 ℕ.
Hetzelfde geldt voor delen; zo zit 1/2 ook niet 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: ℕ ⊂ ℤ ⊂ ℚ.

Hoogste en laagste getal

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.

Hoofdstelling

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

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.

Het algoritme van Euclides

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 delers van 32 zijn: 1, 2, 4, 8, 16 en 32.

De grootste is dus 4.
Dat betekent dat ggd(12, 32) = 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
44 = 1 x 28 + 16
28 = 1 x 16 + 12
16 = 1 x 12 + 4
12 = 3 x 4 + 0

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.
b) Anders: m = qn + r (gegeven) → r = m – qn
Omdat d|m èn d|n geldt nu: m = z₁d en n = z₂d (z₁, z₂ ∈ ℤ).
Nu geldt: r = m – qn = z₁d – qz₂d = d(z₁ – qz₂). Daar z₁, z₂, q ∈ ℤ en ℤ gesloten is voor aftrekken en vermenigvuldigen geldt: z₁ – qz₂ ∈ ℤ, zeg k.
Dus r = kd, dus d|r; klaar.

2) De weg van rechts naar links

a) Als d|n (rechter kant) dan is d|n (linker kant; klaar)
b) m = qn + r (gegeven), n = z₂d, r = z₃d (rechter kant)
dan m = qz₂d + z₃d = d(qz₂ + z₃). Daar z₂, z₃, q ∈ ℤ en ℤ gesloten is voor optellen en vermenigvuldigen is qz₂ + z₃ ∈ ℤ, zeg k.
Dus m=dk, dus d|m; klaar.

En met 1a), 1b), 2a) en 2b) hebben we ons bewijs helemaal rond.

Ggd met negatieve getallen

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.
Met het algoritme kunnen we er voor zorgen dat de resten altijd positief zijn.

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)
-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

De stelling van Bezout luidt als volgt:

Als m, n ∈ ℤ en d = ggd(m, n) dan ∃ z₁, z₂ ∈ ℤ: z₁m + z₂n = 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
b) 20 = 1 x 16 + 4
c) 16 = 4 x 4 + 0

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.
Dus kan ik 4 schrijven als 4 = 20 – 16 = 20 – 36 – 20 = -(1x)36 + 2 x 20. (z₁ uit de stelling is dus -1 en z₂ is dus 2).

Overigens is de oplossing hierboven één van oneindig veel oplossingen.
Zo is 9 x 36 – 16 x 20 = 4 en -11 x 36 + 20 x 20 = 4.

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.
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.

1) m, n ∈ ℤ. Als |m| = |n| dan d = ggd(m, n) = |m| = |n|. Neem nu z₁ = 0 en z₂ = 1 (of -1 als n<0) en dan geldt: d = z₁m + z₂n; klaar.
2) m, n ∈ ℤ. Als |m|>|n|, dan m = q₁n + r₁.
a) Als r₁ = 0 dan m = q₁n -> d = |n|. Neem z₁ = 0 en z₂ = 1 (of -1 als n<0) en dan geldt: d = z₁m + z₂n; klaar.
b) Als r₁>0 dan
i) m = q₁n + r₁, met 0<r₁<|n|, dus ggd(m, n) = ggd(n, r₁)
ii) n = q₂r₁ + r₂, met 0<r₂<|r₁|, dus ggd(n, r₁) = ggd(r₁, r₂)
iii) r₁ = q₃r₂ + r₃, met 0<r₃<|r₂|, dus ggd(r₁, r₂) = ggd(r₂, r₃)
.
.
.
iv) r_i-2 = q_ir_i-1 + r_i ⇔ r_i-2 = q_ir_i-1 + d
We moeten d uitdrukken in m en n, dus gaan we substitueren…
ad i) m = q₁n + r₁ → r₁ = m – q₁n
ad ii) r₂ = n – q₂r₁ = n – q₂(m – q₁n) = n – q₂m + q₁q₂n = -q₂m + (1 + q₁q₂)n
ad ii) r₃ = r₁ – q₃r₂ = (m – q₁n) – q₃((1 + q₁q₂)n – q₂m) = … = (1 + q₂q₃)m + (-q₁ – q₃ – q₁q₂q₃)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 = r_i-2 = q_ir_i-1 → d = z₁m + z₂n.

Uit al het bovenstaande blijkt dat de Stelling van Bezout waar is.

Dat was een hele bevalling…

Het Lemma van Euclides

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.
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: ∃ z₁, z₂ ∈ ℤ: z₁p + z₂a = 1.
Als we beide zijden met b vermenigvuldigen krijgen we:
z₁pb + z₂ab = b ⇔ z₁pb + z₂mp = b ⇔ b = (z₁b + z₂m)p.
Omdat z₁, z₂, b, m ∈ ℤ en omdat ℤ gesloten is voor vermenigvuldigen en optellen is z₁b + z₂m ∈ ℤ, zeg k.
Dus b = kp en derhalve p|b.

Uit a) en b) volgt hetgeen we bewijzen moesten.

Hoofdstelling van de rekenkunde

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 = p₁ x p₂ x p₃ x … x p_n.

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.
In deel 2) bewijzen we dat deze priemontbinding uniek moet zijn.

1) Inductie:
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.

2) Ieder natuurlijk getal heeft een unieke priemontbinding.
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=p₁p₂p₃…p_n=q₁q₂q₃…q_m waarbij p_i<>q_i en n=m of n<>m.
p₁|x → p₁|q₁q₂q₃…q_m.
Volgens het Lemma van Euclides geldt: p₁|ab met a=q₁ en b=q₂q₃…q_m dan p₁|a=q₁ of p₁|b=q₂q₃…q_m, dus p₁=q₁ of p₁|q₂q₃…q_m, maar dan geldt (Lemma van Euclides) p₁|ab met a=q₂ en b=q₃q₄…q_m, dus p₁=q₂ of p₁|q₃q₄…q_m.
Dit principe kan herhaald worden tot q_m-1.q_m waaruit blijkt dat p₁=q_m-1 of q_m.
In ieder geval zit p₁ in q₁q₂q₃…q_m!
Maar nu kunnen we dus beide zijden p₁p₂p₃..p_n en q₁q₂q₃…q_m delen door p₁.
Dan houden we over p₂p₃p₄…p_n en q₁q₂q₃…q_m met ergens een q_i=p₁ minder.
Maar nu kunnen we met p₂ hetzelfde doen als in stap 2a).
Uiteindelijk zullen uit beide zijden alle p_i’s verdwijnen zodat we overhouden: 1=q_o1q_o2…q_om. Maar omdat alle q_oi’s priemgetallen zijn en alle priemgetallen ≥ 2 kan deze vergelijking helemaal niet bestaan!
Dus moet gelden dat in p₁p₂p₃..p_n=q₁q₂q₃…q_m n=m en we hebben tevens aangetoond dat alle p_i’s uitwisselbaar zijn met alle q_j’s en dus moet de priemontbinding uniek zijn!

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.
Ga zelf na dat deze verzameling gesloten is voor vermenigvuldigen.

Bewijs

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 ℤ.
Alle gehele getallen zitten erin; dan is b = 0.

Ook deze verzameling is gesloten voor vermenigvuldigen.

Bewijs

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.
En dit geldt voor √6, (√6 + 2), (√6 – 2), (3 + √6) en (3 – √6).

Tot slot

We hebben veel werk moeten verzetten om de Hoofdstelling van de Rekenkunde te kunnen bewijzen.
Maar eigenlijk hebben we te veel gedaan.

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.

Bronnen

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=ElliotNicholson