RSA-systemet

Kryptering ved eksponentiering

I artikkelen om kryptografi så vi hvordan vi kunne bruke eksponentiering og kongruensregning til kryptering. Vi krypterte da u k med nøkkel (r, n) ved hjelp av kongruensen

kur (mod n)

Med denne krypteringsmåten er det så å si umulig å dekryptere ved å bruke krypteringsnøkkelen baklengs. Vet vi for eksempel at k er kryptert med nøkkel (r, n), vil vi for å dekryptere måtte finne ut hvilken u som er slik at urk (mod n). Med store tall for r og n blir en slik utregning ekstremt vanskelig.

I stedet dekrypterer vi ved hjelp av en egen dekrypteringsnøkkel, (s, n) ved hjelp av kongruensen

uks (mod n)

I alle eksempler og oppgaver i artikkelen om kryptografi ble begge nøklene angitt uten nærmere forklaring. Vi skal nå se på en metode for å danne dekrypteringsnøkkelen sammen med krypteringsnøkkelen.

Eulers totient-funksjon

Vi starter med å se på noe som heter Eulers totient-funksjon, også kalt Eulers phi-funksjon, fordi den betegnes med den greske bokstaven phi. I denne artikkelen bruker vi symbolet φ for phi, men phi kan også skrives som ϕ.

I en mengde som består av alle positive heltall opp til og med n, betegner totient-funksjonen, φ(n), antall tall i mengden som ikke har felles faktorer med n, altså antall tall, a < n, som er slik at SFF(a, n) = 1. For eksempel er φ(10) = 4, fordi det i mengden {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} finnes fire tall som ikke har felles faktorer med 10, nemlig 1, 3, 7 og 9.

Basert på primtallsfaktorene i n finnes det en generell formel for å beregne φ(n), men vi nøyer oss med å se på et par spesialtilfeller.

Dersom n er et primtall, betyr det at ingen tall, a < n, har noen felles faktor med n, så vi får at φ(n) = n − 1.

Dersom n er et produkt av to forskjellige primtall, n = p · q, blir det litt mer komplisert. Mengden vil da inneholde p tall som har faktoren q felles med n, og q tall som har faktoren p felles med n. Trekker vi disse fra, får vi p · q − pq. Men siden vi da to ganger har trukket fra tallet som både har faktor q og p felles med n, må vi addere 1. Så vi får:

 φ(n) = p · qpq + 1.

Eksempel 1:

Vi lar p = 3, q = 5, og får n = 3 · 5 = 15.

Totient-funksjonen blir φ(15) = 3 · 5 − 3 − 5 + 1 = 8.

Vi ser at dette er riktig, fordi det blant de 15 tallene finnes p = 3 som inneholder faktoren 5, nemlig 5, 10 og 15. Og det finnes q = 5 som inneholder faktoren 3, nemlig 3, 6, 9, 12 og 15. Når vi så trekker fra 3 og 5, har vi regnet med tallet 15 to ganger, og må derfor addere 1.

De 8 tallene vi står igjen med er, markert med oransje,
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

Formelen φ(n) = p · qpq + 1 kan skrives som φ(n) = (p − 1)(q − 1), som er lett å huske og bruke. For eksempel får vi, fordi 15 = 3 · 5, φ(15) = (3 − 1)(5 − 1) = 2 · 4 = 8.

Altså

$\fbox{Hvis p og q er forskjellige primtall, er $\varphi( p \cdot q) = (p−1)(q−1)$ }$

Eksempel 2:

n = 221 er et produkt av primtallene 13 og 17.

Vi har derfor at φ(221) = (13 − 1)(17 − 1) = 12 · 16 = 192.

Oppgave 1:

n = 1591 er et produkt av primtallene 37 og 43. Beregn φ(n).

Se løsningsforslag

Eulers totient-teorem

Eulers totient-teorem sier at hvis to positive heltall, a og n, ikke har noen felles faktorer, vil a opphøyd i φ(n) være kongruent med 1 modulo n.

$\fbox{For all tall, $a, n \in \mathbb N$, der $SFF(a, n) = 1$, vil $a^{\large \varphi(n)} \equiv 1 \, (mod \; n)$}$

Eksempel 3:

I eksempel 1 så vi at φ(15) = 8, og at tallene 1, 2, 4, 7, 8, 11, 13, 14 ikke hadde noen felles faktorer med 15.

Da skal vi ifølge Eulers totient-teorem ha at 18 ≡ 28 ≡ 48 ≡ 78 ≡ 88 ≡ 118 ≡ 138 ≡ 148 ≡ 1 (mod 15).

At dette er tilfelle, er vist ved utregningen under, der vi i et regneark opphøyer tallene a = 1 … 14 i åttende, og så beregner resten modulo 15:

Eulers totient-teorem for 3 * 5

Danne dekrypteringsnøkkel

Vi arbeider videre med regnearket fra eksempel 3, og setter inn en kolonne til, der vi multipliserer den beregnede resten med a:

Eulers totient-teorem for 3 * 5, delvis utvidet

I de tilfellene der resten er 1, får vi naturligvis a · 1 = a. I de andre tilfellene får vi tall som ser vilkårlige ut. Men beregner vi resten av disse igjen modulo 15, ser vi at vi i alle tilfeller ender opp med a:

Eulers totient-teorem for 3 * 5, utvidet

Uavhengig av om SFF(a, n) = 1 gjelder det nemlig at a · aφ(n)a (mod n).

RegnearkÅpne et regneark med tabellen vist over.

 

Oppgave 2:

Åpne regnearket over, og modifiser det til å gjøre utregningene for n = 2 · 7 = 14 i stedet for n = 3 · 5.

Se løsningsforslag

I artikkelen om regneregler i kongruenser lærte vi potensregelen, som sier at vi kan opphøye i en positiv, heltallig eksponent på begge sider av kongruenstegnet. Bruker vi denne regelen på Eulers totient-teorem, får vi, med kn

[aφ(n)]k ≡ 1k (mod n) ⇒ akφ(n) ≡ 1 (mod n)

Følgelig også 

a · akφ(n)a (mod n)

Ved hjelp av regneregler for potenser kan venstre side i likningen skrives som akφ(n)+1, og vi har

$\fbox{For all tall, $a, n \in \mathbb N$ vil $a^{\large k\varphi(n) + 1} \equiv a \, (mod \; n)$}$

Operasjonen akφ(n)+1 modulo n er altså en identitetsoperasjon for alle positive heltall, a. Uavhengig av hvilken a vi starter med, ender vi opp med a.

Så vender vi tilbake til krypteringslikningene, uks (mod n) og kur (mod n). Slår vi disse to sammen, får vi

u ≡ (ur)s (mod n)

som ved hjelp av regneregler for potenser kan skrives om til

uurs (mod n)

eller, hvis vi bytter om høyre og venstre side

ursu (mod n)

r og s må altså være slik at å opphøye i rs modulo n er en identitetsoperasjon. 

Og vi vet nå at dette vil være tilfelle hvis rs = (n) + 1. 

rs må altså være et heltallig multippel av φ(n) pluss 1. Vi har med andre ord kongruenslikningen

sr ≡ 1 (mod φ(n))

Uttrykket sr ≡ 1 (mod φ(n)) betyr at når vi velger krypteringsnøkkel (r, n), må vi velge dekrypteringsnøkkel (s, n) slik at s er en multiplikativ invers til r modulo φ(n).

Multiplikative inverser så vi på i artikkelen om regneregler i kongruenslikninger, der vi sa at et tall, a, har en multiplikativ invers modulo n hvis og bare hvis SFF(an) = 1. Vi kan altså ikke velge r helt fritt, men må kreve at SFF(r, φ(n)) = 1, i motsatt fall vil det ikke finnes noen dekrypteringsnøkkel. Det har heller ingen hensikt å velge en r som er større enn modulus, for i så fall vil det alltid finnes en kongruent, mindre r som har samme egenskaper og er enklere å regne med. Tilsvarende for s.

RSA-systemet

Vi har nå kunnskapen vi trenger til å formulere RSA-systemet for kryptering ved hjelp av privat og offentlig nøkkel, navngitt etter forbokstavene i etternavnene til oppfinnerne Rivest, Shamir og Adleman.

Systemet baserer seg på at sr ≡ 1 (mod φ(n)), og kan punktvis beskrives slik:

  1. Vi velger to primtall, p og q, og beregner n = p · q.
     
  2. Vi beregner φ(n) = (p − 1)(q − 1).
     
  3. Vi velger en r < φ(n) slik at SFF(r, φ(n)) = 1.
     
  4. Vi beregner s slik at s er en multiplikativ invers til r modulo φ(n).
     
  5. Vi lar (r, n) være krypteringsnøkkelen, som er offentlig, og lar (s, n) være dekrypteringsnøkkelen, som er privat.

Å beregne en multiplikativ invers kan vi gjøre ved hjelp av Euklids utvidede algoritme. Dette nettstedet har en app, finne_invers, som bruker denne algoritmen til å beregne multiplikative inverser.

Eksempel 4:

  1. Vi velger p = 7 og q = 11, og beregner n = 7 · 11 = 77.
     
  2. Vi beregner φ(n) = (7 − 1) · (11 − 1) = 60.
     
  3. Vi velger r = 13. Dette er mindre enn 60, og SFF(13, 60) = 1.
     
  4. Vi beregner s = 37 ved å bruke appen finne_invers med «a» = 13, «n» = 60.
     
  5. (13, 77) er nå offentlig krypteringsnøkkel og (37, 77) er privat dekrypteringsnøkkel.

Vi skal så kryptere og dekryptere noen bokstaver med den offentlige og private nøkkelen fra eksempel 4. For å gjøre dette, må bokstavene kodes som tall. Dette gjør vi basert på bokstavenes plass i alfabetet, som vist i denne kodetabellen:

A B C D E F G H I J K L M N
1 2 3 4 5 6 7 8 9 10 11 12 13 14
O P Q R S T U V W X Y Z Æ Ø Å
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Eksempel 5:

Vi skal kryptere og dekryptere F med nøklene fra eksempel 4, (13, 77) og (37, 77).

F kodes med 6 ifølge kodetabellen.

Vi krypterer ved å beregne 613 ≡ 62 (mod 77).

Denne beregningen kan vi gjøre ved hjelp av kommandoen = rest(6^13; 62) i et regneark eller mod(6^13, 62) i GeoGebra.

Så F blir kryptert til 62.

Vi dekrypterer ved å beregne 6237 ≡ 6 (mod 77).

Vi ender opp med 6, som tilsvarer F, som vi startet med.

Denne beregningen involverer for store tall til å bruke regneark eller GeoGebra. I stedet bruker vi appen på dette nettstedet, finne_rest, med «a» = 62, «b» = 37 og «n» = 77.

Oppgave 3:

Krypter og dekrypter bokstaven Y med nøklene fra eksempel 4, (13, 77) og (37, 77).

Hint: Bruk appen finne_rest til beregningene.

Se løsningsforslag

Oppgave 4:

Ta utgangspunkt i primtallene 13 og 19. Begrunn at r = 27 ikke vil være gyldig som del av en krypteringsnøkkel i RSA-systemet basert på disse primtallene, men at 25 vil være det. Bruk r = 25 til å angi en krypteringsnøkkel, og beregn den tilhørende dekrypteringsnøkkelen. 

Hint: For å beregne en multiplikativ invers, bruk appen finne_invers.

Bruk krypterings- og dekrypteringsnøkkelen du har funnet til å kryptere og dekryptere bokstaven Y.

Hint: Bruk appen finne_rest til beregningene.

Se løsningsforslag

Når vi kjenner p og q, er det lett å beregne n = p · q. Det er også lett å beregne φ(n) = (p − 1)(q − 1), og, når vi har valgt en r, å beregne s slik at sr ≡ 1 (mod φ(n)).

Men kjenner vi bare n og ikke faktorene p og q, er vi avhengige av å klare å faktorisere n for å kunne beregne φ(n). Og en slik faktorisering er i praksis umulig hvis n er stor. I artikkelen om faktorisering så vi på et par metoder til å faktorisere vilkårlige heltall, men når tallene blir store, blir metodene for langsomme til å kunne brukes i praksis, og det finnes per 2023 ikke noen effektive algoritmer for å faktorisere store tall. Derimot finnes det effektive algoritmer til å avgjøre om store tall er primtall eller ikke. Det betyr at det er praktisk mulig å finne store p og q, og ut fra disse beregne n, men ikke å gå andre veien, og faktorisere n til p og q.

I praksis brukes gjerne tall med rundt 300 siffer for p og q, helst i samme størrelsesorden, det gjør faktorisering vanskeligere. En koder heller ikke enkeltbokstaver med tall fra 1 til 29, men sekvenser av bokstaver under ett.

Kilder

    • Gustavsen, T.S. Hinna, K.R.C., Borge, I.C., & Andersen, P.A. (2014). QED Matematikk for grunnskolelærerutdanningen 5-10, Bind 2. 1. utgave. Kristiansand: Cappelen Akademisk.
    • Rinvold, A. R. (2009). Visuelle perspektiv. Tallteori. Caspar Forlag.
    • Petersen, V. B., Tvete, K. S. (2013). I tallkongruensenes verden. Caspar Forlag.
    • Johnsen, B. (2001). Kryptografi – den hemmelige skriften. Trondheim: Tapir akademisk forlag.

Kryptografi

Hva er kryptografi?

Tenk, så flink er Åge:
Han kan røversproget!
Hvis en røver utenfor
snakker rorr-ø-vovv-e-rorr
soss-popp-rorr-o-gogg-e-tott,
skjønner han det meget godt!

Kan du røversproget
like godt som Åge?
Du skal ikke bry deg om
at du først er dodd-u-momm,
for når du får øvd deg nok,
blir du foff-loll-i-nonn-kokk!

Slik lyder André Bjerkes barnevers, Røversproget. Røverspråket er et kodespråk som brukes av barn for å holde en melding hemmelig. Røverspråket krypterer meldingen, det vil si at den blir gjort uforståelig for de som ikke behersker røverspråket og kan dekryptere den.

Nå gir ikke røverspråket noen særlig god kryptering, for det er så enkelt som å etter hver konsonant legge til bokstaven o, etterfulgt av samme konsonant om igjen. (Bjerke legger til konsonanten to ganger, antakelig for å få bedre rim og rytme.) Men det illustrerer ideen med å gjøre meldinger uleselige for uvedkommende. Kryptografi er kjent helt fra Julius Cæsars tid, og hadde i militær sammenheng stor betydning under andre verdenskrig, da tyskerne benyttet den avanserte krypteringsmaskinen Enigma. Enorme ressurser ble satt inn av de allierte for å knekke krypteringskodene, og de lyktes, noe som sies å ha hatt stor betydning for D-dagen. Sentral i arbeidet var matematikeren og datapioneren Alan Turing. Filmen The Imitation Game fra 2014 er basert på hans liv og arbeid.

I dag benytter vi kryptografi uten å tenke over det, for eksempel når vi kommuniserer på Internett ved hjelp av protokollen https, Hypertext Transfer Protocol Secure, der Secure indikerer at kommunikasjonen er kryptert.

Ordet kryptografi kommer fra gresk: kryptos, ′skjult′, og graphein, ′skrive′, og betyr altså skjult skrift.

I kryptografi er kongruensregning sentralt.

Forskyvningskoder

For å kunne bruke matematiske operasjoner på bokstaver, bytter vi dem ut med tall. Når vi lagrer tekst på en datamaskin for eksempel, blir hver bokstav erstattet med et tall maskinen kan representere. Det finnes flere standarder for hvilket tall hver bokstav blir tilordnet, de vanligste er ASCII og Unicode. Når vi så skal hente fram teksten igjen, blir tallene gjort tilbake til bokstaver. Da ASCII ble laget, var det ingen som tenkte på at mange språk har flere bokstaver enn de engelske A-Z, så koder for nasjonale bokstaver som Æ, Ø og Å, ble klattet på i ettertid, noe som førte til at det ikke var universell enighet om disse kodene. Resultatet har nok de fleste av oss sett, når tallene som representerer Æ, Ø og Å blir avkodet som [, \ og ].
I denne artikkelen skal vi imidlertid bruke et enkelt system, der bokstavene A-Å tilordnes tallene 1-29 etter hvilken plass de har i alfabetet, slik:

A B C D E F G H I J K L M N
1 2 3 4 5 6 7 8 9 10 11 12 13 14
O P Q R S T U V W X Y Z Æ Ø Å
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Dette oppsettet kommer vi senere til å referere til som «kodetabellen».

Når motorsykkelklubben Hells Angels har tallet 81 på draktene, er det en referanse til denne kodetabellen, for bokstav nummer 8 og 1 i alfabetet er H og A.

En av de enkleste og eldste måtene å kryptere en melding på er å bytte ut bokstaver med andre etter et fast mønster, for eksempel med bokstavene som følger tre plasser bak i alfabetet. Dette kaller vi en forskyvningskode, eller cæsarchiffer.

Så kan vi bruke forskyvningskoden på hver bokstav i et ord, og få for eksempel PDWWHPRUR.

Eksempel 1:

Vi skal kryptere bokstaven N ved å forskyve 3 plasser.

N tilsvarer 14 i kodetabellen. Så vi krypterer ved å beregne 14 + 3 = 17, noe som tilsvarer Q i kodetabellen.

Q har kode 17, så vi dekrypterer ved å beregne 17 − 3 = 14, noe som tilsvarer N, som vi startet med.

Men hva om vi går forbi slutten på kodetabellen? Forskyver vi for eksempel Ø tre plasser, får vi 28 + 3 = 31, som ikke har noen bokstav tilordnet seg. Da starter vi ganske enkelt forfra, og lar A være bokstaven som følger etter Å.

Eksempel 2:

Vi skal kryptere bokstaven Æ ved å forskyve 4 plasser.

Æ tilsvarer 27 i kodetabellen. Så vi krypterer ved å beregne 27 + 4 = 31, noe tilsvarer to plasser etter Å, så vi havner på B.

B har kode 2, så vi dekrypterer ved å beregne 2 − 4 = −2, noe som tilsvarer to plasser før Å, altså Æ, som vi startet med.

Med to konsentriske kodehjul av papp lager vi enkelt en generator for slike forskyvingskoder:

Kodehjul til å lage forskyvningskoder

Men selvfølgelig blir det fort kjent hvilken forskyvning som er benyttet, og hvem som helst kan dekryptere meldingene. For å gjøre det litt mer komplisert, kan vi variere hvor mange plasser vi forskyver bokstavene.

Mottaker av meldingen må da selvsagt kjenne mønsteret vi forskyver etter. Vi kan for eksempel bli enige om at vi baserer oss på hvilken dato det er, og forskyve 1 den første i hver måned, 2 den andre, og så videre. Ordet MYSTISK blir da NZTUJTL den første og OÆUVKUM den andre. Den tjueåttende blir det LXRSHRJ, men den tjueniende er vi tilbake til utgangspunktet MYSTISK, fordi vi da forskyver oss gjennom hele tabellen og ender opp der vi startet.

Så den tjueniende får vi finne på noe annet. Den trettiende og trettiførste får vi samme koder som den første og andre i måneden.

Vi har altså egentlig bare 28 forskjellige muligheter, og kan lett bryte koden med penn og papir, for ikke å snakke om med en datamaskin.

Men åpner vi for forskjellig forskyvning for hver bokstav, blir det annerledes. Vi kan for eksempel velge at A forskyves med 2 til C, B med 8 til J, etc. Nå kan vi for så vidt godt tillate en forskyvning på 0 også. For hver bokstav finnes det da 29 alternativer, totalt 2929 ≈ 2,57 · 1042 kombinasjonsmuligheter. Ikke en gang den raskeste datamaskin vil komme noen vei med å blindt prøve seg fram. Imidlertid finnes det smartere måter å bryte en kode på, bokstavene i et språk opptrer nemlig ikke tilfeldig. Beholder vi ordgrensene i en setning, gjør vi det ekstra enkelt for den som vil dekryptere meldingen vår. På norsk må ord som bare består av én bokstav være I eller Å. Finner vi så disse bokstavene igjen i ord på to bokstaver, kan vi lett nøste oss videre. La oss si at vi finner ut at X er en kryptert Å, og også har ordet XZ. Da må det enten være ÅL, ÅR, ÅA, ÅS, ÅT, ÅK eller ÅH. Ikke alle er like sannsynlige, og vet vi at meldingen antakelig dreier som om noe taktisk militært, må det jo være lov å gjette på ÅS.

Uten ordgrenser blir det vanskeligere, teksten kan for eksempel være satt sammen av sekvenser på fem og fem tegn uten at det har noe med ordlengde å gjøre. Har vi imidlertid en tekst med en viss størrelse, kan vi bruke tekstanalyse til å dekryptere. På norsk er den bokstaven som forekommer flest ganger sannsynligvis en E, siden det er den vanligste bokstaven. Gjennomsnittlig er 15,2 % av bokstavene i en vilkårlig, norsk tekst en E. Den nest vanligste bokstaven er R, med 8,6 %. Ved å sammenlikne hyppigheten av bokstaver med hvor ofte de vanligvis opptrer, vil vi kunne lykkes med en fullstendig dekryptering. På andre språk vil vi kunne finne tilsvarende mønstre.

For å unngå at en kode kan brytes ved tekstanalyse, sørger vi for at det varierer hvor mye en bokstav forskyves. Mottaker av meldingen må selvfølgelig da også vite på hvilken måte dette er gjort. Vi kan da bli enige om et kodeord, en krypteringsnøkkel, som vi lar bestemme forskyvningen. La oss si at vi skal kryptere meldingen VI ANGRIPER NÅ, og kodeordet er WINSTON, da skal V (22) forskyves med W (23), I (9) med I (9), etc. ifølge tabellen under.

V I   A N G R I P E R   N Å
W I N S T O N W I N S T O N
P R   T E V C C Y S H   Å N

Fjerner vi mellomrom, blir resultatet PRTEVCCYSHÅN. Vi ser at bokstaven C forekommer to ganger, men den ene gangen representerer den R, den andre I.

Men selvsagt bør vi ikke velge et kodeord som er så lett å gjette.

Imidlertid vil vi selv i tekster som er kryptert på denne måten kunne oppdage mønstre, som vi etter hvert kan bruke til å avsløre kodeordet. Kodeordet bør derfor byttes ut med jevne mellomrom. Dette kan gjøres ved kodebøker som inneholder informasjon om hvilke kodeord som skal brukes til enhver tid, for eksempel kan vi ha et nytt kodeord hver dag og skifte ved midnatt.

Enigma-maskinen som tyskerne benyttet til kryptering under andre verdenskrig, byttet kontinuerlig krypteringsnøkler automatisk ved hjelp av mekanikk og elektronikk.

Men kodebøker og Enigma-maskiner må distribueres til brukerne uten at fienden får tak i dem. Og det er problematisk. Faktisk gis noen polakker som fikk fatt i en Enigma-maskin mye av æren for at de allierte klarte å knekke de tyske kodene.

I våre dager snakker vi ikke lenger om kodebøker og mekaniske dingser, krypteringsnøklene sendes over Internett, der det er store muligheter for at uvedkommende kan snappe dem opp. Da må det vel være utrolig lett å knekke kodene?

Offentlige nøkler

Med de krypteringssystemene vi har beskrevet, er det viktig å hindre at uvedkommende får kjennskap til krypteringsnøkler, for eksempel ved å stjele en kodebok eller kodegenerator, eller ved å analysere krypterte meldinger. Den som får tak i krypteringsnøkkelen, vil nemlig kunne lese alle meldinger som er kryptert med den. For systemene er reversible, det vil si at vi kan komme fram til den opprinnelige teksten ved å bruke krypteringsnøkkelen baklengs.

Mye bedre er det da hvis krypteringsnøkkelen er enveis, slik at den kun kan brukes til kryptering, ikke til dekryptering. Og slik fungerer moderne krypteringssystemer. Nøkkelen som brukes til kryptering, kan ikke brukes baklengs. For å få fram den opprinnelige teksten, kreves en egen dekrypteringsnøkkel. Det spiller ingen rolle om noen får tak i krypteringsnøkkelen, den kan godt være tilgjengelig for alle. I et slikt system kalles derfor krypteringsnøkkelen for offentlig nøkkel, og dekrypteringsnøkkelen for privat nøkkel.

La oss si at Ola skal sende en melding til Kari. Da gjør de følgende:

Kari lager en offentlig og en privat nøkkel.

Kari sender den offentlige nøkkelen til Ola.

Ola krypterer meldingen med den offentlige nøkkelen og sender den til Kari.

Kari dekrypterer meldingen med den private nøkkelen.

I artikkelen RSA-systemet ser vi hvordan vi kan bruke kongruensregning til å lage et slikt system.

Et system med offentlige og private nøkler kan også brukes baklengs, til såkalte digitale signaturer. Da kodes meldingen med den private nøkkelen, og hvis den lar seg avkode med den offentlige nøkkelen, vet vi at den er kodet av riktig avsender.

Kryptering ved hjelp av kongruenser

I det følgende vil vi la u k bety at tallkoden u krypteres til tallkoden k, og omvendt, at k u betyr at tallkoden k dekrypteres til tallkoden u. Her står u står for «ukryptert» og k for «kryptert».

