Kongruensräkning

Denna sats säger alltså att vi kan byta ut kongruenta tal mot varandra i våra beräkningar. Låt oss se hur detta går till i några exempel.

Här bevisar vi räkneregel 1, ta exempel på alla tre reglerna och lämna bevisen för räkneregel 2 & 3 som övning.

Räkneregel 1 - Addition bevis

Regeln 1 säger att:
$$\mathbf{a + b \equiv a\,' + b\,' \pmod{n}}$$

Eftersom vi vet att \(a \equiv a\,' \pmod{n}\) och \(b \equiv b\,' \pmod{n}\), vilket betyder att det finns två heltal \(\,k_1 \,och \,k_2\), så att

$$\begin{cases}a - a\,' = \,k_1 \cdot n \: \: (1) \\ b - b\,' = \,k_2 \cdot n \: \: (2)\end{cases}$$

Om vi adderar ekvationer (1) + (2) får vi

$$(a + b) - (a\,' + b\,') = (k_1 + k_2)\cdot n$$

Låt oss sätta \(k = k_1 + k_2\), då får vi

$$(a + b) - (a\,' + b\,') =  k\cdot n$$

Här är \(k\) också ett heltal, eftersom både \(k_1\) och \(k_2\) var heltal, vilket bevisar att

$$\mathbf{a + b \equiv a\,' + b\,' \pmod{n}}$$

Exempel: Vi vill beräkna resten då 141 + 31 divideras med 7. Var för sig vet vi att

$$\frac{141}{7}=20 \text{ rest } 1 $$

och att

$$\frac{31}{7}=4 \text{ rest } 3. $$

Vi obeserverar nu att 141 är kongruent med sin rest, 1, modulo 7, då både 141 och 1 har resten 1 vid division med 7. Samma gäller för 31, nämligen att 31 är kongruent med sin rest, 3, modulo 7. Enligt regel 1 kan vi därför byta ut 141 mot 1 och 31 mot 3 i våra beräkningar. Vi får alltså

$$141 + 31 \equiv 1 + 3 \pmod{7}.$$

Här är högerledet mycket enklare att beräkna resten av än vänsterledet ty resten då 1 + 3 = 4 divideras med 7 är 4, men enligt definitionen av kongruenta tal innebär det att 141 + 31 också har samma rest vid division med 7, nämligen resten 4.
Detta är det vanligaste sättet att använda räknereglerna, nämligen genom att byta ut alla tal mot deras respektive rester vid division med n. Det är dock viktigt att observera att regel 1 inte säger att ”resten av en summa är lika med summan av resterna”. Detta stämmer nämligen inte.
Säg till exempel att vi vill beräkna resten av summan 17 + 28 vid division med 6. Summan blir 45, vilken har resten 3 vid division med 6 ty \(45 = 7 \cdot 6+3\). Men var för sig har 17 och 28 resterna 5 respektive 4 vid division med 6. Summan av resterna blir således

5 + 4 = 9,

vilket inte är lika med 3 som var resten av summan. Om vi dock nu beräknar resten av 9 vid division med 6 får vi 3, samma som resten av summan. Så regeln blir istället att ”resten av en summa är lika med resten av summan av resterna”.

Regel 2 - Multiplikation

Regeln 2 säger att: 

$$\mathbf{a \cdot b \equiv a\,' \cdot b\,' \pmod{n}}$$

Exempel: Låt oss se ett exempel på regel 2. Vi vill beräkna resten då (17 · 21) divideras med 5. Var för sig har vi att

$$\frac{17}{5} = 3 \text{ rest } 2 $$

och

$$\frac{21}{5} = 4 \text{ rest } 1 $$

Då ett tal är kongruent med sin rest kan vi byta ut 17 och 21 mot 2 respektive 1 i våra beräkningar och vi får då

$$17\cdot 21\equiv 2\cdot 1=2 \pmod{5}.$$

