Slik Beregner Du Primtallsfaktorisering
Primtallsfaktorisering er å skrive et helt tall som et produkt av primtall, altså de tallene som bare lar seg dele jevnt med 1 og seg selv. Ethvert helt tall større enn 1 har nøyaktig én slik oppdeling, uansett hvordan du kommer fram til den, og det er det som gjør den nyttig: den viser byggeklossene i tallet. Du bruker den til å forkorte brøker, finne alle divisorene til et tall, regne ut minste felles multiplum og største felles divisor, og den ligger under moderne kryptering som RSA.
Manuell prøvedivisjon
Metoden for hånd er rett fram: du prøver å dele tallet med det minste primtallet som går opp i det, fortsetter med det som er igjen, og gjentar helt til du sitter igjen med 1. Test primtallene i stigende rekkefølge, altså 2, 3, 5, 7, 11 og så videre, og hopp videre til neste primtall bare når det nåværende ikke lenger deler jevnt.
La oss faktorisere 360 fra bunnen av:
- 360 er et partall, så del med 2: 360 ÷ 2 = 180.
- 180 er også et partall, del med 2 igjen: 180 ÷ 2 = 90.
- 90 er fortsatt et partall, del med 2 en tredje gang: 90 ÷ 2 = 45.
- 45 er et oddetall, så 2 går ikke opp lenger. Prøv neste primtall, 3: 45 ÷ 3 = 15.
- 15 er delelig med 3 igjen: 15 ÷ 3 = 5.
- 5 er selv et primtall, så del med 5: 5 ÷ 5 = 1.
Du sitter igjen med 1, og er ferdig. Primfaktorene, i rekkefølgen du fant dem, er 2, 2, 2, 3, 3, 5. Grupper de like faktorene med eksponenter, og du får svaret i eksponentform:
360 = 2³ × 3² × 5
Kontrollregn motsatt vei for å være sikker: 2³ = 8, 3² = 9, og 8 × 9 × 5 = 360. Stemmer.
Et faktortre viser samme oppdeling visuelt. Du deler tallet i to faktorer, og deler så videre helt til alle grenene ender i primtall:
360
/ \
2 180
/ \
2 90
/ \
2 45
/ \
3 15
/ \
3 5Det spiller ingen rolle hvilke faktorer du velger underveis. 180 kunne like gjerne vært delt som 4 × 45 eller 6 × 30 i stedet for 2 × 90, og treet ville sett annerledes ut i mellomtrinnene, men bladene nederst blir alltid de samme seks primtallene. Det er selve poenget med at faktoriseringen er unik: rekkefølgen og formen på treet varierer, resultatet gjør det ikke.
Et større eksempel: er 997 et primtall?
Noen ganger er spørsmålet ikke “hva er faktorene”, men “har tallet i det hele tatt noen faktorer utenom 1 og seg selv”. Det spørsmålet svarer du på med samme prøvedivisjon, bare at du kan stoppe mye tidligere enn du kanskje tror.
997 er et oddetall, så 2 er ute med en gang. Kvadratroten av 997 ligger mellom 31 og 32, siden 31² = 961 og 32² = 1024. Det betyr at du bare trenger å teste primtallene opp til og med 31: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 og 31. Hvis ingen av dem deler 997 jevnt, finnes det ingen faktor større enn 31 heller, for en slik faktor måtte vært parret med en motsatt faktor mindre enn 31, og den ville du allerede ha funnet.
| Divisor | 997 ÷ divisor | Rest |
|---|---|---|
| 3 | 332 | 1 |
| 7 | 142 | 3 |
| 11 | 90 | 7 |
| 13 | 76 | 9 |
| 17 | 58 | 11 |
| 19 | 52 | 9 |
| 23 | 43 | 8 |
| 29 | 34 | 11 |
| 31 | 32 | 5 |
Ingen av restene er 0, så ingen av primtallene opp til 31 går opp i 997. Siden 32² allerede overstiger 997, er det ikke nødvendig å teste flere primtall. 997 er et primtall.
Denne grensen, kvadratroten av tallet, er grunnen til at primalitetstesting for hånd sjelden blir uoverkommelig selv for tall i tusentallet: å teste et tall opp mot en million krever bare at du sjekker primtall opp til 1000, ikke opp til en million.
| Tall | Primtallsfaktorisering | Primtall? |
|---|---|---|
| 17 | 17 | Ja |
| 24 | 2³ × 3 | Nei |
| 41 | 41 | Ja |
| 100 | 2² × 5² | Nei |
| 360 | 2³ × 3² × 5 | Nei |
| 997 | 997 | Ja |
Beregn med dine egne tall
Skriv inn et hvilket som helst positivt heltall, og kalkulatoren viser primfaktorene i eksponentform sammen med faktortreet, uten at du trenger å regne noe for hånd.
Et hvilket som helst heltall opptil 1 000 000 000 000. Fortegnet ignoreres.
Skriv inn et heltall for å se primtallsfaktoriseringen og divisorene.
- Distinkte primfaktorer
- —
- Antall divisorer
- —
Praktiske bruksområder
Forkorte brøker med felles primfaktorer
Den vanligste grunnen til å faktorisere i praksis er å forkorte en brøk uten å måtte gjette hvilket tall du kan dele med. Ta 84/126. Faktoriser begge tallene:
84 = 2² × 3 × 7 126 = 2 × 3² × 7
Sammenlign faktorene og plukk ut det laveste antallet av hver primfaktor de har felles: 2 finnes minst én gang i begge (2¹), 3 finnes minst én gang i begge (3¹), og 7 finnes i begge (7¹). Den felles delen er derfor 2 × 3 × 7 = 42, som er den største felles divisoren til 84 og 126.
Del teller og nevner på 42:
84 ÷ 42 = 2 126 ÷ 42 = 3
84/126 forkortes altså til 2/3, i ett steg, uten prøving og feiling med små tall som 2, 3, 6 og 7 hver for seg. Jo større tallene er, desto mer tid sparer denne metoden sammenlignet med å gjette seg fram til en felles divisor.
Finne alle divisorene til et tall
Eksponentformen gir deg også en snarvei til å finne absolutt alle divisorene i et tall, ikke bare primfaktorene. Regelen er enkel: legg til 1 på hver eksponent og gang sammen. For 360 = 2³ × 3² × 5¹ blir det (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24 divisorer totalt, inkludert 1 og 360 selv.
Du finner selve divisorene ved å kombinere hver mulig kombinasjon av 2⁰ til 2³, 3⁰ til 3² og 5⁰ til 5¹:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360
Tell dem opp, det blir nøyaktig 24, som stemmer med formelen. Denne teknikken brukes blant annet når du skal finne alle måtene et antall gjenstander kan deles i like store grupper på, eller når du leter etter felles nevnere for flere brøker på en gang.
Store primtall og kryptografi
RSA-kryptering, som ligger under mye av HTTPS-trafikken på nettet, hviler på at det er lett å gange to store primtall sammen, men uoverkommelig tregt å gå motsatt vei og faktorisere produktet igjen når primtallene har hundrevis av sifre. Metoden med prøvedivisjon du nettopp brukte på 997 fungerer i praksis kun for tall med opptil 15 til 20 sifre før den blir for treg selv for datamaskiner. Nøklene i ekte RSA-kryptering bruker primtall med 150 til 300 sifre hver, langt utenfor rekkevidde for prøvedivisjon selv med enorm regnekraft. Det gapet mellom “lett å gange sammen” og “vanskelig å faktorisere tilbake” er selve sikkerheten i systemet.
Vanlige feil og grensetilfeller
0 og 1 er verken primtall eller sammensatte tall. Et primtall er per definisjon et tall med nøyaktig to positive divisorer, 1 og seg selv. 1 har bare én divisor (seg selv), så det kvalifiserer ikke. 0 er delelig med alle tall, så det passer ikke inn i noen av kategoriene. Faktorisering er derfor udefinert for begge.
Negative tall bruker absoluttverdien. −18 faktoriseres som 18 = 2 × 3², og fortegnet holdes utenfor selve faktoriseringen. Vil du beholde informasjonen om fortegnet, skriver du −18 = −1 × 2 × 3², men −1 regnes ikke som en primfaktor.
Å vite når man kan stoppe prøvedivisjonen. Så snart kvadratet av divisoren du tester overstiger det som er igjen av tallet, er resten selv et primtall, og du er ferdig. Det var nettopp dette som gjorde 997-eksemplet raskt: du trengte aldri teste noe høyere enn 31.
Å glemme at samme primtall kan gå opp flere ganger. I 360-eksempelet gikk 2 opp tre ganger på rad før det var oddetallets tur. Et vanlig feiltrinn er å dele én gang med et primtall, se at det gikk opp, og hoppe videre til neste primtall uten å sjekke om det samme primtallet går opp igjen.
Å hoppe over et primtall i rekkefølgen. Går du rett fra 2 til 5 og glemmer å teste 3, kan du ende opp med et tall som ser ut som et primtall selv om det egentlig er delelig med 3. Test alltid i stigende rekkefølge uten å hoppe over noen.
Ofte stilte spørsmål
Hva brukes primtallsfaktorisering til? Den brukes til å forkorte brøker til enkleste form, finne minste felles multiplum og største felles divisor mellom tall, telle opp alle divisorene til et tall, og den er selve grunnlaget for kryptografiske systemer som RSA, der sikkerheten hviler på at store tall er vanskelige å faktorisere.
Hvordan vet jeg om et tall er et primtall bare ved å se på det? Noen raske sjekker filtrerer bort de fleste sammensatte tallene umiddelbart: er tallet partall og større enn 2, er det ikke et primtall. Ender det på 0 eller 5 og er større enn 5, er det delelig med 5. Er tverrsummen delelig med 3, er tallet det også. Utover det finnes det ingen snarvei uten å faktisk teste divisorer opp til kvadratroten av tallet.
Hva er det største tallet jeg rimelig kan faktorisere for hånd? For hånd med prøvedivisjon holder det seg overkommelig opp til fire, kanskje fem sifre, altså titusener, før det blir upraktisk mange primtall å teste. Grensen henger sammen med kvadratroten: et sekssifret tall krever i verste fall å teste alle primtall opp til rundt 1000, noe som fort blir tungvint uten hjelpemidler. Er tallet mye større, er en kalkulator den praktiske løsningen.
Er alle oddetall primtall? Nei. 9, 15, 21, 25 og 27 er alle oddetall, men ingen av dem er primtall: 9 = 3², 15 = 3 × 5, 21 = 3 × 7, 25 = 5², og 27 = 3³. Å være oddetall utelukker bare 2 som mulig divisor, ikke resten av primtallene.