Hoofdstelling van de rekenkunde

De hoofdstelling van de rekenkunde zegt ons dat je elk natuurlijk getal groter dan 1 op één manier kunt ontbinden in een product van priemgetallen. Het getal 15 kun je bijvoorbeeld ontbinden in het product van twee priemgetallen 3 · 5, het getal 30 in het product van drie priemgetallen 2 · 3 · 5 en het getal 16 bijvoorbeeld in het product van vier priemgetallen 2 · 2 · 2 · 2. Zo'n product van getallen noemen we een priemfactorontbinding. We zeggen dus dat de priemfactorontbinding van het getal 10 gelijk is aan 2 · 5.

De priemgetallen zelf hebben de eenvoudigste priemfactorontbinding, want die hoeven we niet verder te ontbinden. De priemfactorontbinding van het getal 7 is gewoon 7.

Bereken de priemfactorontbinding

Wat de hoofdstelling van de rekenkunde ons zegt

De hoofdstelling van de rekenkunde, ook wel de fundamentele stelling van de rekenkunde genoemd, zegt ons dus twee dingen:

• voor elk natuurlijk getal groter dan 1 kunnen we een priemfactorontbinding vinden,
• elk getal heeft precies één unieke priemfactorontbinding.

Laten we bewijzen dat dit echt zo is.

Bewijs van het bestaan

Eerst bewijzen we dat er voor elk natuurlijk getal groter dan 1 echt minstens één priemfactorontbinding bestaat. Daarvoor gebruiken we volledige inductie. De eerste stap van de volledige inductie is dat we vaststellen dat het kleinste natuurlijke getal dat groter is dan 1, dus het getal 2, een priemgetal is.

Nu laten we zien dat als we een rij getallen 2, …, n hebben waarvoor we een priemfactorontbinding kunnen vinden, ook voor het nieuwe getal n + 1 een priemfactorontbinding bestaat als we dat getal aan deze rij toevoegen. Eerst laten we dat aan een voorbeeld zien.

In het begin is onze rij 2, …, n een beetje vervormd, want die bevat maar één getal, het getal 2. Wij zeggen dat als we aan deze rij het getal n + 1 toevoegen, dus het getal 3, er voor dit getal een priemfactorontbinding zal bestaan. Omdat het getal 3 een priemgetal is, bestaat er daarvoor natuurlijk een priemfactorontbinding: het is het getal 3.

Onze rij 2, …, n heeft nu twee termen: 2, 3. We voegen het getal 4 aan de rij toe. Het getal 4 is geen priemgetal, dus het moet te ontbinden zijn in een product van twee andere natuurlijke getallen die groter zijn dan 1 maar kleiner dan 4. Al zulke getallen maken echter deel uit van onze rij! En in deze rij staan alleen getallen die een priemfactorontbinding hebben! Dus ook het getal 4 moet een priemfactorontbinding hebben: 2 · 2.

Als we teruggaan naar het algemene bewijs, kunnen we opschrijven dat het getal 2 een priemgetal is en dus een priemfactorontbinding heeft. Neem nu aan dat elk getal uit de rij 2, …, n in priemfactoren te ontbinden is: dat is onze inductiehypothese. Dan geldt dat het getal n + 1 ofwel een priemgetal is en dus triviaal in priemfactoren te ontbinden, ofwel een samengesteld getal. Voor dit getal moeten er dus getallen a, b bestaan zodat

$$n+1=a\cdot b$$

waarbij deze natuurlijke getallen natuurlijk kleiner moeten zijn dan n + 1 en groter dan 1:

$$\begin{array}{rcl}a>1,& & a<n+1\\ b>1,& & b<n+1\end{array}$$

De getallen a, b moeten dus deel uitmaken van de rij 2, …, n. Maar voor elk getal uit deze rij bestaat een priemfactorontbinding (dat is onze inductiehypothese), dus we kunnen schrijven

$$\begin{array}{rcl}a& =& p_1\cdot p_2\cdot \dots \cdot p_i\\ b& =& q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

Waarbij alle p_i en q_j priemgetallen zijn en p₁ · p₂ · … · p_i en q₁ · q₂ · … · q_j dus hun priemfactorontbindingen zijn. Omdat we hebben gezegd dat n + 1 te ontbinden is in het product n + 1 = a · b, geldt tegelijk

$$\begin{array}{rcl}n+1& =& a\cdot b\\ & =& p_1\cdot p_2\cdot \dots \cdot p_i\cdot q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

