Priemfactor

Een priemfactor van een natuurlijk getal ${\displaystyle n}$ is een priemgetal dat een deler is van ${\displaystyle n}$, dus waardoor ${\displaystyle n}$ kan worden gedeeld zonder een rest over te houden.

Een ontbinding in priemfactoren (ook wel: ontbinding in factoren of gewoon ontbinding) van een natuurlijk getal ${\displaystyle n}$ is een multiset (hier geschreven als {(...)}) van priemgetallen waarvan het product weer ${\displaystyle n}$ is. Zo is {(2,5)} een ontbinding van 10, want 2 en 5 zijn priemgetallen en 2×5=10, en is {(3,3,11)} een ontbinding van 99, want 3 en 11 zijn priemgetallen en 3×3×11=99.

Ieder element van een ontbinding van ${\displaystyle n}$ is een priemfactor van ${\displaystyle n}$, want het is een deler van ${\displaystyle n}$ en het is een priemgetal.

Een ontbinding in factoren is niet een gewone verzameling maar een multiset, omdat een priemfactor vaak meerdere malen moet worden gebruikt. Bijvoorbeeld: {(2,3,3)} is een ontbinding van het getal 18, want 2×3×3=18; het getal 3 komt tweemaal voor.

De hoofdstelling van de rekenkunde zegt dat elk natuurlijk getal groter dan 1 precies één ontbinding in priemfactoren heeft.

Uitgesplitst naar een aantal gevallen:

• 0 en 1 hebben geen ontbinding, want 0 en 1 kunnen niet worden geschreven als een product van priemgetallen.
• De ontbinding van een priemgetal ${\displaystyle p}$ is de multiset ${\displaystyle \{(p)\}}$.
• Elk ander natuurlijk getal ${\displaystyle n}$ heeft ten minste één priemfactor die kleiner is dan of gelijk is aan de vierkantswortel uit ${\displaystyle n}$.

In tegenstelling tot het uitvoeren van een vermenigvuldiging is het ontbinden in factoren een operatie die potentieel erg veel rekentijd kan vergen. Vermenigvuldigen van twee priemgetallen van 100 cijfers elk kost slechts milliseconden, maar de snelst bekende algoritmen (medio 2003) om getallen van 200 cijfers in factoren te ontbinden vergen vele jaren rekentijd. Hierop zijn enkele cryptografische technieken gebaseerd (onder andere de RSA-encryptie).

Zie Hoofdstelling_van_de_rekenkunde#Bewijs voor het hoofdartikel over dit onderwerp.

Men kan bewijzen dat elk getal kan ontbonden worden in priemfactoren. Hier volgt enkel het bewijs van het bestaan van deze ontbinding, en niet van de uniciteit. De ontbinding van een priemgetal zelf is evident gewoon gelijk aan dat priemgetal. Stel nu dat een natuurlijk getal geen priemgetal is. Dit natuurlijk getal is dus deelbaar door een ander natuurlijk getal (dat niet gelijk is aan zichzelf). Het natuurlijk getal is dus te schrijven als ${\displaystyle m\times n}$ (met ${\displaystyle m}$ en ${\displaystyle n}$ beide natuurlijke getallen). Via inductie volgt nu dat ${\displaystyle m}$ en/of ${\displaystyle n}$ weer te schrijven zijn als het product van twee andere natuurlijke getallen (en als dat niet gaat is ${\displaystyle m}$ en/of ${\displaystyle n}$ een priemgetal). Dit kan herhaald worden tot er enkel priemgetallen overblijven. En dus is elk natuurlijk getal te schrijven als een product van priemfactoren.

• Tabel van priemfactoren