Innhold
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 a ≡ b (mod 3), fordi 3 | (7 − 4) = 3. I figuren under ser vi at a ≡ b (mod 3 fordi a og b strekker seg like langt, nemlig 1, forbi heltallige multipler av 3.
Tilsvarende er c ≡ d (mod 3), fordi 3 | (8 − 5) = 3. I figuren under ser vi at c ≡ d (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 + c ≡ b + d (mod 3) fordi a + c og b + d strekker seg like langt, nemlig 0, forbi heltallige multipler av 3.
Vi har at a ≡ b (mod 7). Avgjør om a + c ≡ b + d (mod 7) når
1) c = 5, d = 12
2) c = 8, d = 16
Vi har altså at a + c ≡ b + d (mod n) når a ≡ b (mod n) og c ≡ 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 ≡ 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).
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å.
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)$.
Finn det laveste, ikke-negative tallet som er kongruent med 243 modulo 13.
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.
Vi har 21 ≡ 147 (mod 14). Bruk divisjonsregelen til å dividere med henholdsvis 3 og 7 på begge sider av kongruenstegnet.
Forkort kongruensrelasjonen 126 ≡ 198 (mod 8) så mye som mulig.
Hint: SFF(126, 198) = 18.
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 ≡ bd (mod n) når a ≡ b (mod n) og c ≡ d (mod n). For setter vi c = a og d = b, får vi at aa ≡ bb (mod n), altså a2 ≡ b2 (mod n). Så kan vi bygge på til a2a ≡ b2b (mod n), deretter til a3a ≡ b3b (mod n) og fortsette helt til vi kommer til ak ≡ bk (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 ak ≡ bk (mod n), trenger ikke a ≡ b (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
I 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). 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.
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.
Lag en addisjonstabell modulo 5.
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, …
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$}$
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.
-
-
- a = 2, n = 5
- a = 3, n = 8
- a = 4, n = 8
- a = 2, n = 5
-
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 (n – 1, n – 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.