Hoofdstelling van de rekenkunde

In de wiskunde, en in het bijzonder in de getaltheorie, zegt de hoofdstelling van de rekenkunde dat elk positief geheel getal groter dan 1 kan worden geschreven als het product van priemgetallen, en dat dit op exact één manier mogelijk is (afgezien van de volgorde van de priemgetallen). Bijvoorbeeld kunnen we het volgende schrijven:

$6936 = 2^3 \times 3 \times 17^2 , \,\!$

$1200 = 2^4 \times 3 \times 5^2 . \,\!$

en er bestaan geen andere ontbindingen van 6936 of 1200 in priemfactoren, afgezien van verwisselingen in de volgorde van bovenstaande factoren.

Merk op dat als 1 een priemgetal zou zijn, de ontbinding in priemfactoren niet uniek zou zijn geweest. Bijvoorbeeld is 1200 = 1³ · 2⁴ · 3 · 5².

Bij het bewijs van deze stelling wordt onder meer gebruikgemaakt van het Euclidische algoritme.

Deze hoofdstelling is geen vanzelfsprekendheid

Het is opmerkelijk dat het bewijs van de eenduidigheid van de ontbinding in priemfactoren noodzakelijk gebruikmaakt van de additieve structuur van de natuurlijke getallen.

Dit blijkt onder meer uit het volgende, van David Hilbert afkomstige, voorbeeld.

Stel dat het bewijs de additieve structuur van $\mathbb{N}$ niet gebruikt en dus alleen de vermenigvuldiging. De verzameling

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

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

Bewijs

Om deze stelling te bewijzen dienen we twee dingen te bewijzen:

• Een dergelijke ontbinding bestaat steeds (existentie)
• Deze ontbinding is uniek (uniciteit)

Hiervoor hebben we echter een lemma nodig:

Lemma

Zij p een priemgetal. Voor elke $a,b \in \mathbb{Z}$ met $p|ab\,$ geldt:

$p|a\or p|b$.

Bewijs van het lemma

Zij

$d=ggd(a,p)\,$

de grootste gemene deler van a en p. Daar p een priemgetal is en d deelt p, geldt dat

$d=1\or d=p$.

Dus als

$p \not | a \,\Rightarrow ggd(a,p)=1\,$.

De stelling van Bachet-Bézout stelt nu dat

$\exists x,y \in \mathbb{Z}$ zodanig dat $xp+ya=1\,$.

Wanneer we nu beide zijden met b vermenigvuldigen krijgen we

$xpb+yab=b\,$.

p deelt ab dus p deelt ook yab. p deelt beide termen aan de linkerkant van de vergelijking, dus

$p|b\,$.

Existentie

We bewijzen het bestaan van zo'n ontbinding door inductie op n. Als n niet priem is dan is n te schrijven als

n = mk met 1 < m < n en 1 < k < n

Uit de inductiehypothese volgt dat er een ontbinding bestaat voor m en k, dus ook voor mk = n.

Uniciteit

We bewijzen nu de uniciteit. Zij

n = p₁p₂...p_k en n = q₁q₂...q_l

twee ontbindingen van n met p_i,q_i priemgetallen voor elke i. We moeten bewijzen dat

• k=l
• p_i = q_i voor elke i (eventueel na hernummering).

Dit bewijzen we door inductie op k. We hebben

p₁ | n = q₁q₂...q_l.

Dankzij herhaaldelijk toepassing van het voorgenoemde lemma weten we dan dat

$p_1|q_1 \or p_1|q_2 \or p_1|q_n$.

Na hernummering mogen we veronderstellen dat

p₁ | q₁.

Daar p₁ en q₁ priemgetallen zijn zijn ze aan elkaar gelijk. Door:

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

te stellen, krijgen we dan:

$m=p_2 p_3...p_k \quad , \quad m=q_2 q_3...q_l$

De inductiehypothese levert dan dat k-1=l-1 dus k=l en p₂ = q₂...p_n = q_n (na hernummering)

Zie ook

• Hoofdstelling van de algebra
• Hoofdstelling van de integraalrekening