Faktorisering

I artikkelen om primtall så vi at et primtall var et heltall større enn $1$ som bare hadde $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 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 så vi at alle heltall kan skrives som et produkt av primtall på en entydig måte. For eksempel er $12 = 2 \cdot 2 \cdot 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å 3. kvadratsetning, altså at $a^2 – b^2 = (a + b)(a – b)$. Et heltall som kan skrives som en differanse av to kvadrattall, $a^2$ og $b^2$, 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^2 – b^2$. Vi skriver først likningen som $b^2 = a^2 – 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 vi får et kvadrattall. Hvis ikke, prøver vi $a + 1$ og gjentar prosessen inntil vi finner et kvadrattall. Hvis vi ender opp med at $n = n \cdot 1$, er $n$ et primtall.

I artikkelen om delelighet lærte vi at $\lfloor x \rfloor$ betydde 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^2 = (11)^2 – 119 = 121 – 119 = 2$.

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

Vi får $b^2 = (12)^2 – 119 = 144 – 119 = 25$.

$25$ er et kvadrattall, $5^2$.

Vi kan derved skrive $119$ som en differanse av to kvadrattall, $12^2 – 5^2$ og følgelig kan $119$ faktoriseres som $(12 + 5)(12 – 5) = 17 \cdot 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^2 = (3)^2 – 7 = 9 – 7 = 2$.

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

Vi får $b^2 = (4)^2 – 7 = 16 – 7 = 9$.

$9$ er et kvadrattall, $3^2$.

Vi kan derved skrive $7$ som en differanse av to kvadrattall, $9^2 – 4^2$ og følgelig kan $7$ faktoriseres som $(4 + 3)(4 – 3) = 7 \cdot 1$. $7$ er følgelig et primtall.

Når det gjelder $17$, starter vi med $a = \lceil \sqrt{17} \rceil = 5$, men må opp til $a = 9$ før vi finner et kvadrattall, og ser at $17$ kan faktoriseres som $(9 + 8)(9 – 8) = 17 \cdot 1$, og følgelig er 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å.

Fermats metode vil ikke kunne faktorisere tall som inneholder primtallsfaktoren $2$ nøyaktig én gang, for eksempel $30 = 2 \cdot 3 \cdot 5$. For ved faktorisering må to-tallet havne i den ene eller andre faktoren, for eksempel $30 = 15 \cdot 2$ eller $30 = 6 \cdot 5$ eller $30 = 10 \cdot 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", 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. La $n$ være tallet som skal faktoriseres, la $f$ være en faktor som skal sjekkes, la $p_1, p_2, \dots, p_r$ 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_1$.
  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 det høyeste primtallet som må sjekkes lik $3$, og primfaktorer 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 \cdot 5 \cdot 5 \cdot 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.

ScreencastSe 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 \cdot 2 \cdot 2 \cdot 3$. Primtallsfaktorene kan da kombineres til
$2 \cdot 2 = 4$,
$2 \cdot 3 = 6$,
$2 \cdot 2 \cdot 2 = 8$,
$2 \cdot 2 \cdot 3 = 12$.

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

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

Blokker brukt som illustrasjon av faktorisering av 12

Et sammensatt tall vil alltid kunne faktoriseres i to andre tall. Er et 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.

Faktoriseringstre Faktoriseringstre Faktoriseringstre

Felles faktorer

Felles faktorer til to tall er naturlig nok faktorer som forekommer i begge tallene.

Eksempel 4:

$24$ har faktorene $\pm 1, \pm 2, \pm 3, \pm 4, \pm 6, \pm 8, \pm 12, \pm 24$, som vi så i eksempel 3.

$32$ har faktorene $\pm 1, \pm 2, \pm 4, \pm 8, \pm 16, \pm 32$.

Felles faktorer for $24$ og $32$ er derved $\pm 1, \pm 2, \pm 4, \pm 8$.

