Sådan Beregner Du Primtalsfaktorisering

Primtalsfaktorisering er processen med at splitte et helt tal op i de primtal, som ganget sammen giver det tal tilbage. 360 kan for eksempel kun skrives som 2 × 2 × 2 × 3 × 3 × 5, og ingen andre primtal indgår. Du har brug for det, fordi primtal er tallenes byggesten: når du kender et tals primfaktorer, kan du forkorte brøker, finde alle dets divisorer, afgøre det største fælles mål mellem to tal, og forstå hvorfor kryptografi som RSA overhovedet virker.

Manuel prøvedivision

Metoden til at finde primfaktorerne i hånden hedder prøvedivision, og den er enkel nok til at gøre på papir. Du starter med det mindste primtal, 2, og dividerer så længe det går op. Går det ikke længere op, går du videre til næste primtal (3, så 5, så 7 og så videre), og gentager processen, indtil det, der er tilbage, selv er 1.

Lad os tage 360 igennem trinene:

1. 360 er lige, så del med 2. 360 ÷ 2 = 180. Skriv 2 ned som første faktor.
2. 180 er stadig lige, del igen med 2. 180 ÷ 2 = 90. Endnu en 2.
3. 90 er stadig lige, del en tredje gang med 2. 90 ÷ 2 = 45. Nu har du tre 2-taller, og 45 er ulige, så 2 går ikke op mere.
4. Prøv næste primtal, 3. 45 ÷ 3 = 15. Skriv 3 ned.
5. 15 er stadig delelig med 3. 15 ÷ 3 = 5. Endnu en 3, og det, der er tilbage, er 5.
6. 5 er et primtal i sig selv, så du er færdig. Skriv 5 ned som den sidste faktor.

Saml faktorerne op: 2, 2, 2, 3, 3, 5. Skrevet i eksponentform bliver det 360 = 2³ × 3² × 5. Tjek regnestykket baglæns for en sikkerheds skyld: 2³ = 8, 3² = 9, og 8 × 9 × 5 = 72 × 5 = 360. Det stemmer.

Tænker du på det som et faktortræ i stedet for en liste af divisioner, ser det sådan ud:

        360
       /    \
      2     180
           /    \
          2      90
                /    \
               2      45
                     /   \
                    3     15
                         /   \
                        3      5

Bladene nederst i træet (2, 2, 2, 3, 3, 5) er præcis de samme faktorer, uanset hvilken rækkefølge du splitter tallet op i undervejs. Havde du i stedet startet med at dele 360 i 36 × 10, var du landet på nøjagtig de samme seks primtal til sidst.

Et større eksempel: er 997 et primtal?

Prøvedivision bruges ikke kun til at splitte sammensatte tal op, den er også den mest direkte måde at afgøre, om et tal overhovedet er et primtal. Reglen, der gør arbejdet overskueligt, er denne: du behøver kun teste primtal op til kvadratroden af tallet. Er der ingen af dem, der går op, er tallet selv et primtal.

For 997 er kvadratroden cirka 31,6, så listen af primtal, du skal teste, stopper ved 31: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31.

• 997 er ulige, så 2 går ikke op.
• Tværsummen er 9 + 9 + 7 = 25, som ikke er delelig med 3, så 3 går ikke op.
• Tallet ender ikke på 0 eller 5, så 5 går ikke op.
• 997 ÷ 7 = 142 rest 3, går ikke op.
• 997 ÷ 11 = 90 rest 7, går ikke op.
• 997 ÷ 13 = 76 rest 9, går ikke op.
• 997 ÷ 17 = 58 rest 11, går ikke op.
• 997 ÷ 19 = 52 rest 9, går ikke op.
• 997 ÷ 23 = 43 rest 8, går ikke op.
• 997 ÷ 29 = 34 rest 11, går ikke op.
• 997 ÷ 31 = 32 rest 5, går ikke op.

Næste primtal er 37, men 37² = 1369, hvilket allerede er større end 997, så der er ingen grund til at teste videre. Ingen af primtallene op til 31 går op i 997, så 997 er et primtal. Det står alene i sin egen faktorisering: 997 = 997¹.

Beregn med dine egne tal

Vil du slippe for at holde styr på divisionerne selv, eller bare tjekke et resultat du er nået frem til i hånden? Indtast et hvilket som helst helt tal herunder, og få primfaktorerne, eksponentformen og alle divisorer på et øjeblik.

Praktiske anvendelser

Forkort en brøk med fælles primfaktorer

