priemfactoren


Ontbinden in priemfactoren..	© h.hofstede (h.hofstede@hogeland.nl)

Wat is een deler?

Nou ja, het woord zegt het eigenlijk al: een deler van een getal, daar kun je dat getal door delen!
En met delen bedoelen we in dit geval dat het antwoord een geheel getal wordt!
Dus als iemand op straat je zou vragen "Wat zijn de delers van 24?" Wat is dan daarop jouw antwoord?

1, 2, 3, 4, 6, 8, 12, 24

(Deze les hebben we het trouwens alleen maar over positieve getallen, dat merk je al wel aan dit antwoord)

Wat is een priemgetal?

Dat is, nou je eenmaal weet wat een deler is, makkelijk uit te leggen:

Een priemgetal is een getal met precies twee delers

(een getal dat geen priemgetal is, wordt een samengesteld getal genoemd).
Maar wacht eens even: het getal 1 is een deler van elk getal, dus dat is alvast één van de twee delers.

En verder is ook elk getal een deler van zichzelf! Dus dat is al een twééde deler van een getal.

Dat betekent dat zo'n priemgetal verder geen delers mag hebben. Het is dus alleen deelbaar door 1 en zichzelf. Daarom zie je ook vaak de volgende definitie van een priemgetal:

Een priemgetal is alleen deelbaar door 1 en door zichzelf

Deze definitie is niet helemaal goed.........
Dat komt omdat het getal 1 zélf geen priemgetal is. Het is wél alleen deelbaar door 1 en door zichzelf, maar het heeft niet precies 2 delers (het heeft namelijk precies één deler).
Hier zie je alle priemgetallen onder de 100 (het zijn er 25):

2	3	5	7	11
13	17	19	23	29
31	37	41	43	47
53	59	61	67	71
73	79	83	89	97

Wat is er nou zo interessant aan die priemgetallen?

Dat zie je vanzelf als je bekijkt hoe getallen kunnen worden opgebouwd uit andere getallen.

Optellen is niet zo heel interessant, want alle getallen die we kennen kunnen door optellen worden verkregen uit het getal 1.
Zo is 5 gelijk aan 1 + 1 + 1 + 1 + 1 en 12 is gelijk aan 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 en ga zo maar door...

Maar vermenigvuldigen is wél interessant.....
Het getal 12 kun je met vermenigvuldigen op twee verschillende manieren uit andere getallen opbouwen:

12 = 2 • 6
12 = 3 • 4

We letten even niet op de volgorde, want 6 • 2 en 4 • 3 kan natuurlijk ook. maar dat zijn eigenlijk natuurlijk dezelfde vermenigvuldigingen. (Verder hebben we de mogelijkheid 12 • 1 ook maar weggelaten want die is nogal saai....)
Maar die 6 kun je ook weer opbouwen uit kleinere getallen, namelijk 2 • 3. En die 4 kun je opbouwen uit 2 • 2
Als je 12 uit zo klein mogelijke getallen wilt opbouwen geeft dat dus:

12 = 2 • 6 = 2 • 2 • 3
12 = 3 • 4 = 3 • 2 • 2

Maar die twee mogelijkheden zijn hetzelfde!
Dus eigenlijk is er maar één manier om het getal 12 op te bouwen uit zo klein mogelijke andere getallen, en dat is

12 = 2 • 2 • 3

Die drie getallen aan de rechterkant van de vergelijking zijn alle drie priemgetallen. Ik hoop dat je dat logisch vindt... Al er een NIET-priemgetal zou staan, dan zou je dat immers nog verder in kleinere getallen kunnen opdelen! Omdat je op deze manier 12 schrijft als product van allemaal priemgetallen heet dit "ontbinden in priemfactoren". Omdat je op deze manier elk getal kunt opdelen in priemfactoren zijn die priemgetallen dus eigenlijk de bouwstenen (wat betreft vermenigvuldigen) van alle getallen die we kennen. Elk bestaand getal kan op deze manier opgebouwd worden uit priemgetallen.

priemgetallen zijn de bouwstenen van alle andere getallen!

't Is eigenlijk net als in de scheikunde. Daar is elke stof een molecuul (wat in de wiskunde een getal is). Maar elk molecuul is opgebouwd uit atomen (dat zijn de wiskundige priemgetallen). Net zoals je scheikundig "Water" kunt schrijven als H₂O zou je wiskundig het getal 45 kunnen schrijven als 3₂5.
En zwavelzuur (H₂SO₄) lijkt dan misschien wel wat op het getal 39375 (= 3₂75₄).
Oké ik geef het toe; het is niet helemaal precies hetzelfde, want er zijn maar een beperkt aantal atomen, en er zijn oneindig veel priemgetallen.

Daarom is wiskunde ook zoveel interessanter dan scheikunde natuurlijk...maar dat wist je natuurlijk al wel.

Direct al een interessante toepassing.

Er is een stelling die zegt dat √2 niet als breuk is te schrijven. Dus er zijn geen enkele p en q, hoe groot ook, te vinden zodat ^p/_q = √2.
Het bewijs van deze stelling is heel eenvoudig met priemgetallen te zien.
Stel dat ^p/_q = √2, dan is dus p = q • √2.
Neem dat in het kwadraat: p² = q² • 2

Kijk nu naar het aantal tweeën in de priemfactorontbinding
• p² heeft een even aantal factoren 2 (namelijk het dubbele aantal van p)
• q² heeft een even aantal factoren 2 (namelijk het dubbele aantal van q)
Dan staat er aan de linkerkant van de blauwe vergelijking een even aantal tweeën en aan de rechterkant een oneven aantal! (die ene 2 extra).

