Faktorisering

I artikkelen om primtall ser vi at et primtall er et heltall større enn 1 som bare har 1 og seg selv som positive faktorer. I denne artikkelen skal vi fokusere på sammensatte tall, det vil si heltall som ikke er primtall, men tvert imot er delelige med flere positive heltall enn bare 1 og seg selv. Disse tallene vil kunne splittes opp i to eller flere heltall, noe vi kaller en faktorisering.

Primtallsfaktorisering

I artikkelen om primtall ser vi at alle heltall kan skrives som et produkt av primtall på en entydig måte. For eksempel er 12 = 2 · 2 · 3. . Vi kaller en slik oppløsning i primtall for en primtallsfaktorisering. Vi skal nå se på et par metoder for primtallsfaktorisering.

Fermats faktoriseringsmetode

Fermats faktoriseringsmetode, oppfunnet av matematikeren Pierre de Fermat, baserer seg på konjugatsetningen, altså at a² − b² = (a + b)(a − b). Et heltall som kan skrives som en differanse av to kvadrattall, a² − b², kan altså faktoriseres som (a + b)(a − b).

Metoden går ut på at vi prøver å faktorisere et heltall, n, ved å finne heltall, a og b, slik at n = a² − b². Vi skriver først likningen som b² = a² − n. Så starter vi med laveste heltall, a, som er større eller lik $\sqrt n$. Så opphøyer vi a i andre, trekker fra n, og ser om b² da blir et kvadrattall. Hvis ikke, prøver vi a + 1 og gjentar prosessen inntil vi finner en b² som er et kvadrattall. Hvis vi ender opp med at n = n · 1, er n et primtall.

I artikkelen om delelighet ser vi at $\lfloor x \rfloor$ betyr det største heltallet som er mindre eller lik x. Vi har et tilsvarende symbol for det minste heltallet som er større eller lik x, $\lceil x \rceil$, klammeparenteser som bare er lukket i toppen, slik at de danner et tak.

Eksempel 1:

Vi skal faktorisere 119. Vi starter med $a = \lceil \sqrt{119} \rceil = 11$.

Vi får b² = a² − n = (11)² − 119 = 121 − 119 = 2.

2 er ikke et kvadrattall, så vi går videre og prøver a + 1 = 12.

Vi får b² = a² − n = (12)² − 119 = 144 − 119 = 25.

25 er et kvadrattall, 5².

Vi har altså at a² = 12² og b² = 5².

Så 119 = 12² − 5², og kan faktoriseres som (12 + 5)(12 − 5) = 17 · 7.

Vi gjenkjenner 7 og 17 som primtall, men fortsetter faktoriseringsprosessen for illustrasjonens skyld:

Vi skal faktorisere 7. Vi starter med $a = \lceil \sqrt{7} \rceil = 3$.

Vi får b² = a² − n = (3)² − 7 = 9 − 7 = 2.

2 er ikke et kvadrattall, så vi går videre og prøver a + 1 = 4.

Vi får b² = a² − n = (4)² − 7 = 16 − 7 = 9.

9 er et kvadrattall, 3².

Vi har altså at a² = 4² og b² = 3².

Så 7 = 4² − 3², og kan faktoriseres som (4 + 3)(4 − 3) = 7 · 1. Siden den ene faktoren er 1, er 7 et primtall.

Når det gjelder 17, starter vi med $a = \lceil \sqrt{17} \rceil = 5$. Vi dropper utregningene, men verken a = 5, a = 6, a = 7 eller a = 8, gir kvadrattall. Men for a = 9 får vi

b² = a² − n = (9)² − 17 = 81 − 17 = 64.

64 er et kvadrattall, 8².

Vi har altså at a² = 9² og b² = 8².

Så 17 = 9² − 8², og kan faktoriseres som (9 + 8)(9 − 8) = 17 · 1. Siden den ene faktoren er 1, er 17 et primtall.

Oppgave 1:

Bruk Fermats metode til å faktorisere 189.