Å finne to talls felles faktorer er nyttig hvis vi for eksempel skal forkorte en brøk, fordi vi da skal stryke faktorer som er felles for teller og nevner.

Største felles faktor

Blant to heltalls felles faktorer vil det naturligvis være en faktor som er størst. Denne heter tallenes største felles faktor, også kalt største felles divisor. På dette nettstedet skriver vi største felles faktor til $a$ og $b$ som $SFF(a, b)$. I andre artikler og bøker vil vi imidlertid kunne støte på betegnelsen SFD, for "største felles divisor", GCD, for "Greatest Common Divisor", eller at $a$ og $b$ bare listes mellom parenteser, som $(a, b)$.

Største felles faktor kan være nyttig i mange sammenhenger. Hvis vi for eksempel skal forkorte en brøk så langt det går, må vi dividere teller og nevner med deres største felles faktor. Største felles faktor trenger vi også når vi skal løse kongruenslikninger og diofantiske likninger. Vi skal derfor studere største felles faktor grundig.

Siden alle faktorer i et negativt tall også er faktorer i det motsvarende positive tallet, vil $SFF(a, b)$ være samme tall, uavhengig av fortegnet til $a$ og $b$. Vi bruker derfor bare positive $a$ og $b$ i eksempler og oppgaver med SFF.

Eksempel 5:

$SFF(24,32) = 8$, som vi kan se av eksempel 4.

På ei tallinje kan vi illustrere at $b$ er en faktor i $a$ ved hjelp av et linjestykke med lengde $b$, som lagt etter seg selv et helt antall ganger treffer i $a$.

At $b$ er felles faktor i $a$ og $c$ kan vi illustrere ved hjelp av et linjestykke med lengde $b$, som lagt etter seg selv et helt antall ganger treffer i både $a$ og $c$. Største felles faktor vil være det lengste linjestykket som kan legges på denne måten.

Eksempel 6:

Vi ser på positive faktorer i $8$ og $12$.

$1$, $2$$4$ og $8$ er faktorer i $8$.

$1$, $2$, $3$$4$$6$ og $12$ er faktorer i $12$.

Felles faktorer er $1$, $2$ og $4$, og største felles faktor er $4$.

Dette er illustrert under. Vi ser at linjestykkene med lengde $1$, $2$ og $4$ treffer i både $8$ og $12$, og $4$ er det lengste av disse.

Illustrasjon av faktorer og felles faktorer i 8 og 12

Hvis et heltall, $b$, er en faktor i  et heltall, $a$, vil tallenes største felles faktor være lik absoluttverdien til $b$:

$\fbox{$ \text{Hvis } b \mid a, \text{ vil } SFF(a, b) = |b|$}$

Det er ikke så vanskelig å forstå. Siden $b$ er en faktor i $a$ og $b$ er en faktor i seg selv, er $b$ en felles faktor for $a$ og $b$. $b$ kan jo ikke ha faktorer som er større enn seg selv, derfor må $b$ også være største felles faktor. For å ta høyde for at $b$ kan være negativ, bruker vi absoluttverditegn.

Eksempel 7:

Vi skal finne $SFF(4, 12)$.

Siden $4 \mid 12$, blir svaret $|4| = 4$.

Dette er illustrert på ei tallinje under. Et linjestykke med lengde $4$ er det lengste stykket vi kan legge som treffer både i $4$ og $12$.

Illustrasjon av at hvis b | a, er SFF(a,b) = |b|

 

Siden alle tall går opp i $0$, har vi at for alle $a$ at

$\fbox{$SFF(a, 0) = |a|$}$

$\pm 1$ går opp i alle heltall. To heltall, $a$ og $b$, sies å være innbyrdes primiske hvis de ikke har andre felles faktorer enn $\pm 1$, det vil si at $SFF(a, b) = 1$. Det betyr imidlertid ikke at $a$ eller $b$  primtall. Andre ord for innbyrdes primiske tall er koprimiske tall og relativt primiske tall.