Kryptering ved addisjon

Vi har tidligere sett hvordan vi kan kryptere ved å tildele bokstavene tallkoder fra 1 til 29 og så forskyve ved å addere et tall, den såkalte krypteringsnøkkelen, til tallkoden. Og vi har sett hvordan vi dekrypterer ved å gå motsatt vei og subtrahere krypteringsnøkkelen fra tallkoden. Matematisk uttrykt krypterer vi da med nøkkel r ved å beregne u k som k = u + r, og vi dekrypterer med nøkkel r ved å beregne k u som u = kr.

Vi har også sett at dette systemet umodifisert skaper problemer hvis vi går forbi slutten på kodetabellen, og at vi løser problemet ved å starte forfra, altså la A følge etter Å. Dette systemet kjenner vi igjen som å regne modulo 29, siden Å er den siste og 29. bokstaven i alfabetet. Det vil si at vi krypterer med nøkkel r ved å beregne u k som ku + r (mod 29), og vi dekrypterer med nøkkel r ved å beregne k u som u ≡ kr (mod 29).

Eksempel 3:

Vi skal kryptere bokstaven Z med krypteringsnøkkel r = 5, altså ved å forskyve 5 plasser modulo 29.

Z tilsvarer u = 26 ifølge kodetabellen, så vi får k ≡ 26 + 5 ≡ 31 ≡ 2 (mod 29), noe som tilsvarer B i kodetabellen.

Dekryptering gir u ≡ 2 − 5 ≡ −3 ≡ 26 (mod 29), som i kodetabellen tilsvarer Z, som vi startet med.

Kryptering ved multiplikasjon

I stedet for å kryptere ved å addere et tall kan vi velge å kryptere ved å multiplisere med et tall.

Kryptering, u k, gjøres da med nøkkel r ved hjelp av kongruensen

kru (mod 29)

Da vi krypterte ved å legge til et tall, dekrypterte vi ved å trekke fra det samme tallet modulo 29. Men når vi krypterer ved å multiplisere med et tall modulo 29, kan vi ikke bare dividere med det samme tallet, da risikerer vi å få noe som ikke er et helt tall. Lar vi for eksempel r være 9 og u være 5, får vi ru ≡ 9 · 5 ≡ 45 ≡ 16 (mod 29). Men 16 dividert med 9 tar oss ikke tilbake til u = 5.

Det vi i stedet må gjøre, er å multiplisere med en multiplikativ invers til r modulo 29, la oss kalle den r. En slik invers er definert slik at r · r ≡ 1 (mod 29). For eksempel er r = 13 en multiplikativ invers til r = 9 modulo 29 fordi r · r ≡ 13 · 9 ≡ 117 ≡ 1 (mod 29). 

(Å beregne at 117 ≡ 1 (mod 29) kan vi gjøre ved å skrive mod(117, 29) i inntastingsfeltet i GeoGebra, eller =rest(117; 29) i et regneark.)

Du finner mer om multiplikative inverser i artikkelen om regneregler i kongruenser.

Kongruensen for å kryptere u k, med nøkkel r var altså

kru (mod 29)

Hvis vi multipliserer med r på begge sider av kongruenstegnet, får vi

r · k ≡ r · ru (mod 29) ⇒ r · k ≡ 1 · u (mod 29) ⇒ u ≡ r · k (mod 29)

Dekryptering, k u, gjøres altså ved å multiplisere k med r. Vi kaller r dekrypteringsnøkkelen. For å kryptere og dekryptere bruker vi altså forskjellige nøkler, henholdsvis r og r.

Dekrypteringsnøkkelen beregnes altså ut fra krypteringsnøkkelen ved å finne en multiplikativ invers. Dette nettstedet har en app for å finne multiplikative inverser.

Eksempel 4:

Vi velger krypteringsnøkkel r = 11. Dekrypteringsnøkkelen er da r = 8, fordi r · r ≡ 8 · 11 ≡ 88 ≡ 1 (mod 29).

Med nøkkelen r = 11 skal vi så kryptere bokstaven E, som vi representerer med u = 5 ifølge kodetabellen. Vi får

kru ≡ 11 · 5 ≡ 55 ≡ 26 (mod 29), altså Z, ifølge kodetabellen.

Denne utregningen kan vi gjøre ved å skrive mod(11*5, 29) i inntastingsfeltet i GeoGebra eller =rest(11*5; 29) i et regneark.

For å dekryptere Z, altså k = 26, beregner vi

u ≡ r k ≡ 8 · 26 ≡ 208 ≡ 5 (mod 29), altså E, som vi startet med.

Denne utregningen kan vi gjøre ved å skrive mod(8*26, 29) i inntastingsfeltet i GeoGebra eller =rest(8*26; 29) i et regneark.

Oppgave 1:

Vi har krypteringsnøkkel r = 10.

Verifiser at en dekrypteringsnøkkel ved multiplikasjon modulo 29 da er r = 3.

Bruk r og r til å kryptere og dekryptere bokstaven H.

Tips: Bruk GeoGebra eller et regneark til utregningene.

Se løsningsforslag

Men det er jo egentlig ingen grunn til å låse seg til å regne modulo 29. Vi kan godt generalisere u k til kru (mod n), der n er et vilkårlig heltall større eller lik 29. Nå følger vi imidlertid ikke lenger kodetabellen, som går modulo 29, så koden k kan ikke lenger tolkes som en bokstav.

r og n utgjør nå sammen krypteringsnøkkelen, mens r og n sammen utgjør dekrypteringsnøkkelen.

Vi kan imidlertid ikke velge r og n helt fritt, vi må kreve at SFF(r, n) = 1, ellers vil ikke r ha noen multiplikativ invers modulo n. Da vi brukte n = 29, var ikke dette noe problem fordi 29 er et primtall, så SFF(r, 29) = 1 for alle r < 29.

Eksempel 5:

Vi velger krypteringsnøkkel (39, 100), altså r = 39, n = 100. Dette er et gyldig valg fordi SFF(39, 100) = 1.

Dekrypteringsnøkkelen blir da (59, 100), altså r = 59, n = 100, fordi r · r ≡ 59 · 39 ≡ 2301 ≡ 1 (mod 100).

Med nøkkelen (39, 100) skal vi så kryptere bokstaven N, som vi representerer med u = 14 ifølge kodetabellen. Vi får

kru ≡ 39 · 14 ≡ 55 ≡ 546 ≡ 46 (mod 100). Siden vi ikke lenger arbeider modulo 29, kan vi ikke representere dette som en bokstav.

For å dekryptere k = 46, beregner vi

u ≡ r k ≡ 59 · 46 ≡ 2714 ≡ 14 (mod 100), altså N, som vi startet med.

(Å beregne at 546 ≡ 46 (mod 100) og 2714 ≡ 14 (mod 100) gjør vi i hodet ved å fjerne alt unntatt de siste to sifrene.)

Oppgave 2:

Begrunn at krypteringsnøkkelen (9, 79) er gyldig til kryptering ved multiplikasjon, og at den tilhørende dekrypteringsnøkkelen blir (44, 79).

Bruk disse nøklene til å kryptere og dekryptere bokstaven B.

Tips: Bruk GeoGebra eller et regneark til utregningene.

Se løsningsforslag

Kryptering ved eksponentiering

Når vi bruker kryptering ved multiplikasjon, kan vi dekryptere en melding hvis vi får kjennskap til krypteringsnøkkelen, fordi vi ut fra denne kan beregne dekrypteringsnøkkelen, i form av en multiplikativ invers. Men nå lager vi en ny krypteringsvariant, der vi opphøyer i nøkkelen i stedet for å multiplisere med nøkkelen.

Kryptering, u k, gjøres da med nøkkel (r, n), ved hjelp av kongruensen

kur (mod n)

Eksempel 6:

Vi skal kryptere F med nøkkel (7, 22).

Fordi F kodes med u = 6, får vi

k ≡ 67 ≡ 279936 ≡ 8 (mod 22). F krypteres som k = 8.

Oppgave 3:

Bruk eksponentiering til å kryptere B, kodet med u = 2, med nøkkel (5, 19).

Tips: Bruk GeoGebra eller et regneark til utregningene.

Se løsningsforslag

Eksempel 7:

Vi skal kryptere C med nøkkel (35, 221).

Fordi C kodes med u = 3, får vi

k ≡ 335 ≡ 61 (mod 221). C krypteres som k = 61.

Å beregne at 335 ≡ 61 (mod 221) klarer vi imidlertid ikke gjøre med GeoGebra eller regneark fordi disse applikasjonene ikke kan beregne rest ved så store tall. Utregningen kan vi imidlertid gjøre ved hjelp av teknikken med toerpotenser, som er beskrevet i avsnittet «Rest ved divisjon av store tall» i artikkelen om anvendelser av kongruens:

Vi ser at 35 = 1 + 2 + 32.

Så 335 = 31 + 2 + 32 = 31 · 32 · 332.

Og vi får

3 ≡ 3 (mod 221)

32 ≡ 9 (mod 221)

34 ≡ (32)2 ≡ 92 ≡ 81 (mod 221)

38 ≡ (34)2 ≡ 812 ≡ 6561 ≡ 152 (mod 221)

316 ≡ (38)2 ≡ 1522 ≡ 23104 ≡ 120 (mod 221)

332 ≡ (316)2 ≡ 1202 ≡ 14400 ≡ 35 (mod 221)

Så 335 ≡ 3 · 9 · 35 ≡ 945 ≡ 61 (mod 221).

Til utregningene underveis kan vi bruke GeoGebra eller et regneark, siden bare tall i en størrelsesorden disse verktøyene håndterer uten problemer er involvert. For eksempel finner vi at 14400 ≡ 35 (mod 221) ved å skrive mod(14400, 221) i GeoGebra eller =rest(14400; 221) i et regneark.

Vi kan også beregne resten direkte ved hjelp av appen for å beregne rest, som finnes på dette nettstedet, med «a» = 3, «b» = 35 og «n» = 221.

Oppgave 4:

Bruk eksponentiering til å kryptere G med nøkkel (25, 99). Gjør beregningene ved hjelp av teknikken med toerpotenser, og sjekk svaret med appen for å beregne rest.

Se løsningsforslag

For å dekryptere, altså beregne k u, må vi finne ut hvilken u som er slik at urk (mod n). Og selv om vi kjenner krypteringsnøkkelen, r, er dette så og si umulig når tallene er store.

Vi trenger altså nå en egen dekrypteringsnøkkel. En slik nøkkel vil, sammen med n, være en s som er slik at ursu (mod n). Grunnen til dette er som følger:

Vi krypterer som sagt med kongruensen kur (mod n). Bytter vi om på leddene, får vi ur ≡ k (mod n). Opphøyer vi begge sider i s, får vi urs ≡ ks (mod n). Og siden ursu (mod n), blir dette u ≡ ks (mod n). Så vi kan dekryptere, k u , ved kongruensen u ≡ ks (mod n). 

En slik dekrypteringsnøkkel, s, kan vi imidlertid ikke automatisk finne selv om vi kjenner krypteringsnøkkelen, slik vi kunne når vi krypterte ved multiplikasjon. Krypteringsnøkkelen kan derfor godt være tilgjengelig for alle. Dekrypteringsnøkkelen må imidlertid holdes hemmelig. Vi ser at dette er et system med private og offentlige nøkler.

Dekryptering, k u, gjøres altså med nøkkel (s, n), ved hjelp av kongruensen

uks (mod n)

Eksempel 8:

I eksempel 6 kodet vi F med u = 6, krypterte med nøkkel (7, 22), og fikk k = 8.

Den tilhørende dekrypteringsnøkkelen er (3, 22).

Vi dekrypterer derfor ved å beregne

u ≡ 83 ≡ 512 ≡ 6 (mod 22). Vi er tilbake til u = 6, altså F, som vi startet med.

Beregningene gjør vi i GeoGebra eller et regnenark.

Oppgave 5:

I oppgave 3 kodet vi B med u = 2, krypterte med nøkkel (5, 19), og fikk k = 13. Den tilhørende dekrypteringsnøkkelen er (11, 19). Bruk denne til å dekryptere k = 13.

Hint: Det er mulig å gjøre beregningene i GeoGebra eller regneark.

Se løsningsforslag

Oppgave 6:

Når en krypteringsnøkkel er (13, 77), er en dekrypteringsnøkkel (37, 77).

Bruk dette til å kryptere og dekryptere bokstaven B, kodet med u = 2.

Gjør beregningene i GeoGebra eller regneark hvis det er mulig. Hvis ikke, bruk metoden med toerpotenser.

Se løsningsforslag

I eksemplene og oppgavene over har vi angitt dekrypteringsnøkkelen uten nærmere forklaring. I artikkelen om RSA-systemet skal vi se hvordan vi kan generere en dekrypteringsnøkkel samtidig som vi genererer krypteringsnøkkelen.

Kilder

    • Gustavsen, T.S. Hinna, K.R.C., Borge, I.C., & Andersen, P.A. (2014). QED Matematikk for grunnskolelærerutdanningen 5-10, Bind 2. 1. utgave. Kristiansand: Cappelen Akademisk.
    • Rinvold, A. R. (2009). Visuelle perspektiv. Tallteori. Caspar Forlag.
    • Petersen, V. B., Tvete, K. S. (2013). I tallkongruensenes verden. Caspar Forlag.
    • Johnsen, B. (2001). Kryptografi – den hemmelige skriften. Trondheim: Tapir akademisk forlag.
    • Bjerke, A. (1980). Moro-vers. Norbok a.s.

Pytagoreiske tripler

Hva er pytagoreiske tripler?

De fleste kjenner Pytagoras′ setning, som sier at i en rettvinklet trekant er kvadratet på hypotenusen lik summen av kvadratene på katetene. z2 = x2 + y2 i figuren under.

Rettvinklet trekant med sider x, y og z

Eksempel 1:

x = 3 og y = 4 gir $z = \sqrt{3^2 + 4^2} = \sqrt{25} = 5$.

Eksempel 2:

x = 2 og y = 3 gir $z = \sqrt{2^2 + 3^2} = \sqrt{13}$.

I eksempel 1 gir heltallige x og y en heltallig z, men ikke i eksempel 2. I tallteorien kalles et trippel (x, y, z) som gir hele tall i Pytagoras′ setning for et pytagoreisk trippel. For eksempel er (3, 4, 5) et pytagoreisk trippel.

Likningen z2 = x2 + y2, der vi bare er ute etter løsninger som er hele tall, er en diofantisk likning av andre grad (kvadratisk, diofantisk likning). Pytagoreiske tripler er løsninger til denne likningen. Vi skal nå se nærmere på disse.

Dobler vi sidelengdene i trekanten fra eksempel 1, får vi en ny, likeformet trekant som er dobbelt så stor, med sidekanter 2 · 3 = 6, 2 · 4 = 8 og 2 · 5 = 10. Det vil si at (6, 8, 10) også er et pytagoreisk trippel. Generelt kan vi lage uendelig mange pytagoreiske tripler på denne måten, ved å multiplisere hver side i trekanten med samme tall, k. Med k = 3, for eksempel, gir eksempel 1 det pytagoreiske trippelet (9, 12, 15).

Naturligvis kan vi gå endre veien også. Ved å dividere med en konstant, k, som går opp i alle elementene i trippelet, får vi et nytt pytagoreisk trippel. I (12, 16, 20) kan vi for eksempel dividere med 4, og får (3, 4, 5). Dividerer vi med de tre tallenes største felles faktor, SFF(x, y, z), står vi igjen med et pytagoreisk trippel der SFF(x, y, z) = 1. Dette kalles et primitivt pytagoreisk trippel.

Oppgave 1:

Avgjør om følgende er primitive pytagoreiske tripler:

      1. (1, 2, 3)
         
      2. (2, 9, 15)
         
      3. (3, 4, 5)

Skjermfilm
Se film der løsningsforslaget vises

Oppgave 2:

Avgjør om følgende er primitive pytagoreiske tripler:

      1. (5, 12, 13)
         
      2. (10, 24, 26)
         
      3. (7, 24, 29)

Se løsningsforslag

Generatorer for pytagoreiske tripler

I forrige avsnitt tok vi utgangspunkt i en rettvinklet trekant med sider lik x = 3, y = 4 og z = 5, og viste med en figur hvordan denne trekanten så ut. Og vi sa at (3, 4, 5) er et primitivt pytagoreisk trippel. Multipliserte vi hvert element i dette triplet med en konstant, fikk vi et nytt pytagoreisk trippel som ikke var primitivt. Dette motsvarte å endre størrelsen på trekanten, men ikke formen. Et annet primitivt pytagoreisk trippel – og multipler av dette – vil imidlertid motsvare en trekant med en annen form.

Under vises eksempler på tre forskjellige, primitive pytagoreiske tripler.

(3, 4, 5)

(5, 12, 13)

(7, 24, 25)

Her ser det ut til å være et mønster. Vi legger merke til at x er oddetall, og z = y + 1 i alle tallene.
Vi kan prøve å finne et nytt trippel med samme form der x = 9 og z = y + 1 ved å sette inn i Pytagoras likning: 92 + y2 = (y + 1)2. Løser vi denne likningen, får vi y = 40. Så (9, 40, 41) er et primitivt pytagoreisk trippel.

Oppgave 3:

Finn y og z slik at (11, y, z) er et primitivt pytagoreisk trippel der z = y + 1.

Se løsningsforslag

Hvor mange slike primitive pytagoreiske tripler der z = y + 1 finnes det? Uendelig? Må x alltid være et oddetall?

Generelt kan vi skrive uttrykket der z = y + 1 slik: x2 + y2 = (y + 1)2. Dette kan omskrives til x2 = (y + 1)2y2.

Hvis y2 er partall, er (y + 1)2 oddetall og omvendt. x2 er derved alltid differansen mellom et oddetall og et partall, og må følgelig være oddetall. Da må x også være oddetall. Alle oddetall kan skrives som 2n + 1, der n er et naturlig tall. Setter vi dette inn i Pytagoras likning, får vi (2n + 1)2 + y2 = (y + 1)2. Løser vi likningen med hensyn på y, får vi at y = 2n2 + 2n, og følgelig at z = 2n2 + 2n + 1.

Vi har altså:

$\fbox{$x = 2n + 1$, $y = 2n^2 + 2n$, $z = 2n^2 + 2n + 1$}$

Her har vi kommet fram til en generator som produserer uendelig mange primitive pytagoreiske tripler, ett for hvert naturlige tall, n, der x er oddetall og z = y + 1. Det kan bevises at triplene er primitive.

Pytagoreernes trippelgenerator

$\fbox{$x = \frac{\displaystyle n^2 − 1}{\displaystyle 2}, y = n, z = \frac{\displaystyle n^2 + 1}{\displaystyle2}$}$

Her er n er et oddetall større enn 1.

Pytagoreernes trippelgenerator er den samme generatoren som vi allerede har utledet, i en litt annen form. Her har x og y byttet plass, og vi krever eksplisitt at n skal være oddetall større enn 1. Her har vi altså at y alltid er oddetall og z = x + 1. De tre første triplene den genererer er (4, 3, 5), (12, 5, 13), (24, 7, 25) som vi kjenner igjen fra tidligere, bare at x og y har byttet plass.

Platons trippelgenerator

$\fbox{$x = 4n, y = 4n^2 − 1, z = 4n^2 + 1$}$

Her er n er et naturlig tall:

Platons trippelgenerator produserer tripler der z = y + 2. De første er (4, 3, 5), (8, 7, 9), (12, 11, 13). Den første kjenner vi fra tidligere, men de to siste er nye. Med Platons trippelgenerator kan vi finne uendelig mange primitive pytagoreiske tripler, ett for hvert naturlig tall, n, der z = y + 2.

Oppgave 4:

Her er et bevis for at triplene Pytagoreernes generator produserer er primitive:

Det er slik at hvis d går opp i a, og d går opp i b, så vil d gå opp i (ab). I triplene som Pytagoreernes generator produserer, er zx = 1, og det eneste tallet som går opp i 1 er 1. z og x har derved ingen felles faktor som kan divideres bort. Triplene er derfor primitive.

Angi et tilsvarende argument for at triplene Platons generator produserer er primitive.

Se løsningsforslag

Generisk trippelgenerator

I forrige avsnitt så vi at Pytagoreernes trippelgenerator produserer alle mulige primitive pytagoreiske tripler der z = y + 1. (Alternativt z = x + 1). Platons trippelgenerator produserer alle mulige primitive pytagoreiske tripler der z = y + 2. Men det finnes alle mulige andre varianter. Nå skal vi finne fram til en generator som produserer alle mulige former for pytagoreiske tripler.

I de eksemplene vi har sett, er alltid x oddetall og y partall, eller omvendt. Men må det alltid være slik? Finnes det primitive pytagoreiske tripler der x og y begge er partall eller begge er oddetall?

Det er ikke så vanskelig å forstå at både x og y ikke kan være partall. For da ville z2 blitt partall, og følgelig z partall. Vi ville altså hatt en faktor k = 2 å forkorte bort, og trippelet ville ikke vært primitivt.

Argumentet for at både x og y ikke kan være oddetall er litt mer innviklet:

Hvis x og y begge er oddetall, er x2 og y2 også oddetall. Summen av to oddetall er et partall, så z2 blir partall, og følgelig z partall. Et partall kan skrives på formen 2n, og et oddetall på formen 2n + 1, der n er et helt tall.

Kvadratet av et partall er på formen (2n)2 = 4n2, som kan skrives som 4m, der m er et helt tall.

Kvadratet av et oddetall er på formen (2n + 1)2 = 4n2 + 4n + 1, som kan skrives som 4m + 1, der m er et helt tall.

Summen av kvadratene av to oddetall blir på formen 4m1 + 1 + 4m2 + 1, som kan skrives som 4m + 2, der m er et helt tall.

Siden x2 + y2 er på formen 4m + 2, vil vi få rest 2 hvis vi dividerer x2 + y2 med 4.

Siden z2 er på formen 4m, vil vi få rest 0 hvis vi dividerer z2 med 4.

Siden x2 + y2 og z2 ikke gir samme rest ved divisjon med 4, kan de ikke være samme tall.

x og y kan følgelig ikke begge være oddetall.

Vi har altså kommet fram til at i et primitivt pytagoreisk trippel er den ene av x og y partall og den andre oddetall. Det spiller ingen rolle hvilken som er hvilken, så i det følgende bestemmer vi oss for å la x være partallet og y oddetallet.

Kvadratet av et partall er et partall og kvadratet av et oddetall er et oddetall. Summen av et partall og et oddetall er et oddetall. Derfor blir z2 = x2 + y2 oddetall, og følgelig z oddetall.

Våre generelle, primitive pytagoreiske tripler blir altså på formen (P, O, O), der P er partall og O er oddetall.

Vi lar y2 bytte side i Pytagoras likning, og får x2 = z2y2. Så bruker vi 3. kvadratsetning baklengs, og får x2 = (z + y)(zy). Vi dividerer med 4 på begge sider av likningen og får

${\large {(\frac{\large x^2}{4}})} = {\large \frac{\large (z + y)(z−y)}{4}}$

Som kan skrives som

  1. ${\large {(\frac{\Large x}{2}})}^2 = {\large \frac{\Large z + y}{ 2}} \cdot {\large \frac{\Large z − y}{ 2}}$

De to tallene på høyre side av likhetstegnet kan ikke ha noen annen felles faktor enn 1. For en felles faktor måtte gått opp i både summen og differansen. Denne summen er ${\large \frac{\Large (z + y) + (z − y)}{2}} = z$, og differansen er ${\large \frac{\Large (z + y) − (z − y)}{2}} = y$. En felles faktor måtte derfor gått opp i både z og y, noe som er umulig fordi vi har forutsatt at vi har et primitivt trippel uten andre felles faktorer enn 1.

Vi vet at produktet av de to tallene på høyre side er kvadrattall fordi venstre side er kvadrattall. Og siden de ikke har felles faktorer, kan de bare bli dette hvis de i seg selv er kvadrattall. Vi kaller første tall for s2 og andre tall for t2:

  1. ${\large \frac{\Large z + y}{ 2}} = s^2$ og ${\large \frac{\Large z − y}{ 2}} = t^2$

Løser vi dette likningssettet med hensyn på z og y, får vi z = s2 + t2 og y = s2t2. Ved å sette disse verdiene inn i 1) og regne ut, får vi at x = 2st.

Vi har tidligere sagt at tallene vi kalte for s2 og t2 ikke har felles faktorer. Det må derved også gjelde s og t. De kan derved ikke begge være partall. De kan heller ikke begge være oddetall, for da ville z = s2 + t2 blitt partall, noe som var mot forutsetningene. For at y skal bli større enn 0, må vi også ha at s > t.

Da har vi endelig kommet fram til følgende teorem:

$\fbox{$\begin{align} &\text{Alle primitive pytagoreiske tripler, }(x, y, z) \\
&\text{kan uttrykkes ved formlene: } \\
&x = 2st, \, y = s^2 − t^2, \, z = s^2 + t^2 \end{align}$}$

