Modulär aritmetik och kongruensräkning

Kongruensräkning gör det möjligt att räkna med rester i stället för stora tal. Här används det för sista siffror, veckodagar och delbarhet.

På den här sidan

Bakgrund

Klockan räknar modulo 12: fyra timmar efter klockan 10 är klockan 2. Kongruensräkning är samma idé för alla heltal. Den gör det möjligt att räkna med enorma tal genom att bara hålla reda på resterna, och den används i kontrollsiffror, kalendrar och kryptering.

Teori

a\equiv\nobreak b\pmod n\ \Leftrightarrow\ n\mid(a-\nobreak b)

Två tal är kongruenta modulo $\displaystyle n$ om de ger samma rest vid division med $\displaystyle n$ . Skrivsättet $\displaystyle a\bmod n$ betyder resten, ett tal mellan 0 och $\displaystyle n-1$ .

Räkneregler

Om $\displaystyle a\equiv b$ och $\displaystyle c\equiv d\pmod n$ gäller

a+\nobreak c\equiv\nobreak b+\nobreak d,\qquad\allowbreak ac\equiv\nobreak bd,\qquad\allowbreak a^k\equiv b^k\pmod n

Man får alltså byta ut ett tal mot dess rest mitt i en beräkning. Division fungerar däremot inte alltid.

Exempel och tillämpningar

Exempel 1: Sista siffran i en stor potens

Uppgift: Bestäm sista siffran i $\displaystyle 7^{100}$ .

Exempel 2: Veckodag

Uppgift: Idag är det tisdag. Vilken veckodag är det om 100 dagar?

Exempel 3: Delbarhet med kongruenser

Uppgift: Visa att $\displaystyle n^3-n$ är delbart med 3 för alla heltal $\displaystyle n$ .

Interaktiva funktioner

Rester på en klocka

Välj ett tal och en modul. Resten är talets läge på en klocka med modulen som antal steg.

Tal: $\displaystyle a=23$

Modul: $\displaystyle n=7$

23=3\cdot\nobreak 7+\nobreak 2\ \Rightarrow\ 23\equiv2\pmod{7}

Resten som läge på en klocka med 7 steg

0123456

Vanliga misstag

Att ge en negativ rest. Resten modulo n ligger alltid mellan 0 och n - 1.
Att dividera i en kongruens utan att kontrollera att det är tillåtet.
Att glömma att byta ut stora tal mot deras rester tidigt i beräkningen.

Vanliga frågor

Tips för kongruensräkning

Viktigt att tänka på

Byt ut tal mot rester så tidigt som möjligt.
Leta efter en potens som är kongruent med 1.

Testa dig själv: Kongruensräkning1/3

Vad är $\displaystyle 23\bmod7$ ?

Testa att du förstått

Träna uppgifter i taluppfattning för Matematik 5. Du får facit och förklaring direkt.

Träna på det här