Eksempel 8:

$25$ og $42$ er innbyrdes primiske fordi $SFF(25, 42) = 1$. Men verken $25$ eller $42$ er primtall.

Hvis vi dividerer to heltall med deres største felles faktor, blir de resulterende tallene innbyrdes primiske:

$\fbox{$ \text {Hvis } SFF(a, b) = d, \text{ vil vi ha at } SFF( \frac{\displaystyle a}{\displaystyle d}, \frac{\displaystyle b}{\displaystyle d}) = 1$}$

Dette tilsvarer å forkorte en brøk så langt det går.

Eksempel 9:

I eksempel 5 fant vi at $SFF(24, 32)= 8$. Da er $SFF({\large \frac{24}{8}}, {\large \frac{32}{8}}) = SFF(3, 4) = 1$.

Største felles faktor til to heltall endrer seg ikke hvis vi adderer heltallige multipler av det ene tallet til det andre:

$\fbox{$SFF(a, b) = SFF(a +cb, b)$}$

Eksempel 10:

I eksempel 5 fant vi at $SFF(24, 32) = 8$. Da er for eksempel $SFF(24 + 32, 32) = SFF(56, 32) = 8$ og $SFF(24 + 3 \cdot 32, 32) = SFF(120, 32) = 8$.

$c$ kan gjerne være negativ, noe som betyr at vi kan bruke denne regelen til å erstatte tall med mindre tall, og derved gjøre det lettere å finne største felles faktor.

Eksempel 11:

Vi skal finne $SFF(30, 72)$. Dette vil være det samme som
$SFF(30, 72 – 2 \cdot 30) = SFF(30, 12) = \\
SFF(30 – 2 \cdot 12, 12) = SFF(6, 12) = SFF(6, 12 – 6) = SFF(6, 6) = 6$
.

Vil vi finne største felles faktor til mer enn to tall, kan vi gjøre det ved å finne største felles faktor til to tall av gangen, i vilkårlig rekkefølge:

$\fbox{$ SFF(a, b, c) = SFF(a, SFF(b, c)) = SFF( SFF(a, b), c)$}$

Eksempel 12:

$SFF(12, 18, 30) = SFF(12, SFF(18, 30)) = SFF(12, 6) = 6$.

Eller

$SFF(12, 18, 30) = SFF(SFF(12, 18), 30) = SFF(6, 30) = 6$.

Finne største felles faktor

Vi kan finne største felles faktor til to tall ved å primtallsfaktorisere tallene og multiplisere sammen de primtallsfaktorene som er felles.

Eksempel 13:

Vi skal finne $SFF(30, 72)$. Vi har at $30 = 2 \cdot 3 \cdot 5$ og $72 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3$. Vi ser at ett totall og ett tretall er felles, derfor er $SFF(30, 72) = 2 \cdot 3 = 6$, som er det samme som vi fant i eksempel 11.

Oppgave 4:

Bruk metoden med primtallsfaktorisering til å finne $SFF(168, 140)$, og benytt resultatet til å forkorte brøken ${\large \frac{140}{168}}$ så langt det går.

Se løsningsforslag

Finne største felles faktor i GeoGebra og regneark

I GeoGebra kan vi beregne SFF ved hjelp av funksjonen sfd eller gcd. Skriver vi for eksempel sfd(30, 72) eller gcd(30, 72) i inntastingsfeltet, svarer GeoGebra med 6 i algebrafeltet,  det samme som vi fant i eksempel 10. Vil vi finne SFF til mer enn to tall samtidig, må vi angi tallene som ei liste, det vil si mellom krøllparenteser, atskilt med komma. Vil vi for eksempel finne SFF(4, 6, 10), skriver vi sfd({4, 6, 10}) eller gcd({4, 6, 10}) i inntastingsfeltet.

