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]

Het bewijs van deze stelling gaat in twee delen:

Daarvoor is de volgende 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 deler 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]

Ieder geheel getal is door een priemgetal te delen en dus is ieder getal te schrijven als het product van alleen priemgetallen.

Het bewijs dat ieder geheel getal n door een priemgetal is te delen, gaat met volledige inductie naar n.

Inductiebegin
Het getal 2 is door een priemgetal te delen, namelijk door 2 zelf.
Inductieveronderstelling
Tot en met n zijn alle gehele getallen door een priemgetal te delen.
Inductiestap
  • Voor het geval n+1 zelf een priemgetal is, is de inductiestap gedaan.
  • Anders zijn er twee getallen a en b, met 2\leq a,b\leq n, zodat n+1 = a·b. Volgens de inductieveronderstelling is a door een priemgetal te delen, en dus is ook n+1 door een priemgetal te delen. Daarmee is ook voor dit geval de inductiestap gedaan.

Uniciteit[bewerken]

Stel dat een getal op twee manieren te schrijven is als het product van priemgetallen. Deel in beide producten de gemeenschappelijke priemgetallen uit. Wat overblijft kan geen priemgetal meer bevatten, want dat priemgetal zou deler zijn van een product van priemgetallen ongelijk aan zichzelf. Er blijft dus slechts het getal 1 over. De voorstelling als product van priemgetallen is dus op de volgorde na uniek.

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