Så Här Beräknar Du Primtalsfaktorisering
Primtalsfaktorisering är att skriva om ett heltal som en produkt av primtal, talet 360 blir till exempel 2^3 × 3^2 × 5. Du behöver det varje gång du ska förkorta ett bråk till sin enklaste form, hitta alla delare till ett tal, avgöra om ett tal är primt, eller förstå varför kryptering som RSA fortfarande håller. Varje heltal större än 1 har exakt en sådan uppdelning, aritmetikens fundamentalsats garanterar det, vilket är anledningen till att metoden alltid ger samma svar oavsett i vilken ordning du testar primtalen.
Manuell provdivision
Provdivision är den metod du faktiskt använder med papper och penna. Idén är enkel: testa de minsta primtalen ett efter ett, dividera bort dem så länge de går jämnt upp, och gå vidare till nästa primtal när det inte längre går.
- Börja med det minsta primtalet, 2. Dividera talet med 2 så många gånger det går jämnt upp, och räkna hur många gånger.
- Gå vidare till nästa primtal, 3. Upprepa samma sak: dividera så länge det går jämnt, räkna gångerna.
- Fortsätt med 5, 7, 11, 13 och så vidare, i stigande ordning.
- Sluta när kvadraten på det primtal du testar överstiger det som återstår. Det som är kvar då är antingen 1, eller ett primtal i sig självt.
- Skriv ihop resultatet i exponentform: varje primtal upphöjt till hur många gånger det gick jämnt upp.
Låt oss köra igenom det med 360.
360 är jämnt, så vi delar med 2: 360 / 2 = 180. Fortfarande jämnt: 180 / 2 = 90. Och igen: 90 / 2 = 45. Nu är 45 udda, så 2 är klar, den gick upp tre gånger. Vi har nu 45 kvar.
45 går inte upp i 2, men det går upp i 3: 45 / 3 = 15. Fortsätt: 15 / 3 = 5. Nu är 5 inte delbart med 3, så 3 är klar, den gick upp två gånger. Kvar: 5.
Nästa primtal är 5, och 5 / 5 = 1. Klart, vi har nått 1 och kan sluta.
Räkna ihop hur många gånger varje primtal gick upp: 2 tre gånger, 3 två gånger, 5 en gång. Det ger:
360 = 2^3 × 3^2 × 5
Kontrollräkna baklänges för att vara säker: 2^3 = 8, 3^2 = 9, och 8 × 9 × 5 = 72 × 5 = 360. Stämmer.
Ett faktorträd visar samma sak grafiskt, du delar upp talet i två faktorer, delar upp de faktorerna igen, och fortsätter tills alla grenar slutar i ett primtal:
360
/ \
2 180
/ \
2 90
/ \
2 45
/ \
3 15
/ \
3 5Läser man av alla löven i trädet får man samma primtal som provdivisionen gav: 2, 2, 2, 3, 3, 5, alltså 2^3 × 3^2 × 5. Ett faktorträd kan se olika ut beroende på vilka faktorer du väljer att dela upp först (du hade lika gärna kunnat börja med 360 = 4 × 90), men löven i slutänden blir alltid desamma. Det är just det fundamentalsatsen säger.
Ett större exempel: är 997 ett primtal?
Provdivision fungerar lika bra som ett primtalstest, du testar helt enkelt om något primtal går jämnt upp, och om inget gör det innan du når stoppgränsen är talet primt.
Ta 997. Kvadratroten ur 997 är ungefär 31,6, så vi behöver bara testa primtal upp till 31: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Går något av dem jämnt upp behöver vi inte testa längre.
997 är udda, så 2 är uteslutet direkt. Siffersumman 9 + 9 + 7 = 25 är inte delbar med 3, så 3 är uteslutet. Talet slutar inte på 0 eller 5, så 5 är uteslutet. Sedan blir det ren division: 997 / 7 ger rest 3, 997 / 11 ger rest 7, 997 / 13 ger rest 9, 997 / 17 ger rest 11, 997 / 19 ger rest 9, 997 / 23 ger rest 8, 997 / 29 ger rest 11, och 997 / 31 ger rest 5. Inget av primtalen upp till 31 går jämnt upp.
Eftersom nästa primtal, 37, redan har en kvadrat (1369) som är större än 997, kan vi sluta här. 997 är ett primtal, faktiskt det största primtalet under 1000.
Jämför det med ett tal som ser lika svårt ut men inte är det: 91. Det ser primt ut vid en snabb blick, men 91 / 7 = 13 jämnt, så 91 = 7 × 13, en produkt av två primtal och alltså sammansatt. Det är exakt den typen av tal där provdivision räddar dig från att gissa fel.
Beräkna med dina egna tal
Att göra provdivisionen för hand fungerar bra för tal upp till några tusen, men blir opraktiskt fort när talen växer eller när du behöver alla delare listade, inte bara primfaktorerna. Skriv in ditt eget tal nedan så får du exponentform, primtal eller sammansatt, antal delare och hela delarlistan direkt.
Vilket heltal som helst upp till 1 000 000 000 000. Tecknet ignoreras.
Ange ett heltal för att se dess primtalsfaktorisering och delare.
- Distinkta primfaktorer
- —
- Antal delare
- —
Praktiska tillämpningar
Förkorta ett bråk med gemensamma primfaktorer
Att förkorta ett bråk är egentligen bara att jämföra primfaktoriseringen av täljare och nämnare och stryka det de har gemensamt. Ta bråket 84/126.
Faktorisera båda talen var för sig: 84 = 2^2 × 3 × 7, och 126 = 2 × 3^2 × 7.
Den gemensamma delen är den lägsta potensen av varje primtal som finns i båda: 2^1 (2 finns med en gång i 126, trots att 84 har två), 3^1 (126 har 3^2 men 84 bara 3^1), och 7^1. Den gemensamma faktorn blir alltså 2 × 3 × 7 = 42.
Dela både täljare och nämnare med 42: 84 / 42 = 2, och 126 / 42 = 3. Bråket 84/126 förkortas till 2/3, och det går inte att förkorta mer eftersom 2 och 3 inte har någon gemensam primfaktor kvar. Det här är samma princip som en kalkylator för största gemensamma delaren använder under huven, primfaktorisering är bara ett sätt att komma fram till den delaren för hand utan att gissa.
Varför stora primtal håller internet säkert
RSA-kryptering, som ligger bakom en stor del av säker kommunikation online, bygger direkt på hur svårt provdivision blir när talen växer. Metoden väljer två stora primtal, kalla dem p och q, och multiplicerar ihop dem till ett tal n = p × q som blir den publika nyckeln. Att multiplicera är trivialt även för enorma tal, en dator gör det på mikrosekunder.
Det som gör systemet säkert är den motsatta vägen: att gå från n tillbaka till p och q, alltså exakt den provdivision vi just gjorde för hand med 360 och 997. Problemet är att provdivision skalar oerhört dåligt. Att testa primtal upp till kvadratroten av n låter hanterligt för ett tresiffrigt tal som 997, men riktiga RSA-nycklar använder primtal med hundratals siffror vardera, vilket ger ett n på över 600 siffror för en 2048-bitars nyckel. Ingen känd metod, varken provdivision eller de snabbaste kända faktoriseringsalgoritmerna, klarar av att spränga ett tal av den storleken inom rimlig tid med dagens datorer. Hela säkerheten vilar alltså på samma idé som faktorträdet ovan, bara i en skala där uppgiften går från ett fingerövning till praktiskt omöjlig.
Vanliga misstag och gränsfall
- Att tro att 0 eller 1 är primtal eller sammansatta. Ingetdera. Ett primtal måste ha exakt två delare, 1 och sig självt. 1 har bara en delare (sig självt), och 0 är delbart med alla tal, så båda faller utanför definitionen och saknar en primtalsfaktorisering.
- Att glömma absolutbeloppet vid negativa tal. Primtalsfaktorisering är definierad för positiva heltal. Ett tal som -360 faktoriseras genom att först ta absolutbeloppet, 360, och sedan räkna som vanligt: -360 = -1 × 2^3 × 3^2 × 5, där tecknet hanteras separat från själva faktoriseringen.
- Att inte veta när man kan sluta testa. Många fortsätter att testa primtal långt förbi vad som behövs. Regeln är enkel: så fort kvadraten på det primtal du testar blir större än det som återstår, är resten själv ett primtal (om den inte redan är 1). För 997 kunde vi sluta vid 31, eftersom 37^2 = 1369 redan överstiger 997.
- Att blanda ihop primtalsfaktorisering med att bara lista delare. De hänger ihop men är inte samma sak. Delarna till 360 är 24 stycken, från 1 upp till 360, medan primtalsfaktoriseringen bara har tre distinkta primtal (2, 3 och 5). Delarlistan byggs genom att kombinera primfaktorerna i alla möjliga kombinationer, den kortare primtalsfaktoriseringen är byggstenen, inte slutresultatet.
En tabell över några exempel gör skillnaden tydligare:
| Tal | Primtalsfaktorisering | Primt eller sammansatt |
|---|---|---|
| 12 | 2^2 × 3 | Sammansatt |
| 17 | 17 | Primt |
| 60 | 2^2 × 3 × 5 | Sammansatt |
| 91 | 7 × 13 | Sammansatt |
| 360 | 2^3 × 3^2 × 5 | Sammansatt |
| 997 | 997 | Primt |
Vanliga frågor
Vad används primtalsfaktorisering till? De vanligaste vardagliga användningarna är att förkorta bråk till enklaste form, hitta största gemensamma delaren eller minsta gemensamma multipeln för två eller flera tal, och lista alla delare till ett tal. I den andra änden av skalan bygger modern kryptografi som RSA hela sin säkerhet på att multiplikation är enkel men faktorisering av stora tal är extremt svårt.
Hur vet jag om ett tal är ett primtal bara genom att titta på det? Ett fåtal snabba tester kan utesluta primtal direkt: jämna tal större än 2, tal som slutar på 0 eller 5 (utom 5 själv), och tal vars siffersumma är delbar med 3 är alla sammansatta. Men för att vara helt säker, som med 91 som ser primt ut men är 7 × 13, finns ingen genväg runt att faktiskt testa delbarhet med primtal upp till kvadratroten av talet.
Vad är det största talet jag rimligen kan faktorisera för hand? Tal upp till några tusen går att provdividera för hand på rimlig tid, som vi gjorde med 997 på elva divisioner. Femsiffriga tal börjar bli tröttsamma men går fortfarande, sexsiffriga och större blir opraktiska utan hjälpmedel eftersom listan av primtal att testa växer med kvadratroten av talet. Det är precis där en kalkylator tar över och sparar dig från att räkna fel på division nummer arton.
Varför ger olika sätt att bygga ett faktorträd alltid samma svar? Oavsett om du börjar med att dela upp 360 som 2 × 180 eller som 4 × 90 eller som 8 × 45, kommer löven längst ner i trädet alltid att bli exakt samma primtal i samma antal. Det är innehållet i aritmetikens fundamentalsats: varje heltal större än 1 har precis en primtalsfaktorisering, oavsett i vilken ordning eller med vilken metod du kommer fram till den.