Het getal n + 1 is dus te ontbinden in het product van priemgetallen p₁ · p₂ · … · p_i · q₁ · q₂ · … · q_j, dus ook het nieuw toegevoegde getal n + 1 heeft een priemfactorontbinding. Hieruit volgt dat elk natuurlijk getal groter dan 1 minstens één priemfactorontbinding heeft.

Bewijs van de uniciteit

We laten nu zien dat er voor elk natuurlijk getal groter dan 1 niet meer dan één priemfactorontbinding bestaat. Deze stelling bewijzen we met een bewijs uit het ongerijmde. We nemen aan dat de stelling niet waar is en dus dat er een natuurlijk getal n groter dan 1 bestaat dat twee verschillende priemfactorontbindingen heeft:

$$\begin{array}{rcl}n& =& p_1\cdot p_2\cdot \dots \cdot p_i\\ n& =& q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

Neem tegelijk aan dat n van alle getallen met meer priemfactorontbindingen het kleinste is. Dat wil zeggen dat er geen kleiner natuurlijk getal bestaat dat meer dan één priemfactorontbinding heeft. Omdat q₁ een van de priemgetallen is die het getal n delen, moet natuurlijk ook gelden dat q₁ het getal p₁ · p₂ · … · p_i deelt.

Verder moeten we het lemma van Euclides gebruiken. Dat zegt dat als een priemgetal p het product van twee gehele getallen a · b deelt, p ook minstens een van de getallen a of b deelt. Een voorbeeld: het priemgetal 3 deelt het getal 84. Het getal 84 kunnen we ontbinden in het product 12 · 7. Het lemma van Euclides zegt dat het priemgetal 3 minstens een van de getallen 12 of 7 deelt, in dit geval deelt het het getal 12.

Met dit lemma kunnen we zeggen dat als q₁ het getal p₁ · p₂ · … · p_i deelt, het ook minstens een van de getallen p₁, p₂, …, p_i moet delen. We mogen aannemen, zonder beperking van de algemeenheid, dat q₁ het getal p₁ deelt. Maar p₁ is ook een priemgetal. Wanneer kan een priemgetal een ander priemgetal delen? Welk priemgetal is bijvoorbeeld deelbaar door het priemgetal 7? Opnieuw alleen het priemgetal 7. Het kan geen ander priemgetal delen, want dan zou het geen priemgetal zijn. Er moet dus gelden p₁ = q₁.

Dat betekent dat er in beide priemfactorontbindingen één priemgetal is dat gelijk is: het priemgetal p₁, respectievelijk q₁. Laten we beide priemfactorvergelijkingen delen door p₁, respectievelijk q₁:

$$\begin{array}{rcl}\frac{n}{p_1}& =& \frac{p_1\cdot p_2\cdot \dots \cdot p_i}{p_1}\\ \frac{n}{q_1}& =& \frac{q_1\cdot q_2\cdot \dots \cdot q_j}{q_1}\end{array}$$

Omdat p₁ = q₁, krijgen we aan de linkerkant hetzelfde getal, dat we bijvoorbeeld m noemen. Er geldt dus dat

$$m=\frac{n}{p_1}=\frac{n}{q_1}$$

Aan de rechterkant vereenvoudigen we alleen de breuken:

$$\begin{array}{rcl}m& =& p_2\cdot p_3\cdot \dots \cdot p_i\\ m& =& q_2\cdot q_3\cdot \dots \cdot q_j\end{array}$$

Het getal m is zeker een natuurlijk getal dat kleiner is dan het getal n, omdat m is ontstaan doordat we n hebben gedeeld door een van zijn priemfactoren. Aan de rechterkant van de vergelijkingen hebben we echter in beide gevallen een priemfactorontbinding van het getal m. We hebben dus een ander getal m geconstrueerd dat kleiner is dan het getal n en dat ook twee verschillende priemfactorontbindingen heeft. Dat is in strijd met onze aanname dat n het kleinste getal is dat meer dan één unieke priemfactorontbinding heeft.

De enige verklaring is dus dat er geen “kleinste getal met meer dan één priemfactorontbinding” bestaat. En dat er geen “kleinste getal met meer dan één priemfactorontbinding” bestaat, betekent dat er geen enkel getal met meerdere priemfactorontbindingen bestaat: elk geheel getal groter dan één heeft dus precies één unieke priemfactorontbinding.