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). Andre steder 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].

Et spesialtilfelle som avviker litt fra definisjonen, er MFM(a, 0) = 0. Dette gjelder for alle hele tall, a, og følgelig er også MFM(0, 0) = 0.

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.

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

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 algebra-artikkelen om brøkregning.

Finne minste felles multiplum

Kombinere primtallsfaktorer

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 tall a, og til slutt multiplisere de gjenstående faktorene i begge tall.

Eksempel 2:

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

Eksempel 3:

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

Eksempel 4:

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

 Vi skal beregne ${\large \frac{1}{60}} + {\large \frac{1}{24}}$. Fra eksempel 4 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}}$

Oppgave 1:

Vi vet at 63 = 3 · 3 · 7 og at 135 = 3 · 3 · 3 · 5.

Bruk dette 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 ingenting å stryke. Alle faktorene blir med i multiplikasjonen, så da har vi at MFM(a, b) = a · b.

Eksempel 6:

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

Bruke SFF

Som vi nevner i avsnittet om å finne største felles faktor, kan sammenlikning av to talls primtallsfaktorer bli en uoverkommelig oppgave for store tall. Heldigvis finnes det en måte å finne MFM på som ikke krever faktorisering, men baserer seg på 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 ved den metoden sløyfer de felles faktorene før vi multipliserer ut, her dividerer vi dem bort etterpå.

Eksempel 7:

Vi skal finne MFM(252, 198).

I eksempel 12 i artikkelen om største felles faktor 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 2:

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.

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

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.

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

Største felles faktor

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.

Illustrasjon av faktorer og felles faktorer i 8 og 12

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

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

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.

Oppgave 1:

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

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.

Oppgave 2:

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.

