Felles faktorer
I artikkelen om faktorisering ser vi hvordan tall kan deles opp i faktorer. Felles faktorer til to tall er naturlig nok faktorer som forekommer i begge tallene.
Eksempel 1:
24 har faktorene ±1, ±2, ±3, ±4, ±6, ±8, ±12, ±24.
32 har faktorene ±1, ±2, ±4, ±8, ±16, ±32.
Felles faktorer for 24 og 32 er derved ±1, ±2, ±4, ±8.
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). Andre steder 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 2:
SFF(24, 32) = 8, som vi kan se av eksempel 1.
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 3:
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.
±1 går opp i alle heltall.
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 4:
Vi skal finne SFF(4, 12).
Siden 4 | 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.
Siden alle tall går opp i 0, har vi at for alle a at
$\fbox{$SFF(a, 0) = |a|$}$
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 5:
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 6:
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 7:
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.
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 2 fant vi at SFF(24, 32)= 8. Da er $SFF({\large \frac{24}{8}}, {\large \frac{32}{8}}) = SFF(3, 4) = 1$.
Finne største felles faktor
Multiplisere primtallsfaktorer
Vi kan finne største felles faktor til to tall ved å primtallsfaktorisere tallene og multiplisere sammen de primtallsfaktorene som er felles.
Eksempel 10:
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 6.
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.
Bruke 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.
Bruke Euklids algoritme
Å 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. Algoritmen er oppkalt etter matematikeren Euklid fra Alexandria.
I artikkelen om delelighet beskriver 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 to tall, a og b, vil altså være den samme som største felles faktor til b og resten, r, som 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.
Eksempel 11:
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 12:
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.
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.
Det følgende er formelt bevis for Euklids algoritme. Her benytter vi oss av regelen om lineære kombinasjoner, som beskrives 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 tar utgangspunkt i likningen a = qb + r.
Hvis t er en faktor i både b og r, vil t 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 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 13:
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 13 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.
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
Se film der utregningene vises