Se løsningsforslag

Fermats faktoriseringsmetode er ikke spesielt effektiv, det kan kreves opptil ${\large \frac{n+1}{2}} − \sqrt n$ trinn for å faktorisere n. Metoden fungerer best ved tall som består av to faktorer som er omtrent like store. Det finnes også måter å effektivisere metoden på, men det går vi ikke inn på her.

Fermats metode vil ikke kunne faktorisere tall som inneholder primtallsfaktoren 2 nøyaktig én gang, for eksempel 30 = 2 · 3 · 5. For ved faktorisering må to-tallet havne i den ene eller andre faktoren, for eksempel 30 = 2 · 15 eller 30 = 6 · 5 eller 30 = 10 · 3. Den ene faktoren må derfor bli et partall mens den andre blir et oddetall. Tallet vil da ikke kunne faktoriseres som (a + b)(a − b) fordi både a + b og a − b alltid vil være enten partall eller oddetall. På den annen side vet vi jo at et tall inneholder faktoren 2 hvis det er et partall, så vi kan dividere bort alle 2-faktorene før vi starter med Fermats metode.

Beregne $\lceil x \rceil$ i GeoGebra og regneark

I GeoGebra finner vi $\lceil x \rceil$ ved hjelp av funksjonen ceil. I GeoGebra er punktum, ikke komma, desimalskilletegn, så hvis vi for eksempel vil finne $\lceil 2{,}75 \rceil$ i GeoGebra, skriver vi ceil(-2.75) i inntastingsfeltet. GeoGebra svarer med −2 i algebrafeltet

I regneark som Excel finner vi $\lceil x \rceil$ ved hjelp av funksjonen med det forferdelige navnet avrund.gjeldende.multiplum.opp.matematisk. Det finnes også andre avrundingsfunksjoner, for eksempel avrund.opp, men denne vil ikke beregne $\lceil x \rceil$ riktig for negative $x$. Det kan angis mange parametere til avrund.gjeldende.multiplum.opp.matematisk, men for å finne $\lceil x \rceil$, angir vi bare x. For eksempel gir =avrund.gjeldende.multiplum.opp.matematisk(-2,75) tallet −2.

Brute force faktorisering

En enkel metode, som heller ikke er spesielt effektiv for høye tall, kalles «brute force», altså «rå kraft», og går ut på å systematisk forsøke å dividere tallet vi vil faktorisere med primtallene fra 2 og oppover. Hvis divisjonen går opp, har vi funnet en faktor. Da utfører vi divisjonen, og får et nytt, mindre tall å faktorisere. Vi forsøker da først samme primtall på nytt, for det kan jo være at samme primtallsfaktor forekommer flere ganger. Når vi har forsøkt alle primtall opp til rota av tallet vi skal faktorisere, er vi i mål.

Litt mer formelt kan metoden beskrives algoritmisk slik:

1. 1. La n være tallet som skal faktoriseres, la f være en faktor som skal sjekkes, la p₁, p₂, … , p₃ være primtallene fra 2 og oppover, og la l være ei liste over faktorer som er funnet. Lista er i utgangspunktet tom.
       
   2. Sett f lik p_m=1, altså første primtall.
       
   3. Hvis divisjonen n : f går opp, er f en faktor. I så fall:
      Føy f til i lista l.
      Sett n = n : f.
       
   4. Hvis divisjonen n : f ikke går opp, er f ikke en faktor. I så fall:
      Sett f lik p_m+1, altså neste primtall.
       
   5. Gjenta trinn 3 og 4 så lenge f er mindre eller lik $\lfloor \sqrt n \rfloor$.
       
   6. l inneholder nå ei liste over alle primtallsfaktorene i n. Er l tom, er n et primtall.

Eksempel 2:

Vi skal faktorisere 1275 ved hjelp av «brute force»-algoritmen.

Vi forsøker første primtall, og sjekker om 1275 er delelig med 2. Det er det ikke.