Se løsningsforslag

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 = aqb.

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:

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

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:

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 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 anan–1 og an–2 er tre etterfølgende fibonaccitall, og vi prøver å finne SFF(anan–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

Faktorisering

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

Primtallsfaktorisering

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

Fermats faktoriseringsmetode

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

Metoden går ut på at vi prøver å faktorisere et heltall, n, ved å finne heltall, a og b, slik at n = a2b2. Vi skriver først likningen som b2 = a2n. 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 b2 da blir et kvadrattall. Hvis ikke, prøver vi a + 1 og gjentar prosessen inntil vi finner en b2 som er et kvadrattall. Hvis vi ender opp med at n = n · 1, er n et primtall.

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

Eksempel 1:

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

Vi får b2 = a2 − n = (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 = a2 − n = (12)2 − 119 = 144 − 119 = 25.

25 er et kvadrattall, 52.

Vi har altså at a2 = 122 og b2 = 52.

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

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

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

Vi får b2 = a2 − n = (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 = a2 − n = (4)2 − 7 = 16 − 7 = 9.

9 er et kvadrattall, 32.

Vi har altså at a2 = 42 og b2 = 32.

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

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

b2 = a2 − n = (9)2 − 17 = 81 − 17 = 64.

64 er et kvadrattall, 82.

Vi har altså at a2 = 92 og b2 = 82.

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

Oppgave 1:

Bruk Fermats metode til å faktorisere 189.

Se løsningsforslag

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

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

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

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

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

Brute force faktorisering

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

Litt mer formelt kan metoden beskrives algoritmisk slik:

    1. 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.
       
    2. Sett f lik pm=1, altså første primtall.
       
    3. Hvis divisjonen nf går opp, er f en faktor. I så fall:
      Føy f til i lista l.
      Sett n = nf.
       
    4. Hvis divisjonen nf ikke går opp, er f ikke en faktor. I så fall:
      Sett f lik pm+1, altså neste primtall.
       
    5. Gjenta trinn 3 og 4 så lenge f er mindre eller lik $\lfloor \sqrt n \rfloor$.
       
    6. l inneholder nå ei liste over alle primtallsfaktorene i n. Er l tom, er n et primtall.

Eksempel 2:

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

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

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

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

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

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

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

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

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

Oppgave 2:

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

SkjermfilmSe film der løsningsforslaget vises

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

Oppgave 3:

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

Se løsningsforslag

Heltallsfaktorisering

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

Eksempel 3:

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

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

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

Blokker brukt som illustrasjon av faktorisering av 12

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.

Faktoriseringstre Faktoriseringstre Faktoriseringstre

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

Primtall

Hva er primtall?

Alle heltall større enn 1 er delelige med minst to positive heltall, nemlig 1 og tallet selv. Finnes det ikke flere positive heltall det er delelig med, er tallet et primtall. I motsatt fall er det et sammensatt tall. Det er vanlig å bruke symbolet p for å representere et primtall.

Studerer vi de første naturlige tallene, ser vi at:

1 ikke er et primtall fordi det ikke er større enn 1.

2 er et primtall fordi det bare er delelig med 1 og seg selv.

3 er et primtall fordi det bare er delelig med 1 og seg selv.

4 ikke er et primtall fordi det, i tillegg til å være delelig med 1 og seg selv, også er delelig med 2. Vi har at 4 : 2 = 2.

Alle partall er delelige med 2, derfor er 2 det eneste partallet som er et primtall.

På ei tallinje vil det bare være linjestykker med lengde 1 eller lengde lik primtallet selv som treffer i primtallet hvis vi legger dem etter seg selv, slik det er vist under for p = 7.

Illustrasjon av at ingen tall går opp i 7

Det er umulig å dele et primtall opp i mindre blokker med like mange elementer i hver. Derfor er det litt ironisk at sjokoladen Smil ifølge reklamen er «skapt for å deles», når den inneholder 13 biter, og 13 er et primtall. Den eneste måten å dele en Smil likt på er at noen får alle bitene, eller at 13 personer får 1 bit hver.

Eratosthenes′ såld

For å lage ei liste med alle primtall opp til et gitt tall, n, kan vi bruke en metode som heter Eratosthenes′ såld, der vi i gjentatte operasjoner stryker multipler av primtall, inntil vi står igjen med bare primtallene. Metoden kan beskrives algoritmisk slik:

    1. Lag ei liste av påfølgende heltall fra 2 til n.
       
    2. La p til å begynne med være lik 2, det første primtallet.
       
    3. Stryk alle multipler av p fra lista.
       
    4. Finn det neste tallet større enn p som står igjen på lista. Dette tallet er det neste primtallet. Sett p lik dette tallet.
       
    5. Gjenta trinn 3 og 4 inntil p er større enn $\sqrt n$.
       
    6. Alle gjenværende tall på lista er nå primtall.

Grunnen til at vi ikke trenger å sjekke høyere tall enn $\sqrt n$, er at hvis et tall, n, ikke er et primtall, kan det faktoriseres som a · b, der ab. Hvis tallet er et kvadrattall, vil $a = b = \sqrt n$. I motsatt fall vil $a < \sqrt n$ og $b > \sqrt n$. I begge tilfeller ser vi at vi vil ha funnet a når vi har sjekket alle tall opp til og med $\sqrt n$.

SkjermfilmSe film der Eratosthenes′ såld brukes på tallene opp til 60
 

Oppgave 1:

Bruk metoden med Eratosthenes′ såld til å finne alle primtall opp til 120. Hvilket primtall er det største du trenger å stryke multipler av?

​Se løsningsforslag

Teoremer om primtall

​Dersom et primtall går opp i et tall som er et produkt av to faktorer, vil det gå opp i minst én av faktorene. I motsatt fall måtte vi jo funnet litt av primtallet i den ene faktoren og litt i den andre, noe som er umulig siden primtall ikke kan deles opp. Kaller vi primtallet p og faktorene a og b, kan vi formulere dette som et teorem slik:

$\fbox{$\text{Hvis } p \mid ab \text{, vil } p \mid a \text{ eller }p \mid b$}$

Oppgave 2:

900 kan skrives som 20 · 45. Bruk teoremet over til å avgjøre om følgende er riktig:

      • 3 går opp i 900. Da går 3 opp i 45.
         
      • 5 går opp i 900. Da kan ikke 5 gå opp i både 20 og 45.

Se løsningsforslag

Så kommer vi til det som kalles tallteoriens fundamentalteorem. Det slår fast at ethvert heltall, n > 1, kan skrives som et produkt av primtall på en entydig måte.

Hvis dette hadde vært unike primtall, ville vi kunne skrevet det slik:

n = p1 · p2 · p3 · … · pr

Men et primtall kan naturligvis forekomme flere ganger, for eksempel er 12 = 2 · 2 · 3. Tar vi høyde for dette, får vi:

$\fbox{$n = p_1^{\large k_{\Large 1}} \cdot p_2^{\large k_{\Large 2}} \cdot p_3^{\large k_{\Large 3}} \cdot \, \dots \, \cdot p_r^{\large k_{\Large r}}$}$

Her er k et naturlig tall, noe vi uttrykker matematisk som $k \in \mathbb N$.

For eksempel er 40 = 23 · 51, her er k1 = 3, k2 = 1.

Det finnes uendelig mange primtall.

Beviset for dette er et såkalt reductio ad absurdum-bevis, der vi antar det motsatte av det vi vil bevise, og så påviser at antakelsen fører til en selvmotsigelse.

Det motsatte av at det finnes uendelig mange primtall er at det bare finnes et endelig antall primtall, la oss kalle dette antallet for r. Primtallene selv kaller vi p1, p2p3, … , pr. Her er p1 = 2, p2 = 3, p3 = 5, p4 = 7, p5 = 11, og så videre oppigjennom lista med primtall.

La oss kalle tallet vi får når vi multipliserer disse primtallene for A. Da vil A være delelig med samtlige av disse primtallene, for vi har jo at Ap1 · p2 · p3 · … · pr. Men A+1 vil ikke være delelig med noen av dem.

Ifølge fundamentalteoremet må likevel A+1, på linje med alle andre tall, være et unikt produkt av primtall. Og siden det ikke er noen av p1, p2p3, … , pr, må det finnes andre primtall enn disse. Påstanden om at det bare finnes et gitt antall, r, primtall kan derfor ikke være riktig. Utgangspunktet vårt, påstanden om at det finnes uendelig mange primtall, må derfor være riktig.

A+1 vil enten være et nytt primtall, eller tall satt sammen av andre primtallsfaktorer enn p1, p2p3, … , pr.

Eksempel 1:

Vi undersøker de tre første primtallene, 2, 3, 5, og får A+1 = 2 · 3 · 5 + 1 = 31. Dette er et nytt primtall. Det er imidlertid ikke det første primtall etter 5, vi har hoppet over primtallene 7, 11, 13, 17, 19, 23 og 29.

​Eksempel 2:

Vi undersøker de seks første primtallene, og får A+1 = 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031. Dette er et tall satt sammen av primtallsfaktorene 59 og 509.

Det vil finnes vilkårlig lange sekvenser med etterfølgende tall som ikke er primtall. Ta for eksempel tallet
4! = 4 · 3 · 2 · 1.
4! + 2 være delelig med 2.
4! + 3 vil være delelig med 3.
4! + 4 vil være delelig med 4.
Vi får altså en følge av minst tre tall som ikke er primtall.

Bak et vilkårlig tall, n!, vil det alltid følge n−1 tall som ikke er primtall, nemlig
n! + 2, n! + 3, … n! + n

NB! Dette betyr ikke at vi alltid må helt opp til n! + 2 for å finne en sekvens med n−1 sammensatte tall. Lar vi for eksempel n = 6, får vi 6! = 720, og den etterfølgende sekvensen med n−1 = 6−1 = 5 sammensatte tall blir 722, 723, 724, 725, 726. Men allerede etter tallet 23 følger fem sammensatte tall, 24, 25, 26, 27, 28.

På Internett kan vi finne lister over primtall, for eksempel har primes.utm.edu (First Fifty Million Primes) en liste over de første 50 000 000 primtallene.

Primtallsfunksjoner i GeoGebra

I GeoGebra kan vi bruke funksjonen erprimtall til å avgjøre om et tall er et primtall eller ikke. Skriver vi for eksempel erprimtall(12) i inntastingsfeltet, svarer GeoGebra med false i algebrafeltet. Skriver vi erprimtall(13), svarer GeoGebra med true

Vi kan primtallsfaktorisere et tall ved hjelp av funksjonen faktorer. GeoGebra presenterer da tallets faktorer i en matrise i algebrafeltet. Første kolonne inneholder primtallsfaktorene, andre kolonne hvor mange ganger hver enkelt faktor forekommer. Skriver vi for eksempel faktorer(294) i inntastingsfeltet, presenterer GeoGebra matrisen

$\begin{bmatrix}2 & 1\\3 & 1\\7 & 2\end{bmatrix}$ i algebrafeltet fordi 294 = 21 · 31 · 72.

Vi kan finne første primtall som kommer etter et vilkårlig tall med funksjonen nesteprimtall. Skriver vi for eksempel nesteprimtall(20) i inntastingsfeltet, svarer GeoGebra 23 i algebrafeltet. 

Tilsvarende kan vi finne siste primtall før et vilkårlig tall med funksjonen forrigeprimtall.

Største primtall

Det finnes ingen formel for å finne primtall, og en må basere seg på omstendelige utregninger for å vise at et tall virkelig er et primtall. Med moderne datateknologi kan imidlertid beregninger gjøres svært fort, og en har derfor funnet fram til svært høye primtall. Ifølge primes.utm.edu (Top Ten Record Primes) er det største primtallet som er kjent per desember 2024, lik 2136279841 − 1. Dette tallet har 41 024 320 sifre, skrev vi det ut med ett siffer per centimeter, ville det bli over 410 kilometer langt. Tallet ble registret i oktober 2024. Den tidligere rekorden stammer fra mars 2018, så det går en stund mellom hver gang et nytt største primtall blir funnet.

Primtallstvillinger

Dersom to tall, p og p + 2, begge er primtall, kalles de primtallstvillinger. Eksempel på primtallstvillinger er {5, 7}, {11, 13} og {17, 19}. Primtallstvillingene blir sjeldnere når p blir større. Ifølge primes.utm.edu (Ten Largest Known Twin Primes) er den største primtallstvillingen som er kjent per desember 2024 lik 2 996 863 034 895 · 21 290 000 − 1. Tallet har 388 342 sifre og ble registrert i september 2016. En vet ikke om det finnes uendelig mange primtallstvillinger.

Hypoteser om primtall

To hypoteser om primtall er at ethvert partall større enn 2 kan skrives som en sum av to primtall, og at ethvert partall kan skrives som differansen mellom to primtall på uendelig mange måter. Dette er altså påstander som en tror er riktige, men som ikke er bevist. Ingen har heller klart å komme opp med eksempler som motbeviser påstandene. Så her er en sjanse til å bli historisk!

En annen hypotese er at det finnes uendelig mange primtall som er 1 større enn et kvadrattall, altså på formen n2 + 1. For eksempel 22 + 1 = 5 og 42 + 1 = 17.

Men bortsett fra tallet 3 finnes det ingen primtall som er 1 mindre enn et kvadrattall, altså på formen n2 − 1.

Å begrunne dette er neste oppgave.

Oppgave 3:

Begrunn at det for n > 2 ikke finnes primtall på formen n2 − 1. Hint: konjugatsetningen baklengs.

Se løsningsforslag

Mersenne-primtall og perfekte tall

I gammel tid fantes det en hypotese om at alle tall på formen 2n − 1 var primtall når n var primtall, men sammensatte tall ellers. For eksempel, for primtallet 2 er 22 − 1 = 3 et primtall, for primtallet 3 er 23 − 1 = 7 et primtall, og for det sammensatte tallet 4 er 24 − 1 = 15 et sammensatt tall. Men bare halvparten av påstanden er riktig:

$\fbox{$\text{Hvis } n \text{ er et sammensatt tall, er } 2^n − 1 \text{ et sammensatt tall}$}$

Av dette følger at hvis 2n − 1 ikke er et sammensatt tall, er n ikke et sammensatt tall. Med andre ord:

$\fbox{$\text{Hvis } 2^n − 1 \text{ er et primtall, er } n \text{ et primtall}$}$

Men det motsatte er ikke alltid riktig. Bruker vi for eksempel primtallet 11, får vi 211 − 1 = 2047, som er et sammensatt tall, 2047 = 23 · 89.

Primtall på formen 2n − 1 kalles Mersenne-primtall, etter den franske munken Marin Mersenne. De første n som gir Mersenne-primtall er 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127.

En vet ikke om det finnes uendelig mange Mersenne-primtall. Ifølge primes.utm.edu (Ten Largest Known Mersenne Primes) er det største Mersenne-primtallet som er kjent per desember 2024, lik 2136279841 − 1, og det er også det største kjente primtallet, som nevnt tidligere. Alle de største primtallene som er kjent per desember 2024 er Mersenne-primtall. Dette skyldes antakelig at tall på denne formen er de enkleste for en datamaskin å verifisere at virkelig er primtall.

Et perfekt tall er et tall som er lik summen av sine egne ekte faktorer, det vil si alle hele, positive tall det kan deles med, som ikke er lik tallet selv. For eksempel er 6 = 1 + 2 + 3 et perfekt tall, det samme er 28 = 1 + 2 + 4 + 7 + 14.

Det viser seg at tallene, n, som gir Mersenne-primtall, produserer perfekte tall etter formelen 2(n − 1)(2n − 1).

For n = 2 får vi 2(2 − 1)(22 − 1) = 2 · 3 = 6

For n = 3 får vi 2(3 − 1)(23 − 1) = 4 · 7 = 28

For n = 5 får vi 2(5 − 1)(25 − 1) = 16 · 31 = 496

Oppgave 4:

De tre første perfekte tallene er 6, 28 og 496. Hva blir det fjerde perfekte tallet? Hint: Bruk formelen over og lista over de første n som gir Mersenne-primtall.

Se løsningsforslag

Primtallsetningen

Kjenner vi et oddetall, n, og vil finne neste oddetall, vet vi at det må bli n+2. Kjenner vi et tall, m, i fem-gangen og vil finne det neste, vet vi at det må bli m+5. Noe slikt system finnes ikke for primtall. Vi kan ikke ut fra et primtall, p, beregne hva det neste primtallet er. Men primtallene blir færre og færre jo lenger ut på tallinja vi går. Dette er jo rimelig, for jo større tallene er, jo flere mulige primtallsfaktorer finnes.

En har funnet ut at uttrykket $ \frac{\displaystyle n}{\displaystyle \ln n}$ gir et anslag over hvor mange primtall det finnes som ikke er høyere enn n.

Uttrykket er altså ikke helt nøyaktig, men gir kun et anslag. Det finnes for eksempel 168 primtall som ikke er høyere enn n = 1000, mens formelen gir ${\large \frac{1000}{\ln 1000}} \approx 144{,}7$.

Anslaget blir imidlertid mer og mer nøyaktig jo større n blir. Det virkelige antall primtall og anslaget blir like når n blir uendelig stor. Dette er primtallsetningen, som vi matematisk kan uttrykke slik, der p(n) er det virkelige antall primtall lavere enn n:

$\fbox{Primtallsetningen: ${\displaystyle \lim_{n \to \infty}}\; \frac{\displaystyle \text{ }p(n)\text{ }}{\frac{\displaystyle n}{\displaystyle \ln n}} = 1$}$

Oppgave 5:

Gjør et anslag over hvor mange primtall det finnes som er lavere enn 5 000 000.

Se løsningsforslag

Primtallsetningen ble foreslått av matematikeren Carl Friedrich Gauss på slutten av syttenhundretallet, og bevist på slutten av attenhundretallet. Siden har en imidlertid kommet fram til en funksjon som gir et mye bedre anslag over antall primtall:

$li(n) = \int \limits_2^n \frac{\displaystyle 1}{\displaystyle \ln x}dx$

For eksempel er li(1000) ≈ 176,56. Det kan vi regne ut i GeoGebra ved å skrive Integral(1 / ln(x), 2, 1000) i inntastingsfeltet.

Kilder

    • Breiteig, T. (2007). Bak tallene. Innføring i tallteori. Kompendium, Universitetet i Agder.
    • Rosen, Kenneth H. (1984). Elementary Number Theory and Its Applications. Addison-Wesley.
    • primes.utm.edu

Delelighet

Om delelighet

Når vi dividerer to heltall på hverandre, blir resultatet av og til et heltall, for eksempel er 24 : 8 = 3 og −21 : 3 = −7. Vi sier da at divisjonen går opp. Men resultatet kan også bli et tall med desimaler, for eksempel er 9 : 2 = 4,5. Vi sier da at divisjonen ikke går opp.

Generelt, hvis a og b er vilkårlige heltall, og a : b = t er et heltall, går divisjonen opp, og vi sier at a er delelig med b. Andre måter å si det samme på er at b går opp i a, at b er en divisor i a, eller at b er en faktor i a. I matematisk terminologi skriver vi dette som b | a. Det motsatte, at b ikke går opp i a, skriver vi som ba.

At divisjonen a : b = t går opp, kan vi tolke som at en blokk med a elementer kan deles opp i t blokker med b elementer i hver.

Vi kan også tolke det slik at hvis vi på ei tallinje legger b etter seg selv t ganger, havner vi i a.

Eksempel 1:

6 : 3 = 2

Det betyr at en blokk med a = 6 elementer kan deles opp i t = 2 blokker med b = 3 elementer i hver:

Illustrasjon av at 6:3 = 2 betyr at 6 elementer kan grupperes i 2 blokker med 3 elementer i hver

Legger vi b = 3 etter seg selv t = 2 ganger, havner vi i a = 6:

Illustrasjon av at 6:3 = 2 betyr at 3 går 2 ganger opp i 6

Eksempel 2:

8 : 2 = 4

Det betyr at en blokk med a = 8 elementer kan deles opp i t = 4 blokker med b = 2 elementer i hver:

Illustrasjon av at 8:4 = 2 betyr at 8 elementer kan grupperes i 4 blokker med 2 elementer i hver

Legger vi b = 2 etter seg selv t= 4 ganger, havner vi i a = 8.

Illustrasjon av at 8:2 = 4 betyr at 2 går 4 ganger opp i 8

Hvis a, b og c er heltall, der c er en faktor i b og b er en faktor i a, er c også en faktor i a.

En annen måte å si det samme på er at hvis a er delelig med b, og b er delelig med c, er a delelig med c.

I matematisk terminologi:

$\fbox{$\text {Hvis } c \mid b \text{ og } b \mid a \text{, vil } c \mid a$}$

Det betyr at hvis a kan deles opp i blokker med b elementer i hver og b kan deles opp i blokker med c elementer i hver, kan a deles opp i blokker med c elementer i hver.

Vi tar med et bevis for denne påstanden. Det er et direkte, algebraisk bevis, det vil si at vi ved manipulasjon av symboler demonstrerer at påstanden er riktig.

Hvis c | b, finnes det et heltall, k, slik at ck = b. Hvis b | a, finnes det et heltall, l, slik at bl = a. Vi har da at a = bl = (ck)l = c(kl). Siden k og l er heltall, er kl heltall. a kan derved skrives som c multiplisert med et heltall, noe som betyr at c | a og påstanden er bevist.

Eksempel 3:

2 er en faktor i 4, og 4 er en faktor i 8, derfor er 2 en faktor i 8. Eller, sagt på en annen måte, 8 er delelig med 4 og 4 er delelig med 2, derfor er 8 delelig med 2. Vi kan illustrere det med blokker slik:

Illustrasjon av tall som går opp i hverandre

og på ei tallinje slik:

Illustrasjon av tall som går opp i hverandre

Det er også slik at hvis et heltall, t, er en faktor i et annet, a, er det også en faktor i alle heltallige multipler av a.

En annen måte å si det samme på er at hvis a er delelig med t, er alle heltallige multipler av a også delelige med t.

Eksempel 4:

2 er en faktor i 4, derfor er 2 også en faktor i 8, 12, 16, 20 og så videre. Eller sagt på en annen måte, tallene 8, 12, 16, 20 og så videre er delelige med 4, derfor er de også delelige med 2. Vi kan illustrere det på ei tallinje slik:

Illustrasjon av at 2 går oppi multipler av 4

Mer generelt er det slik at hvis et heltall, t, er en faktor i to andre heltall, a og b, er det også en faktor i alle summer av heltallige produkter av a og b.

Sagt på en annen måte, hvis heltallene a og b er delelige med heltallet t, er alle summer av heltallige produkter av a og b også delelige med t.

I matematisk terminologi:

$\fbox{$\text {Hvis } t \mid a \text{ og } t \mid b \text{, vil } t \mid (ma + nb)$}$

Her er m og n vilkårlige heltall.

Tallet ma + nb kalles en lineær kombinasjon av a og b. Vi vil derfor referere til denne regelen som «regelen om lineære kombinasjoner».

Eksempel 5:

3 er en faktor i 6 og 9. Da er 3 en faktor i 57, fordi 57 kan skrives som en lineær kombinasjon av 6 og 9.
57 = 2 · 6 + 5 · 9.

7 er en faktor i 14 og 35. Da er 7 en faktor i 259, fordi 259 kan skrives som en lineær kombinasjon av 14 og 35.
259 = (−9) · 14 + 11 · 35.

Oppgave 1:

9 er en faktor i 18 og 27. Begrunn at 9 derfor er en faktor i 63.

Se løsningsforslag

Det er også slik at hvis a, b og c er heltall, der c er en faktor i a, men ikke en faktor i b, er c heller ikke en faktor i a + b.

En annen måte å si det samme på er at hvis a er delelig med c, men b ikke er delelig med c, er a + b ikke delelig med c.

I matematisk terminologi:

$\fbox{$\text {Hvis } c \mid a \text{ men } c \nmid b \text{, vil } c \nmid (a + b)$}$

Beviset for denne påstanden er et såkalt «bevis ved selvmotsigelse», eller «reductio ad absurdum». Vi tar utgangspunkt i det motsatte av det vi skal bevise, nemlig at a + b faktisk er delelig med c. Så demonstrerer vi at dette fører til en selvmotsigelse. Vi kommer fram til at b faktisk er delelig med c, noe som er i strid med den ene av forutsetningene.

Vi antar altså at c | (a + b). Da finnes det et heltall, k, slik at ck = a + b. Siden c | a, vet vi at det finnes et heltall, l, slik at cl = a. Dette kan vi sette sammen til ck = cl + b. Vi flytter cl over til venstre side med fortegnsskifte, og får ckcl = b. Setter vi c utenfor parentes, får vi c(kl) = b. Siden k og l er heltall, er kl heltall. b kan derved skrives som c multiplisert med et heltall, noe som er i strid med en av forutsetningene. Setningen er derved bevist.

c kan allikevel være en faktor i lineære kombinasjoner av a og b.

Eksempel 6:

3 er en faktor i 6, men ikke i 4. 3 kan derfor ikke være en faktor i 10 = 6 + 4. Men 3 er en faktor i 18 = 6 + 3 · 4.

Delelighetsregler

Nå skal vi se på en praktisk anvendelse av regelen om lineære kombinasjoner, nemlig å vise hvordan vi kan utlede regler for om et vilkårlig heltall er delelig med 2, 3, 4, 5 eller 9.

For å begrunne reglene kommer vi til å skrive tallene på utvidet form,
n = am10m + am−110m−1 + … + a110 + a0, som beskrives i artikkelen om tall og tallsystemer. I noen tilfeller bruker vi også tallets tverrsum, som beskrives i samme artikkel.

Toerregelen

Når vi studerer et tall på utvidet form, ser vi at vi multipliserer alle koeffisientene unntatt a0 med potenser av 10. Setter vi 10 utenfor parentes, får vi følgende uttrykk for et tall på utvidet form:

n = (am 10m−1+ am−1 10m−2+ … + a1)10 + a0

Vi trenger ikke bry oss med alle detaljene inni parentesen, så for enkelhets skyld kaller vi hele dette uttrykket for b:

n = 10b + a0

Vi vet at 10 er delelig med 2, følgelig er alle multipler av 10 også er delelige med 2. Det vil si at 10b er delelig med 2, uavhengig av verdien til b. Hvis nå a0 også er delelig med 2, sier regelen om lineære kombinasjoner at n også er delelig med 2. Siden koeffisienten a0 representerer siste siffer i tallet n, følger toerregelen:

$\fbox{Tall er delelige med 2 når siste siffer er delelig med 2}$

Eksempel 7:

336 er delelig med 2 fordi 6 er delelig med 2.

227 er ikke delelig med 2 fordi 7 ikke er delelig med 2.

Femmerregelen

Samme argument, basert på at 10 er delelig med 5, fører til femmerregelen:

$\fbox{Tall er delelige med 5 når siste siffer er delelig med 5}$

Eksempel 8:

220 er delelig med 5 fordi 0 er delelig med 5.

231 er ikke delelig med 5 fordi 1 ikke er delelig med 5.

Firerregelen

Vi gjør nå et tilsvarende triks med tallet på utvidet form, men baserer oss på at alle koeffisienter unntatt a1 og a0 blir multiplisert med potenser av 100, og setter 100 utenfor parentes:

n = (am10m−2 + am−110m−3 + … + a2)100 + a110 + a0

Vi trenger ikke bry oss med alle detaljene inni parentesen, så for enkelhets skyld kaller vi hele dette uttrykket for b:

n = 100b + a110 + a0

Vi vet at 100 er delelig med 4, følgelig er alle multipler av 100 også er delelige med 4. Det vil si at 100b er delelig med 4, uavhengig av verdien til b. Hvis nå a110 + a0 også er delelig med 4, sier regelen om lineære kombinasjoner at n også er delelig med 4. Siden uttrykket a110 + a0 representerer tallet dannet av de to siste sifrene i tallet n, følger firerregelen:

$\fbox{Tall er delelige med 4 når tallet dannet av de to siste sifrene er delelig med 4}$

Eksempel 9:

336 er delelig med 4 fordi 36 er delelig med 4.

222 er ikke delelig med 4 fordi 22 ikke er delelig med 4.

Hvis vi har brukt firerregelen og funnet at et tall er delelig med 4, vet vi automatisk at det også er delelig med 2. Og omvendt, hvis vi har brukt toerregelen og funnet at et tall ikke er delelig med 2, vet vi automatisk at det heller ikke er delelig med 4.

Nierregelen

Toer- og femmerregelen virker fordi 2 og 5 går opp i tallsystemets grunntall, nemlig 10, og firerregelen fordi 4 går opp i grunntallet opphøyd i 2, nemlig 100. Noe slikt system finnes imidlertid ikke for 3 og 9, så for å finne regler for delelighet med 3 og 9 må vi angripe problemet på en litt annen måte. Vi starter med å addere (− 1 + 1) til alle tierpotensene i tallet på utvidet form. Det kan vi fritt gjøre, for vi adderer jo bare 0.

n = am(10m − 1 + 1) + am−1(10m−1 − 1 + 1) + … + a1(10 − 1 + 1) + a0

som ved å skille ut multiplikasjonen av koeffisientene med 1 kan omformes til

n = am(10m − 1) + am−1(10m−1 − 1) + … + a1(10 − 1) + am · 1 + am−1 · 1 + … + a1 · 1 + a0

Poenget med dette er at alle tierpotensene minus 1 vil være multipler av 9, nemlig 9, 99, 999, og så videre. Vi kan altså forenkle uttrykket til

n = 9b + am + am−1 + … + a1 + a0, der b er et eller annet tall vi ikke trenger å bry oss om.

9b er delelig med 9 fordi det er en multippel av 9. Hvis nå am + am−1 + … + a1 + a0 også er delelig med 9, sier regelen om lineære kombinasjoner at n også er delelig med 9. Vi ser at am + am−1 + … + a1 + a0 er summen av koeffisientene i tallet, det vil si det samme som tverrsummen, som beskrives i artikkelen om tall og tallsystemer. Av dette følger nierregelen:

$\fbox{Tall er delelige med 9 når tverrsummen er delelig med 9}$

Hvis tverrsummen blir et stort tall som vi kanskje ikke vet om er delelig på 9, bruker vi nierregelen på dette tallet også.

Eksempel 10:

48528 er delelig med 9 fordi T(48528) = 27 er delelig med 9. Hvis vi skulle være usikre på om 27 er delelig med 9, tar vi tverrsummen på nytt, T(27) = 9.

116 er ikke delelig med 9 fordi T(116) = 8 ikke er delelig med 9.

222 er ikke delelig med 9 fordi T(222) = 6 ikke er delelig med 9.

Treerregelen

I begrunnelsen for nierregelen skrev vi tallet n som

n = 9b + am + am−1 + … + a1 + a0. Fordi 9 er en multippel av 3, vil alle tall på formen 9b være delelige med 3. Hvis am + am−1 + … + a1 + a0, altså tverrsummen, også er delelig med 3, vil n være delelig med 3. Av dette følger treerregelen:

$\fbox{Tall er delelige med 3 når tverrsummen er delelig med 3}$

Hvis tverrsummen blir et stort tall som vi kanskje ikke vet om er delelig på 3, bruker vi treerregelen på dette tallet også.

Eksempel 11:

48525 er delelig med 3 fordi T(48525) = 24 er delelig med 3. Hvis vi skulle være usikre på om 24 er delelig med 3, tar vi tverrsummen på nytt, T(24) = 6.

116 er ikke delelig med 3 fordi T(116) = 8 ikke er delelig med 3.

222 er delelig med 3 fordi T(222) = 6 er delelig med 3.

Hvis vi har brukt nierregelen og funnet at et tall er delelig med 9, vet vi automatisk at det også er delelig med 3. Og omvendt, hvis vi har brukt treerregelen og funnet at et tall ikke er delelig med 3, vet vi automatisk at det heller ikke er delelig med 9.

Oppgave 2:

Avgjør om 1386 er delelig med henholdsvis 2, 3, 4, 5 og 9 ved å bruke delelighetsregler. Bruk reglene i den rekkefølgen du ønsker.

Se løsningsforslag

Divisjon med rest

Innledningsvis sa vi at hvis divisjonen a : b = t går opp, betyr det at t er et helt tall. a kan da deles i t blokker med b elementer i hver.

I eksempel 2 så vi for eksempel at 8 : 2 = 4 betydde at a = 8 elementer kunne organiseres i t = 4 blokker med b = 2 elementer i hver.

Hvis divisjonen derimot ikke går opp, vil det ikke være mulig å organisere alt i blokker med b elementer. Det kan være mulig å danne et antall fulle blokker med b elementer, men det vil alltid være en blokk som ikke blir full.

Eksempel 12:

Divisjonen 7 : 3 går ikke opp. Forsøker vi å dele a = 7 elementer i blokker med b = 3 elementer, vil vi få to fulle blokker, men også en blokk som bare inneholder ett element:

Illustrasjon av at 7:3 ikke går opp

Eksempel 13:

Divisjonen 6 : 4 går ikke opp. Forsøker vi å dele a = 6 elementer i blokker med b = 4 elementer, vil vi få én full blokk, men også en blokk som bare inneholder to elementer:

Illustrasjon av at 6:4 ikke går opp

Antall elementer i en blokk som ikke er full, kaller vi for en rest, og å dividere på denne måten kalles å dividere med rest. I eksempel 12 er resten 1, i eksempel 13 er resten 2. Ser vi tilbake på eksempel 1 og 2, der divisjonen gikk opp, fantes det ingen elementer i blokker som ikke var fulle. Det er det samme som at resten er 0.

Utfører vi divisjonene i eksempel 12 og 13 på ordinær måte, får vi 7 : 3 = 2,3 og 6 : 4 = 1,5.

Streken over tretallet betyr at sifferet 3 gjentar seg i det uendelige.

Vi ser at heltallsdelen av svarene, henholdsvis 2 og 1, forteller hvor mange fulle blokker vi får.

Multipliserer vi desimaldelen av svarene med divisor, finner vi ut hva resten blir, henholdsvis 0, 3 · 3 = 1 og 0,5 · 4 = 2.

Eksempel 14:

Tabellen under viser tallene fra 0 til 10 dividert med 4. Vi bruker heltallsdelen av resultatene til å regne ut hvor mange hele blokker på 4 vi får, og desimaldelen av resultatene multiplisert med 4 til å regne ut hvilken rest vi får i hvert tilfelle.

Tall: 0 1 2 3 4 5 6 7 8 9 10
Tall dividert på 4: 0,00 0,25 0,50 0,75 1,00 1,25 1,50 1,75 2,00 2,25 2,50
Hele blokker: 0 0 0 0 1 1 1 1 2 2 2
Rest: 0 1 2 3 0 1 2 3 0 1 2

Vi ser at vi starter med 0 blokker og 0 i rest. Hver gang tallet øker med 1, øker resten med 1, inntil tallet blir en multippel av 4. Da går resten tilbake til 0, og vi får en ny full blokk med 4 elementer.

Alle hele tall dividert på 4 vil kunne representeres unikt som i eksempel 14, med et antall blokker à 4 elementer, og en rest som varierer mellom 0 og 3.

Å dividere på denne måten vil vi heretter referere til som å dividere med rest, og antall fulle blokker kaller vi kvotienten i divisjonen. En kvotient er her altså et helt tall, noe den ikke trenger være ved vanlig divisjon.

GeoGebra / regneark

Når vi dividerer med rest, kan vi i GeoGebra finne kvotienten ved hjelp av funksjonen div, og resten ved hjelp av funksjonen mod. Skriver vi for eksempel div(7, 4) i inntastingsfeltet, svarer GeoGebra med tallet 1 i algebrafeltet. Tilsvarende gir mod(7, 4) tallet 3 i algebrafeltet. Dette er det samme som vi fant i eksempel 14.

I regneark som Excel heter de tilsvarende funksjonene kvotient og rest. For eksempel gir =kvotient(7; 4) tallet 1 og =rest(7; 4) tallet 3. Vi legger merke til at i et regneark innledes alle kommandoer med likhetstegn, og argumentene skilles med semikolon, ikke komma.

Divisjonsalgoritmen

Generelt vil alle hele tall, a, dividert på et positivt heltall, b, på en unik måte kunne representeres som en kvotient, q, og en rest, r, som varierer mellom 0 og b−1. Dette er divisjonsalgoritmen, eller divisjonslemmaet, som vi matematisk uttrykker slik:

$\fbox{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$}$

Hvis divisjonen a : b går opp, blir resten r = 0. Hvis b > a, blir q = 0 og r = a, slik vi ser i eksempel 15.

Eksempel 15:

I eksempel 14 er b = 4, mens a varierer fra 0 til 10.

Vi ser at a ved hjelp av divisjonsalgoritmen kan uttrykkes som

$\begin{align}
0 &= 0 \cdot 4 + 0 \\
1 &= 0 \cdot 4 + 1 \\
2 &= 0 \cdot 4 + 2 \\
3 &= 0 \cdot 4 + 3 \\
4 &= 1 \cdot 4 + 0 \\
5 &= 1 \cdot 4 + 1 \\
6 &= 1 \cdot 4 + 2 \\
7 &= 1 \cdot 4 + 3 \\
8 &= 2 \cdot 4 + 0 \\
9 &= 2 \cdot 4 + 1 \\
10 &= 2 \cdot 4 + 2 \\
\end{align}$

Ei tallinje kan brukes til å illustrere divisjonsalgoritmen. I a = qb + r er q antall ganger vi må legge b etter hverandre for å komme så langt at vi bare mangler resten, r, på å nå fram til a.

Eksempel 16:

$\begin{align}
8 &= 2 \cdot 4 + 0 \\
14 &= 3 \cdot 4 + 2
\end{align}$

Dette er illustrert på tallinja under. Linjestykket med lengde b = 4 rekker nøyaktig fram til a = 8 når vi legger det etter seg selv q = 2 ganger, her er resten r = 0. Men vi får det ikke til å rekke nøyaktig fram til a = 14. Da legger vi det etter seg selv q = 3 ganger, og bruker en rest på r = 2 på å nå a.

Illustrasjon av divisjonsalgoritmen

Divisjonsalgoritmen er svært nyttig i mange sammenhenger. I artikkelen om faktorisering ser vi for eksempel at den gir oss en effektiv metode til å finne to talls største felles faktor.

Divisjonsalgoritmen kan også brukes på negative tall. a i uttrykket a = qb + r vil da være mindre enn null, mens b forblir positiv. Vi får en negativ q, mens r, som skal ligge mellom 0 og b−1 forblir positiv eller 0.

Eksempel 17:

$\begin{align}
−8 &= −2 \cdot 4 + 0\\
−14 &= −4 \cdot 4 + 2
\end{align}$

Akkurat som for positive tall kan vi illustrere dette med ei tallinje.

Eksempel 18:

Tallene fra eksempel 17 er illustrert under. Linjestykket med lengde b = 4 rekker nøyaktig fram til −8 når vi legger det etter seg selv −2 ganger, her er rest 0. Men vi får det ikke til å rekke nøyaktig fram til −14. Siden resten skal være positiv, må vi gå forbi −14 ved å legge b = 4 etter seg selv −4 ganger og så bruke resten på 2 til å gå tilbake til 14.

Illustrasjon av divisjonsalgoritmen for negative tall

Beregning med GeoGebra / regneark

For å kunne bruke divisjonsalgoritmen på to tall, a og b, må vi beregne q og r. I GeoGebra kan vi bruke funksjonene div og mod til dette, og i Excel funksjonene kvotient og rest, slik vi så tidligere. Dessverre håndterer ikke Excel negative a riktig. Skal vi for eksempel finne kvotient og rest når a = −14 og b = 4, skriver vi =kvotient(-14; 4), og får −3, og =rest(-14; 4), og får 2. Men prøver vi å regne oss tilbake, får vi −4 · 3 + 2 = −10, ikke −14. GeoGebra gjør det derimot riktig. div(-14, 4) gir −4, og mod(-14, 4) gir 2. Og −4 · 4 + 2 = −14, slik vi så i eksempel 18.

Manuell beregning

Nå skal vi se på en metode til å beregne q og r for hånd, eller med en vanlig kalkulator.

q er tallet vi skal multiplisere med b for å komme så nærme a at vi havner eksakt i a når vi adderer resten, r. q finner vi ved å dividere ab og så runde ned til nærmeste heltall. For å indikere at vi runder ned til nærmeste heltall bruker vi symboler med klammeparenteser som bare er lukket i bunnen, slik at de danner et golv: $\lfloor \; \rfloor$.

Formelt sett er $\lfloor x \rfloor$ definert som det største heltallet som er mindre eller lik x. For positive tall betyr det å sløyfe tallets desimaler, slik vi gjorde i eksempel 13 og 14. Men for negative tall vil det ikke være slik. Vi kan tenke oss at vi finner $\lfloor x \rfloor$ ved å starte på x og gå mot venstre langs tallinja til vi treffer første heltall.

Eksempel 19:

$\begin{align}
\lfloor 2{,}75 \rfloor &= 2\\
\lfloor 2 \rfloor &= 2\\
\lfloor −2 \rfloor &= −2\\
\lfloor −2{,}75 \rfloor &= −3 \;\;\text{NB!}
\end{align}$

Som nevnt gir qb et tall som er slik at når vi adderer resten, r, havner vi i a. Altså: qb + r = a, det vil si at r = aqb.

Det betyr at vi i praksis kan bruke divisjonsalgoritmen på a og b slik:

    1. Vi finner $q = \lfloor \frac{\displaystyle a}{\displaystyle b} \rfloor$
       
    2. Vi finner r = aqb
       
    3. Vi skriver opp uttrykket a = qb + r

Eksempel 20:

Vi skal bruke divisjonsalgoritmen på a = 1028, b = 34.

Vi finner $\frac{\displaystyle a}{\displaystyle b} = {\large \frac{1028}{34}} \approx 30{,}24$

$q = \lfloor 30{,}24 \rfloor = 30$

og r = 1028 − 30 · 34 = 8

Så 1028 = 30 · 34 + 8.

Eksempel 21:

Vi skal bruke divisjonsalgoritmen på a = −380, b = 75.

Vi finner $\frac{\displaystyle a}{\displaystyle b} = {\large \frac{−380}{75}} \approx −5{,}07$

$q = \lfloor −5{,}07 \rfloor = −6$

og r = −380 − (−6 · 75) = 70

Så −380 = −6 · 75 + 70.

Oppgave 3:

Bruk divisjonsalgoritmen på

        • a = 133, b = 21
           
        • a = −50, b = 8

Se løsningsforslag

Beregne $\lfloor x \rfloor$ i GeoGebra og regneark

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

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

Kilder

    • Rosen, Kenneth H. (1984). Elementary Number Theory and Its Applications. Addison-Wesley.

Tall og tallsystemer

Hva er tall?

Et tall er i seg selv bare en abstrakt idé, ingen fysisk størrelse. Men vi symboliserer tallene fysisk med skrift eller med lyd. I matematisk sammenheng dominerer de hinduarabiske symbolene 0, 1, 2, 3, 4, 5, 6, 7, 8 og 9. Men det finnes også andre symboler, for eksempel romertall. I, II, III, IV, V, VI, VII, VIII, IX er romertallene fra 1 til 9. Romertall har imidlertid ikke noe symbol for 0. I skriftspråk eller tale varierer det fra land til land hva tall heter. For eksempel heter 3 «tre» i Skandinavia, «three» i England, «trois» i Frankrike, «tres» i Spania og «drei» i Tyskland.

Posisjonssystemer

For å holde orden på tallene trenger vi et system. Det vi skal befatte oss med i denne artikkelen, kalles posisjonssystemer fordi et siffers verdi er avhengig av posisjonen det har blant de andre sifrene. Men det finnes også andre systemer. Romertall V betyr for eksempel alltid 5, uansett posisjon.

Titallsystemet

Vårt vanlige tallsystem er et posisjonssystem som kalles titallsystemet fordi det består av 10 symboler. Symbolene kalles gjerne sifre, og titallsystemet kalles også desimaltallsystemet eller det dekadiske tallsystem. Sifrene er de velkjente 0, 1, 2, 3, 4, 5, 6, 7, 8 og 9.

Titallsystemet inneholder altså 10 forskjellige sifre som kan representere fra 0 til 9 enheter. Men hva gjør vi hvis vi skal representere mer enn 9? Jo, vi putter symbolene i grupper. En gruppe der hvert symbol representerer antall 1-ere, en gruppe der hvert symbol representerer antall 10-ere, en gruppe der hvert symbol representerer antall 100-ere, osv. På den måten kan de 10 symbolene brukes til å representere ubegrenset mange enheter.
I bildet under er tallet 1457 representert ved å bygge grupper med multibasemateriell.
1 blokk à 1000 klosser + 4 plater à 100 klosser + 5 staver à 10 klosser + 7 enkeltklosser.

1457 i titallsystemet representert ved klosser

Tallet 1457 betyr altså 1 · 1000 + 4 · 100 + 5 · 10 + 7.

Hvor mye hvert siffer representerer, er avhengig av hvilken posisjon det har i tallet, og verdien øker ti ganger for hver plass vi flytter mot venstre. Titallsystemet vårt er altså et posisjonssystem med base 10.

100 og 1000 kan skrives på potensform som 102 og 103, det vil si 10 multiplisert med seg selv henholdsvis to ganger og tre ganger. Vi kan også skrive 10 som 101 og 1 som 100.
1457 betyr altså 1 · 103 + 4 · 102 + 5 · 101 + 7 · 100.
Her framgår det tydelig at hvert siffer representerer en potens av 10, der vi starter på 0 lengst til høyre, og øker med 1 for hver posisjon vi flytter oss mot venstre.

Av og til er det hull i rekka av potenser i et tall. 2003 betyr for eksempel 2 · 103 + 3 · 100. Potensene 102 og 101 trengs ikke. Dette angis ved å sette sifferet null i den tilhørende posisjonen. 2003 betyr altså 2 · 103 + 0 · 102 + 0 · 101 + 3 · 100.
Sifferet 0 fungerer som en plassfyller som ikke bidrar til tallets verdi. Uten 0 ville ikke posisjonssystemet fungert.

Årsaken til at akkurat 10 er valgt som base i vårt tallsystem, sies å være at mennesker har ti fingre, det finnes ikke noen matematisk begrunnelse. Et hvert annet naturlig tall kan brukes i stedet. I bildet under er 5 valgt som base, og vi bruker der 3 blokker à 53 = 125 klosser, 4 plater à 52 = 25 klosser, 2 staver à 51 = 5 klosser og 1 enkeltkloss. Tallet som representeres er altså i titallsystemet som 3 · 53 + 4 · 52 + 2 · 51+1 · 50 = 486. Her multipliseres hvert siffer med en potens av basen 5.

3421 i femtallsystemet representert ved klosser

For å unngå forvirring om hvilket tallsystem vi arbeider i, angir vi systemets base med et subskript. 34215 = 48610 betyr for eksempel at 3421 i femtallsystemet er det samme som 486 i titallsystemet.

Andre systemer

Tallsystemer som i tillegg til titallsystemet brukes mye i dag, er totallsystemet (det binære tallsystemet), sekstentallsystemet (heksadesimalsystemet) og sekstitallsystemet.

Moderne datamaskiner arbeider i totallsystemet fordi dette systemet bare har to sifre, 0 og 1, noe som er enkelt for en datamaskin å håndtere. For mennesker er det imidlertid tungvint, fordi selv små tall blir lange og tunge å lese. For å øke lesbarheten presenterer vi derfor gjerne sifrene gruppert fire og fire i sekstentallsystemet.

Og hvor bruker vi så sekstitallsystemet? Jo, på klokka. 601 sekunder utgjør et minutt, og 602 sekunder utgjør en time.

Lista under viser tallet 17 representert i posisjonssystemer med baser fra 1 til 17.

100012 = 1223 = 1014, = 325 = 256 = 237 = 218 = 189 = 1710 = 1611 = 1512 = 1413 = 1314 = 1215 = 1116 = 1017.

Dette nettstedet har en egen IKT-artikkel om tallsystemer.

Oppgave 1:

Regn ut hva 30415 i femtallsystemet blir i titallsystemet.

SkjermfilmSe film der løsningsforslaget vises
 

Oppgave 2:

Regn ut hva 523067 i sjutallsystemet blir i titallsystemet.

Se løsningsforslag

Formelt om posisjonssystemer

I dette avsnittet gir vi en mer formell definisjon av posisjonssystemer, og ser spesielt på totallsystemet og sekstentallsystemet.

Tall på utvidet form

Lar vi b være grunntallet i et tallsystem, altså 2 i totallsystemet, 3 i tretallsystemet, og så videre, kan ethvert naturlig tall, n, skrives entydig på formen under. Her har vi for enkelhets skyld skrevet a1b1 som a1b og a0b0 som a0.

$\fbox{$n = a_mb^m + a_{m−1}b^{m−1} + \dots + a_1b + a_0$}$

Her er:
$b \in \mathbb N, b > 1$

Hver av koeffisientene a0, a1, … , am er en av 0, 1, 2, 3, … , b − 1.
am≠ 0.

Et tall skrevet på denne måten sies å være på utvidet form, eller utviklet form.

Eksempel 1:

Vi skal skrive 145710 på utvidet form. Siden vi er i titallsystemet, er grunntallet lik 10. Vi får
145710 = 1 · 103 + 4 · 102 + 5 · 10 + 7.

Eksempel 2:

Vi skal skrive 34215 på utvidet form. Siden vi er i femtallsystemet, er grunntallet, lik 5. Vi får
34215 = 3 · 53 + 4 · 52 + 2 · 5 + 1.

Oppgave 3:

Skriv 523067 på utvidet form.

Se løsningsforslag

Sifre

Koeffisientene a0, a1, … , am kalles sifrene i tallet. Tillatte verdier for disse sifrene er 0, 1, … , b − 1. I titallsystemet er grunntallet b = 10, så b − 1 = 9, og de tillatte koeffisientene blir 0, 1, … , 9. I totallsystemet er b = 2, så b − 1 = 1, og de tillatte koeffisientene blir bare 0, 1. For eksempel betyr 10112: 1 · 23 + 0 · 22 + 1 · 2 + 1.

Totallsystemet er enerådende i digitale datamaskiner, dette skyldes at regnereglene er svært enkle, og at tall med bare to sifre er lett å representere fysisk i maskinen. Tall er som tidligere nevnt noe abstrakt som må gis en fysisk representasjon for at vi skal kunne arbeide med dem. Mennesker representerer tallene som skrift eller tale, i en datamaskin representeres de som elektriske ladninger, magnetisme, eller speil. I en CD-plate representeres for eksempel sifferet 1 ved at en laserstråle reflekteres i et punkt på plata, mens 0 representeres ved at den ikke reflekteres.

For mennesker er imidlertid totallsystemet tungvint fordi selv små tall blir lange og tunge å lese. For eksempel krever 99910 ti sifre i totallsystemet: 11111001112. For å øke lesbarheten presenterer vi derfor gjerne sifrene gruppert fire og fire i sekstentallsystemet.

I sekstentallsystemet er grunntallet b = 16, så de tillatte koeffisientene er 0, 1, … , 15. Og her får vi et problem, for vi har koeffisienter med flere sifre, og det er uforenelig med prinsippet i et posisjonssystem. La oss for eksempel si at vi har a1 = 3 og a0 = 12, altså et tall som er på utvidet form er 3 · 16 + 12. Skriver vi dette på normal, kort måte, blir det 312. Men det betyr jo 3 · 162 + 1 · 16+ 2. Så vi kan ikke tillate at koeffisienter opptar mer enn én posisjon i posisjonssystemet. Løsningen på problemet er å innføre flere siffersymboler. En kunne valgt å lage helt nye symboler, men i stedet har en valgt å bruke de første bokstavene i alfabetet, A, B, C, D, E, F, for å representere henholdsvis 1010, 1110, 1210, 1310, 1410 og 1510. For eksempel er F2D16 = 15 · 162 + 2 · 16 + 13 · 160 = 388510.

I et tallsystem med høyere grunntall vil vi trenge enda flere siffersymboler. Da fortsetter vi i alfabetet. G, H, …

Omregning mellom tallsystemer

For å regne om fra to- til sekstentallsystemet grupperer vi sifrene fire og fire fra høyre. Da kan hver gruppe utgjøre et tall fra 0 til 15, altså 0 – F i sekstentallsystemet. Dette er vist i tabellen under, der det er fylt på med ledende nuller slik at hvert tall har fire sifre.

Totallsystemet 0000 0001 0010 0011 0100 0101 0110 0111 1000
Sekstentallsystemet 0 1 2 3 4 5 6 7 8

 

Totallsystemet 1001 1010 1011 1100 1101 1110 1111
Sekstentallsystemet 9 A B C D E F

Oppgave 4:

Regn ut hva tallet 110000010010112 blir i sekstentallsystemet ved å slå sifrene sammen i grupper på fire fra høyre

SkjermfilmSe film der løsningsforslaget vises
 

Oppgave 5:

Gitt et tall i totallsystemet, 111010011112.

      1. Regn ut hva tallet blir i sekstentallsystemet ved å slå sifrene sammen i grupper på fire fra høyre.
         
      2. Regn ut hva tallet blir i titallsystemet.

​Se løsningsforslag

For å regne om fra titallsystemet til et annet tallsystem er det følgende en grei metode: Vi dividerer tallet n, som vi vil konvertere, med grunntallet b i tallsystemet vi vil konvertere til. Da får vi en kvotient, q, og en rest, r, som er et tall mellom 0 og b − 1. Resten blir koeffisient a0 i det nye tallsystemet, og q dividerer vi på nytt med b. Den nye resten blir nå koeffisient a1 i det nye tallsystemet, og den nye q dividerer vi på nytt med b. Og slik fortsetter vi til q blir 0.

Eksempel 3:

48610 i titallsystemet skal regnes om til femtallsystemet. Her er altså grunntallet vi skal konvertere til, b = 5.

486 : 5 gir q = 97, r = a0 = 1

97 : 5 gir q = 19, r = a1 = 2

19 : 5 gir q = 3, r = a2 = 4

3 : 5 gir q = 0, r = a3 = 3

Så 48610 = 34215.

Oppgave 6:

Regn om 48610 i titallsystemet til sekstallsystemet.

SkjermfilmSe film der løsningsforslaget vises
 

Addisjon og subtraksjon i andre tallsystemer

Prinsippene for å addere og subtrahere er de samme i alle tallsystemer, vi må bare huske på at grunntallene er forskjellige. Dette påvirker verdiene vi overfører fra en kolonne til en annen. Hvis vi for eksempel i titallsystemet adderer 6 og 6 i en kolonne, får vi 12, noe vi håndterer ved å skrive 2-tallet underst, og overføre 10 en kolonne mot venstre, det vil si å skrive 1 i mente. Adderer vi 9 og 7 og 8, får vi 24, noe vi håndterer ved å skrive 4-tallet underst og overføre to ganger 10 en kolonne mot venstre, det vil si å skrive 2 i mente. I titallsystemet overfører vi altså multipler av 10 fra kolonne til kolonne. I andre tallsystemer overfører vi multipler av grunntallet i det tallsystemet vi arbeider i. Hvis vi for eksempel i 7-tallsystemet skal addere 6 og 6, blir det 5 mer enn 7. Det vil si at vi skriver 5-tallet underst og overfører 7-tallet en kolonne mot venstre, altså skriver vi 1 i mente. Skal vi addere 6 + 5 + 6, blir det 3 mer enn to ganger 7. Det vil si at vi skriver 3-tallet underst og overfører to 7-tall en kolonne mot venstre, altså skriver vi 2 i mente.

SkjermfilmSe film som sammenlikner addisjon i ti- og femtallsystemet
 

Når vi subtraherer i titallsystemet, og skal trekke et siffer fra et annet som er mindre, må vi «låne» 10 i kolonna til venstre. Skal vi for eksempel subtrahere 8 fra 32, kan vi i høyre kolonne ikke subtrahere 8 fra 2, vi må «låne» 10 fra 3-tallet. I høyre kolonne får vi da 10 − 8 + 2 = 4, i venstre kolonne står det igjen 2 etter at vi har «lånt» 10, så svaret blir 24. I 7-tallsystemet gjør vi tilsvarende, bare at vi «låner» 7 i stedet for 10. Skal vi for eksempel subtrahere 6 fra 44, kan vi i høyre kolonne ikke subtrahere 6 fra 4, vi må «låne» 7 fra 4-tallet. I høyre kolonne får vi da 7 − 6 + 4 = 5, i venstre kolonne står det igjen 3 etter at vi har «lånt» 7, så svaret blir 35.

SkjermfilmSe film som sammenlikner subtraksjon i ti- og femtallsystemet
 

Tverrsum

Et naturlig tall, n, kan skrives på utvidet form som n = ambm + am1bm−1 + … + a1b + a0. Hvis vi ser bort fra potensene av b, og bare adderer koeffisientene, får vi tverrsummen av tallet, T(n):

$\fbox{$T(n) = a_m + a_{m−1} + \dots + a_1 + a_0$}$

Tverrsummen kan beregnes for alle grunntall, men i det følgende holder vi oss til vårt vanlige titallsystem, b = 10.

Eksempel 4:

T(870642) = 8 + 7 + 0 + 6 + 4 + 2 = 27.

Alternerende tverrsum

Hvis vi i stedet for å addere alle sifrene i et tall vekselvis adderer og subtraherer annet hvert siffer, får vi den alternerende tverrsummen av tallet, A(n):

$\fbox{$A(n) = a_0 − a_1 + a_2 − a_3 + \dots + (−1)^ma_m$}$

Vi starter altså til høyre og går mot venstre, slik at a0 blir addert, a1 subtrahert, og så videre. Uttrykket (−1)m betyr at annet hvert ledd blir addert og annet hvert subtrahert fordi (−1)m er lik 1 når m er partall, og lik −1 når m er oddetall.

Dette nettstedet har en app som beregner T(n) og A(n).

Eksempel 5:

A(870642) = 2 − 4 + 6 − 0 + 7 − 8 = 3

Oppgave 7:

Gitt et tall, n = 7193536.

      1. Finn tverrsummen til tallet, T(n)
         
      2. Finn den alternerende tverrsummen til tallet, A(n)

​Se løsningsforslag

Kilder

    • Breiteig, T. (2007). Bak tallene. Innføring i tallteori. Kompendium, Universitetet i Agder.