Kongruens, regneregler


Addisjonsregelen, subtraksjonsregelen og multiplikasjonsregelen

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 $r_1$. Tilsvarende gjelder for $c$ og $d$, la oss kalle denne lengden $r_2$. Da vil både $a + c$ og $b + d$ strekke seg $r_1 + r_2$ 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 $a \equiv b \, (mod \; 3)$, fordi $3 \mid (7 – 4) = 3$. I figuren under ser vi at $a \equiv b \, (mod \; 3)$ fordi $a$ og $b$ strekker seg like langt, nemlig $1$, forbi heltallige multipler av $3$.

Tilsvarende er $c \equiv d \, (mod \; 3)$, fordi $3 \mid (8 – 5) = 3$. I figuren under ser vi at $c \equiv d \, (mod \; 3)$ fordi $c$ og $d$ strekker seg like langt, nemlig $2$, forbi heltallige multipler av $3$.

Da skal $a + c = 15 \equiv b + d = 9 \, (mod \; 3)$. Og i figuren under ser vi at $a + c \equiv b + 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 $a \equiv b \, (mod \; 7)$. Avgjør om $a + c \equiv b + d \, (mod \; 7)$ når

$c = 5, \, d = 12$

$c = 8, \, d = 16$

Se løsningsforslag

Vi har altså at $a + c \equiv b + d \, (mod \; n)$ når $a \equiv b \, (mod \; n)$ og $c \equiv d \, (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 \equiv 2 \, (mod \; 7)$ og $29 \equiv 1 \, (mod \; 7)$. Vi får derfor at

$30 + 29  \equiv 2 + 1 \equiv 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 \equiv 3 + 2 \equiv 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 \cdot 9 \cdot 12 \equiv 1 \cdot 2 \cdot 5 \equiv 10 \equiv 3 \, (mod \; 7)$.

Oppgave 2:

Du vet at $365 \equiv 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

Når vi har store tall, er det imidlertid ikke alltid så lett å finne mindre, kongruente tall. Vi ser enkelt at $15 \equiv 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 \equiv 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 \, 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)$.

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

$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

Divisjonsregelen

Vi kan altså addere, subtrahere og multiplisere med kongruente tall på begge sider av kongruenstegnet. Det samme gjelder imidlertid ikke å dividere, vi kan ikke uten videre dividere med samme tall på begge sider kongruenstegnet, slik vi kan i en vanlig likning.

Eksempel 7:

Vi ser på uttrykket $18 \equiv 36 \, (mod \; 9)$. Dette er riktig. Både $18$ og $36$ gir rest $0$ modulo $9$.

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

$9 \equiv 18 \, (mod \; 9)$. Dette er fremdeles riktig. Både $9$ og $18$ gir rest $0$ modulo $9$.

Men dividerer vi i stedet med $3$ på begge sider av kongruenstegnet, får vi

$\color{red}{6 \equiv 12 \, (mod \; 9)}$. Dette er ikke riktig. $6$ gir rest $6$, men $12$ gir rest $3$ modulo $9$.

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

$\color{red}{3 \equiv 6 \, (mod \; 9)}$. Dette er heller ikke riktig. $3$ gir rest $3$, men $6$ gir rest $6$ modulo $9$.

Regelen for divisjon sier 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{ og } d = SFF(c, n), \text{ vil } a \equiv b \, (mod \; \frac{\displaystyle n}{\displaystyle d})$}$

Eksempel 8:

Vi ser på uttrykket $18 \equiv 36 \, (mod \; 9)$ fra eksempel 7 igjen.

Vi har at $SFF(2, 9) = 1$. Vi kan derfor dividere med $2$ på begge sider hvis vi samtidig dividerer $9$ med $1$. Og å dividere med $1$ betyr jo å gjøre ingenting. Derfor var divisjonen riktig.

Men 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 \equiv 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 \equiv 6 \, (mod \; 3)$. Dette er riktig. Både $3$ og $6$ gir rest $0$ modulo $3$.

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 \equiv 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 \equiv 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 $ac \equiv bd \, (mod \; n)$ når $a \equiv b \, (mod \; n)$  og  $c \equiv d \, (mod \; n)$. For setter vi $c = a$ og $d = b$, får vi at $aa \equiv bb \, (mod \; n)$, altså $a^2 \equiv b^2 \, (mod \; n)$. Så kan vi bygge på til $a^2a \equiv b^2b \, (mod \; n)$, deretter til $a^3a \equiv b^3b \, (mod \; n)$ og fortsette helt til vi kommer til $a^k \equiv b^k \, (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 \cdot 9 \cdot 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 $29^{16} \, (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 delelighetsreglene i artikkelen om kongruensregning.

Det motsatte er imidlertid ikke alltid tilfelle. Fordi om $a^k \equiv b^k \, (mod \; n)$, trenger ikke $a \equiv b \, (mod \; n)$. For eksempel er $2^2 \equiv 4^2 \, (mod \; 4)$, men $2 \not \equiv 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 \equiv 0 \, (mod \; 6)$. $n – a$ 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 \cdot 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 $\frac{\displaystyle 1}{\displaystyle 2}$ og den multiplikative inversen til $\frac{\displaystyle 1}{\displaystyle 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 $\overline 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$. i 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, $\overline a$, har det imidlertid uendelig mange i samme restklasse, på formen $\overline a + kn$, der $k$ er et heltall.

Eksempel 11:

$2$ er en multiplikativ invers til $3 \, (mod \; 5)$ fordi $3 \cdot 2 = 6 \equiv 1 \, (mod \; 5)$.

Dette er illustrert med rødt i figuren under. Vi ser at $3 \cdot 2$ strekker seg $1$ forbi $5$.

Alle tall på formen $2 + k \cdot 5$ er også multiplikative inverser til $3 \, (mod \; 5)$: $\dots -8, -3, 2, 7, 12, \dots$

$3$ er en multiplikativ invers til $3 \, (mod \; 4)$ fordi $3 \cdot 3 = 9 \equiv 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 \cdot 3$ strekker seg $1$ forbi et multippel av $4$.

Alle tall på formen $3 + k \cdot 4$ er også multiplikative inverser til $3 \, (mod \; 4)$: $\dots -5, -1, 3, 7, 11, \dots$

$5$ er en multiplikativ invers til $3 \, (mod \; 7)$ fordi $3 \cdot 5 = 15 \equiv 1 \, (mod \; 7)$.

Dette er illustrert med grønt i figuren under. Vi ser at $3 \cdot 5$ strekker seg $1$ forbi et multippel av $7$.

Alle tall på formen $5 + k \cdot 7$ er også multiplikative inverser til $3 \, (mod \; 7)$: $\dots -9, -2, 5, 12, 19, \dots$

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 \cdot 2 = 6$ strekker seg $0$ forbi $6$ og at linja $3 \cdot 3$ strekker seg $3$ forbi $6$. Prøver vi med $3 \cdot 4 = 12$, vil linja strekke seg $0$ forbi et multippel av $6$, og linja $3 \cdot 5$ vil strekke seg $3$ forbi et multippel av $6$. Og slik vil det fortsette. Hvis $b$ er et partall, vil $3 \cdot b \equiv 0 \, (mod \; 6)$, og hvis $b$ er et oddetall, vil $3 \cdot b \equiv 3 \, (mod \; 6)$. Vi vil aldri finne en $b$ slik at $3 \cdot b \equiv 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 et 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 \ne 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.

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.
  • Wikipedia