Kongruens

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 = 6$. 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 \cdot 24 = 6$.

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å biler regner gjerne modulo 100 000, det vil si at etter 99 999 følger 0. Vinkler kan regnes modulo 360. Y2k-krisa nyttårsaften i 1999 oppsto fordi noen eldre datamaskiner daterte modulo 100, slik at år 2000 ville bli regnet som tidligere enn år 1999.

I eksempel 1 så vi at hvis vi starter en togreise klokka 23, er vi framme klokka 6 både hvis turen tar 7 og 31 timer. Vi er også framme klokka 6 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 lærte vi 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$, 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 $a \equiv b \, (mod \; n)$. For eksempel er $31 \equiv 55 \, (mod \; 24)$.

At to tall, $a$ og $b$, ikke er kongruente modulo $n$ skriver vi som $a \not \equiv b \, (mod \; n)$. For eksempel er $31 \not \equiv 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 $a \equiv b \, (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 \cdot 24$, som illustrert med sirkelen over. Derfor er $31$ og $55$ kongruente modulo $24$. Men $54$ strekker seg bare $6$ forbi $2 \cdot 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 et multippel av 24. For eksempel er 54 – 31 = (48 + 6) – (24 + 7) = 48 – 24 +(6 – 7) = 48 – 24 -1 = 23.

Nettopp dette er definisjonen på kongruens. To tall er kongruente modulo $n$ hvis differansen av tallene er et 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 $-2 \equiv 1 \, (mod \; 3)$ er riktig.

Her får vi $a – b = -2 – 1 = -3$. Siden $n = 3 \mid -3$, er påstanden riktig.

Oppgave 1:

Avgjør om følgende påstander er riktige:

  1. $65 \equiv 17 \, (mod \; 12)$
     
  2. $-12 \equiv 18 \, (mod \; 5)$
     
  3. $42 \equiv 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 et 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 \equiv 7 \, (mod \; 24)$, fordi $79 = 7 + 3 \cdot 24$

$31 \equiv 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, "$\equiv$", er også en relasjon. Denne relasjonen er refleksiv, symmetrisk og transitiv:

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

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 kilo appelsiner koster tjuefire kroner når prisen per kilo er åtte kroner", som $3 \cdot 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 \equiv 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 \equiv 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 \equiv 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 \equiv 350\, (mod \; 400)$.

Restklasser

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$. Her er $r$ resten vi får når vi heltallsdividerer $a$$b$, og vi har at $0 \le r < b$. I eksempel 15 i den samme artikkelen brukte vi divisjonsalgoritmen på tallene fra $a = 0$ til $a = 10$ med $b = 4$, og fikk

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

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 \equiv 4 \equiv 8  \, (mod \; 4)$, $1 \equiv 5 \equiv 9 \, (mod \; 4)$$2 \equiv 6 \equiv 10 \, (mod \; 4)$ og $3 \equiv 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, \dots, n – 1$ ved heltallsdivisjon med $n$.

Restklasser kalles også kongruensklasser fordi alle tallene i samme klasse er kongruente.

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 eller flere av gruppene. Det er 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 \equiv 0 \, (mod \; 7)$, men det er 31 dager i mars, og $31 \equiv 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 at $-7 \equiv 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.
  • Wikipedia