der s og t er hele, positive tall, SFF(s, t) = 1, s > t, og ett av tallene s og t er partall mens det andre er oddetall.

Basert på de primitive triplene som kan genereres basert på dette teoremet kan vi lage andre tripler som ikke er primitive ved å multiplisere hvert element med en konstant.

Oppgave 5:

I figuren under vises to verdier av s og t, og triplene de genererer ved hjelp av teoremet over. Bygg videre på tabellen slik at den i alt inneholder ti forskjellige, primitive pytagoreiske tripler. Bruk så små verdier av s og t som mulig.

Tabell med genererte pytagoreiske tripler

Regneark
Åpne et regneark for å lage pytagoreiske tripler
.

Se løsningsforslag

Pytagoreisk trekant

En rettvinklet trekant der sidelengdene danner et pytagoreisk trippel, kalles en pytagoreisk trekant. Vi skriver inn en sirkel med radius r i en pytagoreisk trekant, slik som vist under:

Sirkel innskrevet i pytagoreisk trekant

Så skal vi vise at radien alltid blir et helt tall:

Det totale arealet til trekanten er

  1. $A = \frac{\displaystyle xy}{\displaystyle 2}$

Men den kan også deles opp i tre mindre trekanter med høyde r, som vist under

Sirkel innskrevet i pytagoreisk trekant, delt i tre

Arealet uttrykt ved disse trekantene blir

  1. $A = \frac{\displaystyle rx}{\displaystyle 2} + \frac{\displaystyle ry}{\displaystyle 2} + \frac{\displaystyle rz}{\displaystyle 2}$

Løser vi 1) og 2) med hensyn på r, får vi

  1. $r = \frac{\displaystyle xy}{\displaystyle x + y + z}$

Vi viste i forrige avsnitt at x, y og z danner et pytagoreisk trippel hvis x = 2st, y = s2t2 og z = s2 + t2. Setter vi dette inn i 3), får vi

$r = \frac{\displaystyle 2st(s^2 − t^2)}{\displaystyle 2st + s^2 − t^2 + s^2 + t^2} = \frac{\displaystyle t(s^2 − t^2)}{\displaystyle t + s} = \frac{\displaystyle t(s + t)(s − t)}{\displaystyle t + s} = t(s − t)$

Siden t og s er hele tall, blir også radien, r, et helt tall.

Sum av to kvadrattall

Pytagoreiske tripler er slik at summen av to kvadrattall er et kvadrattall. Det er nå naturlig å spørre seg om hvilke tall generelt som kan skrives som summen av to kvadrattall. Et eksempel på tall som kan skrives som en sum av to kvadrattall er 5 og 13, for 5 = 12 + 22 og 13 = 22 + 32. Men 7 og 11 kan ikke skrives som sum av to kvadrattall.

For å avgjøre om et odde primtall kan skrives som summen av to kvadrattall kan vi bruke følgende teorem, som vi angir uten bevis:

$\fbox{$\begin{align} &\text{Et odde primtall kan skrives som en sum av to kvadrattall} \\
&\text{hvis og bare hvis det er kongruent med 1 modulo 4} \end{align}$}$

Vi ser at dette er tilfelle for 5 og 13, som er kongruente med 1 modulo 4, men ikke 7 og 11, som er kongruente med 3 modulo 4.

Mer generelt har vi, for alle naturlige tall:

$\fbox{$\begin{align} &\text{Et naturlig tall kan skrives som en sum av to kvadrattall hvis og bare hvis} \\
&\text{ingen av tallets primtallsfaktorer er kongruente med 3 modulo 4,} \\
&\text{med mindre faktoren forekommer et par antall ganger} \end{align}$}$

Eksempel 3:

Vi skal avgjøre om 10 kan skrives som en sum av kvadrattall. Vi primtallsfaktoriserer 10 som 10 = 2 · 5.

$2 \equiv 2 \, (mod \; 4)$ og $5 \equiv 1 \, (mod \; 4)$. Siden ingen av faktorene er kongruente med 3 modulo 4, kan vi konkludere med at 10 kan skrives som en sum av kvadrattall. Og vi har 10 = 12 + 32.

Eksempel 4:

Vi skal avgjøre om 14 kan skrives som en sum av kvadrattall. Vi primtallsfaktoriserer 14 som 14 = 2 · 7.

$2 \equiv 2 \, (mod \; 4)$, så den faktoren er ok. Men $7 \equiv 3 \, (mod \; 4)$, og 7 forekommer et odde antall ganger, nemlig 1 gang, så vi kan derfor konkludere med at 14 ikke kan skrives som en sum av kvadrattall.

Eksempel 5:

Vi skal avgjøre om 98 kan skrives som en sum av kvadrattall. Vi primtallsfaktoriserer 98 som 98 = 2 · 7 · 7.

$2 \equiv 2 \, (mod \; 4)$, så den faktoren er ok. $7 \equiv 3 \, (mod \; 4)$, men 7 forekommer et par antall ganger, nemlig 2 ganger, så vi kan derfor konkludere med at 98 kan skrives som en sum av kvadrattall. Og vi har 98 = 72 + 72.

Oppgave 6:

Avgjør om følgende kan skrives som en sum av to kvadrattall:

26

39

45

Skjermfilm
Se film der løsningsforslaget vises

NB! I filmen brukes uttrykket «gi rest 3 ved divisjon med 4» i stedet for «kongruent med 3 modulo 4».

Oppgave 7:

Avgjør om følgende kan skrives som en sum av to kvadrattall:

20

38

18

Se løsningsforslag

Oppgave 8:

Over er det angitt to teoremer om hvilke tall som kan skrive som en sum av kvadrattall. Det første gjelder bare odde primtall, mens det andre gjelder alle naturlige tall. Forklar at det som gjelder odde primtall kan utledes av det som gjelder naturlige tall.

Se løsningsforslag

Tripler av høyere potens enn 2

I et pytagoreisk trippel finner vi egentlig fram til et kvadrat med heltallig sidelengde z, som har flateinnhold lik summen av flateinnholdet i to andre kvadrater med heltallig sidelengde x og y. Dette er illustrert i figuren under for x = 3, y = 4, z = 5.

Pytagoreisk trippel som sum av kvadrattall

Da er det naturlig å spørre seg om vi kan finne tre kuber med heltallig sidelengde der volumet av den første pluss volumet av den andre er lik volumet av den tredje. Altså en z som er slik at z3 = x3 + y3, der z, x og y er hele tall. Det noe overraskende svaret er at det gjør det ikke. Den diofantiske likningen av tredje grad på formen z3 = x3 + y3 har ingen løsning.

Faktisk har ingen diofantiske likninger av n-te grad på formen zn = xn + yn løsning når n > 2. (Vi ser da bort fra såkalte trivielle løsninger, der noen av x, y og z er 0.)

For n = 2 finnes det altså uendelig mange heltallige tripler med x, y og z, de pytagoreiske triplene, som vi har studert tidligere på denne siden. Men for n > 2 finnes det ingen. Dette ble formulert i 1637 av den franske juristen og matematikeren Pierre de Fermat. Noe generelt bevis kom han ikke med, så dette ble hetende Fermats gjetning, Fermats store sats eller Fermats siste sats. Fermat beviste imidlertid gjetningen for n = 4. I løpet av de neste hundreårene kom det bevis for tilfellene der n = 3, n = 5 og n = 7. Men et bevis som er gyldig for alle n, kom ikke før i 1995. I 2016 ble Sir Andrew John Wiles tildelt Abelprisen for dette beviset.
Siden gjetningen er bevist, kalles den nå også Fermats siste teorem. Søket etter bevis på Fermats gjetning har ført til betydelig utvikling i grener av matematikken.

Det generelle beviset for Fermats teorem er imidlertid svært komplisert. Men da Fermat lanserte sin gjetning, skrev han at han hadde funnet et vidunderlig bevis, men at det ikke ble plass til det i margen. At det har vært så komplisert å faktisk komme fram til et bevis tyder vel på at Fermat bløffet eller tok feil. Men om noen faktisk klarer å finne et enkelt bevis for Fermats teorem, vil de nok få navnet sitt skrevet med gullbokstaver i matematikkens historie.

Oppgave 9:

Finn Wiles′ bevis på nettet og skriv et kort sammendrag.

Bare tulla. Beviset er 150 sider langt og tok 7 år å utarbeide.

Kilder

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

Diofantiske likninger

Hva er diofantiske likninger

En likning på formen ax + by = c, der a, b og c er vilkårlige tall, kaller vi for en lineær likning. Et annet ord for lineær likning er førstegradslikning, fordi de ukjente, x og y er av første grad. Dette i motsetning til en likning som f.eks. ax2 + by = c, som er en andregradslikning.

Med å løse en slik likning mener vi å finne alle kombinasjoner av x og y som gjør at uttrykket på venstre og høyre side av likhetstegnet har samme verdi.

Eksempel 1:

Vi ser på likningen x + 2y = 2. (Her er a = 1, b = 2 og c = 2.)

Løser vi mhp. y, får vi $y = −{\large \frac{x}{2}} + 1$. Grafisk sett er dette ei rett linje med stigningstall $−{\large \frac{1}{2}}$, som skjærer y-aksen i y = 1:

Heltallsløsninger av likningen x + 2y = 2

I noen punkter på ei slik linje kan det være at både x og y er hele tall, slik som markert i grafen over.

En likning med flere ukjente der vi bare er ute etter heltallige løsninger, kalles diofantiske likninger, oppkalt etter grekeren Diofantos. Det vi skal studere i denne artikkelen, er lineære diofantiske likninger med to ukjente, det vil si likninger på formen ax + by = c, der a, b og c er hele tall. For enkelhets skyld kommer vi bare til å kalle dette diofantiske likninger.

Eksistens av løsninger

Hvis vi lurer på hvordan vi kan kombinere sedler på 500 kr og 200 kr til 2500 kr, vil svaret på dette være løsninger til den diofantiske likningen 500x + 200y = 2500, der x er antall sedler på 500 kr og y er antall sedler på 200 kr. Ved å prøve oss fram finner vi ut at det finnes tre muligheter:

x = 1, y = 10, altså 1 · 500 kr + 10 · 200 kr.

x = 3, y = 5, altså 3 · 500 kr + 5 · 200 kr.

x = 5, y = 0, altså 5 · 500 kr.

Men hvis vi i stedet spør om hvordan vi kan kombinere sedler på 1000 kr og 200 kr til 2500 kr, skjønner vi at det ikke går. Det finnes altså ikke noen heltallige løsninger av likningen 1000x + 200y = 2500, der x er antall sedler på 1000 kr og y er antall sedler på 200 kr.

Plottet under viser grafene til de to likningene. 500x + 200y = 2500 i blått, med de heltallige løsningene markert, og 1000x + 200y = 2500 i grønt. Vi ser at den grønne grafen ikke går gjennom noen punkter der både x og y er hele tall.

Grafer til to diofantiske likninger

Men hva er egentlig grunnen til at vi kan kombinere sedler på 500 kr og 200 kr til 2500 kr, men ikke sedler på 1000 kr og 200 kr? Med andre ord, hva er den prinsipielle forskjellen på de diofantiske likningene 500x + 200y = 2500 og 1000x + 200y = 2500?

Intuitivt kan vi si at det med sedler på 500 kr og 200 kr er mulig «å treffe på» 2500 kr, mens vi med sedler på 1000 kr og 200 kr «hopper forbi» 2500 kr. Vi kan få 2400 og 2600, men ikke 2500. Den matematiske årsaken har med største felles faktor, SFF, å gjøre:

Vi har SFF(500, 200) = 100, og SFF(1000, 200) = 200. Og forskjellen er at 100 går opp i totalbeløpet på 2500, mens 200 ikke gjør det. Generelt har vi:

$\fbox{$ \text{En diofantisk likning } ax + by = c \text{ har løsning hvis og bare hvis } SFF(a, b) \, | \, c$}$

Med andre ord må alle tall som går opp i a og b også gå opp i c. Største felles faktor lærte vi om i artikkelen om faktorisering.

Det kan imidlertid være at x og/eller y er negative tall, slik at løsningene ikke kan representere fysiske enheter. Spør vi for eksempel hvordan vi kan kombinere vekter på 4 og 5 kg til totalt 11 kg, skjønner vi at det ikke går. Men det betyr ikke at likningen 4x + 5y = 11 ikke har løsning, for SFF(4, 5) = 1 | 11. Men løsningene involverer negative tall, for eksempel y = −1 hvis x = 4. Og siden vi ikke kan ha et negativt antall vekter, finnes ingen fysisk løsning.

En diofantisk likning som er løsbar, vil alltid ha et uendelig antall løsninger hvis vi aksepterer negative tall.

Oppgave 1:

Avgjør om de diofantiske likningene
4x + 12y = 16
og
3x + 12y = 16
har løsning

​Se løsningsforslag

For å løse en diofantisk likning kan vi i enkle tilfeller prøve oss fram, for eksempel ser vi lett at x = 0, y = 3, er en løsning til 5x + 4y = 12. I andre tilfeller kan dette imidlertid være vanskelig fordi tallene er for store, som for eksempel i 1257x + 389y = 47893. Det kan også være vanskelig å avgjøre om vi har funnet alle relevante løsninger.

Vi skal derfor systematisk se på metoder for å løse lineære, diofantiske likninger.

Løse ved omforming til kongruenslikninger

Hvis vi har en likning på formen ax + by = c, kan vi flytte leddet by over på høyre side, og få ax = c + b(−y). Kaller vi −y for k, og b for n, blir det ax = c + kn.

I artikkelen om kongruens lærte vi at ab (mod n) betyr at det finnes et heltall, k, slik at a = b + kn.

Siden vi i en diofantisk likning bare opererer med heltall, betyr det at ax = c + kn er det samme som axc (mod b).

En lineær, diofantisk likning, ax + by = c, kan altså skrives om til en kongruenslikning, axc (mod b) eller by ≡ c (mod a), og så løses ved hjelp av de verktøyene vi har til rådighet for å løse slike likninger, slik vi lærte i artikkelen om kongruenslikninger.

Eksempel 2:

Vi kan løse problemet med å kombinere sedler på 500 kr og 200 kr til 2500 kr på følgende måte:

Vi starter med likningen 500x + 200y = 2500

Vi flytter y-leddet over på høyre side: 500x = 2500 − 200y

Vi skriver som kongruenslikning: 500x ≡ 2500 (mod 200).

Skulle vi fulgt standardoppskriften, skulle vi nå erstattet 500 og 2500 med mindre tall som er kongruente modulo 200. Men i dette tilfellet er det så lett å finne SFF at vi gjør det først, og forenkler likningen ved å dividere.

Vi har SFF(a, n) = SFF(500, 200) = 100. Vi dividerer alle ledd med 100 og får:

5x ≡ 25 (mod 2).

Vi kan her forenkle videre ved å dividere på begge sider av kongruenstegnet med 5. Modulus forblir uendret fordi SFF(5, 2) = 1. Og vi får:

x ≡ 5 (mod 2).

Siden 5 > 2, erstatter vi 5 med $5 − \lfloor \frac{\displaystyle 5}{\displaystyle 2} \rfloor \cdot 2 = 5 − 2 \cdot 2 = 1$.

Det endelige resultatet blir x ≡ 1 (mod 2).

(Denne erstatningen kunne vi gjort uten den omstendelige utregningen, for alle oddetall er kongruente med 5 modulo 2, så vi kunne puttet inn 1 uten mer dikkedarer.)

x = 1 er altså en løsning til kongruenslikningen, og derved også til den diofantiske likningen vi startet med.

Setter vi x = 1 inn i den diofantiske likningen, altså 500x + 200y = 2500, får vi 500 · 1 + 200y = 2500, som løst mhp. y gir y = 10.

Vi kan altså få 2500 kr ved å kombinere én seddel på 500 kr og ti på 200 kr.

Vi vet at hvis en kongruenslikning modulo n har løsning, har den uendelig mange, som kan være fordelt på alt fra 1 til n restklasser. Det betyr at en løsbar diofantisk likning også har uendelig mange løsninger. Dette kommer vi tilbake til i et senere avsnitt.

I eksempel 2 var det b, ikke a, vi brukte som modulus da vi omformet den diofantiske likningen til en kongruenslikning. Men vi kan like gjerne bruke a, slik det er vist i eksempel 3.

Eksempel 3:

Vi starter med samme likning som i eksempel 2: 500x + 200y = 2500

Så flytter vi x-leddet over på høyre side: 200y = 2500 − 500x

Vi skriver som kongruenslikning:

200y ≡ 2500 (mod 500).

Vi har SFF(a, n) = SFF(200, 500) = 100. Vi dividerer alle ledd med 100 og får:

2y ≡ 25 (mod 5).

Siden 25 > 2, erstatter vi 25 med $25 − \lfloor \frac{\displaystyle 25}{\displaystyle 5} \rfloor \cdot 5 = 25 − 5 \cdot 5 = 0$.

Og vi får: 2y ≡ 0 (mod 5).

(Denne erstatningen kunne vi også gjort uten den omstendelige utregningen, for siden 5 går opp i 25, skjønner vi at 25 er kongruent med 0 modulo 5, og kunne puttet inn 0 uten mer dikkedarer.)

Nå kunne vi gått veien om en multiplikativ invers for å finne den endelige løsningen, men vi ser direkte at y = 0 er en løsning.

y = 0 er altså en løsning til kongruenslikningen, og derved også til den diofantiske likningen vi startet med.

Setter vi y = 0 inn i den diofantiske likningen, altså 500x + 200y = 2500, får vi 500x + 200 · 0 = 2500, som løst mhp. x gir x = 5.

Vi kan altså få 2500 kr med fem sedler på 500 kr ingen på 200 kr.

Vi fikk ikke samme svar i eksempel 3 som i eksempel 2, men den diofantiske likningen har altså uendelig mange løsninger, og nå har vi funnet to av dem.

Når vi skal velge om vi skal flytte x-leddet eller y-leddet over på høyre side, gjør det ofte utregningene enklere å velge slik at vi får lavest modulus. I eksempel 2 fikk vi 200 når vi flyttet y-leddet, og i eksempel 3 fikk vi 500 når vi flyttet x-leddet.

Oppgave 2:

Avgjør om den lineære, diofantiske likningen 21x + 14y = 147 er løsbar, og finn i så fall en løsning.

​Se løsningsforslag

Finne alle løsninger

I eksemplet med sedlene fikk vi 1 seddel på 500 kr og 10 sedler på 200 kr da vi regnet modulo 200, og fem sedler på 500 kr og ingen sedler på 200 kr da vi regnet modulo 500. Det er to forskjellige svar, men begge svarene er riktige. Og en løsbar diofantisk likning har altså uendelig mange løsninger.

Generelt er det slik at vi løser diofantiske likninger ved først å finne én spesiell løsning, og så generalisere ut fra den.

I artikkelen om kongruensregning så vi at det fantes uendelig mange løsninger til en løsbar kongruenslikning, og lærte hvordan vi ut fra én løsning kunne beregne hvilke restklasser løsningene lå i. Metoden kan også brukes på diofantiske likninger, men i en diofantisk likning er vi bare interessert i selve løsningene, ikke hvilke restklasser de tilhører, og hvis vi har løst den diofantiske likningen ved hjelp av Euklids algoritme baklengs, har vi heller ikke noen kongruenslikning å arbeide ut fra.

Vi angir derfor en metode til å finne alle løsninger til en lineær, diofantisk likning basert på den opprinnelige likningen. La oss si at vi har funnet et løsningspar, to heltall x = x0 og y = y0, som tilfredsstiller den diofantiske likningen ax + by = c. Da vil alle løsninger av likningen være på formen

$x_k = x_0 + \frac{\displaystyle b}{\displaystyle d}k$

og

$y_k = y_0 − \frac{\displaystyle a}{\displaystyle d}k$

der k er et vilkårlig helt tall, og d = SFF(a, b).

Forklart med ord betyr dette at når vi har funnet et tallpar, x0 og y0, som er en løsning, kan vi finne nye løsningspar, xk og yk, ved å addere heltallige multipler av $\frac{\displaystyle b}{\displaystyle d}$ til x0, og å subtrahere heltallige multipler av $\frac{\displaystyle a}{\displaystyle d}$ fra y0, der vi henter a og b fra den opprinnelige likningen og beregner d som SFF(a, b). For eksempel

$x_1 = x_0 + \frac{\displaystyle b}{\displaystyle d} \cdot 1$ og $y_1= y_0 − \frac{\displaystyle a}{\displaystyle d} \cdot 1$

$x_2 = x_0 + \frac{\displaystyle b}{\displaystyle d} \cdot 2$ og $y_2 = y_0 − \frac{\displaystyle a}{\displaystyle d} \cdot 2$

$x_{−1} = x_0 + \frac{\displaystyle b}{\displaystyle d}(−1)$ og $y_{−1} = y_0 − \frac{\displaystyle a}{\displaystyle d}(−1)$

$x_{−2} = x_0 + \frac{\displaystyle b}{\displaystyle d}(−2)$ og $y_{−2} = y_0 − \frac{\displaystyle a}{\displaystyle d}(−2)$

og så videre. Det finnes i utgangspunktet uendelig mange muligheter, og vi finner dem ved å sette inn forskjellige verdier av k. For eksempel 1, 2, −1, −2, slik vi har vist over.

Eksempel 4:

I eksempel 2 fant vi at en løsning av den diofantiske likningen 500x + 200y = 2500.

Vi har da at a = 500, b = 200 og d = SFF(200, 500) = 100.

Og vi har sett at x0 = 1 og y0 = 10 er en løsning til denne likningen. Så, som et generelt uttrykk for xk og yk, får vi:

$x_k = x_0 + \frac{\displaystyle b}{\displaystyle d}k = 1 + {\large \frac{200}{100}}k = 1 + 2k$

$y_k = y_0 − \frac{\displaystyle a}{\displaystyle d}k = 10 − {\large \frac{500}{100}}k = 10 − 5k$

Tabellen under viser løsningene for verdier av k mellom −5 og 5. Alle parene av x og y gir riktig løsning av likningen, men hvis x og y skal representere antall pengesedler, kan tallene ikke være negative. Løsningene der både x og y er større eller lik null er derfor markert med gult.

k −5 −4 −3 −2 −1 0 1 2 3 4 5
x −9 −7 −5 −3 −1 1 3 5 7 9 11
y 35 30 25 20 15 10 5 0 −5 −10 −15

Eksempel 5:

Tar vi utgangspunkt i løsningen i eksempel 3, får vi følgende utregning når vi vil finne alle løsninger:

x0 = 5 og y0 = 0. Vi har som før at a = 500, b = 200 og d = SFF(200, 500) = 100. Så da får vi som et generelt uttrykk for xk og yk:

$x_k = x_0 + \frac{\displaystyle b}{\displaystyle d}k = 5 + {\large \frac{200}{100}}k = 5 + 2k$

$y_k = y_0 − \frac{\displaystyle a}{\displaystyle d}k = 0 − {\large \frac{500}{100}}k = − 5k$

Tabellen under viser løsningene for verdier av k mellom −5 og 5. Kombinasjoner der både x og y er større eller lik null er markert med gult.

k −5 −4 −3 −2 −1 0 1 2 3 4 5
x −5 −3 −1 1 3 5 7 9 11 13 15
y 25 20 15 10 5 0 −5 −10 −15 −20 −25

Vi ser at tallene markert med gult er de samme i tabellene i eksempel 4 og 5. k er forskjellig, men det har ingen betydning for løsningene.

Vi kan altså få 2500 kroner ved å kombinere

1 seddel på 500 kr og 10 sedler på 200 kr.

3 sedler på 500 kr og 5 sedler på 200 kr.

5 sedler på 500 kr og ingen sedler på 200 kr.

Oppgave 3:

Finn et uttrykk for alle løsninger til den lineære, diofantiske likningen fra oppgave 2, 21x + 14y = 147.

​Se løsningsforslag

Finne ikke-negative løsninger

Som vi så et eksempel på da vi regnet med sedler, er vi av og til ikke interessert i negative løsninger av en diofantisk likning. Slik er det ofte når vi opererer med ting fra den virkelige verden. Skruer og muttere, voksne og barn, gule og røde lodd, etc. Vi må alltid ha 0 eller flere enheter.

Skal vi holde oss til ikke-negative løsninger, betyr det at vi i den generelle løsningen må begrense k slik at vi bare får løsninger der xk ≥ 0 og yk ≥ 0. Det vil si at vi i det generelle uttrykket vi fant for x og y må ha

$x_0 + \frac{\displaystyle b}{\displaystyle d}k \geq 0$

og

$y_0 − \frac{\displaystyle a}{\displaystyle d}k \geq 0$

Her må vi altså sette inn verdiene vi finner for x0, y0, a, b og d, og løse ulikhetene med hensyn på k.

Eksempel 6:

I eksempel 4, da vi regnet modulo 200, fant vi at et generelt uttrykk for løsningen til likningen 500x + 200y = 2500 var:

xk = 1 + 2k

yk = 10 − 5k

Her må vi ha at xk = 1 + 2k ≥ 0.

Vi løser ulikheten ved å flytte 1 over til høyre side med fortegnsskifte og dividere begge sider med 2, noe som gir k ≥ −0,5.