I regneark som Excel kan vi finne største felles faktor for et vilkårlig antall positive heltall med funksjonen sff. Vil vi for eksempel finne SFF(4, 6, 10), skriver vi =sff(4; 6; 10). 

Selv om største felles faktor er definert for negative tall, gir imidlertid Excel feilmelding hvis vi prøver å bruke sff på negative tall. Det problemet kan vi omgå ved å ta absoluttverdien til negative tall ved hjelp av funksjonen abs. Skal vi for eksempel beregne SFF(-18, 30), skriver vi =sff(abs(-18); 30).

GeoGebra kan imidlertid finne SFF til negative tall. Skal vi for eksempel beregne SFF(-18, 30), skriver vi sfd(-18, 30) eller gcd(-18, 30) i inntastingsfeltet.

Euklids algoritme for å finne største felles faktor

Å finne største felles faktor til to tall ved å primtallsfaktorisere tallene og så sammenlikne de enkelte faktorene vil kunne være helt uoverkommelig for store tall. Vi skal derfor se på en strukturert metode til å finne største felles faktor uten å gå veien om de enkelte primfaktorene.

Euklids algoritme er en systematisk måte å erstatte heltallpar med mindre heltallpar på, uten at parenes største felles faktor endres.

I artikkelen om delelighet lærte vi divisjonsalgoritmen: Hvis $a \in \mathbb Z, b \in \mathbb N$, vil det alltid finnes unike heltall, $q$ og $r$ slik at $a = qb + r$, der $0 \le r < b$. Da gjelder følgende sammenheng:

$\fbox{$\text{Hvis } a = qb + r \text{, vil } SFF(a, b) = SFF(b, r)$}$

Største felles faktor til $a$ og $b$ vil altså være den samme som største felles faktor til $b$ og resten, $r$, vi får når vi utfører divisjon med rest på $a$ og $b$.

Euklids algoritme baserer seg på å gjentatte ganger bytte $a$ og $b$ med $b$ og $r$ i divisjonsalgoritmen inntil $r = 0$. Algoritmen forutsetter egentlig at $a \ge 0$, men siden SFF er uavhengig av tallenes fortegn, kan vi ved å operere på absoluttverdier også bruke algoritmen på negative tall. Algoritmen er oppkalt etter matematikeren Euklid fra Alexandria.

Eksempel 14:

Vi skal finne $SFF(63, 30)$.

Vi har da $a = 63$ og $b = 30$.

Vi finner $q = {\large \lfloor \frac{63}{30} \rfloor} = 2$ og $r = 63 – 2 \cdot 30 = 3$. Så $63 = 2 \cdot 30 + 3$.

Følgelig er $SFF(63, 30) = SFF(30, 3)$.

Vi har da $a = 30$ og $b = 3$.

Vi finner $q = {\large \lfloor \frac{30}{3} \rfloor} = 10$ og $r = 30 – 10 \cdot 3 = 0$. Så $30 = 10 \cdot 3 + 0$.

Følgelig er $SFF(30, 3) = SFF(3, 0)  = 3$.

Så $SFF(63, 30) = 3$.

Eksempel 15:

Vi skal finne $SFF(252, 198)$.

Vi finner $q = {\large \lfloor \frac{252}{198} \rfloor} = 1$, og $r = 252 – 1 \cdot 198 = 54$. Så $252 = 1 \cdot 198 + 54$.

Følgelig er $SFF(252, 198) = SFF(198, 54)$.

Vi finner $q = {\large \lfloor \frac{198}{54} \rfloor} = 3$, og $r = 198 – 3 \cdot 54 = 36$. Så $198 = 3 \cdot 54 + 36$.

Følgelig er $SFF(198, 54) = SFF(54, 36)$.

Vi finner $q = {\large \lfloor \frac{54}{36} \rfloor} = 1$, og $r = 54 – 1 \cdot 36 = 18$. Så $54 = 1 \cdot 36 + 18$.

Følgelig er $SFF(54, 36) = SFF(36, 18)$.

