Hoofdstelling van de rekenkunde

In de wiskunde, en in het bijzonder in de getaltheorie, zegt de hoofdstelling van de rekenkunde dat elk natuurlijk getal groter dan ${\displaystyle 1}$ kan worden geschreven als het product van priemgetallen en dat dit op precies één manier mogelijk is, afgezien van de volgorde van die priemgetallen. Als het getal zelf een priemgetal is, bestaat het product uit dat enkele priemgetal. Zo is bijvoorbeeld:

${\displaystyle 6936=2^{3}\cdot 3\cdot 17^{2}}$

en

${\displaystyle 1200=2^{4}\cdot 3\cdot 5^{2}}$

Er bestaan geen andere manieren om ${\displaystyle 6936}$ en ${\displaystyle 1200}$ in priemfactoren te ontbinden.

Merk op dat als ${\displaystyle 1}$ als priemgetal beschouwd zou worden, de ontbinding in priemfactoren slechts op factoren 1 na uniek zou zijn. Voor het getal ${\displaystyle 1200}$ bijvoorbeeld zouden er dan oneindig veel alternatieven bestaan, namelijk:

${\displaystyle 1200=1^{n}\cdot 2^{4}\cdot 3\cdot 5^{2}}$

waarbij ${\displaystyle n}$ elk natuurlijk getal kan zijn.

Bewijs

Het bewijs van deze stelling gaat in twee delen:

• existentie, de ontbinding bestaat steeds;
• uniciteit of eenduidigheid, deze ontbinding is uniek.

Existentie

Het bewijs dat ieder geheel getal ${\displaystyle n}$ is te schrijven als het product van alleen priemgetallen, gaat met behulp van volledige inductie.

Inductiebegin

Het getal 2 is te schrijven als een product van alleen priemgetallen, namelijk 2 (een product met één factor).

Inductiehypothese

Alle ${\displaystyle m}$ met ${\displaystyle m<n}$ zijn te schrijven als een product van alleen priemgetallen.

Inductiestap

Er zijn twee gevallen:

• Als ${\displaystyle n}$ een priemgetal is, zijn we al klaar.
• Anders zijn er ${\displaystyle p,q}$ met ${\displaystyle 2\leq p,q<n}$ zodat ${\displaystyle p\cdot q=n}$. Volgens de inductiehypothese zijn er producten van priemgetallen zodat ${\displaystyle p_{1}\cdot \ldots \cdot p_{k}=p}$ en ${\displaystyle q_{1}\cdot \ldots \cdot q_{l}=q}$. We kunnen nu ${\displaystyle n}$ schrijven als

${\displaystyle p_{1}\cdot \ldots \cdot p_{k}\cdot q_{1}\cdot \ldots \cdot q_{l}=n}$.

Uniciteit

Stel dat een getal op twee manieren te schrijven is als het product van een serie priemgetallen. Deel in beide producten de gemeenschappelijke priemgetallen uit. Wat overblijft in de eerste serie kan geen priemgetal meer bevatten, want de priemgetallen die overblijven uit de tweede serie zouden volgens het lemma van Euclides door de overblijvende priemgetallen in de eerste serie zijn te delen. Er blijft dus slechts het getal 1 over.

Tegenvoorbeeld

Door David Hilbert werd aangetoond dat het bewijs van de eenduidigheid van de ontbinding in priemfactoren noodzakelijk gebruikmaakt van de additieve structuur van de natuurlijke getallen. Ter illustratie dient het volgende, van Hilbert afkomstige, voorbeeld van een verzameling waarbinnen de hoofdstelling van de rekenkunde niet geldt.

Beschouw de volgende deelverzameling van ${\displaystyle \mathbb {N} }$:

${\displaystyle H:=\{3j+1:j\in \mathbb {N} \}}$

Deze verzameling heeft dezelfde multiplicatieve structuur als ${\displaystyle \mathbb {N} }$. Een 'priemgetal' in H is, net als in ${\displaystyle \mathbb {N} }$, een getal dat niet te schrijven is als een product van 2 getallen uit H, beide groter dan 1. Als er voor de verzameling van de natuurlijke getallen een eenduidigheidsbewijs, van de ontbinding in priemfactoren, zou bestaan dat alleen gebruikmaakt van de vermenigvuldiging, zou dat ook een geldig eenduidigheidsbewijs zijn in de verzameling H. Het blijkt echter dat in H de ontbinding niet eenduidig is, omdat bijvoorbeeld ${\displaystyle 100=25\cdot 4=10\cdot 10}$. Merk op dat 4, 10 en 25 binnen H alle drie een priemgetal zijn, omdat ze binnen H niet verder kunnen worden ontbonden.