Vi må også ha at yk = 10 − 5k ≥ 0.

Vi løser ulikheten ved å flytte 10 over til høyre side med fortegnsskifte og dividere begge sider med −5. Vi husker at vi må snu ulikhetstegnet når vi didviderer med et negativt tall, så dette gir k ≤ 2.

Det betyr altså at −0,5 ≤ k ≤ 2. Siden k må være hele tall, tilsvarer dette k = 0, k = 1 og k = 2.

Og vi får

x0 = 1 + 2 · 0 = 1
y0 = 10 − 5 · 0 = 10

x1 = 1 + 2 · 1 = 3
y1 = 10 − 5 · 1 = 5

x2 = 1 + 2 · 2 = 5
y2 = 10 − 5 · 2 = 0

Altså (1, 10), (3, 5) og (5, 0).

Som er det samme som vi fant i tabellen i eksempel 4.

Eksempel 7:

I eksempel 5, da vi regnet modulo 500, fant vi et annet generelt uttrykk for løsningen til likningen 500x + 200y = 2500 som var:

xk = 5 + 2k

yk = − 5k

Her må vi altså ha at

xk = 5 + 2k ≥ 0, noe som gir k ≥ −2,5.

og

yk = −5k ≥ 0, noe som gir k ≤ 0.

Det betyr altså at −2,5 ≤ k ≤ 0. Siden k må være hele tall, tilsvarer dette k = −2, k = −1 og k = 0.

Og vi får
x−2 = 5 + 2(−2) = 1
y−2 = −5(−2) = 10

x−1 = 5 + 2(−1) = 3
y−1 = −5(−1) = 5

x0 = 5 + 2 · 0 = 5
y0 = −5 · 0 = 0

Altså (1, 10), (3, 5) og (5, 0).

Som er det samme som vi fant i tabellen i eksempel 5.

​Oppgave 4:

Finn alle ikke-negative løsninger til den lineære, diofantiske likningen fra oppgave 2 og 3, 21x + 14y = 147.

Se løsningsforslag

Grafisk framstilling av løsninger

En lineær likning på formen ax + by = c kan ved hjelp av enkel algebra omformes til $y = −\frac{\displaystyle a}{\displaystyle b}x + \frac{\displaystyle c}{\displaystyle b}$. Dette kjenner vi igjen som likningen for ei rett linje med stigningstall $−\frac{\displaystyle a}{\displaystyle b}$ som skjærer y-aksen i $\frac{\displaystyle b}{\displaystyle c}$.

I introduksjonen skrev vi likningen x + 2y = 2 på denne måten som $y = −{\large \frac{1}{2}}x + 1$, en funksjon som har grafen under.

Heltallsløsninger av likningen x + 2y = 2

I grafen er punkter som er heltallige løsninger av likningen, markert. Vi ser at hvis vi fra ett av disse punktene går to skritt til høyre og ett ned, kommer vi til neste punkt. Mer formelt sagt adderer vi 2 til x-verdien, og adderer −1 til y-verdien

Tallene 2 og −1 kommer fra stigningstallet. Generelt vil vi i grafen til ax + by = c , med stigningstall $−\frac{\displaystyle a}{\displaystyle b}$, komme fra én heltallsløsning, (x, y), til neste ved å addere b til x og −a til y: (x + b, ya).

Vi kan selvsagt også gå fra høyre mot venstre ved å subtrahere b fra x og −a fra y: (xb, y +a).

I eksemplet der vi studerte hvordan sedler på 500 kr og 200 kr kunne kombineres til 2500 kr, hadde vi likningen 500x + 200y = 2500, som omformet og forkortet blir $y = −{\large \frac{5}{2}}x + {\large \frac{25}{2}}$. Grafen til denne funksjonen er vist under, med de heltallige løsningene (1, 10), (3, 5) og (5, 0) markert.

Heltallsløsninger til likningen 500x + 200y = 2500

Grafen til 500x + 200y = 2500 med heltallsløsninger markert

Her er stigningstallet $−{\large \frac{5}{2}}$, så a = 5, b = 2. Starter vi i (1, 10) og bruker formelen (x+b, ya), får vi (1+2, 10−5) = (3, 5). Gjør vi det samme en gang til, får vi (3+2, 5−5) =(5, 0). Som er de to andre løsningene til den diofantiske likningen.

Oppgave 5:

Løs likningen fra oppgave 2, 3 og 4, 21x + 14y = 147, som en vanlig likning med hensyn på y og tegn grafen i GeoGebra. Plott inn løsningene fra oppgave 4.

Se løsningsforslag

Oppgave 6:

En snekker lager krakker med 3 bein og bord med 4 bein. En dag har han brukt opp 33 bein, hvor mange krakker og bord han kan ha laget?

Se løsningsforslag

Vi skal avslutte med å se på et alternativ til å løse diofantiske likninger ved å skrive dem om til kongruenslikninger, Euklids algoritme baklengs.

Løse ved Euklids algoritme baklengs

I artikkelen om faktorisering lærte vi å bruke Euklids algoritme til å finne to talls største felles faktor. Brukt baklengs kan algoritmen benyttes til å løse lineære, diofantiske likninger.

Metoden virker i utgangspunktet bare på spesialtilfeller av den diofantiske likningen ax + by = c, der SFF(a, b) = 1 og c = 1, men utvides lett til å fungere også når SFF(a, b) > 1 eller c ≠ 1.

Prinsippet er at vi tar utgangspunkt i likningen ax + by = 1 og bruker Euklids algoritme til å finne SFF(a, b). Så nøster vi oss tilbake gjennom utregningen for å finne en lineær kombinasjon av a og b som er en løsning til likningen.

Vi illustrerer med et par eksempler.

Eksempel 8:

Vi skal løse likningen 43x + 5y = 1.

Her er SFF(a, b) = 1 og c = 1.

Vi starter med å bruke Euklids algoritme til å finne SFF(43, 5).

$\begin{align}43 &= 8 \cdot 5 + 3\\
5 &= 1 \cdot 3 + 2\\
3 &= 1 \cdot 2 + 1\\
2 &= 2 \cdot 1 + 0 \end{align}$

Konklusjonen er at SFF(43, 5) = 1, men det visste vi jo allerede. Det vi egentlig er ute etter, er å uttrykke resten, r, som en lineær kombinasjon av de to andre tallene, a og b. I siste linje er resten 0, så den er ikke så interessant. Men de andre linjene skriver vi om som vist under, a og b er markert med brunt:

$\begin{align}43 &= 8 \cdot 5 + 3 \, \Rightarrow \, 3 = {\color{brown}{43}} − 8 \cdot {\color{brown}{5}}\\
\\
5 &= 1 \cdot 3 + 2 \, \Rightarrow \, 2 = {\color{brown}{5}} − 1 \cdot {\color{brown}{3}}\\
\\
3 &= 1 \cdot 2 + 1 \, \Rightarrow \, 1 = {\color{brown}{3}} − 1 \cdot {\color{brown}{2}}\end{align}$

I siste linje erstatter vi så 2-tallet med uttrykket i linja over:

Estatning av tall i Euklids algoritme baklengs

Altså

$1 = {\color{brown}{3}} − 1 \cdot {\color{brown}{2}}$
$\Downarrow$
$1 = {\color{brown}{3}} − 1 \cdot ({\color{brown}{5}} − 1 \cdot {\color{brown}{3}})$
$\Downarrow$
$1 = 2 \cdot {\color{brown}{3}} − 1 \cdot {\color{brown}{5}}$

Vi passer på å ikke gjøre utregningene fullt ut, i stedet holder vi rede på hvor mange av de brune tallene vi har.

Vi har nå

$\begin{align}3 &= {\color{brown}{43}} − 8 \cdot {\color{brown}{5}}\\
1 &= 2 \cdot {\color{brown}{3}} − 1 \cdot {\color{brown}{5}} \\
\end{align}$

I siste linje erstatter vi 3-tallet med uttrykket i linja over

Estatning av tall i Euklids algoritme baklengs

Altså

$1 = 2 \cdot {\color{brown}{3}} − 1 \cdot {\color{brown}{5}}$
$\Downarrow$
$1 = 2 \cdot ({\color{brown}{43}} − 8 \cdot {\color{brown}{5}}) − 1 \cdot {\color{brown}{5}}$
$\Downarrow$
$1 = 2 \cdot {\color{brown}{43}} − 17 \cdot {\color{brown}{5}}$

Det betyr at x = 2, y = 17 er en løsning til den diofantiske likningen 43x + 5y = 1, som vi startet med.

Eksempel 9:

Vi skal løse likningen 25x + 7y = 1.

Her er SFF(a, b) = 1 og c = 1.

Vi starter med å bruke Euklids algoritme til å finne SFF(25, 7):

$\begin{align}25 &= 3 \cdot 7 + 4\\
7 &= 1 \cdot 4 + 3\\
4 &= 1 \cdot 3 + 1\\
3 &= 3 \cdot 1 + 0 \end{align}$

Vi dropper den siste linja, i de andre uttrykker vi resten, r, som en lineær kombinasjon av a og b, markert med brunt:

$\begin{align}4 &= {\color{brown}{25}} − 3 \cdot {\color{brown}{7}} \\
3 &= {\color{brown}{7}} − 1 \cdot {\color{brown}{4}} \\
1 &= {\color{brown}{4}} − 1 \cdot {\color{brown}{3}} \\
\end{align}$

I siste linje erstatter vi så 3-tallet med uttrykket i linja over

$1 = {\color{brown}{4}} − 1 \cdot {\color{brown}{3}}$
$\Downarrow$
$1 = {\color{brown}{4}} − 1 \cdot ({\color{brown}{7}} − 1 \cdot {\color{brown}{4}})$
$\Downarrow$
$1 = 2 \cdot {\color{brown}{4}} − 1 \cdot {\color{brown}{7}}$

Vi har nå

$\begin{align}4 &= {\color{brown}{25}} − 3 \cdot {\color{brown}{7}}\\
1 &= 2 \cdot {\color{brown}{4}} − 1 \cdot {\color{brown}{7}} \\
\end{align}$

I siste linje erstatter vi 4-tallet med uttrykket i linja over

$1 = 2 \cdot {\color{brown}{4}} − 1 \cdot {\color{brown}{7}}$
$\Downarrow$
$1 = 2 \cdot ({\color{brown}{25}} − 3 \cdot {\color{brown}{7}}) − 1 \cdot {\color{brown}{7}}$
$\Downarrow$
$1 = 2 \cdot {\color{brown}{25}} − 7 \cdot {\color{brown}{7}}$

Det betyr at x = 2, y = −7 er en løsning til den diofantiske likningen 25x + 7y = 1, som vi startet med.

Oppgave 7:

Finn en løsning til den diofantiske likningen 11x + 3y = 1, ved hjelp av Euklids algoritme baklengs.

​Se løsningsforslag

Så langt har vi altså sett på spesialtilfeller av den diofantiske likningen ax + by = c, der SFF(a, b) = 1 og c = 1. Nå skal vi generalisere metoden ved hjelp av to enkle triks.

Siden vi må ha SFF(a, b) | c for at likningen skal ha løsning, vil vi alltid kunne forkorte likningen med SFF(a, b), slik at vi får SFF(a, b) = 1.

Eksempel 10:

Vi skal løse den diofantiske likningen 50x + 14y = 10. Her har vi SFF(50, 14) = 2. Siden 2 | 10, har likningen løsning. Vi forkorter med 2 og får

25x + 7y = 5, som vi arbeider videre med i eksempel 11.

Siden vi kan multiplisere med samme tall på begge sider i en likning, vil vi, hvis a og b er løsninger til ax + by = 1, ha at ca og cb er løsninger til ax + by = c. Vi kan altså løse likningen ax + by = c ved først å løse ax + by = 1, og så multiplisere svarene med c.

Eksempel 11:

Vi skal løse den diofantiske likningen 25x + 7y = 5. Vi ser da først på likningen 25x + 7y = 1. Denne likningen løste vi i eksempel 9, og fikk

x = 2, y = −7.

Derfor er x = 5 · 2 = 10, y = 5 · (−7) = −35 løsninger til likningen 25x + 7y = 5.

Oppgave 8:

Finn en løsning til likningen fra oppgave 2, 21x + 14y = 147, ved hjelp av Euklids algoritme baklengs. 

​Se løsningsforslag

Vi så tidligere at en lineær, diofantisk likning kan gjøres om til en kongruenslikning, og selvsagt kan vi også gå andre veien, gjøre en kongruenslikning om til en diofantisk likning. Det betyr at Euklids algoritme baklengs også kan brukes til å løse kongruenslikninger ved at vi først gjør dem om til diofantiske likninger.

Kilder

    • Rosen, Kenneth H. (1984). Elementary Number Theory and Its Applications. Addison-Wesley.
    • Rinvold, A. R. (2009). Visuelle perspektivTallteori. Caspar Forlag.
    • Petersen, V. B., Tvete, K. S. (2013). I tallkongruensenes verden. Caspar Forlag.
    • Gustavsen, T.S., Hinna, T.R.C., Borge, I.C., Andersen, P.S. (2014). QED 5-10, bind 2. Cappelen Damm A/S.

Kongruenslikninger

Modellere med kongruenslikninger

Eksempel 1:

En jogger løper intervaller på 2 km i ei rundløype som er 5 km lang. Etter hvert intervall tar han en pause. Når han ved en pause er 4 km inn i løypa, hvor mange intervaller på 2 km kan han da ha løpt?

Dette er et eksempel på et problem som kan løses ved hjelp av en kongruenslikning. Likningen blir

2x ≡ 4 (mod 5), der x er antall intervaller.

Likningen sier at x antall intervaller på 2 km må rekke 4 km forbi et antall hele runder på 5 km.

I artikkelen om regneregler for kongruens lærte vi divisjonsregelen, som sier at vi kan dividere med samme tall, c, på begge sider av kongruenstegnet, hvis vi samtidig dividerer modulus, n, med SFF(c, n).

Siden SFF(2, 5) = 1, kan vi dividere med 2 på begge sider av kongruenstegnet uten å endre modulus, og vi får

x ≡ 2 (mod 5).

Antall intervaller må altså være kongruente med 2 modulo 5, med andre ord på formen 2 + k · 5, der k er et helt tall. Joggeren kan ha løpt 2 + 0 · 5 = 2 intervaller, 2 + 1 · 5 = 7 intervaller, og så videre. Dette er illustrert i figurene under.

Illustrasjon av 2 intervaller på 2 km i 5 km løype

Illustrasjon av 7 intervaller på 2 km i 5 km løype

Her kan ikke k være negativ, siden joggeren ikke kan ha løpt et negativt antall runder. Men matematisk sett er også 2 + (−1) · 5 = −3 og 2 + (−2) · 5 = −8 løsninger til kongruenslikningen. Tolker vi disse i forhold til det opprinnelige problemet, representerer løsningene at joggeren har løpt motsatt vei. Dette er illustrert i figurene under.

Illustrasjon av -3 intervaller på 2 km i 5 km løype

Illustrasjon av -8 intervaller på 2 km i 5 km løype

Vi er vant med å modellere med vanlige likninger, for eksempel setter vi uten videre opp likningen 8x = 40, hvis vi skal representere problemet «Hvor mange kg appelsiner til 8 kroner per kg kan vi ha kjøpt når vi betalte 40 kroner?»

Men kongruenslikninger er uvante for de fleste av oss, derfor vil vi slite mer med å formulere problemer i form av kongruenslikninger.

Kongruenslikningen i eksempel 1 hadde uendelig mange løsninger, på formen 2 + k · 5, mens den vanlige likningen med appelsinene bare hadde én løsning. Videre ser vi at vi at, uansett hva vi hadde betalt for appelsinene, ville kunnet finne en løsning på likningen. Hadde vi betalt 44 kroner, ville det betydd at vi hadde kjøpt 5,5 kg. Det er ikke noe krav at løsningen skal være et helt tall. I en kongruenslikning derimot, må løsningene være hele tall. Det betyr at ikke alle kongruenslikninger har løsning.

Eksempel 2:

Hvis løypa i eksempel 1 hadde vært 6 km og joggeren tok pause 3 km inn i løypa, skjønner vi at han ikke kunne løpt et helt antall intervaller på 2 km. For intervallene ville alltid slutte 2 km inn, 4 km inn, og tilbake ved start. Så kongruenslikningen

2x ≡ 3 (mod 6)

har ingen løsning.

En kongruenslikning vil enten ikke ha løsning eller ha uendelig mange løsninger.

I denne artikkelen skal vi se nærmere på hvordan vi avgjør om en kongruenslikning har løsning eller ikke, og lære metoder for å systematisk løse kongruenslikninger. Mer presist snakker vi i denne artikkelen om lineære kongruenslikninger, eller første grads kongruenslikninger, fordi den ukjente, x, er av første grad. Men for enkelhets skyld sier vi her bare kongruenslikninger. En lineær kongruenslikning er på formen axb (mod n), der a, b og n er hele tall, a ≠ 0, n > 0.

Men vi skal først øve litt på å modellere med kongruenslikninger.

Oppgave 1:

Modeller problemene under med kongruenslikninger. NB! Du blir ikke bedt om å løse likningene.

      1. En friidrettsutøver løper 300-meters intervaller på en 400-meters bane, og står stille og hviler mellom hvert intervall. Når hun gir seg, har hun passert målstreken med 100 meter. Hvor mange intervaller kan hun ha løpt?
         
      2. En forstadsbane passerer et stoppested første gang klokka 05:00, deretter hvert 12. minutt. Hvor hyppig passerer banen deretter på hele klokkeslett?

Se løsningsforslag

Oppgave 2:

Foreslå en situasjon som kan modelleres med kongruenslikningen 4x ≡ 0 (mod 10).

Se løsningsforslag

Kongruenslikner og restklasser

I eksempel 1 hadde vi kongruenslikningen 2x ≡ 4 (mod 5), og fant ut at løsningene var på formen 2 + k · 5, der 5 var modulus. Markerer vi løsningene i en tabell med antall kolonner lik modulus, altså 5, blir det slik:

1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 29
21 22 23 24 25

Vi ser at løsningene havner i samme kolonne, de er i samme restklasse, slik vi lærte om i artikkelen om kongruens

I eksempel 2 så vi at likningen 2x ≡ 3 (mod 6) ikke hadde løsning. Vi ser nå på et tredje eksempel:

Eksempel 3:

Vi har kongruenslikningen 9x ≡ 12 (mod 15).

Ved prøving og feiling i et regneark finner vi følgende løsninger: 3, 8, 13, 18, 23, 28, 33, 38, 43, 48, 53, 58.

Markerer vi løsningene i eksempel 3 i en tabell med antall kolonner lik modulus, altså 15, blir det slik:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

Her ser vi at løsningene havner i tre forskjellige restklasser. Så hva er forskjellen på kongruenslikningene i eksempel 1, 2 og 3?

En lineær kongruenslikning er, som nevnt, på formen axb (mod n). I eksempel 1 hadde vi SFF(a, n) = SFF(2, 5) = 1 og i eksempel 3 SFF(a, n) = SFF(9, 15) = 3. Så det kan se ut til at SFF(a, n) har noe med antall restklasser å gjøre. Og det er riktig, løsningene til en kongruenslikning havner i SFF(a, n) restklasser.

Men i eksempel 2 hadde vi SFF(a, n) = SFF(2, 6) = 2, og den likningen hadde allikevel ingen løsning. Det er fordi en kongruenslikning har løsning hvis og bare hvis SFF(a, n) | b. I eksempel 1 hadde vi SFF(2, 5) = 1 | 4 og i eksempel 3 SFF(9, 15) = 3 | 12. Men i eksempel 2 hadde vi SFF(2, 6) = 2 ∤ 3.

Siden 1 går opp i alle tall, har alle kongruenslikninger der SFF(a, n) = 1 løsning.

Vi har altså

$\fbox{$\begin{align} &ax \equiv b \, (mod \; n) \text{ har ingen løsning hvis } SFF(a,n) \nmid b \\
&ax \equiv b \, (mod \; n) \text{ har løsning i } SFF(a,n) \text{ restklasser hvis } SFF(a,n) \mid b \end{align}$}$

SFF er en kombinasjon av alle felles faktorer, så, sagt på en annen måte, må alle faktorer som er felles for a og n også være faktorer i b for at likningen skal ha løsning. Hvis a og n er innbyrdes primiske, slik at SFF(a, n) = 1, vil alle løsningene havne i samme restklasse.

Når vi snakker om å løse en kongruenslikning, mener vi egentlig å finne hvilke restklasser likningen har løsning i. Som representant for klassen velger vi det minste ikke-negative tallet i klassen. I eksempel 1 blir det 2, og i eksempel 3 blir det 3, 8 og 13.

Innen hver restklasse finnes det uendelig mange kongruente løsninger, men løsningene fra forskjellige restklasser er ikke kongruente med hverandre. Løsninger fra forskjellige restklasser kaller vi derfor også gjerne innbyrdes inkongruente løsninger.

Oppgave 3:

Avgjør om følgende kongruenslikninger har løsning, og i så fall hvor mange restklasser de har løsninger i:

      1. 4x ≡ 8 (mod 10)
         
      2. 3x ≡ 8 (mod 10)
         
      3. 4x ≡ 9 (mod 10)
         
      4. 84x ≡ 108 (mod 12)

Se løsningsforslag

Metoder for å løse lineære kongruenslikninger

Vi skal nå se hvordan vi kan bruke regneregler for kongruenser til å løse lineære kongruenslikninger. Noen av disse er felles med reglene for å løse vanlige likninger, slik det er beskrevet i algebra-artikkelen om likninger og ulikheter, men ikke alle. Det finnes regler vi bare kan bruke på kongruenslikninger, og regler vi bare kan bruke på vanlige likninger.

De første tre reglene går ut på å rydde i leddene, og å erstatte store/negative tall med mindre/positive tall.

Flytte over ledd og skifte fortegn

I artikkelen om regneregler for kongruens presenterte vi en regel som sier at vi kan addere samme heltall på begge sider av kongruenstegnet. Det betyr at

$\fbox{$ax + c \equiv b + c\, (mod \; n) \text{ har samme løsninger som } ax \equiv b \, (mod \; n)$}$

Dette er helt tilsvarende regelen vi har for vanlige likninger, og vil i praksis si at vi kan flytte et tall over til andre siden av kongruenstegnet hvis vi samtidig skifter fortegn. x representerer et tall, derfor kan vi også flytte ledd med x på samme måte.

Eksempel 4:

Vi skal løse kongruenslikningen 3x + 4 ≡ 7 + 2x (mod 5).

Vi flytter 4 over til høyre side og 2x over til venstre side med fortegnsskifte:

$\begin{align} 3x − 2x &\equiv 7 − 4 \, (mod \; 5) \\
x & \equiv 3 \;\;\;\;\, (mod \; 5) \end{align}$

Erstatte store / negative tall med kongruente tall

I artikkelen om regneregler for kongruens så vi at vi i en kongruens kan erstatte tall med kongruente tall. 

Dette betyr at vi kan erstatte tall som er større eller lik n med kongruente, mindre tall, og negative tall med kongruente, positive tall. Siden denne regelen er tett knyttet til kongruensbegrepet, finnes det ingen tilsvarende regel for vanlige likninger.

En praktisk måte å bruke regelen på er, som vi har sett, å erstatte tall, tn eller t < 0 med $ s = t − \lfloor \frac{\displaystyle t}{\displaystyle n} \rfloor \cdot n$, der n er modulus. Vi vil da alltid få 0 ≤ s < n.

Eksempel 5:

Vi skal forenkle kongruenslikningen x ≡ 17 (mod 7). Vi kan da erstatte

17 med $17 − \lfloor \frac{\displaystyle 17}{\displaystyle 7} \rfloor \cdot 7 = 17 −2 \cdot 7 = 3$.

Og vi får x ≡ 3 (mod 7).

 

Vi skal forenkle kongruenslikningen x ≡ −11 (mod 3). Vi kan da erstatte

−11 med $−11 − \lfloor \frac{\displaystyle −11}{\displaystyle 3} \rfloor \cdot 3 = −11 −(−4) \cdot 3 = 1$.

Og vi får x ≡ 1 (mod 3).

 

Vi skal forenkle kongruenslikningen 5x ≡ 3 (mod 4). Vi kan da erstatte

5 med $5 − \lfloor \frac{\displaystyle 5}{\displaystyle 4} \rfloor \cdot 4 = 5 − 1 \cdot 4 = 1$.

Og vi får x ≡ 3 (mod 4).

 

Vi skal forenkle kongruenslikningen −5x ≡ 12 (mod 6). Vi kan da erstatte

−5 med $−5 − \lfloor \frac{\displaystyle −5}{\displaystyle 6} \rfloor \cdot 6 = −5 − (−1) \cdot 6 = 1$.

Og vi kan erstatte 12 med $12 − \lfloor \frac{\displaystyle 12}{\displaystyle 6} \rfloor \cdot 6 = 12 − 2 \cdot 6 = 0$.

Og vi får x ≡ 0 (mod 6).

Oppgave 4:

Forenkle kongruenslikningen x + 4 ≡ 13 − 5x (mod 5).