Den sista likheten är en vanlig likhet då vi inte har använt någon kongruensräkning i det steget utan helt enkelt bara multiplicerat ihop 2 och 1. Denna beräkning säger oss att talen (17 · 21) och 2 har samma rest vid division med 5. Då talet 2 är mindre än 5 är det lika med sin egen rest vid division med 5. Det följer därför att (17 · 21) har resten 2 vid division med 5.

Även här är det viktigt att observera att regel 2 inte säger att ”resten av en produkt är lika med produkten av resterna”. Säg till exempel att vi vill beräkna resten av produkten (15 · 10) vid division med 4. Denna rest blir 2 ty

$$15 \cdot 10 = 150 = 148 + 2 = 37 \cdot 4 + 2.$$

Men var för sig har 15 och 10 resterna 3 respektive 2 vid division med 4. Produkten av resterna blir således

$$3 \cdot 2 = 6,$$

vilket inte är lika med resten 2. I detta fall skulle den korrekta regeln vara att ”resten av en produkt är lika med resten av produkten av resterna”.

Räkneregel 3 - Potenser

Regeln 3 säger att:

$$\mathbf{a^m \equiv (a\,')^m \pmod{n}}$$

Exempel: Låt oss nu se ett exempel på regel 3. Vi vill beräkna resten av \(2^{10}\) vid division med 3. Vi använder först potenslagarna för att skriva om talet:

$$2^{10} = 2^{2 \cdot 5} = (2^2)^5 = 4^5.$$

Basen är nu 4 och vi kan enligt regel 3 byta ut den mot ett annat kongruent tal modulo 3, förslagsvis resten vid division med 3. Denna rest är 1 så vi får alltså att

$${4}^{5} \equiv {1}^{5}\, \pmod{3}.$$

Detta innebär sammantaget att

$$2^{10} = 4^5 \equiv 1^5 = 1\, \pmod{3},$$

där vi har använt vanlig likhet överallt där vi inte gjort någon kongruensräkning. Det betyder alltså att talen \(2^{10}\) och 1 har samma rest vid division med 3. Men då resten av 1 vid division med 3 är 1 (eftersom 1 är mindre än 3) innebär det att resten av \(2^{10}\) är 1 vid division med 3.

Även i detta fall stämmer det inte att regel 3 säger att ”resten av en potens är lika med potensen av resten”. Säg till exempel att vi vill beräkna resten av \(7^2\) vid division med 4. Denna rest blir 1 ty

$$7^2 = 49 = 48+1=12 \cdot 4 + 1.$$

Men resten av basen 7 vid division med 4 blir 3 och potensen av denna blir

$$3^2 = 9,$$

Tillämpning av räknereglerna för kongruenser

Vi har nu gått igenom de olika räknereglerna. Låt oss se hur vi kan använda kongruensräkning för att lösa några olika problem.

Om det är torsdag i dag, vilken veckodag är det då om en miljon dagar?

Namnen på veckans dagar återkommer som bekant var sjunde dag. Är det till exempel torsdag i dag kommer det därför att vara torsdag igen om sju dagar, fjorton dagar, osv., det vill säga om en multipel av 7 antal dagar.

Detta kan vi använda för att lösa vårt problem. Om det antal dagar som gått från i dag är delbart med 7 (det vill säga ger rest noll vid division med 7), då är den sökta veckodagen samma veckodag som i dag (alltså en torsdag). Om vi istället till exempel får resten 1 vid division med 7, betyder det att den sökta veckodagen är en fredag; resten 2 vid division med 7 innebär lördag, osv.

Därför undersöker vi vilken rest vi får då vi dividerar talet en miljon med 7. Talet en miljon kan vi skriva i potensform som 10⁶. Vi använder regel 3 och byter ut basen 10 mot resten 3 vid division med 7 och skriver sedan om denna potens med hjälp av potenslagarna:

$${10}^{6} \equiv {3}^{6} = {3}^{2 \cdot 3} = (3^2)^3 = 9^3 \, \pmod{7}.$$

Vi kan nu återigen använda regel 3 och byta ut basen 9 mot resten 2 vid division med 7 och vi får då

$${9}^{3} \equiv {2}^{3}\, \pmod{7}.$$

Den sista potensen är tillräckligt liten för att beräkna för hand och vi får slutligen

$$2^3 = 8.$$

Vi har nu alltså kommit fram till att \(10^6\) och 8 har samma rest vid division med 7. Men resten då 8 divideras med 7 är 1, alltså är resten då en miljon divideras med 7 lika med 1. Därför är det fredag om en miljon dagar, givet att det är torsdag idag.

Vilken är den sista siffran i talet (72⁴ + 13⁶)?

Den sista siffran i ett heltal är entalssiffran, som ju kan anta 10 olika värden (0 till 9). Att ta reda på den sista siffran i talet (72⁴ + 13⁶) är därför samma sak som att beräkna resten vid division med 10. Vi använder oss av regel 1 och 3 som tillsammans säger att vi kan byta ut baserna mot deras respektive rest vid division med 10. Vi får då att

$$ {72}^{4} + {13}^{6} \equiv {2}^{4} + {3}^{6}\, \pmod{10}.$$

Vi använder nu potenslagarna för att skriva om detta och får

$$2^4 + 3^6 = 2^{2 \cdot 2} + 3^{3 \cdot 2} =(2^2)^2 +(3^3)^2 = 4^2 + 27^2 = 16 + 27^2.$$

Här kan vi nu återigen använda första och tredje räkneregeln och vi får

$$16 + 27^2 \equiv 6 +7^2 = 6 + 49 \equiv 6+9 = 15 \pmod{10}.$$

Vi har nu alltså kommit fram till att (72⁴ + 13⁶) och 15 har samma rest vid division med 10. Då 15 har resten 5 vid division med 10 följer det att (72⁴ + 13⁶) har resten 5 vid division med 10, det vill säga att den sista siffran i talet (72⁴ + 13⁶) är 5.

Resten av stora tal

De stora talen är användbara vid flera tekniska tillämpningar av modulär aritmetik som encryption teknik till exempel. Låt oss nu titta på ett exempel.

Vad är resten av \( 5^{41615103} \) vid division med 6?

Vi vet ju att den enda möjliga rest är 0, 1, 2, 3, 4 eller 5, men hur man bestämmer vilket av dem det är?

Låt oss hitta ett mönster genom att titta på rester av talet 5 upphöjt till de första fem potensen vid division med 6.

5¹ har resten 5 vid division med 6, vilken kan skrivas

$$5^1 \equiv 5 \pmod{6}$$

Och 5² har resten 1 vid division med 6, vilken kan skrivas

$$5^2 \equiv 1 \pmod{6}$$

Enligt regeln 2 kan vi kombinera de här två ekvationerna genom att att multiplicera båda vänstra sidorna och båda högra sidorna för att få en ny kongruensrelation

$$5^1 \cdot 5^2 \equiv 5 \cdot 1 \pmod{6}$$

Vilket ger oss

$$5^3 \equiv 5 \pmod{6}$$

På samma sätt får vi (\(5^4 \equiv 1 \pmod{6}\)) osv.

\begin{align*}
5^1 \equiv 5 \pmod{6}, \\
5^2 \equiv 1 \pmod{6}, \\
5^3 \equiv 5 \pmod{6}, \\
5^4 \equiv 1 \pmod{6}, \\
5^5 \equiv 5 \pmod{6},\\ 
\hspace{-5.6cm} ...
\end{align*}

Vi har nu alltså kommit fram till att resen av \(5^n\) vid division med 6 har resten 5 för udda heltalen, \((n = 1, 3, 5, ...)\) och har resten 1 för jämna heltalen, \((n = 0, 2, 4, ...)\).

Det är ju tydligt att 41615103 är ett udda heltal, vilket betyder att talet \( 5^{41615103} \) har resten 5 vid division med 6.