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 $2 = 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.

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$. I GeoGebra heter den tilsvarende funksjonen ceil. I GeoGebra er desimalskilletegn punktum, ikke komma, så hvis vi vil finne $\lceil-2{,}75 \rceil$ i GeoGebra, skriver vi ceil(-2.75).

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.

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 7$.

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
Oppgave 3:

Bruk "brute force"-algoritmen til å faktorisere $1660$.

Se løsningsforslag

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.

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)$ alltid være samme, positive heltall, 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$ er 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)$.

Se løsningsforslag

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, b \in \mathbb Z, b > 0$, 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 heltallsdividerer $a$ med $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$.

Oppgave 5:

Bruk Euklids algoritme til å finne $SFF(1365, 495)$.

Se løsningsforslag

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.

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 måte å illustrere Euklids algoritme på er å tenke seg at vi skal fylle et rektangel med kvadratiske ruter. Sidelengden på den største ruten vi kan fylle rektangelet med vil være lik største felles faktor til rektangelets lengde og bredde.

Eksempel 16:

Vi skal fylle et rektangel med størrelse 50×15 med kvadratiske ruter, og skal finne ut hvor store ruter vi kan bruke.

De største rutene vi kan bruke, har sidelengde på $SFF(50, 15)$, fordi det er den største sidelengden som vil gå opp i både rektangelets lengde og bredde.

Så bruker vi Euklids algoritme til å finne SFF.

I første trinn har vi $a = 50$, $b = 15$, og divisjonsalgoritmen gir $50 = 3 \cdot 15 + 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

Fra første trinn i Euklids algoritme har vi altså $b = 15$ og $r = 5$, så i andre trinn skal vi finne  $SFF(15, 5)$. Dette er sidelengden til de største rutene vi kan bruke til å fylle det lille rektangelet, fordi det er den største sidelengden som vil gå opp i både rektangelets lengde og bredde.

Divisjonsalgoritmen gir $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

Og så kommer det store poenget: Størrelsen på det lille rektangelet er avledet av størrelsen på det store rektangelet gjennom divisjonsalgoritmen. Største felles faktor til sidelengdene i det lille kvadratet er derfor den samme som største felles faktor til sidelengdene i det store kvadratet. Med andre ord vil de største rutene som dekker det lille rektangelet også være de største rutene som dekker det store rektangelet.

De største kvadratiske rutene som 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.

I regneark som Excel kan vi finne største felles faktor for et vilkårlig antall positive heltall med funksjonen sff. Selv om største felles faktor er definert for negative tall, gir Excel feilmelding hvis vi prøver å bruke sff på negative tall. Det problemet kan vi omgå med å ta absoluttverdien til negative tall ved hjelp av funksjonen abs. Skal vi for eksempel beregne $SFF(-18, 30)$, skriver vi =sff(abs(-18); 30). I GeoGebra heter funksjonen for å finne SFF sfd eller gcd. GeoGebra godtar også negative tall, for eksempel sfd(-18, 30). Vil vi finne SFF 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 $SFF(4, 6, 10)$, skriver vi sfd({4, 6, 10}) eller gcd({4, 6, 10}).

Minste felles multiplum

Beslektet med største felles faktor er minste felles multiplum. Minste felles multiplum til to positive heltall, $a$ og $b$, er det minste positive heltallet som er delelig med både $a$ og $b$. Minste felles multiplum er bare definert for positive heltall. 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]$.

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$.

Oppgave 6:

Bruk metoden med primtallsfaktorisering til å finne $MFM(63, 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 21:

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å.

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 22:

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$.

Oppgave 7:

Benytt at $SFF(3528, 9450) = 126$ til å finne $MFM(3528, 9450)$.

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$.

I regneark som Excel kan vi finne minste felles multiplum for et vilkårlig antall positive heltall med funksjonen mfm. I GeoGebra heter funksjonen for å finne MFM også mfm, men vi kan også bruke lcm. 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}).

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.
  • Gustavsen, TS, Hinna, K.R.C., Borge, I.C., Andersen P.S. (2014). QED 5-10, bind 2. Høyskoleforlaget
  • Wikipedia