Se løsningsforslag

Dividere med samme tall på begge sider

I artikkelen om regneregler for kongruens presenterte vi en regel som sier at vi kan dividere med et tall, c, på begge sider av kongruenstegnet hvis vi samtidig dividerer modulus, n, med SFF(c, n). Det vil si at

$\fbox{$cax \equiv cb\, (mod \; n) \text{ har samme løsninger som } ax \equiv b \, (mod \; \frac{\displaystyle n}{\displaystyle d}), \text{ der } d = SFF(c, n)$}$

Denne regelen minner om den vi har i vanlige likninger, men mens vi i vanlige likninger kan dividere med et vilkårlig tall forskjellig fra 0 på begge sider av likhetstegnet, kan vi i en kongruenslikning axb (mod n) bare dividere med tall som går opp i både a og b, ellers ville vi jo sitte igjen med noe som ikke var heltall. Det største tallet vi kan dividere med er c = SFF(a, b). I tillegg må også modulus divideres med SFF(c, n).

Eksempel 6:

Vi skal løse kongruenslikningen 4x ≡ 12 (mod 18). Vi ser at vi kan forenkle likningen ved å dividere med SFF(4, 12) = 4 på begge sider av kongruenstegnet. Det har vi lov til hvis vi samtidig dividerer modulus 18 med SFF(4, 18) = 2. Og vi får x ≡ 3 (mod 9).

Tidligere i artikkelen har vi sagt at, så fremt en kongruenslikning, axb (mod n), har løsning, har den løsning i SFF(a, n) restklasser.

Bruker vi denne regelen på eksempel 6, ser vi at likningen vi starter med har løsning i SFF(4, 18) = 2 restklasser, mens likningen vi ender opp med bare har løsning i SFF(1, 9) = 1 restklasse. Allikevel er det vi har gjort riktig.

Som tidligere nevnt finnes det uendelig mange løsninger til en løsbar kongruenslikning. Ved prøving og feiling i et regneark finner vi at noen av løsningene til den opprinnelige likningen i eksempel 6 er 3, 12, 21, 30, 39, 48. Disse havner i to restklasser modulo 18, nemlig 3, 21, 39 i restklasse 3, og 12, 30, 48 i restklasse 12.

Ved prøving og feiling i likningen vi ender opp med i eksempel 6, finner vi også der de samme løsningene, for eksempel 3, 12, 21, 30, 39, 48. Men alle havner nå i samme restklasse, restklasse 3 modulo 9.

Det vi har gjort er altså riktig, løsningene er beholdt, men restklassene har kollapset inn i én enkelt restklasse. Vi kan imidlertid enkelt rekonstruere de opprinnelige restklassene ved hjelp av følgende regel:

$\fbox{$\begin{align} &\text{Hvis } x = t \text{ er en løsning til kongruenslikningen } ax \equiv b\, (mod \; n), \\
&\text{vil alle restklasser med løsning mod n være gitt ved } x_k = t + k \frac{\displaystyle n}{\displaystyle d} \\
&\text{der } d = SFF(a, n) \text{ og } 0 \le k < d \end{align}$}$

Eksempel 7:

I eksempel 6 har vi kommet fram til at en løsning til kongruenslikningen 4x ≡ 12 (mod 18) er x = 3.
Og vi har d = SFF(4, 18) = 2. Det vil si at de opprinnelige restklassene er $x_0 = 3 + 0 \cdot \frac{\displaystyle 18}{\displaystyle 2} = 3$
og
$x_1 = 3 + 1 \cdot \frac{\displaystyle 18}{\displaystyle 2} = 12$

Oppgave 5:

Finn alle restklasser som inneholder løsninger til likningen 6x ≡ 12 (mod 9).

Se løsningsforslag

Å finne alle restklasser som inneholder løsninger til en kongruenslikning vil vi for enkelhets skyld heretter bare omtale som å løse kongruenslikningen.

Når vi har brukt de tre reglene nevnt over, har vi forenklet kongruenslikningen så langt det går. I eksemplene og oppgavene så langt har vi da stått igjen med et uttrykk på formen xt (mod n), der t er et eller annet tall. Vi har altså endt opp med at den ukjente, x, står igjen alene på venstre side av kongruenstegnet, og en løsning til kongruenslikningen er funnet. Imidlertid er det ikke alltid at dette skjer.

Eksempel 8:

Vi skal forenkle kongruenslikningen 4x ≡ 6 (mod 9). Det største tallet vi kan dividere med er SFF(4, 6) = 2.

Og vi får 2x ≡ 3 (mod 9). (Her er d = SFF(2, 9) = 1, så modulus 9 blir uendret)

Vi ser at vi i eksempel 8 ikke har klart å få x alene på venstre side, men står igjen med uttrykket 2x ≡ 3 (mod 9).

Vi skal imidlertid se at vi ved hjelp av en siste regel alltid vil kunne isolere x på venstre side.

Multiplisere med invers

I artikkelen om regneregler for kongruens presenterte vi en regel som sier at vi i en kongruens kan multiplisere med samme heltall på begge sider av kongruenstegnet. Det betyr at

$\fbox{$ax \cdot c \equiv b \cdot c\, (mod \; n) \text{ har samme løsninger som } ax \equiv b \, (mod \; n)$}$

I den samme artikkelen presenterer vi en multiplikativ invers til et tall, a modulo n som et tall, a, som er slik at a · a ≡ 1 (mod n). Det vil si at hvis vi i en kongruenslikning på formen axb (mod n) multipliserer med a på begge sider, vil vi få (a · a)xb · a (mod n), noe som, siden (a · a) ≡ 1 (mod n), kan forenkles til xb · a (mod n), og vi har isolert x på venstre side.

Den eneste haken er at vi vet at ikke alle tall har en multiplikativ invers modulo n. I artikkelen om regneregler for kongruens anga vi følgende regel:

$\fbox{$\text{Det finnes en } \overline a \text{ slik at } a \cdot \overline a \equiv 1 \, (mod \; n) \text{ hvis og bare hvis } SFF(a, n) = 1$}$

Hvis vi imidlertid har brukt forenklingsreglene vi nevnte tidligere på siden, har vi dividert bort alle felles faktorer i a og n, slik at vi er garantert at SFF(a, n) = 1, og at det derfor vil finnes en multiplikativ invers. Når vi har forenklet en løsbar kongruenslikning så langt det går, vil vi derfor alltid kunne isolere x på venstre side ved bruk av en multiplikativ invers.

I en vanlig likning vil det alltid finnes en multiplikativ invers, å multiplisere med a betyr jo det samme som å dividere med a. Siden vi kan dividere med alle tall unntatt 0, vil vi derfor kunne isolere x i likningen ax = b ved å dividere med a på begge sider. I ett trinn gjør vi derved det vi trenger to trinn for å gjøre i en kongruenslikning.

Hvis et tall har multiplikativ invers modulo n, kan vi finne en invers ved prøving og feiling blant tallene i intervallet [1, n − 1], eller ved å lage multiplikasjonstabeller modulo n. For store n kan dette bli tungvint, vi kan da bruke noe som heter Euklids utvidede algoritme.

Dette nettstedet har en app som finner multiplikative inverser ved hjelp av Euklids utvidede algoritme.

En liste over multiplikative inverser for modulo n for n mellom 2 og 13 finnes nederst i artikkelen om regneregler for kongruens.

Eksempel 9:

Vi skal få x til å stå alene på venstre side i kongruenslikningen 4x ≡ 7 (mod 9).

Siden SFF(4, 9) = 1, vet vi at 4 har en multiplikativ invers modulo 9. Fra lista nederst i artikkelen om regneregler for kongruens finner vi at en invers til a = 4 modulo 9 er a = 7.

Vi multipliserer med 7 på begge sider av kongruenstegnet og får (4 · 7)x ≡ 7 · 7 (mod 9) ⇒ x ≡ 49 (mod 9).

Nå har vi fått et tall som er større enn modulus på 9 på høyre side, så vi bruker regelen om å erstatte med kongruente tall og erstatter 49 med $49 − \lfloor \frac{\displaystyle 49}{\displaystyle 9} \rfloor \cdot 9 = 49 − 5 \cdot 9 = 4$.

Så vi får x ≡ 4 (mod 9).

Oppgave 6:

x til å stå alene på venstre side i kongruenslikningen 4x ≡ 3 (mod 7).

Se løsningsforslag

Løsningsalgoritme

Mange lærebøker har en nokså springende tilnærming til å løse kongruenslikninger. De trekker fram enkelteksempler og spesialtilfeller, men gir ingen systematisk gjennomgang. Men med de metodene vi har sett på, skal vi nå sette opp en algoritme, det vil si en trinnvis framgangsmåte, for å løse kongruenslikninger, som alltid virker.

En kongruenslikning der leddene er ordnet, er på formen axb (mod n). Siden a og b kan endre seg når vi går gjennom de forskjellige trinnene, gir vi dem et subskript avhengig av hvilket trinn vi er i, for eksempel a1, b1 i trinn 1.

Vi illustrerer med et gjennomgående eksempel.

Eksempel 10:

Vi skal løse kongruenslikningen −5x + 6 ≡ 52 − 3x (mod 14).

Trinn 1:

Vi starter med å, med fortegnsskifte, flytte alle ledd med x over på venstre side, alle konstanter over på høyre side, og trekke sammen like ledd. Når dette er gjort, har vi en likning på formen a1xb1 (mod n).

Eksempel 10.1:

Vi flytter −3x til venstre side og 6 til høyre side med fortegnsskifte, trekker sammen og får

−2x ≡ 46 (mod 14).

Trinn 2:

Hvis ikke 0 ≤ a1 < n, erstatter vi a1 med $a_1 − \lfloor \frac{\displaystyle a_1}{\displaystyle n} \rfloor \cdot n$. Tilsvarende for b1.

Vi har nå likningen a2xb2 (mod n).

Eksempel 10.2:

Vi har a1 = −2 < 0, så vi erstatter −2 med $−2 − \lfloor {\large \frac{−2}{14}} \rfloor \cdot 14 = −2 − (−1) \cdot 14 = 12$.

Vi har b1 = 46 > 14, så vi erstatter 46 med $46 − \lfloor {\large \frac{46}{14}}\rfloor \cdot 14 = 46 − 3 \cdot 14 = 4$.

Resultatet blir 12x ≡ 4 (mod 14).

Trinn 3:

Vi avgjør om likningen har løsning. Vi finner da d = SFF(a2, n). Hvis d | b2, har likningen løsninger i d restklasser. I motsatt fall har likningen ikke løsning.

Eksempel 10.3:

Vi får d = SFF(12, 14) = 2.

2 | 4, så likningen har løsninger i 2 restklasser.

Trinn 4:

Hvis likningen er løsbar, dividerer vi alle ledd med d hvis d > 1. For enkelhets skyld kaller vi heretter $\frac{\displaystyle n}{\displaystyle d}$ for m.

Vi har nå likningen a4xb4 (mod m).

Eksempel 10.4:

Vi dividerer alle ledd med d = 2 og får 6x ≡ 2 (mod 7).

Trinn 5:

For å undersøke om likningen kan forenkles mer, finner vi c = SFF(a4, b4). Hvis c > 1, dividerer vi a4 og b4 med c. Det er ikke nødvendig å gjøre noe med modulus, for vi vet at SFF(a4, m) = 1, siden vi i trinn 4 dividerte bort alle felles faktorer.

Vi har nå likningen a5xb5 (mod m).

Eksempel 10.5:

Vi får c = SFF(6, 2) = 2. Så vi dividerer a4 = 6 og b4 = 2 med 2 og får a5 = 3 og b5 = 1, slik at likningen blir 3x ≡ 1 (mod 7).

Trinn 6:

Vi finner en multiplikativ invers til a5 (mod m) og multipliserer med denne på begge sider av kongruenstegnet.

Vi har nå likningen xb6 (mod m).

Eksempel 10.6

I tabellen nederst i artikkelen om regneregler for kongruens finner vi at en multiplikativ invers til a5 = 3 modulo 7 er a5 = 5.

Vi multipliserer med 5 på begge sider av kongruenstegnet og får (3 · 5)x ≡ 1 · 5 (mod 7) ⇒ x ≡ 5 (mod 7).

Trinn 7:

Dersom ikke 0 ≤ b6 < m, erstatter vi b6 med $b_6 − \lfloor \frac{\displaystyle b_6}{\displaystyle m} \rfloor \cdot m$.

Vi har nå likningen xb7 (mod m).

Eksempel 10.7

Vi har 0 < b6 = 5 < 7, så det er ikke nødvendig med noen erstatning.

Trinn 8:

Vi har nå funnet en løsning, t, til likningen xb7 (mod m). Vi finner så de d restklassene med løsninger til den opprinnelige likningen, a1xb1 (mod n), ved å bruke formelen xk = t + k · m, der k er et helt tall slik at 0 ≤ k < d. d fant vi i trinn 3.

Eksempel 10.8:

Vi har funnet at t = 5. Vi har d = 2, så restklassene med løsninger modulo 14 blir x0 = 5 + 0 · 7 = 5 og x1 = 5 + 1 · 7 = 12.

Så løsningene er x ≡ 5, 12 (mod 14).

Dette nettstedet har en app som løser kongruenslikninger ved hjelp av denne algoritmen.

Oppgave 7:

Løs kongruenslikningene under hvis de er løsbare:

      1. 270x − 10 ≡ −130 + 14x (mod 44)
         
      2. −108x − 100 ≡ 229 + 10x (mod 44)

Se løsningsforslag

Vi har nå presentert en algoritme, en kokebokoppskrift, på å løse en kongruenslikning, såfremt den er løsbar. Fordelen med oppskriften er at den alltid virker. En ulempe er imidlertid at den av og til kan være tungvint fordi det finnes enkle grep vi kan gjøre for å løse likningen på en kjapp måte.

Eksempel 11:

Vi skal løse kongruenslikningen 11x ≡ 22 (mod 4).

Her er både a = 11 og b = 22 større enn n = 4, så løsningsalgoritmen sier at vi skal erstatte a og b med mindre, kongruente tall, noe som resulterer i likningen 3x ≡ 2 (mod 4), som vi så må arbeide videre med.

Imidlertid ser vi at vi kan dividere med 11 på begge sider av kongruenstegnet. Siden SFF(a, n) = SFF(11, 4) = 1, trenger vi ikke endre modulus, og vi får løsningen direkte: x ≡ 2 (mod 4).

Eksempel 12:

Vi skal løse kongruenslikningen 7x ≡ −6 (mod 8).

Her er b = −6 negativ, så løsningsalgoritmen sier at vi skal erstatte b med et positivt, kongruent tall, noe som resulterer i likningen 7x ≡ 2 (mod 8), som vi så må arbeide videre med.

Vi ser imidlertid at a = 7 ≡ −1 (mod 8), så vi går mot strømmen og erstatter a = 7 med a = −1 og får −x ≡ −6 (mod 8). Så er det bare å multiplisere med −1 på begge sider, og vi får løsningen direkte: x ≡ 6 (mod 8).

Oppgave 8:

Løs kongruenslikningen 60x ≡ −50 (mod 7) på en enkel måte.

Se løsningsforslag

Vi avslutter med en klassisk nøtt vi gjerne forsøker å løse ved prøving og feiling, men som kan løses ved hjelp av kongruensregning.

Eksempel 13:

Vi skal finne ut hvordan vi ved hjelp av ei bøtte som tar 5 liter og ei bøtte som tar 3 liter kan måle opp akkurat 1 liter, når bøttene ikke har målestreker.

Det vi lurer på er hvordan vi ved å fylle den store bøtta fra den lille kan stå igjen med en rest på akkurat 1 liter i den lille. Det kan uttrykkes som at vi vil finne en heltallig x slik at 3x ≡ 1 (mod 5), der 3 er volumet til den lille bøtta, 5 er volumet til den store bøtta og x er antall ganger vi fyller den lille bøtta.

Vi ser at SFF(a, n) = SFF(3, 5) = 1, så likningen har løsning i 1 restklasse.

Fra tabellen med multiplikative inverser modulo 5 ser vi at 2 er en multiplikativ invers til 3 modulo 5, så vi multipliserer med 2 på begge sider av kongruenstegnet og får x ≡ 2 (mod 5).

I praksis betyr det at vi fyller den lille bøtta, heller over i den store, fyller den lille en gang til og heller over til den store er full. Da har vi fylt opp totalt 5 liter, og det er det en rest på 1 liter i den lille bøtta.

En annen løsning er x = 2 + 1 · 5 = 7. Vi kan altså også få 1 liter vann ved å helle over i den store 7 ganger. Vi må jo da tømme den store bøtta hver gang den er full, det kan vi tenke på som å erstatte 5 med 0, som er kongruent modulo 5. Operasjonen vil forløpe i trinn som forklart under, tallene i parentes forteller hvor mye det er igjen i bøttene.

Vi heller over 3 liter. (0, 3).

Vi heller over 3 liter, med en pause mens vi tømmer den store bøtta. (0, 1).

Vi heller over 3 liter. (0, 4).

Vi heller over 3 liter, med en pause mens vi tømmer den store bøtta. (0, 2).

Vi heller over 3 liter og tømmer den store bøtta. (0, 0).

Vi har nå gjort en modulus, altså 5, overhellinger av 3 liter, og er tilbake ved utgangspunktet med to tomme bøtter. I løpet av to trinn til er vi derved framme ved samme løsning som før:

Vi heller over 3 liter. (0, 3).

Vi heller over til den store bøtta er full, og har da en rest på 1 liter i den lille bøtta.

Flere løsninger er x = 2 + 2 · 5 = 12, x = 2 + 3 · 5 = 17, og så videre. også. Men særlig praktisk er det ikke, for vi er jo innom riktig løsning flere ganger underveis.

Oppgave 9:

Vi har to bøtter uten målestreker på henholdsvis 5 og 7 liter og skal måle opp akkurat 1 liter.

      1. Sett opp en kongruenslikning som uttrykker dette problemet.
         
      2. Vis at likningen har løsning, og finn den enkleste løsningen.
         
      3. Forklar hvordan løsningen kan omsettes i praksis.

Se løsningsforslag

Kilder

    • Rosen, Kenneth H. (1984). Elementary Number Theory and Its Applications. Addison-Wesley.
    • Rinvold, A. R. (2009). Visuelle perspektiv. Tallteori. Caspar Forlag.
    • Petersen, V. B., Tvete, K. S. (2013). I tallkongruensenes verden. Caspar Forlag.
    • Gustavsen, T.S., Hinna, T.R.C., Borge, I.C., Andersen, P.S. (2014). QED 5-10, bind 2. Cappelen Damm A/S.

Kongruens, anvendelser

I artikkelen om regneregler for kongruens ble vi kjent med hvordan vi kan gjøre beregninger med kongruenser. I denne artikkelen ser vi på hvordan vi kan bruke reglene til å begrunne delelighetsregler, kjapt finne feil i en addisjon eller multiplikasjon, sjekke om en EAN−13-kode eller et personnummer er gyldig, utvikle en metode for å finne ut hvilken ukedag en vilkårlig dato faller på, og finne rest ved divisjon av store tall,

Kongruens og delelighetsregler

I artikkelen om delelighet brukte vi regelen om lineære kombinasjoner til å utlede delelighetsregler. Nå skal vi ta en titt på delelighetsreglene en gang til, og se hvordan vi kan begrunne dem ved hjelp av regnereglene for kongruenser. Vi skal i tillegg introdusere elleveregelen, som sier at et tall er delelig på 11 hvis den alternerende tverrsummen er delelig på 11.

I artikkelen om tall og tallsystemer lærte vi å skrive tall på utvidet form som am10m + am−110m − 1 + … + a110 + a0.

Eksempel 1:

2657 skrives på utvidet form som 2 · 103+ 6 · 102 + 5 · 10 + 7.

Regler for å avgjøre om et tall, t, er delelig med et tall, n, går ut på å erstatte t med et tall vi på en enkel måte kan avgjøre om er delelig med n. Teknikken med å bruke kongruenser til dette går ut på å erstatte t med et mindre tall som er kongruent med t modulo n. Siden tallene er kongruente, vil divisjon med n gi samme rest, og hvis denne resten er 0, er begge tallene delelige med n.

I de fleste tilfellene går teknikken ut på å skrive tallet n på utvidet form og erstatte 10 med et annet tall som er kongruent med 10 modulo n. Som vi har lært, vil da også potenser av dette tallet være kongruente med potenser av 10 modulo n.

Eksempler på bruk av reglene finnes i artikkelen om delelighet.

Toerregelen

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

Denne regelen begrunner vi slik:

Siden 10 ≡ 0 (mod 2), kan vi bytte ut alle forekomster av 10 med 0 når vi regner modulo 2:

nam10m + am−110m−1 + … + a0am0m + am−10m−1 + … + a0 ≡ 0 + 0 + … + a0a0 (mod 2)

Et tall er altså kongruent med sitt siste siffer modulo 2. Hvis vi får rest 0 når vi dividerer siste siffer med 2, får vi også rest 0 hvis vi dividerer hele tallet med 2.

Femmerregelen

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

Teknikken er akkurat samme som for toerregelen, bare at vi regner modulo 5 i stedet for modulo 2:

Siden 10 ≡ 0 (mod 5), kan vi bytte ut alle forekomster av 10 med 0 når vi regner modulo 5:

nam10m + am−110m−1 + … + a0am0m + am−10m−1 + … + a0 ≡ 0 + 0 + … + a0a0 (mod 5)

Et tall er altså kongruent med sitt siste siffer modulo 5. Hvis vi får rest 0 når vi dividerer siste siffer med 5, får vi også rest 0 hvis vi dividerer hele tallet med 5.

Firerregelen

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

For å vise denne regelen kan vi ikke erstatte 10 med 0 fordi 10 ≢ 0 (mod 4), 10 er ikke delelig med 4. Derimot kan vi benytte at 100 ≡ 0 (mod 4), 100 er delelig med 4. Vi kan bytte ut alle forekomster av 100 med 0 når vi regner modulo 4:

nam100m + am−1100m−1 + … + a110 + a0am0m + am−10m−1 + … + a110 + a0 ≡ 0 + 0 + … + a110 + a0a110 + a0 (mod 4)

Et tall er altså kongruent med tallet dannet av de siste to sifrene modulo 4. Hvis vi får rest 0 når vi dividerer tallet dannet av de siste to sifrene med 4, får vi også rest 0 hvis vi dividerer hele tallet med 4.

Treerregelen

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

For å vise denne regelen erstatter vi alle potenser av 10 med potenser av 1. Det kan vi gjøre fordi 10 ≡ 1 (mod 3).

nam10m + am−110m−1 + … + a0am1m + am−11m−1 + … + a0am + am−1 + … + a0 (mod 3)

Et tall er altså kongruent med summen av sine sifre modulo 3. Hvis vi får rest 0 når vi dividerer summen av sifrene med 3, får vi også rest 0 hvis vi dividerer hele tallet med 3. Denne siffersummen er det vi kaller tverrsummen, som vi ble kjent med i artikkelen om tall og tallsystemer.

Nierregelen

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

Begrunnelsen er akkurat samme som for treerregelen, fordi 10 ≡ 1 (mod 9):

nam10m + am−110m−1 + … + a0am1m + am−11m−1 + … + a0am + am−1 + … + a0 (mod 9)

Et tall er altså kongruent med summen av sine sifre modulo 9. Hvis vi får rest 0 når vi dividerer summen av sifrene med 9, får vi også rest 0 hvis vi dividerer hele tallet med 9.

Så presenterer vi en regel som er vanskelig å begrunne uten bruk av kongruensregning:

Elleveregelen

$\fbox{Tall er delelige med 11 når den alternerende tverrsummen er delelig med 11}$

Her baserer vi oss på at 10 ≡ −1 (mod 11) og erstatter alle potenser av 10 med potenser av −1:

nam10m + am−110m−1 + … + a0am(−1)m + am−1(−1)m−1 + … + a0 (mod 11)

Her vil −1 gi et fortegnsskifte hvis vi opphøyer i et oddetall, men ikke noe fortegnsskifte hvis vi opphøyer i et partall. Det vil si at a1, a3, og så videre vil få fortegnsskifte, men ikke a0, a2, og så videre. Vi har altså at

n ≡ a0a1 + a2a3 + … + (−1)mam (mod 11)

Denne summen av sifre med vekslende fortegn er den alternerende tverrsummen, som vi ble kjent med i artikkelen om tall og tallsystemer.

Eksempel 2:

132 er delelig med 11 fordi A(132) = 2 − 3 + 1 = 0 er delelig med 11.

116 er ikke delelig med 11 fordi A(116) = 6 − 1 + 1 = 6 ikke er delelig med 11.

81048 er delelig med 11 fordi A(81048) = 8 − 4 + 0 − 1 + 8 = 11 er delelig med 11.

Når det gjelder treer- og nierregelen kan vi ta tverrsummen på nytt hvis vi ender opp med et stort tall. Det kan vi ikke med den alternerende tverrsummen, men vi kan finne kongruente tall ved å subtrahere eller addere 11 gjentatte ganger. Men siden vi vekselvis adderer og subtraherer sifre, ender vi imidlertid sjelden opp med særlig store tall.