Vi finner $q = {\large \lfloor \frac{36}{18} \rfloor} = 2$, og $r = 36 – 2 \cdot 18 = 0$. Så $36 = 2 \cdot 18 + 0$.

Følgelig er $SFF(36, 18) = SFF(18, 0) = 18$.

Så $SFF(252, 198) = 18$.

Dette nettstedet har en app som finner SFF ved hjelp av Euklids algoritme. Hvis du der huker av for "Vis utregning", lister appen opp trinnene i utregningen, det kan være veldig instruktivt. Appen finner også minste felles multiplum, som vi tar for oss litt lenger ned.

Oppgave 5:

Bruk Euklids algoritme til å finne $SFF(1365, 495)$. for hånd, og og bruk deretter appen som finner SFF til å sjekke at du har regnet riktig.

Se løsningsforslag

Når vi skal løse kongruenslikninger og diofantiske likninger, kommer vi til å bruke Euklids algoritme baklengs. Det vil være enklere å få til hvis vi har en skikkelig forståelse av hvordan algoritmen virker. Vi ser først på et formelt bevis. Her benytter vi oss av regelen om lineære kombinasjoner som vi lærte i artikkelen om delelighet: Hvis $t$ er en faktor i $a$ og $t$ er en faktor i $b$, vil $t$ være en faktor i alle lineære kombinasjoner av $a$ og $b$.

Vi har altså likningen $a = qb + r$.

Hvis $t$ er en faktor i både $b$ og $r$, vil $t$ følgelig også være en faktor i $a$, som er en lineær kombinasjon av $b$ og $r$.

Vi bytter så om på leddene og skriver likningen som $r = a – qb$.

Hvis nå $t$ er en faktor i både $a$ og $b$, vil $t$ følgelig også være en faktor i $r$, som er en lineær kombinasjon av $a$ og $b$.

Vi har derved vist at alle faktorer som er felles for $a$ og $b$ også er felles for $b$ og $r$. Derved vil største felles faktor også være den samme.

Det som gjenstår er da å argumentere for at resten blir mindre hver gang vi bruker divisjonsalgoritmen, slik at vi er garantert at den på ett eller annet tidspunkt blir $0$.

Første gang vi bruker divisjonsalgoritmen, får vi

$a = q_1b + r_1$ , der $0 \le r_1 < b$.

Siden vi så erstatter $a$ med $b$ og $b$ med $r_1$, får vi andre gang

$b = q_2r_1 + r_2$, der $0 \le r_2 < r_1$.

Fordi vi bare opererer med hele tall, betyr $r_2 < r_1$ at $r_2$ må være minst $1$ mindre enn $r_1$. For hver gang vi bruker divisjonsalgoritmen på denne måten, reduseres altså resten med minst $1$. Siden den i utgangspunktet var mindre enn $b$, vil den bli $0$ i løpet av maksimalt $b -1$ trinn.

En fin illustrasjon av å finne SFF ved hjelp av Euklids algoritme er å tenke seg at vi skal fylle et rektangel med kvadratiske ruter. Skal rutene passe inn, må de ha en sidelengde som går opp i både høyden og bredden på rektangelet, slik at vi kan legge et helt antall ruter både i høyden og bredden. Den største sidelengden en rute kan ha, er det største tallet som går opp i både høyde og bredde, altså SFF(h, b).

Eksempel 16:

Vi skal fylle et rektangel med størrelse 50×15 med kvadratiske ruter, og bruker Euklids algoritme til å finne SFF(50, 15).

I første trinn får vi $50 = 15 \cdot 3 + 5$.

Det betyr at rektangelet rommer 3 hele ruter på 15×15, men at det blir et resterende, lite rektangel på 5×15, som illustrert under:

Illustrasjon av første trinn med å fylle 15 * 50 med kvadratiske ruter

I andre trinn får vi $15 = 3 \cdot 5 + 0$.