Vi forsøker neste primtall, og sjekker om 1275 er delelig med 3. Det er det. Vi noterer at 3 er en faktor, og utfører divisjonen 1275 : 3 = 425.

Vi arbeider videre med 425, og sjekker om 425 er delelig med 3. Det er det ikke.

Vi forsøker neste primtall, og sjekker om 425 er delelig med 5. Det er det. Vi noterer at 5 er en faktor, og utfører divisjonen 425 : 5 = 85.

Vi arbeider videre med 85, og sjekker om 85 er delelig med 5. Det er det. Vi noterer at 5 er en faktor, og utfører divisjonen 85 : 5 = 17.

Vi arbeider videre med 17. Men siden $\lfloor \sqrt {17} \rfloor = 4$, er 3 det høyeste primtallet som må sjekkes, og primtallsfaktorer opp til 3 har vi allerede dividert ut, så vi slår fast at 17 er et primtall.

Vi lister så opp faktorene vi har funnet, og konkluderer med at 1275 = 3 · 5 · 5 · 17.

Algoritmen forutsetter at vi kjenner alle primtallene, p, som er slik at p er mindre eller lik $\sqrt n$. Hvis ikke, kan vi i stedet først sjekke tallet 2, og deretter alle oddetallene oppover.

Oppgave 2:

Bruk «brute force»-algoritmen til å faktorisere 231.

Se film der løsningsforslaget vises

 
Dette nettstedet har en app som primtallsfaktoriserer ved hjelp av «brute force»-algoritmen. Hvis du der huker av for «Vis utregning», lister appen opp trinnene i utregningen, det kan være veldig instruktivt.

Oppgave 3:

Bruk «brute force»-algoritmen til å faktorisere 1660 for hånd, og sjekk deretter utregningene med appen som primtallsfaktoriserer.

Se løsningsforslag

Heltallsfaktorisering

Selv om et heltall kan primtallsfaktoriseres på en entydig måte, betyr ikke det at det er den eneste måten det kan faktoriseres på. Det kan også faktoriseres i ethvert produkt av sine primtallsfaktorer. I tillegg har alle tall 1, −1 og seg selv som faktorer. Siden vi kan kombinere −1 med de andre faktorene, vil alle faktorene opptre både i en positiv og negativ variant.

Eksempel 3:

24 primtallsfaktoriseres som 2 · 2 · 2 · 3. Primtallsfaktorene kan da kombineres til
2 · 2 = 4
2 · 3 = 6
2 · 2 · 2 = 8
2 · 2 · 3 = 12

I tillegg kommer 1 og 24. Alle disse kan igjen kombineres med −1, så alt i alt er
±1, ±2, ±3, ±4, ±6, ±8, ±12, ±24 faktorer i 24.

Oppdeling av små tall i positive faktorene kan lett illustreres med blokker, som vist under, der 12 er representert som henholdsvis 12 · 1, 6 · 2, 4 · 3, 3 · 4 og 2 · 6.

Et sammensatt tall vil alltid kunne faktoriseres i to andre tall. Er ett av disse sammensatt, kan det igjen faktoriseres i to nye tall, og så videre. Dette kan illustreres i en tre-struktur, slik som vist under, der 24 faktoriseres på tre forskjellige måter. Ytterst på grenene finner vi primtallene, som ikke kan faktoriseres videre. De er de samme i alle tre tilfeller, 2, 2, 2 og 3, fordi faktoriseringen i primtall er unik.

Kilder

• • Rosen, Kenneth H. (1984). Elementary Number Theory and Its Applications. Addison-Wesley.
  • Breiteig, T. (2007). Bak tallene. Innføring i tallteori. Kompendium, Universitetet i Agder.
  • Rinvold, R. (2009). Tallteori. Caspar forlag.
  • Gustavsen, TS, Hinna, K.R.C., Borge, I.C., Andersen P.S. (2014). QED 5-10, bind 2. Høyskoleforlaget