Oppgave 1:

Avgjør om 924 er delelig med 2, 3, 4, 5, 9 og 11 ved å bruke delelighetsregler. Gjør testene i den rekkefølgen du ønsker.

Skjermfilm
Se film der løsningsforslaget vises

Kontrollere regnestykker

Nierprøven

Adderer vi tverrsummene til to tall, blir svaret kongruent med tverrsummen til summen av tallene modulo 9:

$\fbox{$T(a) + T(b) \equiv T(a + b) \, (mod \; 9)$}$

Det er lett å innse at dette er riktig, for som vi så da vi studerte delelighetsreglene, er et talls tverrsum kongruent med tallet selv modulo 9, T(a) ≡ a (mod 9) og T(b) ≡ b (mod 9). Da må T(a) + T(b) ≡ a + b (mod 9), ifølge regelen for å addere på begge sider av en kongruensrelasjon, som vi har lært tidligere. Og igjen, et tall er kongruent med sin egen tverrsum modulo 9, a + b ≡ T(a + b) (mod 9).

Dette utnytter vi i den såkalte nierprøven: Hvis vi adderer to tall og tverrsummen til svaret ikke er kongruent med summen av addendenes tverrsum modulo 9, er ikke addisjonen korrekt.

Eksempel 3:

Vi skal bruke nierprøven til å kontrollere utregningen 2556 + 845 = 3411.

Vi får T(a) = T(2556) = 18, T(b) = T(845) = 17, så T(a) + T(b) = 35. Tar vi tverrsummen en gang til, får vi T(35) = 8.

T(svar) = T(3411) = 9.

Siden 8 og 9 ikke er kongruente modulo 9, er ikke utregningen riktig. Riktig svar er 3401, med tverrsum T(3401) = 8.

Nierprøven fanger imidlertid ikke opp feil som er multipler av 9, så vi kan ikke konkludere med at en addisjon er riktig fordi om nierprøven ikke påviser feil. Hadde vi for eksempel fått det gale svaret 3410 i eksempel 3, ville vi ikke funnet feilen fordi T(3410) = 8.

Eksempel 4:

Vi skal bruke nierprøven til å kontrollere utregningen: 1342 + 786 = 2164.

Vi får T(a) = T(1342) = 10. T(b) = T(786) = 21, så T(a) + T(b) = 31. Tar vi tverrsummen en gang til, får vi T(31) = 4.

T(svar) = T(2164) = 13. Tar vi tverrsummen en gang til, får vi T(13) = 4.

Siden 4 og 4 er kongruente modulo 9, har vi ikke påvist feil. Men utregningen er allikevel feil, riktig utregning er 1342 + 786 = 2128. Men vi oppdager ikke feilen fordi den er en multippel av 9, 2164 − 2128 = 45.

Nierprøven virker også på multiplikasjon. Multipliserer vi tverrsummene til to tall, blir svaret kongruent med tverrsummen til produktet av tallene modulo 9:

$\fbox{$T(a) \cdot T(b) \equiv T(a \cdot b) \, (mod \; 9)$}$

Vi kunne laget en treerprøve som virket etter samme prinsipp, men den ville ikke fange opp feil som nierprøven ikke fanger opp, og ville feile for alle multipler av 3, så nierprøven er et bedre valg.

Elleveprøven

Adderer vi de alternerende tverrsummene til to tall, blir svaret kongruent med den alternerende tverrsummen til summen av tallene modulo 11:

$\fbox{$A(a) + A(b) \equiv A(a + b) \, (mod \; 11)$}$

Dette utnytter vi i den såkalte elleveprøven: Hvis vi adderer to tall og den alternerende tverrsummen til svaret ikke er kongruent med summen av addendenes alternerende tverrsum modulo 11, er ikke addisjonen korrekt.

Eksempel 5:

Vi skal bruke elleveprøven til å kontrollere utregningen: 1342 + 786 = 2164.

Vi får A(a) = A(1342) = 2 − 4 + 3 − 1 = 0. A(b) = A(786) = 6 − 8 + 7 = 5, så A(a) + A(b) = 5.

A(svar) = A(2164) = 4 − 6 + 1 − 2 = −3. Vi adderer 11 en gang og får 8.

Siden 5 og 8 ikke er kongruente modulo 11, er ikke utregningen riktig. Riktig svar er 2128.

​Eksempel 4 og 5 besto av nøyaktig samme, uriktige regnestykke. Men nierprøven sviktet fordi svaret var 45 for høyt, og 45 er en multippel av 9. Men 45 er ikke en multippel av 11, derfor fungerte elleveprøven.

Gjennomsnittlig vil nierprøven feile i hvert niende tilfelle og elleveprøven feile i hvert ellevte tilfelle. Men begge prøvene vil bare feile hvis feilen både er en multippel av både 9 og 11, hvert 99. tilfelle. Det er derfor bare ca. 1 % sannsynlighet for at begge prøvene feiler.

Elleveprøven virker også på multiplikasjon. Multipliserer vi de alternerende tverrsummene til to tall, blir svaret kongruent med den alternerende tverrsummen til produktet av tallene modulo 11:

$\fbox{$A(a) \cdot A(b) \equiv A(a \cdot b) \, (mod \; 11)$}$

Oppgave 2:

Bruk nierprøven og/eller elleveprøven til å kontrollere utregningen 757 · 987 = 747249.

Skjermfilm
Se film der løsningsforslaget vises

Oppgave 3:

Bruk nierprøven og/eller elleveprøven til å kontrollere utregningene under. (Legg merke til at faktorene er de samme i alle oppgavene, så resultater fra en deloppgave kan brukes i en annen):

      1. 1234 · 364 = 224588
         
      2. 1234 · 364 = 449194
         
      3. 1234 · 364 = 449176

​Se løsningsforslag

Oppgave 4:

Hva betyr følgende for resultatet av en multiplikasjon?

      1. Både nierprøven og elleveprøven påviser feil.
         
      2. Enten nierprøven eller elleveprøven påviser feil.
         
      3. Verken nierprøven eller elleveprøven påviser feil.

​Se løsningsforslag

Kontrollsiffer

Strekkoder, som vi i dag finner på nesten alt mulig i butikken, brukes til å identifisere en vare. For å verifisere at koden blir riktig avlest, inneholder den et kontrollsiffer som er laget slik at en vektet sum av sifrene i strekkoden blir 0 modulo 10. Vektinga gjøres slik at sifrene annet hvert multipliseres med 1 og 3, for å avsløre om to etterfølgende siffer byttes om. Uten vekting ville jo tverrsummen uansett blitt den samme.

En mye brukt strekkode er EAN-13, som består av 13 siffer, hvorav det siste er kontrollsifferet.

Et eksempel på en EAN-13-kode er sifrene 9-7-8-8-2-0-2-4-2-0-9-8-7, der kontrollsifferet er 7. Koden og vektene satt opp i en tabell ser slik ut:

Strekkode 9 7 8 8 2 0 2 4 2 0 9 8 7
Vekt 1 3 1 3 1 3 1 3 1 3 1 3 1
Vektet kode 9 21 8 24 2 0 2 12 2 0 9 24 7

Vi ser at summen av de vektede kodene blir 9 + 21 + 8 + 24 + 2 + 0 + 2 + 12 + 2 + 0 + 9 + 24 + 7 = 120. Siden 120 ≡ 0 (mod 10), er dette en gyldig EAN-13-kode.

Oppgave 5:

Avgjør om 7-6-1-3-0-3-5-8-3-0-5-9-0 er en gyldig EAN-13-kode.

​Se løsningsforslag

Et annet eksempel på bruk av kontrollsifre finner vi i personnummer. Et personnummer er elleve siffer langt og består av fødselsdato (d1d2), -måned (m1m2) og -år (å1å2), etterfulgt av et tresifret løpenummer (n1n2n3), der n3 er oddetall for menn, og partall for kvinner. Til slutt kommer to kontrollsifre (k1k2).

Kontrollsifrene er slik at en vektet tverrsum skal være kongruent med 0 modulo 11 både ved bruk av det ene og det andre sifferet. I noen tilfeller vil et kontrollsiffer måtte være 10 for at tverrsummen skal bli riktig, men da blir personnummeret 12 siffer langt, og må forkastes.

Til å beregne kontrollsifferet i en EAN-kode ble det brukt en vekting som besto av 1 og 3 annet hvert. Tilsvarende for personnummer er mer komplisert, 3-7-6-1-8-9-4-5-1-0 for første kontrollsiffer og 5-4-3-2-7-6-5-4-3-2-1 for andre. Vi kan sette det opp i en tabell slik:

Personnummer d1 d2 m1 m2 å1 å2 n1 n2 n3 k1 k2
Vekt ved k1 3 7 6 1 8 9 4 5 2 1 0
Vekt ved k2 5 4 3 2 7 6 5 4 3 2 1

Hvis for eksempel Harry Potter oppgir at fødselsnummeret hans er 31078012334, kontrollerer vi først gyldigheten ved å se på første kontrollsiffer:

Personnummer 3 1 0 7 8 0 1 2 3 3 4
Vekt ved k1 3 7 6 1 8 9 4 5 2 1 0
Vektet personnummer 9 7 0 7 64 0 4 10 6 3 0

Og den vektede summen blir 9 + 7 + 0 + 7 + 64 + 0 + 4 + 10 + 6 + 3 + 0 ≡ 110 ≡ 0 (mod 11).

Så ser vi på andre kontrollsiffer:

Personnummer 3 1 0 7 8 0 1 2 3 3 4
Vekt ved k2 5 4 3 2 7 6 5 4 3 2 1
Vektet personnummer 15 4 0 14 56 0 5 8 9 6 4

Og den vektede summen blir 15 + 4 + 0 + 14 + 56 + 0 + 5 + 8 + 9 + 6 + 4 ≡ 121 ≡ 0 (mod 11).

Personnummeret er derved gyldig.

Navn og personnummer aksepteres i mange tilfeller som bevis på en persons identitet. Men personnummer kan lett kommer på avveie, for eksempel ved at uvedkommende leser det på et førerkort eller bankkort.

Det fantes en periode en side på Internett der en kunne registrere seg som bruker å oppgi navn og personnummer. Siden sjekket så navn og personnummer mot folkeregisteret og avviste registreringen hvis noe var feil. Hvis vi kjente en persons navn og fødselsdato, kunne vi da prøve oss fram til vi ble akseptert, og på den måten finne ut av personnummeret.

For en gitt fødselsdato finnes det nemlig ikke så veldig mange mulige personnumre.

La oss si at vi på Facebook ser at Harry Potter fylte 38 år 31. juli 2018. Da kjenner vi de 6 første sifrene i personnummeret, 310780. Løpenummeret må vi gjette på. Det finnes i utgangspunktet 1000 muligheter, men ved å google litt, finner vi ut at på det tidspunktet ble det bare tildelt sifre mellom 000 og 499. Siden Harry Potter er mann, må det tredje sifferet være oddetall. Og 17 % av løpenumrene må forkastes fordi de resulterer i at et kontrollsiffer blir 10. Det gjenstår da bare ca. 207 muligheter, og statistisk vil vi i gjennomsnitt få treff etter om lag 100 forsøk.

Oppgave 6:

Avgjør om 21023712345 er et gyldig personnummer.

​Se løsningsforslag

Ukedagsformelen

Ukedagene er et glimrende eksempel på kongruensregning, der vi regner modulo 7. Nå skal vi utlede en formel, en evighetskalender for å finne hvilken ukedag en vilkårlig dato faller på.

Vi starter med å nummerere dagene fra 1 til 7, der 1 er ukens første dag, mandag. 

Hvis året hadde 364 dager, ville en gitt dato falle på samme ukedag hvert år fordi 364 ≡ 0 (mod 7). Når 1. mars år 2000 var onsdag, altså dag 3, ville 1. mars 2001 blitt dag 3 + 364 ≡ 3 + 0 ≡ 3 (mod 7), også en onsdag.

Men lengden på året bestemmes ut fra hvor lang tid Jorda bruker på å gå rundt Sola, og de fleste årene har 365 dager. Når 1. mars 2000 var dag 3, blir 1. mars 2001 dag 3 + 365 ≡ 3 + 1 ≡ 4 (mod 7), altså en torsdag.

Vi øker altså dagnummeret med 365 ≡ 1 (mod 7) for hvert år etter år 2000. 

Vil vi lage en formel for å finne ukedagen til 1. mars et vilkårlig år, tar vi utgangspunkt i at 1. mars 2000 var dag nummer 3, og adderer antall år etter 2000 modulo 7.

u ≡ 3 + y − 2000 (mod 7), der y er året der vi vil finne dagnummeret til 1. mars. 

Eksempel 7:

1. mars 2002 blir u ≡ 3 + 2002 − 2000 ≡ 5 (mod 7), en fredag.

1. mars 2003 blir u ≡ 3 + 2003 − 2000 ≡ 6 (mod 7), en lørdag.

Men Jorda bruker ikke nøyaktig 365 dager på turen rundt Sola, men om lag en kvart dag mer. For at året skal bli et helt antall dager, lar en 3 år bestå av 365 dager og 1 år – skuddåret, består av 366 dager. Et skuddår forskyver dagnummeret med 366 ≡ 2 (mod 7) dager. Vi må justere formelen for å ta høyde for den ekstra dagen.

Skuddår er år med årstall som er delelige med 4, så 2000, 2004, 2008, etc. var skuddår. Vi finner derved antall skuddår etter år 2000 ved å telle antall hele fireårsperioder etter år 2000. Det blir $\lfloor \frac{\displaystyle y − 2000}{\displaystyle 4} \rfloor$.

For hvert skuddår må vi addere 1 ekstra til dagnummeret, så formelen blir 

$u \equiv 3 + y − 2000 + \lfloor \frac{\displaystyle y − 2000}{\displaystyle 4} \rfloor \, (mod \; 7)$

Formelen er nå korrekt innenfor et ganske stort tidsspenn.

Eksempel 8:

Vi kan beregne at 1. mars 2065 vil falle på en søndag:
$u \equiv 3 + 2065 − 2000 + \lfloor \frac{\displaystyle 2065 − 2000}{\displaystyle 4} \rfloor \equiv 3 + 2065 − 2000 + 16 \equiv 84 \equiv 0 \, (mod \; 7)$.

Logikken er den samme for år før år 2000, så vi kan regne ut at Harry Belafonte (1/3-1927) ble født på en tirsdag:
$u \equiv 3 + 1927 − 2000 + \lfloor \frac{\displaystyle 1927 − 2000}{\displaystyle 4} \rfloor \, \equiv 3 + 1927 − 2000 − 19 \equiv −89 \equiv 2 (mod \; 7)$.

Men Jorda bruker ikke nøyaktig 365 og en kvart dag på runden rundt Sola, men litt mindre. For å kompensere for dette sløyfes skuddårsdagen i hele hundreår som ikke er delelige med 4. Det vil si at år 1700, 1800 og 1900 ikke var skuddår, mens år 2000 var skuddår. For de tre første hele hundreårene i en periode på 400 år tas det altså bort en skuddårsdag, men ikke for det fjerde.

Nå skal vi se hvordan vi kan implementere denne mekanismen matematisk. Tabellen under viser verdien til $\frac{\displaystyle 3n}{\displaystyle 4}$ og $\lceil \frac{\displaystyle 3n}{\displaystyle 4} \rceil$ for n = 0, 1, … , 9.

n 0 1 2 3 4 5 6 7 8 9
$\frac{\displaystyle 3n}{\displaystyle 4}$ 0 0,75 1,5 2,25 3 3,75 4,5 5,25 6 6,75
$\big \lceil \frac{\displaystyle 3n}{\displaystyle 4}\big \rceil$ 0 1 2 3 3 4 5 6 6 7

 

Vi ser at $\lceil \frac{\displaystyle 3n}{\displaystyle 4} \rceil$ øker tre ganger i trinn på 1, men ikke øker i det fjerde trinnet. Og dette er akkurat det vi trenger for å kompensere for de utelatte skuddårene. Lar vi h betegne antall hele hundreår i årstallet, trekker vi fra $\lceil \frac{\displaystyle 3(h − 20)}{\displaystyle 4} \rceil$.

Nå har vi en komplett formel for å regne ut hvilken ukedag 1. mars faller på i et vilkårlig år:

$u \equiv 3 + y − 2000 + \lfloor \frac{\displaystyle y − 2000}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3(h − 20)}{\displaystyle 4} \rceil \, (mod \; 7)$

Nå er det jo litt tungvint å regne i forhold til år 2000. Regnet vi i forhold til år 0, ville vi slippe å trekke fra 2000 hele veien. Grunnen til at vi startet på år 2000, er at det er praktisk å regne med datoer vi lett kan sjekke på kalenderen. Bruker vi formelen til å regne oss tilbake til år 0, ser vi imidlertid at 1. mars år 0 også ville falt på en onsdag og hatt dagnummer 3. I forhold til skuddår, er år 0 også delelig på 4 og på 400. År 0 har altså samme egenskaper som år 2000, så vi kan bytte ut 2000 med 0 i formelen:

$u \equiv 3 + y − 0 + \lfloor \frac{\displaystyle y − 0}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3(h − 0)}{\displaystyle 4} \rceil \, (mod \; 7)$.

Å trekke fra 0 kan vi selvfølgelig droppe, så vi får:

$u \equiv 3 + y + \lfloor \frac{\displaystyle y}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3h}{\displaystyle 4} \rceil \, (mod \; 7)$, der y er årstallet og h antall hundreår i årstallet, altså $\lfloor \frac{\displaystyle y}{\displaystyle 100} \rfloor$.

Eksempel 9:

Vi skal regne ut hvilken ukedag 1. mars 3165 faller på. Vi får

$u \equiv 3 + 3165 + \lfloor \frac{\displaystyle 3165}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3\cdot 31}{\displaystyle 4} \rceil \equiv 3 + 3165 + 791 − 24 \equiv 3935 \equiv 1 \, (mod \; 7)$

En mandag

Nå er det selvfølgelig ikke særlig tilfredsstillende å bare kunne regne ut hvilken ukedag 1. mars faller på. Men tar vi utgangspunkt i 1. mars, finner vi også greit ut hvilken ukedag andre datoer faller på ved å beregne hvor stor forskyvningen er i hver måned. Grunnen til at vi har valgt akkurat 1. mars som utgangspunkt er ikke tilfeldig. Dette er første dag etter en eventuell skuddårsdag. Med første mars som utgangspunkt, vil en eventuell skuddårsdag alltid falle i slutten av en periode, og beregningene blir mye enklere. Vi later derfor som om mars er årets første måned.

Tabellen under viser hvor stor forskyvningen av ukedagene er pr. måned, og hvor stor den akkumulerte forskyvingen er totalt den første i hver måned, målt fra første mars. Forskyvningen finnes ved å beregne antall dager i måneden modulo 7. For eksempel 31 ≡ 3 (mod 7) for måneder med 31 dager. Den variable lengden på februar påvirker ikke den akkumulerte forskyvningen siden den ligger sist i perioden.

En morsom digresjon er at i den romerske kalenderen begynte året også 1. mars, slik at september, oktober, november og desember var måned nummer 7, 8, 9 og 10, slik som i tabellen under. Det forklarer at månedsnavnene er avledet av de latinske ordene for 7, 8, 9 og 10, septem, octo, novem og decem.

Nummer Måned Forskyvning Akkumulert forskyvning
1 mars 3 0
2 april 2 3
3 mai 3 5
4 juni 2 8
5 juli 3 10
6 august 3 13
7 september 2 16
8 oktober 3 18
9 november 2 21
10 desember 3 23
11 januar 3 26
12 februar 0 (1) 29

 

Vi kan altså finne ukedagen den første i hver måned ved å bruke ukedagsformelen for å finne ukedagen 1. mars falt på, og så legge til månedsforskyvningen.

Eksempel 10:

Vi har tidligere funnet ut at første mars år 2000 var en onsdag, med dagnummer 3. Da blir dagnummeret til 1. oktober samme år 3 + 18 ≡ 0 (mod 7). Altså var 1. oktober år 2000 en søndag.

Litt klønete er det jo med denne tabellen, det ville vært mer elegant hvis vi kunne beregnet forskyvningen ved hjelp av en formel. Og faktisk viser det seg at $\lfloor \frac{\displaystyle 13m − 1}{\displaystyle 5} \rfloor − 2$, der m er månedsnummeret regnet fra mars, er lik den akkumulerte forskyvningen. Så nå kan vi utvide ukedagsformelen til å beregne hvilken dag den 1. i hver måned faller på, når vi husker at januar og februar regnes som måned 11 og 12 året før:

$u \equiv 3 + y + \lfloor \frac{\displaystyle y}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3h}{\displaystyle 4} \rceil + \lfloor \frac{\displaystyle 13m − 1}{\displaystyle 5} \rfloor − 2 \, (mod \; 7)$.

Eksempel 11:

Vi skal finne ut hvilken dato 1. juni 2013 falt på. Juni er måned 4, når vi regner fra mars. Vi får

$u \equiv 3 + 2013 + \lfloor \frac{\displaystyle 2013}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3 \cdot 20}{\displaystyle 4} \rceil + \lfloor \frac{\displaystyle 13 \cdot 4 − 1}{\displaystyle 5} \rfloor − 2 \equiv$

$3 +2013 + 503 − 15 + 10 − 2 \equiv 6\, (mod \; 7)$

En lørdag.

Vi skal finne ut hvilken dato 1. februar 1966 falt på. Februar 1966 er måned 12 i 1965, når vi regner fra mars. Vi får

$u \equiv 3 + 1965 + \lfloor \frac{\displaystyle 1965}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3 \cdot 19}{\displaystyle 4} \rceil + \lfloor \frac{\displaystyle 13 \cdot 12 − 1}{\displaystyle 5} \rfloor − 2 \equiv $

$3 + 1965 + 491 − 15 + 31 − 2 \equiv 2473 \equiv 2\, (mod \; 7)$

En tirsdag.

Så gjenstår det bare å utvide formelen til å gjelde en vilkårlig dato, ikke bare den 1. hver måned. Dette er enkelt, for hvis datoen er d, legger vi til d − 1, det vil si antall dager datoen kommer etter den 1. Så ukedagsformelen blir

$u \equiv 3 + y + \lfloor \frac{\displaystyle y}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3h}{\displaystyle 4} \rceil + \lfloor \frac{\displaystyle 13m − 1}{\displaystyle 5} \rfloor − 2 + d − 1 \, (mod \; 7)$

Vi ser at 3 − 2 − 1 = 0, så disse leddene kan strykes, og vi får ukedagsformelen i sin endelige form:

$\fbox{$u \equiv y + \lfloor \frac{\displaystyle y}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3h}{\displaystyle 4} \rceil + \lfloor \frac{\displaystyle 13m − 1}{\displaystyle 5} \rfloor + d \, (mod \; 7)$}$

Her er y årstallet, h antall hundreår i årstallet, m månedsnummeret regnet fra mars, og d dagnummeret.

Dette nettstedet har en app som finner ukedager ved hjelp av ukedagsformelen. Hvis du der huker av for «Vis utregning», lister appen opp detaljene i utregningen.

Eksempel 12:

Vi skal finne ut hvilken ukedag månelandingen 20. juli 1969 fant sted på. Juli er måned 5, når vi regner fra mars. Vi får

$u \equiv 1969 + \lfloor \frac{\displaystyle 1969}{\displaystyle 4} \rfloor − \lceil \frac{\displaystyle 3 \cdot 19}{\displaystyle 4} \rceil + \lfloor \frac{\displaystyle 13 \cdot 5 − 1}{\displaystyle 5} \rfloor + 20 \equiv $

$1969 + 492 − 15 + 12 + 20 \equiv 2478 \equiv 0 \, (mod \; 7)$

En søndag.

​Oppgave 7:

Bruk ukedagsformelen til å finne ut hvilken ukedag følgende begivenheter fant sted.

      1. Angrepet på tvillingtårnene i New York den 11. september 2001.
         
      2. Wolfgang Amadeus Mozarts fødsel den 27. januar 1756.

Se løsningsforslag

Fordi vår tidsregning hopper over år 0, gir ukedagsformelen ikke riktige svar for årstall tidligere enn år 1.

Rest ved divisjon av store tall

Som vi skal se i artikkelen om kryptografi, vil vi kunne ha behov for å finne resten vi får når to store tall divideres på hverandre. Så lenge tallene ikke er for store, kan vi enkelt gjøre slike beregninger direkte med en datamaskin eller kalkulator, for eksempel ved kommandoen rest i Excel eller mod i GeoGebra. Men tall som er så store at de har noen nytte i kryptografi, klarer ikke disse verktøyene å håndtere direkte. Vi må da gjøre tallene om til mindre, kongruente tall, som vi kan bruke i vanlige beregninger.

I eksempel 9 i artikkelen om regneregler for kongruens viste vi at 2916 ≡ 4 (mod 19) ved å benytte at potensen 2916 kunne skrives som $(29)^{\large 2^{\Large 2^{\Large 2^{\Large 2}}}}$ og så bruke potensregelen til å finne tall kongruente med 29, 292, etc.