Det betyr at det lille rektangelet rommer 3 hele ruter på 5×5 uten at det blir plass til overs, som illustrert under:

Illustrasjon av andre trinn med å fylle 15 * 50 med kvadratiske ruter

Siden størrelsen på det lille rektangelet er avledet av størrelsen på det store rektangelet gjennom divisjonsalgoritmen, er største felles faktor til sidelengdene i det lille rektangelet lik største felles faktor til sidelengdene i det store rektangelet. Med andre ord vil de største rutene som nøyaktig dekker det lille rektangelet også være de største rutene som nøyaktig dekker det store rektangelet.

De største kvadratiske rutene som nøyaktig vil dekke et rektangel på 50×15 er derfor 5×5.

I eksempel 16 fant vi størrelsen på rutene i løpet av to trinn i Euklids algoritme. Må vi bruke flere trinn, vil hvert trinn representere en inndeling i mindre ruter.

Hvor mange trinn vi må gå gjennom med Euklids algoritme, vil variere. Hvis $b \mid a$, vil vi bare trenge ett trinn fordi $r$ da allerede i første trinn vil bli null. Får vi i hvert trinn $q = 1$, vil tallverdiene bli redusert langsomt, og det kan hende vi vil trenge mange trinn. Dette vil være tilfelle hvis vi skal finne SFF til to etterfølgende fibonaccitall. Dersom $a_n$, $a_{n-1}$ og $a_{n-2}$ er tre etterfølgende fibonaccitall og vi prøver å finne $SFF(a_n, a_{n-1})$, vil vi i første trinn få $a_n = 1 \cdot a_{n-1} + a_{n-2}$. For det er jo slik fibonaccitallene er bygget opp, hvert tall er summen av de to foregående. Og slik vil det fortsette. Vi vil få $a_{n-1} = 1 \cdot a_{n-2} + a_{n-3}$ og så videre.

Den franske matematikeren Gabriel Lamé har imidlertid vist at antall trinn i Euklids algoritme aldri vil være flere enn fem ganger antall sifre i det minste tallet vi vil finne SFF til. For eksempel vil SFF(144, 89) bli beregnet i maksimalt $5 \cdot 2 = 10$ trinn.

Euklids algoritme kan ikke brukes hvis b = 0, men SFF(a, 0) = |a|, for alle hele tall, a. Det kan kanskje virke litt underlig, men |a| er det største tallet som går opp i a, og |a| går også opp i 0 fordi $0 = |a| \cdot 0$.

Setter vi a = 0, følger det at SFF(0, 0) = 0.

Minste felles multiplum

Beslektet med største felles faktor er minste felles multiplum. Minste felles multiplum til to heltall, $a$ og $b$, er det minste positive heltallet som er delelig med både $a$ og $b$. På dette nettstedet skriver vi minste felles multiplum til $a$ og $b$ som $MFM(a, b)$. I andre artikler og bøker vil vi imidlertid kunne støte på betegnelsen LCM, for "Least Common Multiple", eller at $a$ og $b$ bare listes mellom klammeparenteser, som $[a, b]$.

Siden MFM er definert som positivt, vil MFM(a, b) være uavhengig av fortegnet til a og b. Vi bruker derfor bare positive a og b i eksempler og oppgaver med MFM.

Et spesialtilfelle som ikke er helt i henhold til definisjonen, er MFM(a, 0) = 0, for alle hele tall, a, og følgelig MFM(0, 0) = 0.

På ei tallinje kan vi illustrere minste felles multiplum til to tall, $a$ og $b$, ved å legge et linjestykke med lengde $a$ etter seg selv og et linjestykke med lengde $b$ etter seg selv. $MFM(a, b)$ vil da være det første tallet begge linjestykkene treffer i.

Eksempel 17:

$MFM(4, 6) = 12$, fordi $12$ er det minste tallet som er delelig på både $4$ og $6$.

