Primtallsfaktorisering

Slik Brytes et Tall Ned til Primtallsbyggeklosser

Hvert helt tall større enn 1 kan brytes ned til et unikt sett med primtall multiplisert sammen — dets primtallsfaktorisering. Angi et helt tall, og denne kalkulatoren finner den faktoriseringen umiddelbart, sammen med om tallet selv er et primtall.

Formelen

Aritmetikkens fundamentalteorem garanterer at hvert helt tall N større enn 1 har nøyaktig én primtallsfaktorisering, opp til rekkefølgen faktorene skrives i:

$$\vA{N} = \vB{p_1}^{\vC{a_1}} \times \vB{p_2}^{\vC{a_2}} \times \cdots \times \vB{p_k}^{\vC{a_k}}$$

hvor hver $\vB{p_i}$ er et distinkt primtall og hver $\vC{a_i}$ er hvor mange ganger det primtallet deler jevnt inn i N.

Denne kalkulatoren finner den faktoriseringen ved bruk av prøvedivisjon: starter ved 2, den sjekker gjentatte ganger om hvert tall deler jevnt inn i det som er igjen, og deler det ut (og teller hvor mange ganger) når det gjør det, og går deretter videre til neste kandidat. Når en kandidats kvadrat overstiger det som gjenstår, må alt som fortsatt er igjen selv være et primtall — enhver mindre faktor ville allerede ha blitt funnet:

$$\text{hvis } \vD{d}^2 > \vE{\text{gjenværende verdi}}, \text{ da er } \vE{\text{gjenværende verdi}} \text{ et primtall}$$

Regneeksempel

Å finne primtallsfaktoriseringen til 360:

1. 360 ÷ 2 = 180, ÷ 2 = 90, ÷ 2 = 45 (2 deler inn 3 ganger; 45 er oddetall, så gå videre).
2. 45 ÷ 3 = 15, ÷ 3 = 5 (3 deler inn 2 ganger; 5 er ikke delelig med 3 igjen).
3. 5 gjenstår, og ingen ytterligere divisors kvadrat er ≤ 5, så 5 selv er et primtall.
4. Resultat: 2³ × 3² × 5.

Viktige Faktorer å Vurdere

• Hver primtallsfaktorisering er unik — dette er nøyaktig det aritmetikkens fundamentalteorem garanterer. Uansett hvordan et tall brytes ned, kommer primtallsfaktoriseringen alltid ut likt (bortsett fra rekkefølgen faktorene skrives i), som er hvorfor primtallsfaktorisering er en så fundamental byggekloss på tvers av tallteori.
• Primtallsfaktorisering er mekanismen bak å finne en Største Felles Faktor eller Minste Felles Multiplum for hånd. Å sammenligne to talls primtallsfaktoriseringer direkte avslører deres SFF (de delte primfaktorene, ved den lavere delte eksponenten) og MFM (hver primfaktor, ved den høyere eksponenten) — se SFF/MFM-kalkulatoren for den spesifikke sammenligningen.
• Å faktorisere store tall blir beregningsmessig mye vanskeligere etter hvert som antall siffer øker, noe som er grunnlaget for enkelte krypteringsmetoder. Prøvedivisjon (metoden brukt her) fungerer godt for tall folk vanligvis skriver inn for hånd, men å faktorisere et svært stort tall med hundrevis av siffer kan være beregningsmessig ugjennomførbart selv for kraftige datamaskiner — denne vanskeligheten er nøyaktig det som ligger til grunn for RSA-krypteringens sikkerhet.
• Et primtall har nøyaktig én primfaktor: seg selv, opphøyd i første potens. Dette er hvorfor denne kalkulatorens «er dette tallet et primtall»-sjekk faller direkte ut av faktoriseringsprosessen — hvis prøvedivisjon aldri finner en faktor mindre enn tallets egen kvadratrot, har tallet ingen faktorisering annet enn seg selv.

Vanlige Feil

• Å forveksle primtallsfaktorisering med en fullstendig liste over faktorer. Faktorene til 12 er 1, 2, 3, 4, 6 og 12, men primtallsfaktoriseringen er bare 2² × 3 — primtallsfaktorisering beholder bare primtallsbyggeklossene, ikke hvert tall som deler jevnt.
• Å behandle 1 som et primtall. Per definisjon har et primtall nøyaktig to distinkte divisorer (1 og seg selv) — 1 har bare én, så det er verken primtall eller sammensatt, og dukker aldri opp i en primtallsfaktorisering.
• Å miste oversikten over gjentatte primfaktorer. Primtallsfaktoriseringen til 8 er 2³, ikke bare «2» — å glemme hvor mange ganger et primtall deler, endrer tallet som faktoriseringen faktisk representerer.

Greit å Vite

• Trenger du Største Felles Faktor eller Minste Felles Multiplum av to tall i stedet for ett talls egne faktorer? Største Felles Faktor og Minste Felles Multiplum-kalkulator sammenligner direkte primtallsfaktoriseringene til to tall.
• Forkorter du en brøk til enkleste form? Brøkkalkulator bruker de samme delte primfaktorene som denne kalkulatoren finner.
• Jobber du i stedet med et svært stort eller svært lite tall? Vitenskapelig Notasjon-kalkulator konverterer mellom standard- og vitenskapelig notasjon.