I eksemplet ser det ut som vi hadde flaks, siden 16 er en potens av 2. Men faktum er at alle tall kan skrives som en sum av toerpotenser, og derved kan denne metoden utvides til å fungere på alle tall.

De første toerpotensene er 20 = 1, 21 = 2; 22 = 4, 23 = 8; 24 = 16; 25 = 32; 26 = 64; 27 = 128; 28 = 256; 29 = 512; 210 = 1024; 211 = 2048; 212 = 4096; 213 = 8192.

For å finne toerpotensene et tall er sammensatt av, trekker vi suksessivt fra den største toerpotensen vi kan.

Eksempel 13:

Vi skal skrive 605 som en sum av toerpotenser.

Den største potensen vi kan trekke fra er 512:
605 − 512 = 93.

Nå er den største potensen vi kan trekke fra 64:
93 − 64 = 29.

Nå er den største potensen vi kan trekke fra 16:
29 − 16 = 13.

Nå er den største potensen vi kan trekke fra 8:
13 − 8 = 5.

Nå er den største potensen vi kan trekke fra 4:
5 − 4 = 1.

Nå er den største potensen vi kan trekke fra 1:
1 − 1 = 0.

Så 605 = 1 + 4 + 8 + 16 + 64 + 512.

I det følgende bruker vi regneeksempler der tallene ikke er større enn at vi kan kontrollere svaret i et regneark eller GeoGebra.

Eksempel 14:

Vi skal finne resten vi får når vi dividerer 715 med 13.

Vi skriver først 15 som en sum av toerpotenser: 15 = 1 + 2 + 4 + 8, så

715 = 71+2+4+8 = 7 · 72 · 74 · 78.

Så erstatter vi suksessivt de enkelte faktorene med mindre, kongruente tall. (Utregningene underveis gjør vi med Excel eller GeoGebra.)

Faktoren 7 kan ikke bli mindre, men for 72 får vi

72 ≡ 49 ≡ 10 (mod 13)

74 skriver vi først som (72)2. Siden vi har funnet ut at 72 ≡ 10 (mod 13), gir potensregelen at

74 ≡ (72)2 ≡ 102 ≡ 100 ≡ 9 (mod 13)

Så skriver vi 78 som (74)2. Siden vi har funnet ut at 74 ≡ 9 (mod 13), gir potensregelen at

78 ≡ (74)2 ≡ 92 ≡ 81 ≡ 3 (mod 13)

Så vi har 715 ≡ 7 · 72 · 74 · 78 ≡ 7 · 10 · 9 · 3 ≡ 1890 ≡ 5 (mod 13).

Resten blir 5. Dette kan vi kontrollere ved å skrive =rest(7^15;13) i et regneark eller mod(7^15,13) i GeoGebra.

Dette nettstedet har en app som finner rest ved divisjon av store tall. Hvis du der huker av for «Vis utregning», lister appen opp trinnene i beregningen, det kan være veldig instruktivt.

Vil vi holde tallene så små som mulig i utregningen, kan det imidlertid av og til lønne seg å velge negative tall i en kongruens.

Eksempel 15:

Vi gjør om igjen noen av utregningene i eksempel 14, men nå med negative tall der det forenkler utregningen:

72 ≡ 49 ≡ −3 (mod 13)

74 ≡ (72)2 ≡ (−3)2 ≡ 9 ≡ −4 (mod 13)

78 ≡ (74)2 ≡ (−4)2 ≡ 16 ≡ 3 (mod 13)

Så vi har 715 ≡ 7 · 72 · 74 · 78 ≡ 7 · (−3) · (−4) · 3 ≡ 252 ≡ 5 (mod 13).

Oppgave 8:

Bruk metoden med toerpotenser til å beregne resten du får når du dividerer 613 med 11. Kontroller svaret i et regneark eller GeoGebra, eller med appen som finner rest.

Se løsningsforslag

Kilder

    • Gustavsen, T.S., Hinna, T.R.C., Borge, I.C., Andersen, P.S. (2014). QED 5-10, bind 2. Cappelen Damm A/S.
    • Rinvold, A. R. (2009). Visuelle perspektiv. Tallteori. Caspar Forlag.
    • Petersen, V. B., Tvete, K. S. (2013). I tallkongruensenes verden. Caspar Forlag.
    • Petersen V.B., Tvete K.S., (2013). I tallkongruensenes verden. Caspar forlag.

Kongruens, regneregler

Addisjons-, subtraksjons- og multiplikasjonsregler

Når vi løser likninger, kan vi addere, subtrahere og multiplisere med samme tall på begge sider av likhetstegnet. Det samme kan vi gjøre på begge sider av kongruenstegnet:

$\fbox{$ \begin{align} \text{Hvis } a &\equiv b \, (mod \; n) \text{, vil }\\
a + c &\equiv b + c \, (mod \; n) \\
a − c &\equiv b − c \, (mod \; n) \\
ac &\equiv bc \, (mod \; n) \end{align} $}$

Men i en kongruensrelasjon modulo n kan vi utvide dette til å ikke bare gjelde samme tall, men to vilkårlige tall som er kongruente modulo n:

$\fbox{$ \begin{align} \text{Hvis } a &\equiv b \, (mod \; n) \text{ og } c \equiv d \, (mod \; n)\text{, vil }\\
a + c &\equiv b + d \, (mod \; n) \\
a − c &\equiv b − d \, (mod \; n) \\
ac &\equiv bd \, (mod \; n) \end{align} $}$

Vi kan illustrere dette for addisjon ved å tenke på at når a og b er kongruente modulo n, strekker de seg like langt forbi heltallige multipler av n, la oss kalle denne lengden r1. Tilsvarende gjelder for c og d, la oss kalle denne lengden r2. Da vil både a + c og b + d strekke seg r1 + r2 forbi heltallige multipler av n, og følgelig også være kongruente modulo n.

Tilsvarende kan vi argumentere for multiplikasjon, og subtraksjon kan vi se på som addisjon med et negativt tall.

Eksempel 1:

a = 7, b = 4,
c = 8, d= 5,
n = 3

Her er ab (mod 3), fordi 3 | (7 − 4) = 3. I figuren under ser vi at ab (mod 3 fordi a og b strekker seg like langt, nemlig 1, forbi heltallige multipler av 3.

Tilsvarende er cd (mod 3), fordi 3 | (8 − 5) = 3. I figuren under ser vi at cd (mod 3) fordi c og d strekker seg like langt, nemlig 2, forbi heltallige multipler av 3.

Da skal a + c = 15 ≡ b + d = 9 (mod 3). Og i figuren under ser vi at a + cb + d (mod 3) fordi a + c og b + d strekker seg like langt, nemlig 0, forbi heltallige multipler av 3.

Illustrasjon av addisjon av kongruenser

Oppgave 1:

Vi har at ab (mod 7). Avgjør om a + cb + d (mod 7) når

1) c = 5, d = 12

2) c = 8, d = 16

Se løsningsforslag

Vi har altså at a + cb + d (mod n) når ab (mod n) og cd (mod n).

Det betyr at vi i uttrykk som a + c (mod n) kan erstatte a med et tall som er kongruent med a modulo n, og c med et tall som er kongruent med c modulo n. Det kan benyttes til å forenkle utregninger.

Eksempel 2:

Vi skal regne ut 30 + 29 (mod 7). Siden vi kjenner 7-gangen, ser vi uten videre at 30 ≡ 2 (mod 7) og 29 ≡ 1 (mod 7). Vi får derfor at

30 + 29 ≡ 2 + 1 ≡ 3 (mod 7).

Eksempel 3:

Vi lurer på hvilken ukedag 18. oktober vil falle på når 18. august er en fredag.

August har 31 dager og september 30. Siden det er 7 dager i uka, betyr det en forskyvning av ukedagen på

31 + 30 ≡ 3 + 2 ≡ 5 (mod 7).

Ukedagen forskyves 5 dager fram, til onsdag. 18. oktober er altså en onsdag når 18 august er en fredag.

I artikkelen om anvendelser av kongruens skal vi se hvordan vi kan bruke kongruens til å finne ukedagen til en vilkårlig dato er i hele vår tidsregning.

På samme måte som vi i en addisjon kan erstatte tall med kongruente tall, kan vi også gjøre det i en multiplikasjon.

Eksempel 4

8 · 9 · 12 ≡ 1 · 2 · 5 ≡ 10 ≡ 3 (mod 7).

Oppgave 2:

Du vet at 365 ≡ 1 (mod 7) og at 15. mars 2017 er en onsdag. Bruk kongruensregning til å finne ut hvilken ukedag 15. mars 2021 vil falle på.

Se løsningsforslag

Finne mindre, kongruente tall

Når vi har store tall, er det imidlertid ikke alltid så lett å finne mindre, kongruente tall. Vi ser enkelt at 15 ≡ 1 (mod 7), men hva med for eksempel 1 641 739 (mod 7)?

Trekker vi modulus fra tallet, får vi et kongruent tall. Vi kan derfor finne en løsning ved å gjentatte ganger trekke modulus fra tallet, inntil tallet er blitt mindre enn modulus.

Eksempel 5:

Vi skal forenkle 29 (mod 7). Vi trekker 7 gjentatte ganger fra 29 og får

29 − 7 = 22.
22 − 7 = 15.
15 − 7 = 8.
8 − 7 = 1. 

Så 29 ≡ 1 (mod 7).

Men med et tall som 1 641 739 må vi gjenta prosessen 234 534 ganger, helt umulig i praksis.

Da benytter vi i stedet et knep vi lærte da vi så på divisjonsalgoritmen i artikkelen om delelighet. Hvis t er tallet vi skal redusere, og n er modulus, vil $\lfloor \frac{\displaystyle t}{\displaystyle n} \rfloor$ være det største antall ganger n går opp i t. Trekker vi fra n dette antallet ganger, sitter vi igjen med et tall som er større eller lik 0 og mindre enn modulus. Det vil si det laveste, ikke-negative tallet som er kongruent med t.

Denne metoden fungerer også for negative tall. Og tall som allerede er redusert så langs som mulig, vil forbli som de er.

Altså:

$\fbox{$ \text{Hvis } t \equiv a \, (mod \; n) \text{ vil } k = t − \lfloor \frac{\displaystyle t}{\displaystyle n} \rfloor \cdot n \equiv a \, (mod \; n) \text{, og } 0 \le k < n$}$

Eksempel 6.1:

$1 \, 641 \, 739 \equiv 1 \, 641 \, 739 − \lfloor \frac{\displaystyle 1 \, 641 \, 739}{\displaystyle 7} \rfloor \cdot 7 \equiv 1 \, 641 \, 739 − 234 \, 534 \cdot 7 \equiv 1 \, (mod \; 7)$.

Eksempel 6.2:

$−376 \equiv −376 − \lfloor \frac{\displaystyle −376}{\displaystyle 9}\rfloor \cdot 9 \equiv −376 − (−42 \cdot 9 ) \equiv 2 \, (mod \; 9)$.

Eksempel 6.3:

$4 \equiv 4 − \lfloor \frac{\displaystyle 4}{\displaystyle 6}\rfloor \cdot 6 \equiv 4 − 0 \cdot 6 \equiv 4 \, (mod \; 6)$.

Oppgave 3:

Finn det laveste, ikke-negative tallet som er kongruent med 243 modulo 13.

Se løsningsforslag

Divisjonsregler

I en vanlig likning kan vi addere, subtrahere, multiplisere og dividere med samme tall på begge sider av likhetstegnet, så lenge vi ikke dividerer med null.

Og vi har sett at reglene for addisjon, subtraksjon og multiplikasjon også gjelder når likhetstegnet byttes ut med et kongruenstegn.

På en måte kan vi si at regelen for divisjon også gjelder når likhetstegnet byttes ut med et kongruenstegn, men vi må utvide kravet om at vi ikke kan dividere på null. Skal vi dividere med samme tall på begge sider av kongruenstegnet i en relasjon modulo n, kan vi heller ikke dividere på en nulldivisor til n.

Et tall, a ≠ 0, er en nulldivisor modulo n hvis SFF(a, n) > 1.

En alternativ definisjon av nulldivisorer tillater også verdien 0. 0 sies da å være en triviell nulldivisor. Det motsatte kalles ikke-trivielle nulldivisorer eller ekte nulldivisorer. Med nulldivisorer mener vi på dette nettstedet imidlertid alltid ekte nulldivisorer, det vil si at verdien 0 ikke er tillatt.

Eksempel 7:

Vi ser på uttrykket 18 ≡ 36 (mod 9).

Denne uttrykket er riktig, for både 18 og 36 gir rest 0 modulo 9.

Dividerer vi med 3 på begge sider av kongruenstegnet, får vi

6 ≡ 12 (mod 9)

Dette er ikke riktig. 6 gir rest 6, men 12 gir rest 3, modulo 9.

Dividerer vi med 6 på begge sider av kongruenstegnet, får vi

3 ≡ 6 (mod 9)

Dette er heller ikke riktig. 3 gir rest 3, men 6 gir rest 6, modulo 9.

Men dividerer vi med 2 på begge sider av kongruenstegnet, får vi

9 ≡ 18 (mod 9)

Dette er riktig. Både 9 og 18 gir rest 0 modulo 9.

I eksempel 7 ser vi at det ikke er korrekt å dividere med 3 og 6. Dette fordi 3 og 6 er nulldivisorer modulo 9. Vi har at SFF(3, 9) > 1 og SFF(6, 9) > 1. Det er imidlertid korrekt å dividere med 2, som ikke er nulldivisor modulo 9. SFF(2, 9) = 1.

Imidlertid kan vi dividere med vilkårlige tall hvis vi, når vi dividerer på begge sider med et tall, c, samtidig dividerer modulus, n, med alle nulldivisorene som finnes i c. Dette kan vi gjøre ved å dividere med alle primtallsfaktorene som er felles for n og c. Noe som kan utføres i en enkelt operasjon ved å dividere på produktet av disse faktorene. Dette produktet er det samme som SFF(c, n), slik det er beskrevet i artikkelen om faktorisering.

Regelen for divisjon sier altså at vi i en kongruensrelasjon modulo n kan dividere med et tall, c, på begge sider av kongruenstegnet hvis vi samtidig dividerer n med SFF(c, n):

$\fbox{$\text{Hvis } ac \equiv bc \, (mod \; n), \text{ vil } a \equiv b \, \big(mod \; \frac{\displaystyle n}{\displaystyle SFF(c, n)}\big)$}$

Eksempel 8:

Vi ser på uttrykket 18 ≡ 36 (mod 9) fra eksempel 7 igjen.

Vi har at SFF(3, 9) = 3. Vil vi dividere med 3 på begge sider, må vi samtidig dividere n = 9 med 3. Og vi får

6 ≡ 12 (mod 3)

Dette er riktig. Både 6 og 12 gir rest 0 modulo 3.

Vi har også at SFF(6, 9) = 3. Vil vi dividere med 6 på begge sider, må vi samtidig dividere n = 9 med 3. Og vi får

3 ≡ 6 (mod 3)

Dette er riktig. Både 3 og 6 gir rest 0 modulo 3.

Vi har at SFF(2, 9) = 1. Det betyr at vi ikke trenger å dividere n = 9 med noe, for å dividere med 1 har jo ingen effekt. Og vi får

9 ≡ 18 (mod 9)

Som er riktig, og det samme som i eksempel 7.

Når SFF(c, n) = 1 har vi altså et spesialtilfelle av divisjonsregelen:

$\fbox{$\text{Hvis } ac \equiv bc \, (mod \; n) \text{ og } SFF(c, n) = 1, \text{ vil } a \equiv b \, (mod \; n)$}$

Med andre ord, hvis tallet vi dividerer med ikke har felles faktorer med modulus, kan vi dividere uten å endre modulus.

Oppgave 4:

Vi har 21 ≡ 147 (mod 14). Bruk divisjonsregelen til å dividere med henholdsvis 3 og 7 på begge sider av kongruenstegnet.

Se løsningsforslag

Oppgave 5:

Forkort kongruensrelasjonen 126 ≡ 198 (mod 8) så mye som mulig.
Hint: SFF(126, 198) = 18.

Se løsningsforslag

Potensregelen

Potensregelen sier at vi kan opphøye i en positiv, heltallig eksponent på begge sider av kongruenstegnet.

$\fbox{$\begin{align} \text{Hvis } a &\equiv b \, (mod \; n) \text{ og } k \in \mathbb N \text{, vil }\\
a^k &\equiv b^k \, (mod \; n) \end{align}$}$

En kjapp begrunnelse:

Regelen følger umiddelbart av produktregelen, som sier at acbd (mod n) når ab (mod n) og cd (mod n). For setter vi c = a og d = b, får vi at aabb (mod n), altså a2b2 (mod n). Så kan vi bygge på til a2ab2b (mod n), deretter til a3ab3b (mod n) og fortsette helt til vi kommer til akbk (mod n).

Denne regelen er svært nyttig. Så langt har vi ikke gjort noe vi ikke kunne gjort med funksjonen rest i et regneark eller funksjonen mod i GeoGebra, for eksempel å finne 8 · 9 · 12 (mod 7). Men potensregelen lar oss håndtere tall som er langt høyere enn det disse verktøyene har kapasitet til. Dette skal vi se nøyere på i artikkelen om anvendelser av kongruens.

Eksempel 9:

Vi skal finne det laveste ikke-negative tallet som er kongruent med 2916 (mod 19).

Vi har at

$29 \equiv 10 \, (mod \; 19)$.

Da gir potensregelen at

$29^2 \equiv 10^2 \equiv 100 \equiv 5 \, (mod \; 19)$.

$29^4 \equiv {(29^2)}^2 \equiv 5^2 \equiv 25 \equiv 6 \, (mod \; 19)$.

$29^8 \equiv {(29^4)}^2 \equiv 6^2 \equiv 36 \equiv 17 \, (mod \; 19)$.

$29^{16} \equiv {(29^8)}^2 \equiv 17^2 \equiv 289 \equiv 4 \, (mod \; 19)$.

I neste siste linje kunne vi brukt −2 i stedet for 17, og i siste linje fått en enklere utregning:

$29^{16} \equiv {((29)^8)}^2 \equiv (−2)^2 \equiv 4 \, (mod \; 19)$.

Potensregelen er også sentral når vi skal utlede reglene for delelighet ved hjelp av kongruenser, slik det er beskrevet i artikkelen om kongruensregning.

Det motsatte er imidlertid ikke alltid tilfelle. Fordi om akbk (mod n), trenger ikke ab (mod n). For eksempel er 22 ≡ 42 (mod 4), men 2 ≢ 4 (mod 4). Dette er analogt med at vi alltid kan multiplisere med samme tall på begge sider av kongruenstegnet, men ikke alltid dividere med samme tall.

Additiv invers

algebra-artikkelen om regneregler i algebra introduserte vi invers-begrepet, og sa at en additiv invers til et tall, a, er det tallet som gir 0 når vi adderer det til a. Ved vanlig addisjon vil dette tallet alltid være −a

For eksempel er −3 den additive inversen til 3 fordi 3 + (−3) = 0, og 4 er den additive inversen til −4 fordi −4 + 4 = 0.

Regner vi modulo n, vil imidlertid additiv invers til et tall, a, være tall som gir 0 når vi adderer det til a modulo n. For eksempel er 2 en additiv invers til 4 modulo 6 fordi 2 + 4 ≡ 0 (mod 6). na vil alltid være en additiv invers til a modulo n.

Under ser vi en addisjonstabell modulo 6. Vi ser at parene (0, 0), (1, 5), (2, 4), og (3, 3) er additive inverser modulo 6 fordi disse parene gir 0 i tabellen.

+ 0 1 2 3 4 5
0 0 1 2 3 4 5
1 1 2 3 4 5 0
2 2 3 4 5 0 1
3 3 4 5 0 1 2
4 4 5 0 1 2 3
5 5 0 1 2 3 4

Slike tabeller lager vi enkelt i et regneark. Vi fyller ut en formel i første celle i tabellen, som vist under, og drar den ut til de andre cellene.

Illustrasjon av hvordan en addisjonstabell lages i et regneark

Et tall har uendelig mange additive inverser modulo n. Dersom et tall, b, er en additiv invers modulo n, vil alle tall i samme restklasse, det vi si alle tall som gir samme rest som b ved divisjon med n, være additive inverser. Tallene vil være på formen b + kn, der k er et helt tall.

Eksempel 10:

Alle tall på formen 2 + k · 6 vil være additive inverser til 4 (mod 6). For eksempel

$\begin{align}2 + (−2)6 &= −10 \\
2 + (−1)6 &= −4 \\
2 + 0 \cdot 6 &= 2 \\
2 + 1 \cdot 6 &= 8 \\
2 + 2 \cdot 6 &= 14 \end{align}$

For disse tallene gir

$\begin{align}4 + (−10) \equiv −6 \equiv 0 \, &(mod \; 6) \\
4 + (−4) \equiv 0 \, &(mod \; 6) \\ 
4 + 2 \equiv 6 \equiv 0 \, &(mod \; 6) \\
4 + 8 \equiv 12 \equiv 0 \, &(mod \; 6) \\
4 + 14 \equiv 18 \equiv 0 \, &(mod \; 6) \end{align}$

Som ved vanlig addisjon vil −a alltid være en additiv invers til a.

Oppgave 6:

Lag en addisjonstabell modulo 5.

Se løsningsforslag

Multiplikativ invers

Ved vanlig multiplikasjon er en multiplikativ invers til et tall, a, det tallet som gir 1 når vi multipliserer det med a. For eksempel er den multiplikative inversen til 2 lik ${\large \frac{ 1}{2}}$ og den multiplikative inversen til ${\large \frac{1}{2}}$ er lik 2.

Regner vi modulo n, vil imidlertid en multiplikativ invers til et tall, a, være et tall som gir 1 når vi multipliserer det med a modulo n.

Vi skriver en multiplikativ invers til a som a−1 eller a.

Under ser vi en multiplikasjonstabell modulo 5. Vi ser at parene (1, 1), (2, 3) og (4, 4) er multiplikative inverser modulo 5 fordi disse parene gir 1 i tabellen.

* 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1

Mens et tall alltid har en additiv invers modulo n, er det ikke sikkert det har en multiplikativ invers. Under ser vi en multiplikasjonstabell modulo 6. Vi ser at parene (1, 1) og (5, 5) er multiplikative inverser modulo 6 fordi disse parene gir 1 i tabellen. Vi ser imidlertid at verken 2, 3 eller 4 har multiplikative inverser modulo 6.

* 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 1 2 3 4 5
2 0 2 4 0 2 4
3 0 3 0 3 0 3
4 0 4 2 0 4 2
5 0 5 4 3 2 1

Hvis et tall har en multiplikativ invers, a, har det imidlertid uendelig mange inverser i samme restklasse, på formen a + kn, der k er et heltall.

Eksempel 11:

Vi ser på multiplikative inverser til 3, med modulus henholdsvis 5, 4 og 7.

2 er en multiplikativ invers til 3 (mod 5) fordi 3 · 2 ≡ 6 ≡ 1 (mod 5).

Dette er illustrert med rødt i figuren under. Vi ser at 3 · 2 strekker seg 1 forbi 5.

Alle tall på formen 2 + k · 5 er også multiplikative inverser til 3 (mod 5): … , −8, −3, 2, 7, 12, …

3 er en multiplikativ invers til 3 (mod 4) fordi 3 · 3 ≡ 9 ≡ 1 (mod 4). 3 er altså sin egen multiplikative invers modulo 4.

Dette er illustrert med blått i figuren under. Vi ser at 3 · 3 strekker seg 1 forbi en multippel av 4

Alle tall på formen 3 + k · 4 er også multiplikative inverser til 3 (mod 4): … , −5, −1, 3, 7, 11, …

5 er en multiplikativ invers til 3 (mod 7) fordi 3 · 5 ≡ 15 ≡ 1 (mod 7).

Dette er illustrert med grønt i figuren under. Vi ser at 3 · 5 strekker seg 1 forbi en multippel av 7.

Alle tall på formen 5 + k · 7 er da også multiplikative inverser til 3 (mod 7): … , −9, −2, 5, 12, 19, …

Illustrasjon av multiplikative inverser til 3 modulo henholdsvis 5, 4 og 7

I eksempel 11 fant vi multiplikative inverser til 3 modulo henholdsvis 5, 4 og 7. Men hva om vi ønsket å finne en multiplikativ invers til 3 modulo 6? I figuren over ser vi at linja 3 · 2 = 6 strekker seg 0 forbi 6 og at linja 3 · 3 = 9 strekker seg 3 forbi 6. Prøver vi med 3 · 4 = 12, vil linja strekke seg 0 forbi en multippel av 6, og linja 3 · 5 = 15 vil strekke seg 3 forbi en multippel av 6. Og slik vil det fortsette. Hvis b er et partall, vil 3 · b ≡ 0 (mod 6), og hvis b er et oddetall, vil 3 · b ≡ 3 (mod 6). Vi vil aldri finne en b slik at 3 · b ≡ 1 (mod 6). Det finnes altså ingen multiplikativ invers til 3 modulo 6.

