priemfactorontbinding

© h.hofstede (h.hofstede@hogeland.nl)

De priemfactorontbinding is eenduidig.

Stel dat er wél getallen zijn die twee verschillende priemfactorontbindingen hebben.
Noem dan het kleinste van al die getallen N.
Dan geldt dus N = p₁p₂p₃p₄p₅... = q₁q₂q₃q₄q₅...

Daarbij zijn de p's en q´s priemgetallen. Een priemgetal uit het p-rijtje komt niet voor in het q-rijtje, want als dat wel zo zou zijn zouden we beide kanten door dat priemgetal kunnen delen en hadden we een ander getal gevonden dat kleiner is dan N en ook verschillende priemfactorontbindingen heeft.

Herrangschik nu alle priemgetallen zodat p₁ het kleinste priemgetal is (in ieder geval dus kleiner dan alle q's, en eventueel nog gelijk aan enkele andere p's)
Omdat dus p₁ < q₁ kunnen we q₁ door p₁ delen. Stel dat dat d keer gaat en rest r geeft, dan geldt dus:

r is de rest bij het delen.
Maar dan geldt (beide kanten van N door p₁ delen)::

De laatste term aan de rechterkant is een geheel getal k
Daarvoor geldt p₁k = r q₂q₃q₄q₅...
De rechterkant is kleiner dan N omdat r kleiner is dan q₁
Dus is de linkerkant ook kleiner dan N
Dus het getal p₁k is een getal dat kleiner is dan N maar dat toch op twee verschillende manieren ontbonden kan worden.
Dat is in strijd met het feit dat N het kleinste getal was waarvoor dat gold!
Dus bestaat er niet zo'n kleinste getal, dus bestaat er helemaal niet zo'n getal.

q.e.d.

't Is wel een gedoe met al die pkrqd 's.
Met getallen zou het er zó uitzien:

Stel dat 3 • 7 • 13 • 13 • 97 = 5 • 5 • 11 • 29 • 43 ('t scheelt niet eens veel!)
Delen door de kleinste (door 3 dus):   7 • 13 • 13 • 97 = ⁵/₃ • 5 • 11 • 29 • 43
Maar uitdelen geeft   ⁵/₃ = 1 + ²/₃
Dus 7 • 13 • 13 • 97 = ⁽1^{+ 2}/₃⁾ • 5 • 11 • 29 • 43 = 1 • 5 • 11 • 29 • 43 + ²/₃ • 5 • 11 • 29 • 43
Dus is ²/₃ • 5 • 11 • 29 • 43 een geheel getal k
Vermenigvuldig weer met 3:   2 • 5 • 11 • 29 • 43 = 3 • k
Hier staat een getal op twee verschillende manieren ontbonden dat kleiner is dan het oorspronkelijke omdat 2 kleiner is dan 5. De manieren zijn zeker verschillend omdat de factor 3 links niet voorkomt. (zelfs als de 2 geen priemgetal zou zijn maar nog verder te ontbinden kan er nooit een factor 3 komen want 2 < 3)