Kongruensräkning

Följande viktiga räkneregler gäller när vi räknar med kongruenser:

$$Räkneregel\,1:\,\,a+b\,\pmod{n}\equiv a\,\pmod{n}+b\,\pmod{n}$$

$$Räkneregel\,2:\,\,a\cdot b\,\pmod{n}\equiv a\,\pmod{n}\cdot b\,\pmod{n}$$

$$Räkneregel\,3:\,\,{a}^{m}\,\pmod{n}\equiv {(a\,\pmod{n})}^{m}$$

Vi kommer nu att gå igenom var och en av dessa räkneregler, och se hur vi kan använda dem.

Räkneregel 1 - Addition

Räkneregeln som gäller vid addition är

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

Denna räkneregel säger oss att vi kan beräkna resten då summan a + b divideras med n på två olika sätt:

  • genom att först summera talen a och b, och sedan beräkna resten vid division med talet n, eller
  • genom att beräkna resten då a respektive b var för sig divideras med n, och sedan summera dessa resttermer.

Vill vi till exempel beräkna vilken resten blir då summan av 141 och 31 divideras med 7, då har vi alltså två olika sätt som vi kan använda för att beräkna denna rest.

Det första sättet är att beräkna summan av 141 och 31, dividera denna summan med 7 och därigenom ta reda på resten:

$$141+31\,\pmod{7}=$$

$$=172\,\pmod{7}\equiv$$

$$\equiv 4\,\pmod{7}$$

Den sökta resten vid division med 7 är alltså 4.

Det andra sättet är att ta reda på resten då termerna 141 och 31 var för sig divideras med 7, och sedan addera dessa resttermer:

$$141\,\pmod{7}+31\,\pmod{7}\equiv$$

$$\equiv 1\,\pmod{7}+3\,\pmod{7}\equiv$$

$$\equiv 4\,\pmod{7}$$

Även i detta fall är den sökta resten vid division med 7 lika med 4.

Räkneregel 2 - Multiplikation

Räkneregeln som gäller vid multiplikation är

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

Denna räkneregel säger oss att vi kan beräkna resten då produkten a ∙ b divideras med n på två olika sätt:

  • genom att först multiplicera talen a och b, och sedan beräkna resten då denna produkt divideras med talet n, eller
  • genom att beräkna resten då a respektive b var för sig divideras med n, och sedan multiplicera dessa resttermer.

Vill vi till exempel beräkna vilken resten blir då produkten av 17 och 21 divideras med 5, då har vi alltså två olika sätt som vi kan använda för att beräkna denna rest.

Det första sättet är att beräkna produkten av 17 och 21, dividera denna produkt med 5 och därigenom ta reda på resten:

$$17\cdot 21\,\pmod{5}=$$

$$=357\,\pmod{5}\equiv$$

$$\equiv 2\,\pmod{5}$$

Den sökta resten vid division med 5 är alltså 2.

Det andra sättet är att ta reda på resten då faktorerna 17 och 21 var för sig divideras med 5, och sedan multiplicera de rester som vi kommer fram till:

$$17\,\pmod{5}\cdot 21\,\pmod{5}\equiv$$

$$\equiv 2\,\pmod{5}\cdot 1\,\pmod{5}\equiv$$

$$\equiv 2\cdot 1\,\pmod{5}=$$

$$=2\,\pmod{5}$$

Även i detta fall är den sökta resten vid division med 5 lika med 2.

I detta exempel var det dock enklare att först dividera faktorerna 17 och 21 var för sig och sedan multiplicera resterna, än att först multiplicera 17 och 21, och sedan dividera. Om vi är uppmärksamma på vilka värden vi räknar med, kan vi alltså förenkla våra beräkningar genom att välja det ena eller det andra sättet att beräkna resten.

Räkneregel 3 - Potenser

Räkneregeln som gäller vid potenser är

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

Denna räkneregel säger oss att vi kan beräkna resten då potensen am divideras med n på två olika sätt:

  • genom att först beräkna värdet av potensen am, och sedan beräkna resten vid division med talet n, eller
  • genom att beräkna resten då a divideras med n, och sedan upphöja resultatet till m.

Vill vi till exempel beräkna vilken resten blir då potensen 210 divideras med 3, då har vi alltså två olika sätt att beräkna denna rest.

Det första sättet är att beräkna värdet av potensen 210, dividera detta värde med 3 och därigenom ta reda på resten:

$$ {2}^{10}\,\pmod{3}=$$

$$=1024\,\pmod{3}\equiv$$

$$\equiv 1\,\pmod{3}$$

Den sökta resten vid division med 3 är alltså 1.

Det andra sättet är att beräkna resten då basen 2 divideras med 3, och sedan upphöja denna rest till exponenten. Dock är det i detta fall bättre att först skriva om potensen med hjälp av räkneregeln för potenser av potenser, så att vi får en annan rest än 2 då vi dividerar basen med 10:

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

Sedan räknar vi vidare som planerat:

$$ {(4\,\pmod{3})}^{5}\equiv$$

$$\equiv {(1\,\pmod{3})}^{5}\equiv$$

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

$$=1\,\pmod{3}$$

Även i detta fall är den sökta resten vid division med 3 lika med 1.

Tillämpning av räknereglerna för kongruenser

När vi nu har gått igenom de tre räknereglerna för kongruenser ska vi titta på några exempel på problem som vi kan lösa med hjälp av dessa regler.


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), 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 106. Därmed ger oss räkneregel 3 som bekant två olika sätt att beräkna den sökta resten:

$${10}^{6}\,\pmod{7}\equiv {(10\,\pmod{7})}^{6}$$

Vi väljer att börja räkna utifrån det högra ledet, så vi får följande:

$$ {(10\,\pmod{7})}^{6}\equiv$$

$$\equiv {(3\,\pmod{7})}^{6}\equiv$$

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

$$\equiv {(9\,\pmod{7})}^{3}\equiv$$

$$\equiv {(2\,\pmod{7})}^{3}\equiv$$

$$\equiv {2}^{3}\,\pmod{7}=8\,\pmod{7}\equiv$$

$$\equiv 1\,\pmod{7}$$

Vad vi har kommit fram till här är alltså att resten då talet en miljon divideras med 7 är lika med 1.

Det tolkar vi som att den sökta veckodagen är en fredag.


Vilken är den sista siffran i talet 724?

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 724 är därför samma sak som att beräkna resten vid division med 10. Därför räknar vi modulo 10.

Detta gör vi med hjälp av den tredje räkneregeln:

$$ {72}^{4}\,\pmod{10}\equiv$$

$$\equiv {(72\,\pmod{10})}^{4}\equiv$$

$$\equiv {(2\,\pmod{10})}^{4}\equiv$$

$$\equiv {2}^{4}\,\pmod{10}=16\,(mod\,10)\equiv$$

$$\equiv 6\,\pmod{10}$$

Vad vi nu har kommit fram till är att den sista siffran i talet 724 är en 6:a.


Videolektion

Har du en fråga du vill ställa om Kongruensräkning? Ställ den på Pluggakuten.se!
Har du kommentarer till materialet på den här sidan? Mejla feedback@matteboken.se!