Dette stemmer med det vi så i multiplikasjonstabellen modulo 6. Produkter av 3 hopper mellom 0 og 3 og treffer aldri på 1. Tilsvarende ser vi at produkter av 2 og 4 også følger et mønster som aldri treffer på 1.

Grunnen er at SFF(2, 6), SFF(3, 6) og SFF(4, 6) er større enn 1. Felles faktorer mellom a og n vil alltid føre til et mønster som aldri treffer 1 forbi en multippel av n.

Det er altså slik at et tall, a, bare har multiplikativ invers modulo n hvis a og n ikke har felles faktorer større enn 1:

$\fbox{$\text{Det finnes en } \overline a \text{ slik at } a \cdot \overline a \equiv 1 \, (mod \; n) \text{ hvis og bare hvis } SFF(a, n) = 1$}$

Oppgave 7:

Avgjør om det finnes en multiplikativ invers til a modulo n i eksemplene under. Hvis ja, finn en multiplikativ invers ved prøving og feiling.

      1. a = 2, n = 5
         
      2. a = 3, n = 8
         
      3. a = 4, n = 8

Se løsningsforslag

Ved vanlig regning har alle a ≠ 0 en multiplikativ invers, og den er lett å finne, vi beregner bare $\frac{\displaystyle 1}{\displaystyle a}$. Men når vi regner modulo n, er det altså ikke sikkert at a i det hele tatt har multiplikativ invers, og hvis den har det, vil det aldri være $\frac{\displaystyle 1}{\displaystyle a}$ fordi vi bare opererer med hele tall. I oppgave 7 har vi funnet en multiplikativ invers ved prøving og feiling, men hvis vi arbeider med store tall kan prøving og feiling bli veldig arbeidskrevende.

En systematisk metode å finne en multiplikativ invers på er Euklids utvidede algoritme, den vil bli gjennomgått her etter hvert.

Dette nettstedet har en app som finner multiplikative inverser ved hjelp av Euklids utvidede algoritme. Hvis du der huker av for «Vis utregning», lister appen opp trinnene i utregningen.

En liste over multiplikative inverser modulo n for n mellom 2 og 13 er vist under.

n = 2
(1, 1)
n = 3
(1, 1), (2, 2)
n = 4
(1, 1), (3, 3)
     
n = 5
(1, 1), (2, 3), (3, 2), (4, 4)
 
n = 6
(1, 1), (5, 5)
 
n = 7
(1, 1), (2, 4), (3, 5), (4, 2),
(5, 3), (6, 6)
     
n = 8
(1, 1), (3, 3), (5, 5), (7, 7)
 
n = 9
(1, 1), (2, 5), (4, 7), (5, 2),
(7, 4), (8, 8)
n = 10
(1, 1), (3, 7), (7, 3), (9, 9)
 
     
n = 11
(1, 1), (2, 6), (3, 4), (4, 3),
(5, 9), (6, 2), (7, 8), (8, 7),
(9, 5), (10, 10)
n = 12
(1, 1), (5, 5), (7, 7), (11, 11)
 
 
n = 13
(1, 1), (2, 7), (3, 9), (4, 10),
(5, 8), (6, 11), (7, 2), (8, 5),
(9, 3), (10, 4), (11, 6), (12, 12)

Vi ser at (1, 1) alltid er multiplikative inverser modulo n. Det er fordi 1 · 1 ≡ 1 (mod n), uavhengig av n. Vi ser også at (– 1, – 1) alltid er multiplikative inverser modulo n, for eksempel at (10, 10) er multiplikative inverser modulo 11, og (11, 11) er multiplikative inverser modulo 12. Vi har at (n – 1) · (n – 1) = n2 – 2n + 1, som kan skrives som (n – 2)n + 1. Siden n – 2 er et helt tall, er (n – 2)n et heltallig multiplum av n, og følgelig kongruent med 0 modulo n. (n – 2)n + 1 blir følgelig kongruent med 1 modulo n. Så (n – 1) · (n – 1) ≡ 1 (mod n), uavhengig av n.

Kilder

    • Rosen, Kenneth H. (1984). Elementary Number Theory and Its Applications. Addison-Wesley.
    • Rinvold, A. R. (2009). Visuelle perspektiv. Tallteori. Caspar Forlag.
    • Petersen, V. B., Tvete, K. S. (2013). I tallkongruensenes verden. Caspar Forlag.
    • Gustavsen, T.S., Hinna, T.R.C., Borge, I.C., Andersen, P.S. (2014). QED 5-10, bind 2. Cappelen Damm A/S.

Kongruens

Regning modulo n

Eksempel 1:

La oss si at vi tar et tog som bruker 7 timer fra Oslo til Trondheim, og vil vi regne ut når vi er framme hvis vi starter klokka 11. Og det er jo lett, vi adderer bare antall timer vi bruker på turen til klokkeslettet vi starter, og finner ut at vi er framme klokka 11 + 7 = 18. Men hva om vi starter klokka 23? Bruker vi samme teknikk til å regne ut når vi er framme, får vi 23 + 7 = 30. Og det er jo ikke et gyldig klokkeslett. Problemet er at vi ikke har tatt hensyn til at klokkeslett settes tilbake fra 24 til 0 når vi passerer midnatt. Så riktig svar blir 23 + 7 − 24 = 06. Tar en togreise 31 timer og vi starter klokka 23, passerer klokka midnatt to ganger før vi er framme, så vi er framme klokka 23 + 31 − 2 · 24 = 06.

At vi går tilbake til 0 når hver gang vi kommer til 24, kalles å regne modulo 24. På klokka regnes timer modulo 24, mens minutter og sekunder regnes modulo 60. Ukedagene nummereres modulo 7 og månedene modulo 12. Tripptellere på eldre biler regner gjerne modulo 100 000, det vil si at etter 99 999 følger 0. Vinkler regnes gjerne modulo 360. Y2k-krisa nyttårsaften i 1999 oppsto fordi noen eldre datamaskiner daterte modulo 100, slik at år 2000 ville bli regnet som år 0.

Begrepet kongruens

I eksempel 1 så vi at hvis vi starter en togreise klokka 23, er vi framme klokka 06 både hvis turen tar 7 og 31 timer. Vi er også framme klokka 06 hvis turen tar 55 eller 79 timer. Det er fordi tallene 7, 31, 55 og 79 gir samme rest når de divideres på 24. Vi sier at de er kongruente modulo 24. I artikkelen om delelighet ble vi kjent med divisjonsalgoritmen, som sier at et heltall, a, på en unik måte kan skrives som en kombinasjon av andre heltall: a = bq + r. Lar vi a være togturens lengde og b døgnets lengde på 24 timer, får vi

$\begin{align}
7 &= 0 + 7 \\
31 &= 24 + 7 \\
55 &= 48 + 7 \\
79 &= 72 + 7
\end{align}$

Resten, r, er i alle tilfeller 7. Dette er illustrert under, der vi tenker oss at vi beveger oss rundt en sirkel med 24 delestreker.

Illustrasjon av rest 7 ved addisjon modulo 24

At to tall, a og b, er kongruente modulo n skriver vi som ab (mod n). For eksempel er 31 ≡ 55 (mod 24).

At to tall, a og b, ikke er kongruente modulo n skriver vi som ab (mod n). For eksempel er 31 ≢ 54 (mod 24).

Å regne med kongruenser kan være nyttig i mange sammenhenger. Vi starter med å gjøre det litt klarere hva kongruens er.

At ab (mod n) betyr som nevnt at a og b gir samme rest når de divideres med n. En måte å tenke seg dette på er at både a og b strekker seg like langt forbi heltallige multipler av n. For eksempel strekker 31 seg 7 forbi 24, og 55 strekker seg 7 forbi 2 ganger 24, som illustrert med sirkelen over. Derfor er 31 og 55 kongruente modulo 24. Men 54 strekker seg bare 6 forbi 2 ganger 24, derfor er ikke 31 og 54 kongruente modulo 24.

La oss gjøre noen subtraksjonsstykker med tallene 7, 31, 55 og 79, som vi har sagt er kongruente modulo 24.

$\begin{align}
79 − 55 &= 24 \\
79 − 31 &= 48 \\
79 − 7 &= 72 \\
55 − 31 &= 24 \\
55 − 7 &= 48 \\
31 − 7 &= 24 \end{align}$

Vi ser at vi i alle tilfeller ender opp med heltallige multipler av 24. Det er fordi resten på 7 alltid forsvinner i subtraksjonen. For eksempel er 79 − 31 = (72 + 7) − (24 + 7) = 72 − 24 + (7 − 7) = 72 − 24 + 0 = 48.

Hvis vi subtraherer to tall som ikke har samme rest modulo 24, får vi ikke et tall som er en multippel av 24. For eksempel er 54 − 31 = (48 + 6) − (24 + 7) = 48 − 24 +(6 − 7) = 48 − 24 − 1 = 23.

Nettopp dette er en definisjon av kongruens. To tall er kongruente modulo n hvis differansen av tallene er en heltallig multippel av n, eller sagt på en annen måte, at n går opp i differansen av tallene:

$\fbox{$a \equiv b \, (mod \; n) \text{ hvis } n \mid (a − b)$}$

Eksempel 2:

Vi skal avgjøre om påstanden 7 ≡ 1 (mod 3) er riktig.

Her får vi a − b = 7 − 1 = 6. Siden n = 3 | 6, er påstanden riktig.

Oppgave 1:

Avgjør om følgende påstander er riktige:

      1. 65 ≡ 17 (mod 12)
         
      2. −12 ≡ 18 (mod 5)
         
      3. 42 ≡ 27 (mod 7)

Se løsningsforslag

En annen måte å definere kongruens på, er si at to tall er kongruente modulo n hvis vi kan komme fra det ene tallet til det andre ved å addere en heltallig multippel av n:

$\fbox{$a \equiv b \, (mod \; n) \text{ hvis det finnes et heltall, $k$, slik at } a = b + kn$}$

Eksempel 3:

79 ≡ 7 (mod 24), fordi 79 = 7 + 3 · 24.

31 ≡ 55 (mod 24), fordi 31 = 55 + (−1)24.

Og, som tidligere nevnt, kan vi definere kongruens ved hjelp av rest:

$\fbox{$a \equiv b \, (mod \; n) \text{ hvis $a$ og $b$ gir samme rest ved divisjon med } n$}$

I algebra-artikkelen om regneregler i algebra er «>», «<» og «=» nevnt som eksempler på relasjoner. Kongruens, «≡», er også en relasjon. Denne relasjonen er refleksiv, symmetrisk og transitiv:

$\fbox{$\begin{align} &a \equiv a \, (mod \; n) \\
&\text{Hvis } a \equiv b \, (mod \; n) \text{, er } b \equiv a \, (mod \; n) \\
&\text{Hvis } a \equiv b \, (mod \; n) \text{ og } b \equiv c \, (mod \; n) \text{, er } a \equiv c \, (mod \; n) \end{align}$}$

Modellering med kongruenser

Når vi skal bruke kongruensregning til å løse problemer, er det oftest ikke slik at problemene er ferdig stilt opp som kongruenser. Vi må selv tolke situasjonene og formulere dem matematisk. Dette er helt tilsvarende det vi gjør i mange andre sammenhenger, som for eksempel å formulere «Tre kg appelsiner koster tjuefire kroner når prisen per kg er åtte kroner», som 3 · 8 = 24. For de fleste av oss er slike eksempler enkle, fordi metodene er så innarbeidet. Men med kongruens som et nytt begrep, er det mer krevende å formulere problemer.

Eksempel 4:

Vi skal formulere følgende påstander som kongruenser:

      1. Tallet 156 er delelig med 12.
        Det betyr at 156 delt på 12 gir rest 0. Med andre ord er 156 kongruent med 0 modulo 12:
        156 ≡ 0 (mod 12).
         
      2. Om 16 dager er det samme ukedag som om 2 dager.
        Det er 7 dager i uka. At 16 og 2 dager gir samme ukedag, betyr at vi får samme rest når vi dividerer disse tallene med 7. Siden de gir samme rest, er tallene kongruente modulo 7:
        16 ≡ 2 (mod 7).
         
      3. Tallet 356 har samme siste siffer som tallet 126.
        At tallene har samme siste siffer betyr at de gir samme rest når de blir dividert med 10. Siden de gir samme rest, er tallene kongruente modulo 10:
        356 ≡ 126 (mod 10).

Oppgave 2:

Formuler påstandene under som kongruenser. Begrunn svarene.

      1. Tallet 37 gir samme rest ved divisjon med 8 som tallet 69.
         
      2. Om 15 timer er klokka det samme som for 9 timer siden.
         
      3. Tallet 15 er et oddetall.

Se løsningsforslag

Eksempel 5:

En friidrettsbane er 400 meter lang, med en målstrek. Vi skal med en kongruens beskrive at 50 meter før målstreken er det samme som 350 meter etter målstreken.

At banen er 400 meter lang, betyr at alle lengder som gir samme rest dividert med 400 er like langt unna målstreken. Med andre ord er disse lengdene kongruente modulo 400. Så vi får:
−50 ≡ 350 (mod 400).

Restklasser

I artikkelen om delelighet beskrev vi divisjonsalgoritmen, som sier at et heltall, a, på en unik måte kan skrives som en kombinasjon av andre heltall, a = bq + r. Her er r resten vi får når vi heltallsdividerer ab, og vi har at 0 ≤ r < b. I eksempel 1 på denne siden brukte vi divisjonsalgoritmen på tallene fra a = 0 til a = 10 med b = 4, og fikk

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

Vi har lært at to tall er kongruente modulo n hvis n går opp i differansen av tallene. Studerer vi tallene i lista over, ser vi at alle tallene som gir samme rest er kongruente modulo 4, fordi 4 går opp i alle differanser av dem: 0 ≡ 4 ≡ 8 (mod 4), 1 ≡ 5 ≡ 9 (mod 4), 2 ≡ 6 ≡ 10 (mod 4) og 3 ≡ 7 (mod 4). Disse fire gruppene med tall kaller vi restklassene modulo 4. Det finnes altså 4 restklasser modulo 4. Generelt vil det finnes n restklasser modulo n. Disse består av tallene som gir en rest på henholdsvis 0, 1, 2, … , n − 1 ved heltallsdivisjon med n.

Restklasser kalles også kongruensklasser fordi alle tallene i samme klasse er kongruente.

For å finne restklassen kan vi bruke kommandoen mod i GeoGebra og =rest i Excel. For eksempel mod(10, 4) eller = rest(10; 4) for å finne restklassen til 10 modulo 4, som er 2.

Det er ikke vanskelig å finne eksempler på bruk av restklasser i hverdagen. Når læreren i en gymtime deler elevene inn i fire grupper ved å telle dem 1, 2, 3, 4, 1, 2, 3, 4, … , er det en oppdeling i restklasser. Selv om restklassene modulo 4 egentlig er 0, 1, 2, 3, er prinsippet det samme. Navnet spiller ingen rolle, de kunne like gjerne vært delt inn i gruppe «grønn», «gul», «rød» og «blå». Hvis antall elever ikke er delelig på 4, vil det bli for få elever i en av gruppene. Det er da med andre ord ikke like mange elementer i alle restklassene.

En kalender er et annet eksempel. Her står tallene i samme restklasse modulo 7 pent under hverandre i kolonner. 1, 8, 15, 22 og 29, for eksempel. Alle disse tallene er kongruente med 1 modulo 7. Grunnen til at modulus er 7, er at det er 7 dager i uka.

Bildet under viser kalenderen for februar og mars 2017.

Illustrasjon av restklasser med kalender

Vi ser at det i februar er 4 datoer i hver kolonne, altså i 4 hver restklasse. Men i mars er det fire kolonner med 4 datoer og tre med 5. Det er fordi det er 28 dager i februar, og 28 ≡ 0 (mod 7), men det er 31 dager i mars, og 31 ≡ 3 (mod 7).

Oppgave 3:

I tabellen under tilhører alle tall i samme kolonne samme restklasse. Hva er modulus?

1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18

Se løsningsforslag

Det er ikke noe i veien for å inkludere negative tall i en oversikt over restklasser. I tabellen under er det lagt til to rader øverst i tabellen fra oppgave 3:

−11 −10 −9 −8 −7 −6
−5 −4 −3 −2 −1 0
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18

Negative tall betyr at vi i periodiske fenomener kan gå både forover og bakover. Med klokka som eksempel betyr for eksempel −7 ≡ 5 (mod 12) at ei analog klokke vil vise det samme når vi stiller den 7 timer tilbake som når vi stiller den 5 timer fram.

Kilder

    • Rosen, Kenneth H. (1984). Elementary Number Theory and Its Applications. Addison-Wesley.
    • Rinvold, A. R. (2009). Visuelle perspektivTallteori. Caspar Forlag.
    • Petersen, V. B., Tvete, K. S. (2013). I tallkongruensenes verden. Caspar Forlag.
    • Gustavsen, T.S., Hinna, T.R.C., Borge, I.C., Andersen, P.S. (2014). QED 5-10, bind 2. Cappelen Damm A/S.

Faktorisering

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

Primtallsfaktorisering

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

Fermats faktoriseringsmetode

Fermats faktoriseringsmetode, oppfunnet av matematikeren Pierre de Fermat, baserer seg på 3. kvadratsetning, altså at a2b2 = (a + b)(ab). Et heltall som kan skrives som en differanse av to kvadrattall, a2 og 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 vi får et kvadrattall. Hvis ikke, prøver vi a + 1 og gjentar prosessen inntil vi finner et kvadrattall. Hvis vi ender opp med at n = n · 1, er n et primtall.

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

Eksempel 1:

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

Vi får b2 = (11)2 − 119 = 121 − 119 = 2.

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

Vi får b2 = (12)2 − 119 = 144 − 119 = 25.

25 er et kvadrattall, 52.

Vi kan derved skrive 119 som en differanse av to kvadrattall, 122 − 52, og følgelig kan 119 faktoriseres som (12 + 5)(12 − 5) = 17 · 7.

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

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

Vi får b2 = (3)2 − 7 = 9 − 7 = 2.

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

Vi får b2 = (4)2 − 7 = 16 − 7 = 9.

9 er et kvadrattall, 32.

Vi kan derved skrive 7 som en differanse av to kvadrattall, 92 − 42, og følgelig kan 7 faktoriseres som (4+3)(4−3) = 17 · 7. 7 er følgelig et primtall.

Når det gjelder 17, starter vi med $a = \lceil \sqrt{17} \rceil = 5$, men må opp til a = 9 før vi finner et kvadrattall, og ser at 17 kan faktoriseres som (9 + 8)(9 − 8) = 17 · 1. 17, og følgelig er et primtall.

Oppgave 1:

Bruk Fermats metode til å faktorisere 189.

Se løsningsforslag

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

Fermats metode vil ikke kunne faktorisere tall som inneholder primtallsfaktoren 2 nøyaktig én gang, for eksempel 30 = 2 · 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 det høyeste primtallet som må sjekkes lik 3, og primtallsfaktorer opp til 3 har vi allerede dividert ut, så vi slår fast at 17 er et primtall.

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

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

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

Felles faktorer

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

Eksempel 4:

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

32 har faktorene ±1, ±2, ±4, ±8, ±16, ±32.

Felles faktorer for 24 og 32 er derved ±1, ±2, ±4, ±8.

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

Største felles faktor

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

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

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

Eksempel 5:

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

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

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

Eksempel 6:

Vi ser på positive faktorer i 8 og 12.

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

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

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

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

Illustrasjon av faktorer og felles faktorer i 8 og 12

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

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

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

Eksempel 7:

Vi skal finne SFF(4, 12).

Siden 4 | 2, blir svaret |4| = 4.

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

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

±1 går opp i alle heltall.

Innbyrdes primiske tall

To heltall, a og b, sies å være innbyrdes primiske hvis de ikke har andre felles faktorer enn ±1, det vil si at SFF(a, b) = 1. Det betyr imidlertid ikke at a eller b er primtall. Andre betegnelser for det samme er koprimisk og relativt primisk.

Eksempel 8:

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

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

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

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

Eksempel 9:

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

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

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

Eksempel 10:

I eksempel 2 fant vi at SFF(24, 32) = 8. Da er for eksempel SFF(24 + 32, 32) = SFF(56, 32) = 8 og SFF(24 + 3 · 32, 32) = SFF(120, 32) = 8.

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

Eksempel 11:

Vi skal finne SFF(30, 72). Dette vil være det samme som SFF(30, 72 − 2 · 30) = SFF(30, 12) = SFF(30 − 2 · 12, 12) = SFF(6, 12) = SFF(6, 12 − 6) = SFF(6, 6) = 6.

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

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

Eksempel 12:

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

Eller

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

Finne største felles faktor

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

Eksempel 13:

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

Oppgave 4:

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

Se løsningsforslag

Finne største felles faktor i GeoGebra og regneark

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

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

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

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

Euklids algoritme for å finne største felles faktor

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

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

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

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

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

Euklids algoritme baserer seg på å gjentatte ganger bytte a og b med b og r i divisjonsalgoritmen inntil r = 0. SFF vil da være den verdien a har når r = 0. Algoritmen forutsetter egentlig at a ≥ 0, men siden SFF er uavhengig av tallenes fortegn, kan vi ved å operere på absoluttverdier også bruke algoritmen på negative tall. Algoritmen er oppkalt etter matematikeren Euklid fra Alexandria.

Eksempel 14:

Vi skal finne SFF(63, 30).

Vi har da a = 63 og b = 30.

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

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

Vi har da a = 30 og b = 3.

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

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

Vi har da at a = 3 og r = 0.

Så SFF(63, 30) = 3.

Eksempel 15:

Vi skal finne SFF(252, 198).

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

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

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

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

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

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

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

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

Vi har da at a = 18 og r = 0.

Så SFF(252, 198) = 18.

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

Oppgave 5:

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

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

Hvis t er en faktor i a og t er en faktor i b, vil t være en faktor i alle lineære kombinasjoner av a og b.

Vi har altså likningen a = qb + r.

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

Vi bytter så om på leddene og skriver likningen som r = aqb.

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

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

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

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

a = q1b + r1 , der 0 ≤ r1 < b.

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

b = q2r1 + r2, der 0 ≤ r2 < r1.

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

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

Eksempel 16:

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

I første trinn får vi 50 = 15 · 3 + 5.

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

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 16 fant vi størrelsen på rutene i løpet av to trinn i Euklids algoritme. Ofte vil vi måtte bruke flere trinn, hvert trinn vil da representere en inndeling i mindre ruter.

Hvor mange trinn vi må gå gjennom med Euklids algoritme, vil variere. Hvis b | a, vil vi bare trenge ett trinn fordi r da allerede i første trinn vil bli null. Får vi i hvert trinn q = 1, vil tallverdiene bli redusert langsomt, og det kan hende vi vil trenge mange trinn. Dette vil være tilfelle hvis vi skal finne SFF til to etterfølgende fibonaccitall. Dersom 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.

Minste felles multiplum

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

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

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

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

Eksempel 17:

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

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

Illustrasjon av at SFF(4, 6) = 12

Begge linjene vil videre treffe i alle multipler av 12.

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

Finne minste felles multiplum

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

Eksempel 18:

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

Eksempel 19:

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

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

Eksempel 20:

Vi skal finne MFM(60, 24). Vi har at 60 = 22 · 31 · 51 og 24 = 23 · 31. Vi ser at høyeste potens av 2 er 3, og høyeste potens av både 3 og 5 er 1. Så MFM(60, 24) = 23 · 31· 51 = 120.

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

Eksempel 21:

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

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

Oppgave 6:

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

Se løsningsforslag

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

Eksempel 22:

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

Alternativt: 20 = 22 · 51 og 21 = 31 · 71. Multipliserer vi høyeste potens av alle faktorene, får vi 22 · 31 · 51 · 71 = 420.

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

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

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

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

Eksempel 23:

Vi skal finne MFM(252, 198).

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

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

Oppgave 7:

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

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

Eller

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

Finne minste felles multiplum i GeoGebra og regneark

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

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

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

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

Kilder

  • Rosen, Kenneth H. (1984). Elementary Number Theory and Its Applications. Addison-Wesley.
  • Breiteig, T. (2007). Bak tallene. Innføring i tallteori. Kompendium, Universitetet i Agder.
  • Rinvold, R. (2009). Tallteori. Caspar forlag.
  • Gustavsen, TS, Hinna, K.R.C., Borge, I.C., Andersen P.S. (2014). QED 5-10, bind 2. Høyskoleforlaget

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

Og det er umulig å dele et primtall opp i mindre blokker med like mange elementer i hver. Derfor 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. Begrunn svaret.

      1. 3 går opp i 900. Da går 3 opp i 45.
         
      2. 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 september 2023 lik 282 589 933 − 1. Dette tallet har 24 862 048 sifre, skrev vi det ut med ett siffer per centimeter, ville det bli over 248 kilometer langt. Tallet ble registret 21. desember 2018. Tidligere rekorder stammer fra mars 2018, januar 2016 og mai 2013. 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 september 2023 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: Tredje kvadratsetning 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 september 2023 lik 282 589 933 − 1, og det er også det største kjente primtallet, som nevnt tidligere. Alle de største primtallene som er kjent per september 2023 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 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