Priemfactor

Een priemfactor van een natuurlijk getal n {\displaystyle n} groter dan 1 is een priemgetal dat een deler is van n {\displaystyle n} , dus waarvoor n {\displaystyle n} gedeeld door het priemgetal een geheel getal is. Het resultaat van het ontbinden in priemfactoren, of korter het ontbinden in factoren of alleen het ontbinden van een natuurlijk getal n {\displaystyle n} is een multiset, hier geschreven als {(...)}, van priemgetallen waarvan het product weer n {\displaystyle n} is. Zo geeft het ontbinden van 10 als antwoord {(2,5)}, want 2 en 5 zijn priemgetallen en 2×5=10 en van 99 geeft {(3, 3, 11)}, want 3 en 11 zijn priemgetallen en 3×3×11=99. De zo bij een getal n {\displaystyle n} gevonden multiset van getallen, wordt de ontbinding van n {\displaystyle n} genoemd. Ieder element van een ontbinding van n {\displaystyle n} is een priemfactor van n {\displaystyle n} , want n {\displaystyle n} kan er door worden gedeeld en het is een priemgetal. Een ontbinding in factoren is geen 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 ieder natuurlijke getal groter dan 1 op precies één manier in priemfactoren kan worden ontbonden. 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 p {\displaystyle p} is de multiset { ( p ) } {\displaystyle \{(p)\}} . Elk ander natuurlijk getal n {\displaystyle n} heeft ten minste één priemfactor die kleiner is dan of gelijk is aan de vierkantswortel uit n {\displaystyle n} . Het ontbinden van een getal in factoren is in tegenstelling tot het vermenigvuldigen van twee getallen een bewerking die veel rekentijd vraagt. De RSA-encryptie is hier op gebaseerd.