Den mest håndgribelige brug af primtalsfaktorisering i hverdagen er at forkorte brøker, uden at skulle gætte dig frem til den rigtige divisor. Tag 84/126 som eksempel. Faktoriser begge tal hver for sig:

• 84 = 2² × 3 × 7
• 126 = 2 × 3² × 7

Den fælles del er det laveste antal af hver primfaktor, som optræder i begge tal: én 2-er (den laveste eksponent mellem 2² og 2¹), én 3-er (mellem 3¹ og 3²), og én 7-er. Ganget sammen giver det 2 × 3 × 7 = 42, som er det største fælles mål mellem 84 og 126. Divider begge tal med 42: 84 ÷ 42 = 2, og 126 ÷ 42 = 3. Brøken 84/126 forkortes altså direkte til 2/3, uden en eneste omvej med prøv-og-fejl.

Find alle divisorer af et tal

Når du kender eksponentformen, kan du også regne ud, præcis hvor mange divisorer et tal har, uden at liste dem alle sammen manuelt. Reglen er: læg 1 til hver eksponent, og gang resultaterne sammen. For 360 = 2³ × 3² × 5¹ giver det (3 + 1) × (2 + 1) × (1 + 1) = 4 × 3 × 2 = 24 divisorer i alt, fra 1 og 2 hele vejen op til 180 og 360 selv. Det er den samme regel, der ligger bag, hvorfor tal som 360 (eller 60, 720, 840) dukker op så ofte i kalendere og målesystemer: mange små primfaktorer i kombination giver usædvanligt mange divisorer i forhold til tallets størrelse, hvilket gør dem lette at dele op i tredjedele, fjerdedele, sjettedele og så videre.

Almindelige fejl og kantsager

• 0 er hverken et primtal eller et sammensat tal. Det har uendeligt mange divisorer (ethvert tal går op i 0), så det passer ikke ind i nogen af de to kategorier.
• 1 er heller ikke et primtal. Definitionen af et primtal kræver præcis to divisorer, 1 og tallet selv. 1 har kun én divisor, sig selv, så det falder uden for definitionen. Det er derfor 1 aldrig optræder i en primtalsfaktorisering, uanset hvor mange gange du “prøver” at dividere med det.
• Negative tal bruger den absolutte værdi. Faktoriseringen af −360 er den samme som af 360 (2³ × 3² × 5), blot med et fortegn foran, som holdes uden for selve faktoriseringen.
• Hvornår du kan stoppe prøvedivisionen. Så snart kvadratet af den divisor, du er nået til, overstiger det, der er tilbage af tallet, kan du stoppe: det resterende tal er selv et primtal, og der er ingen grund til at teste flere kandidater. Det var præcis den regel, der sparede os for at teste primtal over 31 i eksemplet med 997.

Ofte stillede spørgsmål

Hvad bruges primtalsfaktorisering til? Ud over at forkorte brøker og finde divisorer, ligger primtalsfaktorisering til grund for at finde største fælles mål og mindste fælles multiplum mellem tal, og den er selve fundamentet under moderne kryptografi. RSA-kryptering bygger på, at det er hurtigt at gange to store primtal sammen, men enormt tidskrævende at gå den anden vej og faktorisere produktet igen, hvis primtallene er store nok (typisk hundredvis af cifre).

Hvordan ved jeg, om et tal er et primtal, bare ved at kigge på det? Nogle hurtige tjek kan udelukke de fleste sammensatte tal med det samme: et lige tal over 2 er aldrig et primtal, et tal, der ender på 0 eller 5, er aldrig et primtal medmindre det er 5 selv, og er tværsummen delelig med 3, er tallet det også. Er ingen af disse tjek gyldige, er du nødt til at teste egentlig prøvedivision op til kvadratroden, som vist med 997 ovenfor.

Hvad er det største tal, jeg med rimelighed kan faktorisere i hånden? De fleste kan overkomme tal op til nogle tusinde uden større besvær, fordi kvadratroden holder antallet af primtal, du skal teste, nede (kvadratroden af 10.000 er kun 100). Går tallet op i millioner eller derover, bliver prøvedivision i hånden upraktisk, og det er her en beregner for alvor kommer til sin ret.

Er der forskel på “faktorisering” og “primtalsfaktorisering”? Ja. At faktorisere et tal betyder bare at skrive det som et produkt af mindre tal, for eksempel 360 = 20 × 18, hvilket kan gøres på mange måder. Primtalsfaktorisering er den ene, entydige version, hvor alle faktorerne er primtal, og hvor rækkefølgen ikke tæller. Uanset hvilken vej du splitter et tal op undervejs, ender du altid med den samme liste af primtal til sidst.