Dette er illustrert under, der det første tallet linjestykkene med lengde $4$ og $6$ begge treffer i er $12$.

Illustrasjon av at SFF(4, 6) = 12

Begge linjene vil videre treffe i alle multipler av $12$.

Minste felles multiplum får vi blant annet bruk for når vi skal finne fellesnevner for brøker, slik det er beskrevet i algebraartikkelen om brøkregning.

Finne minste felles multiplum

Vi kan finne minste felles multiplum til to tall, $a$ og $b$, ved først å primtallsfaktorisere tallene, så stryke like mange forekomster av faktorene i tall $b$ som det antall ganger de forekommer i $a$, og til slutt multiplisere alle faktorene som ikke er strøket.

Eksempel 18:

Vi skal finne $MFM(4, 6)$. Vi har at $4 = 2 \cdot 2$ og $6 = 2 \cdot 3$. Vi ser at faktor $2$ i $b = 6$ forekommer én gang i $a = 4$, og kan strykes, så får $MFM(4, 6) = 2 \cdot 2 \cdot {\not 2} \cdot 3 = 12$, som er det samme som vi fant i eksempel 17.

Eksempel 19:

Vi skal finne $MFM(60, 24)$. Vi har at $60 = 2 \cdot 2 \cdot 3 \cdot 5$ og $24 = 2 \cdot 2 \cdot 2 \cdot 3$. Vi ser at faktor $2$ i $b = 24$ forekommer to ganger i $a = 60$, og kan strykes to ganger. Faktor $3$ i $b = 24$ forekommer én gang i $a = 60$, og kan strykes én gang. Så $MFM(60, 24) = 2 \cdot 2 \cdot 3 \cdot 5 \cdot {\not 2} \cdot {\not 2} \cdot 2 \cdot {\not 3} = 120$.

En annen måte å gjøre det samme på er å skrive tallene som potenser av primfaktorene, slik det er beskrevet i artikkelen om primtall, og så multiplisere de høyeste potensene av hver faktor. Vi illustrerer med tallene fra eksempel 19:

Eksempel 20:

Vi skal finne $MFM(60, 24)$. Vi har at $60 = 2^2 \cdot 3^1 \cdot 5^1$ og $24 = 2^3 \cdot 3^1$. Vi ser at høyeste potens av $2$ er $3$, og høyeste potens av $3$ og $5$ er $1$. Så $MFM(60, 24) = 2^3 \cdot 3^1 \cdot 5^1 = 120$.

Når vi skal addere brøker med ulik nevner, utvider vi brøkene med nevnernes minste felles multiplum.

Eksempel 21:

 Vi skal beregne ${\large \frac{1}{60}} + {\large \frac{1}{24}}$. Fra eksempel 20 vet vi at $MFM(60, 24) = 120$. Vi må altså utvide brøkene ved å multiplisere med 120 i teller og nevner:

${\large \frac{1}{60}} + {\large \frac{1}{24}} = {\large \frac{1}{60}} \cdot  {\large \frac{120}{120}} + {\large \frac{1}{24}} \cdot  {\large \frac{120}{120}}=  {\large \frac{\frac{120}{60}}{120}} + {\large \frac{\frac{120}{24}}{120}} = {\large \frac{2}{120}} + {\large \frac{5}{120}} = {\large \frac{7}{120}}$.

Oppgave 6:

Bruk metoden med primtallsfaktorisering til å finne $MFM(63, 135)$, og benytt resultatet til å regne ut $ {\large \frac{1}{63}} + {\large \frac{1}{135}}$.

Se løsningsforslag

Dersom to tall, $a$ og $b$, er innbyrdes primiske, inneholder ikke $b$ noen faktorer som også finnes i $a$, så det er ingen ting å stryke. Alle faktorene blir med i multiplikasjonen, så da har vi at $MFM(a, b) = a \cdot b$.

Eksempel 22:

