Priemfactorisatie berekenen

Een getal ontbinden in priemfactoren en controleren of het priem is

Elk geheel getal vanaf 2 is, afgezien van de volgorde van de factoren, op precies één manier te schrijven als product van priemgetallen: dat is de hoofdstelling van de rekenkunde. 360 = 2³ × 3² × 5, 1.001 = 7 × 11 × 13, en 97 valt helemaal niet te ontbinden: het is een priemgetal. Deze rekenhulp geeft de priemfactorisatie, zegt meteen of het getal priem of samengesteld is en toont het herhaald delen zoals je het in de klas opschrijft.

Priemfactorisatie is de sleutel tot veel berekeningen: breuken vereenvoudigen, de GGD of het KGV vinden, delers tellen, wortels vereenvoudigen. Ze helpt leerlingen in de brugklas en op havo en vwo, docenten die opgaven voorbereiden, deelnemers aan de Wiskunde Olympiade en iedereen die nieuwsgierig is naar cryptografie: de veiligheid van RSA berust erop dat zeer grote getallen moeilijk te ontbinden zijn.

1. Voer het getal in

   Typ een geheel getal bij „Geheel getal om te ontbinden” (vanaf 2, tot 18 cijfers). Spaties en duizendtalscheidingstekens worden genegeerd, dus 600.851.475.143 werkt zoals het is. De knoppen bij „Probeer:” laden kant-en-klare voorbeelden.

2. Lees de uitkomst

   Het label toont „Priemgetal” of „Geen priemgetal: samengesteld getal”, daarna verschijnt de ontbinding met exponenten (360 = 2³ × 3² × 5) en uitgeschreven. De knop „Kopiëren” zet 2^3 × 3^2 × 5 op het klembord.

3. Bekijk de eigenschappen

   De kaarten onder „Rekenkundige eigenschappen” tonen τ(n), σ(n), φ(n), het aantal verschillende priemfactoren ω(n) en priemfactoren met multipliciteit Ω(n), of n een kwadraat is, de som van de echte delers en het vorige en volgende priemgetal (tot 10¹²).

4. Controleer met de hand

   De tabel „Herhaald delen (deelladder)” herhaalt elke stap (360 ÷ 2 = 180…) tot quotiënt 1, en „Alle delers” zet de delers op volgorde, met de priemdelers gemarkeerd.

De methode: hoofdstelling en formules

Voor een geheel getal n ≥ 2 schrijf je de ontbinding als n = p1a1 × p2a2 × … × pkak. Je vindt haar door zo lang mogelijk te delen door de kleinste priemfactor; delers testen tot √n is genoeg, want een samengesteld getal heeft altijd een priemfactor die niet groter is dan zijn wortel.

Bij grote getallen combineert de tool drie stappen: proefdeling door de priemgetallen tot 10.000, een deterministische Miller-Rabin-test om priemgetallen te herkennen en het rho-algoritme van Pollard (variant van Brent) om samengestelde restfactoren te splitsen. Alles wordt met exacte gehele getallen berekend, zonder afronding.

• p₁ < p₂ < … < p_k: de verschillende priemfactoren in oplopende volgorde; hun aantal heet ω(n).
• a_i: de exponent (multipliciteit) van p_i; de som a₁ + … + a_k is Ω(n), het aantal priemfactoren met herhaling.
• τ(n) = (a₁ + 1)(a₂ + 1)…(a_k + 1): het aantal delers, omdat een deler voor elke p_i een exponent van 0 tot a_i kiest.
• σ(n) = ∏ (p_i^a_i+1 − 1) / (p_i − 1): de som van alle delers; s(n) = σ(n) − n zegt of het getal perfect, abundant of deficiënt is.
• φ(n) = n × ∏ (1 − 1/p_i): de Eulerfunctie, het aantal getallen van 1 tot n dat relatief priem is met n.
• Kwadraat: n is een kwadraat precies als alle a_i even zijn; dan geldt √n = ∏ p_i^a_i/2, bijvoorbeeld √1.024 = 2⁵ = 32.

Voorbeelden van priemfactorisatie

Waarvoor gebruik je priemfactorisatie?

• Breuken vereenvoudigen: 84/360 = (2² × 3 × 7)/(2³ × 3² × 5) = 7/30, na het wegstrepen van de gemeenschappelijke factoren 2² × 3 = 12.
• Een gemeenschappelijke noemer vinden: het KGV van 360 en 84 is 2.520, de kleinste gemeenschappelijke noemer om 1/360 en 1/84 op te tellen.
• Wortels vereenvoudigen: √360 = √(2² × 3² × 10) = 2 × 3 × √10 = 6√10: elk paar gelijke factoren haal je buiten de wortel.
• Delers tellen en opsommen: handig bij verdeelproblemen (360 stoelen in gelijke rijen zetten: 24 mogelijke opstellingen rijen × kolommen) en bij huiswerk over deelbaarheid.
• Cryptografie en puzzels: RSA berust op de moeilijkheid van ontbinden; het beroemde probleem 3 van Project Euler vraagt de grootste priemfactor van 600.851.475.143, namelijk 6.857.

Veelgemaakte fouten

• Delen door een getal dat geen priemgetal is: 360 delen door 4 of 6 geeft een juist quotiënt maar een onvolledige ontbinding; deel alleen door 2, 3, 5, 7, 11, 13…
• 1 als priemgetal beschouwen: 1 heeft maar één deler en komt nooit voor in een ontbinding.
• 2³ verwarren met 2 × 3: 2³ = 2 × 2 × 2 = 8, terwijl 2 × 3 = 6; de exponent telt hoe vaak de factor voorkomt.
• Een getal priem noemen omdat het „zo lijkt”: 51 = 3 × 17, 91 = 7 × 13 en 1.001 = 7 × 11 × 13 zijn samengesteld; test altijd tot de wortel.

Alle berekeningen gebeuren lokaal in je browser met exacte gehele getallen (BigInt): er wordt geen enkel getal verzonden of opgeslagen. Grenzen: maximaal 18 cijfers; naburige priemgetallen worden getoond tot 10¹², de delerslijst tot 1.000 delers en de tabel met herhaald delen tot 40 priemfactoren (met multipliciteit geteld).