Hoofdstelling van de rekenkunde

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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 manieren om 6936 of 1200 in priemfactoren te ontbinden, afgezien van de volgorde van de factoren.

Merk op dat als 1 een priemgetal zou zijn, de ontbinding in priemfactoren niet uniek zou zijn geweest. Bijvoorbeeld is 1200 = 13 · 24 · 3 · 52.

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

Bewijs[bewerken]

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

Hiervoor hebben we echter een hulpstelling nodig:

Hulpstelling[bewerken]

Als van twee gehele getallen a en b het product ab deelbaar is door het priemgetal p, is p deler van a of van b. Formeel:

\forall\,a,b \in \mathbb{Z}: p\ \text{priem} \and p|ab \implies  p|a\or p|b.
Bewijs van de hulpstelling

Zij d=\operatorname{ggd}(a,p) de grootste gemene deler van a en p. Daar p een priemgetal is en d een deler is van p, geldt:

d=1\or d=p.

Veronderstel nu dat p geen deler is van a, dus:

\operatorname{ggd}(a,p)=1.

Volgens de stelling van Bachet-Bézout zijn er dan gehele getallen x en y zodanig dat:

xp+ya=1.

Vermenigvuldigen van beide zijden met b levert

xpb+yab=b.

Omdat p deler is van ab, deelt p ook yab. Dus is p deler van beide termen aan de linkerkant van de vergelijking, en daarmee deler van b.

Existentie[bewerken]

We bewijzen het bestaan van zo'n ontbinding door volledige inductie naar 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[bewerken]

We bewijzen nu de uniciteit. Zij

n=p_1 p_2...p_k en n=q_1 q_2...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_1|n=q_1 q_2...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_1|q_1.

Daar p_1 en q_1 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_2=q_2,\ldots,p_n=q_n (na hernummering)

Deze hoofdstelling is geen vanzelfsprekendheid[bewerken]

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 \mathbb{N}:

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

Deze verzameling 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. 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 100 = 25·4 = 10·10. Merk op dat 4, 10 en 25 binnen H alle drie irreducibel zijn, omdat ze binnen H niet verder kunnen worden ontbonden.

Zie ook[bewerken]