Vi skal finne $MFM(20, 21)$. Vi har at $20 = 2 \cdot 2 \cdot 5$ og $21 = 3 \cdot 7$. Vi ser at ingen faktorer i $b = 21$ forekommer i $a = 20$, så ingen ting kan strykes. Vi får at $MFM(20, 21) = 2 \cdot 2 \cdot 5 \cdot 3 \cdot 7 = 420$. Som er det samme som $20 \cdot 21$.

Alternativt: $20 = 2^2 \cdot 5^1$ og $21 = 3^1 \cdot 7^1$. Multipliserer vi høyeste potens av alle faktorene, får vi $2^2 \cdot 3^1 \cdot 5^1 \cdot 7^1 = 420$.

Som vi nevnte i avsnittet om å finne største felles faktor, kan analyse av to talls primtallsfaktorer bli en uoverkommelig oppgave for store tall. Heldigvis finnes det en annen måte å finne MFM på, som benytter største felles faktor:

$\fbox{$MFM(a, b) = \frac{\displaystyle a \cdot b}{\displaystyle SFF(a, b)}$}$

Siden vi har en effektiv måte å finne SFF på, nemlig Euklids algoritme, har vi derved også en effektiv måte å finne MFM på.

Prinsippet i denne metoden å finne MFM på er egentlig den samme som ved primtallsfaktorisering, bare at vi da sløyfer de felles faktorene før vi multipliserer ut, her dividerer vi dem bort etterpå.

Eksempel 23:

Vi skal finne $MFM(252, 198)$.

I eksempel 15 fant vi at $SFF(252, 198) = 18$. Så vi får $MFM(252, 198) = \frac{\displaystyle 252 \cdot 198}{\displaystyle 18} = 2772$.

Dette nettstedet har en app som finner MFM på denne måten.

Oppgave 7:

Benytt at $SFF(3528, 9450) = 126$ til å finne $MFM(3528, 9450)$. Regn for hånd, og brukk derette appen som finner MFM til å sjekke at du har regnet riktig.

Se løsningsforslag

Vi kan finne MFM til mer enn to tall ved å finne MFM til to tall av gangen, på samme måte som vi finner SFF til mer enn to tall.

Eksempel 23:

$MFM(12, 18, 30) = MFM(12, MFM(18, 30)) = MFM(12, 90) = 180$.

Eller

$MFM(12, 18, 30) = MFM(MFM(12, 18), 30) = MFM(36, 30) = 180$.

Finne minste felles multiplum  i GeoGebra og regneark

I GeoGebra kan vi beregne MFM ved hjelp av funksjonen mfm eller lcm. Skriver vi for eksempel mfm(252, 198) eller lcm(252, 198) i inntasingsfeltet, svarer GeoGebra med 2772 i algebrafeltet, det samme som vi fant i eksempel 6.  Vil vi finne MFM til mer enn to tall samtidig i GeoGebra, må vi angi tallene som ei liste, det vil si mellom krøllparenteser, atskilt med komma. Vil vi for eksempel finne MFM(4, 6, 10), skriver vi mfm({4, 6, 10}) eller lcm({4, 6, 10}) i inntasingsfeltet.

I regneark som Excel kan vi finne minste felles multiplum for et vilkårlig antall positive heltall med funksjonen mfm. Vil vi for eksempel finne MFM(4, 6, 10), skriver vi =mfm(4; 6; 10).

Selv om minste felles multiplum er definert for negative tall, gir imidlertid Excel feilmelding hvis vi prøver å bruke mfm på negative tall. Det problemet kan vi omgå ved å ta absoluttverdien til negative tall ved hjelp av funksjonen abs. Skal vi for eksempel beregne MFM(-18, 30), skriver vi =mfm(abs(-18); 30).

GeoGebra kan imidlertid finne MFM til negative tall. Skal vi for eksempel beregne MFM(-18, 30), skriver vi mfm(-18, 30) eller lcm(-18, 30) i inntastingsfeltet.

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
  • Wikipedia