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 · 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å 3. kvadratsetning, altså at a2 − b2 = (a + b)(a − b). Et heltall som kan skrives som en differanse av to kvadrattall, a2 og b2, 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 = a2 − b2. Vi skriver først likningen som b2 = a2 − 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 · 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 b2 = (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 b2 = (12)2 − 119 = 144 − 119 = 25.
25 er et kvadrattall, 52.
Vi kan derved skrive 119 som en differanse av to kvadrattall, 122 − 52, og følgelig kan 119 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 b2 = (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 b2 = (4)2 − 7 = 16 − 7 = 9.
9 er et kvadrattall, 32.
Vi kan derved skrive 7 som en differanse av to kvadrattall, 92 − 42, og følgelig kan 7 faktoriseres som (4+3)(4−3) = 17 · 7. 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 · 1. 17, og følgelig er et primtall.
Bruk Fermats metode til å faktorisere 189.
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 · 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:
- La n være tallet som skal faktoriseres, la f være en faktor som skal sjekkes, la p1, p2, … , p3 være primtallene fra 2 og oppover, og la l være ei liste over faktorer som er funnet. Lista er i utgangspunktet tom.
- Sett f lik pm=1, altså første primtall.
- 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.
- Hvis divisjonen n : f ikke går opp, er f ikke en faktor. I så fall:
Sett f lik pm+1, altså neste primtall.
- Gjenta trinn 3 og 4 så lenge f er mindre eller lik $\lfloor \sqrt n \rfloor$.
- 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 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.
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.
Bruk «brute force»-algoritmen til å faktorisere 1660 for hånd, og sjekk deretter utregningene med appen som primtallsfaktoriserer.
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 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.
 |
 |
 |
Felles faktorer
Felles faktorer til to tall er naturlig nok faktorer som forekommer i begge tallene.
Eksempel 4:
24 har faktorene ±1, ±2, ±3, ±4, ±6, ±8, ±12, ±24, som vi så i eksempel 3.
32 har faktorene ±1, ±2, ±4, ±8, ±16, ±32.
Felles faktorer for 24 og 32 er derved ±1, ±2, ±4, ±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 utgjør produktet av alle primtallsfaktorene som er felles for a og 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, positive 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.
Hvis et tall, b, er en faktor i et tall, 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 | 2, 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.
Siden alle tall går opp i 0, har vi at for alle a at
$\fbox{$SFF(a, 0) = |a|$}$
±1 går opp i alle heltall.
Innbyrdes primiske tall
To heltall, a og b, sies å være innbyrdes primiske hvis de ikke har andre felles faktorer enn ±1, det vil si at SFF(a, b) = 1. Det betyr imidlertid ikke at a eller b er primtall. Andre betegnelser for det samme er koprimisk og relativt primisk.
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 2 fant vi at SFF(24, 32) = 8. Da er for eksempel SFF(24 + 32, 32) = SFF(56, 32) = 8 og SFF(24 + 3 · 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 · 30) = SFF(30, 12) = SFF(30 − 2 · 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 · 3 · 5 og 72 = 2 · 2 · 2 · 3 · 3. Vi ser at ett totall og ett tretall er felles, derfor er SFF(30, 72) = 2 · 3 = 6, som er det samme som vi fant i eksempel 11.
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.
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 primtallsfaktorene.
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 ≤ 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. SFF vil da være den verdien a har når r = 0. Algoritmen forutsetter egentlig at a ≥ 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 · 30 = 3.
Så 63 = 2 · 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 · 3 = 0. Så 30 = 10 · 3 + 0.
Følgelig er SFF(30, 3) = SFF(3, 0) = 3.
Vi har da at a = 3 og r = 0.
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 · 198 = 54.
Så 252 = 1 · 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 · 54 = 36.
Så 198 = 3 · 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 · 36 = 18.
Så 54 = 1 · 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 · 18 = 0.
Så 36 = 2 · 18 + 0.
Følgelig er SFF(36, 18) = SFF(18, 0) = 18.
Vi har da at a = 18 og r = 0.
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.
Bruk Euklids algoritme til å finne SFF(1365, 495) for hånd, og bruk deretter appen som finner SFF til å sjekke at du har regnet riktig.
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 = q1b + r1 , der 0 ≤ r1 < b.
Siden vi så erstatter a med b og b med r1, får vi andre gang
b = q2r1 + r2, der 0 ≤ r2 < r1.
Fordi vi bare opererer med hele tall, betyr r2 < r1 at r2 må være minst 1 mindre enn r1. 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 · 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:
I andre trinn får vi 15 = 3 · 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:
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. Ofte vil vi måtte bruke flere trinn, hvert trinn vil da representere en inndeling i mindre ruter.
Hvor mange trinn vi må gå gjennom med Euklids algoritme, vil variere. Hvis b | 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 an, an–1 og an–2 er tre etterfølgende fibonaccitall og vi prøver å finne SFF(an, an–1), vil vi i første trinn få an = 1 · an–1 + an–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å an–1 = 1 · an–2 + an–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 · 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| · 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 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.
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 · 2 og 6 = 2 · 3. Vi ser at faktor 2 i b = 6 forekommer én gang i a = 4, og kan strykes, så vi får MFM(4, 6) = 2 · 2 · 2 · 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 · 2 · 3 · 5 og 24 = 2 · 2 · 2 · 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 · 2 · 3 · 5 · 2 · 2 · 2 · 3 = 120.
En annen måte å gjøre det samme på er å skrive tallene som potenser av primtallsfaktorene, 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 = 22 · 31 · 51 og 24 = 23 · 31. Vi ser at høyeste potens av 2 er 3, og høyeste potens av både 3 og 5 er 1. Så MFM(60, 24) = 23 · 31· 51 = 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{\Large \frac{120}{60}}{120}} + {\large \frac{\Large \frac{120}{24}}{120}} = {\large \frac{2}{120}} + {\large \frac{5}{120}} = {\large \frac{7}{120}}$
Bruk metoden med primtallsfaktorisering til å finne MFM(63, 135), og benytt resultatet til å regne ut $ {\large \frac{1}{63}} + {\large \frac{1}{135}}$.
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 · b.
Eksempel 22:
Vi skal finne MFM(20, 21). Vi har at 20 = 2 · 2 · 5 og 21 = 3 · 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 · 2 · 5 · 3 · 7 = 420. Som er det samme som 20 · 21.
Alternativt: 20 = 22 · 51 og 21 = 31 · 71. Multipliserer vi høyeste potens av alle faktorene, får vi 22 · 31 · 51 · 71 = 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.
Benytt at SFF(3528, 9450) = 126 til å finne MFM(3528, 9450). Regn for hånd, og bruk deretter appen som finner MFM til å sjekke at du har regnet riktig.
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 inntastingsfeltet, 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 inntastingsfeltet.
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