Dat kan dus nooit gelijk zijn!!

Tijd voor een paar interessante stellingen.
Eerst maar direct één van de allerberoemdste stellingen, vooral omdat het bewijs ervan zo prachtig simpel is:

Er bestaan oneindig veel priemgetallen.

Het bewijs komt van Euclides.

Bewijs.

Stel dat je een eindig aantal priemgetallen p₁, p₂, ..., p_n hebt.
Bereken dan het nieuwe getal P = p₁ • p₂ • ... • p_n + 1
Door die "+1" is P is niet deelbaar door één van de bekende priemgetallen. Er zijn dus twee mogelijkheden:
óf P is zelf een priemgetal.
óf P heeft een priemfactor die nog niet in onze verzameling zat.
In beide gevallen hebben we een nieuw priemgetal gevonden.
Dus er zijn oneindig veel priemgetallen.

q.e.d.

Laten we nu gaan naar de belangrijkste stelling over priemgetallen. Zo belangrijk dat hij ook wel de "Hoofdstelling van de rekenkunde" wordt genoemd.

Elk natuurlijk getal groter dan 1 is op precies één manier te schrijven
als het product van een aantal priemgetallen.

Om deze stelling te bewijzen, bewijzen we eerst het Lemma van Euclides, dat zegt:

Lemma van Euclides:
Als ab deelbaar is door priemgetal p, dan is p een deler van a of van b (of van beide).

Bewijs:

Stel dat a niet door p te delen is, dan is de GGD(a, p) = 1
Maar dan zegt de stelling van Bézout dat er getallen x en y zijn zodat xp + ya = 1
Vermenigvuldig met b: xbp + yba = b
ba is door p te delen (gegeven), en xbp is ook door p te delen, dus de hele linkerkant is door p te delen.
Dus is de rechter kant óók door p te delen: p is een deler van b.

q.e.d.

Het lemma kun je natuurlijk makkelijk uitbreiden tot meer getallen:

Als abc deelbaar is door p, dan is (ab)•c deelbaar door p dus is p een deler van (ab) of van c.
In het eerste geval is p een deler van a of van b (weer het Lemma)
Dus samen geldt nu dat p een deler is van a of van b of van c.

Als abcd deelbaar is door p dan is (abc)•d deelbaar door p, dus is.....
enzovoort.

Met dit lemma op zak gaan we terug naar het bewijs van de Hoofdstelling.
Eigenlijk moet je twee dingen bewijzen: ten eerste dát er altijd een priemfactorontbinding is, en ten tweede dat die priemfactorontbinding uniek is voor elk getal.

Bewijs.

1. Er is altijd een priemfactorontbinding.
Het bewijs gaat met volledige inductie:
Voor n = 2 is er een priemfactorontbinding (duh)
Stel dat elk getal p waarvoor 2 < p < n een priemfactorontbinding heeft (inductie-aanname).
Bekijk nu het getal n.
Als n een priemgetal is, dan heeft het een priemfactorontbinding (namelijk gewoon zichzelf).
Als n geen priemgetal is, dan heeft het dus meer dan 2 delers. Noem één van die delers d, dan is n = k • d
Maar omdat k en d kleiner zijn dan n hebben zij beiden een priemfactorontbinding (inductie-aanname).
Zet die priemfactorontbindingen achter elkaar en je hebt een priemfactorontbinding voor n.
Daarmee is het eerste bewijs geleverd.

2. De priemfactorontbinding is uniek
Stel n een getal is dat géén unieke priemfactorontbinding heeft,
dus n = p₁ • p₂ • ... = q₁ • q₂ • ....
Haal nu eerst de priemgetallen die aan beide kanten voorkomen weg door daar door te delen. Dan blijft over:
p_a • p_b • ... = q_j • q_k • ... (nu is dus geen enkele p gelijk aan een q).
Maar stel dat daar links nog wat p's zijn overgebleven, dan is dus p_a • p_b • ... deelbaar door q_i
Dan zegt het Lemma dat q_i een deler is van één van die p's.
Maar dat kan niet want die p's zijn priemgetallen! En ze waren allemaal ongelijk aan de q's !!

Om precies dezelfde reden kan daar rechts ook geen q meer staan natuurlijk.

q.e.d.

Grappig voorbeeld van Hilbert.

De wiskundige David Hilbert liet met een leuk voorbeeld zien dat dat eenduidig zijn van die priemfactorontbinding gebruik maakt van de optelstructuur van de getallen. Dat deed hij met het volgende tegenvoorbeeld.
Hij beschouwde de verzameling van alle getallen die te schrijven zijn als n = 3k + 1. (met k een natuurlijk getal)
Dat is dus de verzameling {1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, ...}
Ook binnen deze verzameling kun je gewoon vermenigvuldigen. Dus deze verzameling heeft ook priemgetallen.
Maar nu is de priemfactorontbinding niet uniek, want bijvoorbeeld geldt 100 = 4 • 25 = 10 • 10.

OPGAVEN

Ontbind de volgende getallen in priemfactoren:

2352

2⁴• 3 • 7²

2310

2 • 3 • 5 • 7 • 11

2200

2³• 5² • 11

7424

2⁸• 29

100793

7²• 11² • 17

9075

3 • 5² • 11²

7533

3⁵ • 31

8125

5⁴• 13

Op hoeveel manieren kun je het getal 210 schrijven als een vermenigvuldiging van drie andere getallen
(allemaal groter dan 1)?

6 manieren

Noem twee getallen waar geen cijfer NUL in voorkomt die met elkaar vermenigvuldigd het getal 10000 opleveren.

625 en 8