Priemfactor: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
k →Vinden van een ontbinding: linkfix |
|||
Regel 20:
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 [[cijfer]]s elk kost slechts milliseconden, maar de snelst bekende [[algoritme]]n (medio 2003) om getallen van 200 cijfers in factoren te ontbinden vergen vele jaren rekentijd. Hierop zijn enkele [[cryptografie|cryptografische]] technieken gebaseerd (onder andere de [[RSA (Cryptografie)|RSA]]-encryptie).
Men kan ook bewijzen dat elk getal kan ontbonden worden in priemfactoren. We geven hier 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). We kunnen het natuurlijk getal dus schrijven als m*n (met m en n beiden natuurlijk getallen). Via inductie vinden we nu dat we m en/of n weer kunnen schrijven als het product van 2 andere natuurlijke getallen (en als dat niet gaat is m en/of n een priemgetal). Dit zal je zo kunnen blijven doen tot er enkel priemgetallen overblijven.
En dus is elk natuurlijk getal te schrijven als een product van priemfactoren.
==Zie ook==
| |||