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 blir 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.
At to tall, a og b, er kongruente modulo n skriver vi som a ≡ b (mod n). For eksempel er 31 ≡ 55 (mod 24).
At to tall, a og b, ikke er kongruente modulo n skriver vi som a ≢ b (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 a ≡ 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 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.
Avgjør om følgende påstander er riktige:
-
-
- 65 ≡ 17 (mod 12)
- −12 ≡ 18 (mod 5)
- 42 ≡ 27 (mod 7)
- 65 ≡ 17 (mod 12)
-
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 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:
-
-
- 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).
- 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).
- 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).
- Tallet 156 er delelig med 12.
-
Formuler påstandene under som kongruenser. Begrunn svarene.
-
-
- Tallet 37 gir samme rest ved divisjon med 8 som tallet 69.
- Om 15 timer er klokka det samme som for 9 timer siden.
- Tallet 15 er et oddetall.
- Tallet 37 gir samme rest ved divisjon med 8 som tallet 69.
-
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 beskriver 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 a på b, 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.
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).
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 |
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 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.