Här är en ren textversion som är optimerad för att kopieras och klistras in direkt i ett dokument eller ett anteckningsblock.

Sammanfattning: Moduloräkning (Matematik 5)

1. Grundläggande definition

Moduloräkning handlar om att studera resten vid division. Vi säger att talet $a$ är kongruent med $b$ modulo $n$ om de ger samma rest vid division med $n$. Detta skrivs:

, $a \equiv b (\mod n) \Leftrightarrow a, b$ $a\equiv b{\pmod {n}}\Leftrightarrow a,b$ har samma rest vid division med n $\Leftrightarrow n | (a - b)$ $\Leftrightarrow n|(a-b)$ .

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

En alternativ definition är att skillnaden mellan talen ska vara delbar med modulet:

n \mid (a – b)

Exempel: $23 \equiv 2 \pmod{7}$ eftersom $23 – 2 = 21$, och 21 är delbart med 7.

2. Räkneregler

Om $a \equiv b \pmod{n}$ och $c \equiv d \pmod{n}$ gäller följande lagar:

Addition: $a + c \equiv b + d \pmod{n}$
Subtraktion: $a – c \equiv b – d \pmod{n}$
Multiplikation: $a \cdot c \equiv b \cdot d \pmod{n}$
Potenser: $a^k \equiv b^k \pmod{n}$

Varning: Division är inte tillåten på samma enkla sätt. Man får endast dividera båda led med en faktor $k$ om $\text{sgd}(k, n) = 1$ (dvs. om faktorn och modulet inte har några gemensamma delare).

Ex. Addition

$13 + 16 = 29 \equiv 4 (\mod 5)$ $13+16=29\equiv 4{\pmod {5}}$

Om vi ersätter talen ovan med andra tal som är kongruenta med de första så får vi samma svar

$13 \equiv 3 (\mod 5)$ $13\equiv 3{\pmod {5}}$

$16 \equiv 1 (\mod 5)$ $16\equiv 1{\pmod {5}}$

$3 + 1 = 4 \equiv 29 (\mod 5)$ $3+1=4\equiv 29{\pmod {5}}$

3. Strategi för stora potenser

För att beräkna resten av stora tal, t.ex. $3^{82} \pmod{10}$, letar man efter en ”bas” som blir $1$ eller $-1$:

Vi vet att $3^4 = 81$.
$81 \equiv 1 \pmod{10}$.
Skriv om ursprungstalet: $3^{82} = 3^2 \cdot (3^4)^{20}$.
Ersätt med kongruenser: $9 \cdot 1^{20} \equiv 9 \pmod{10}$.
Svar: Resten är 9.

4. Negativa rester

Det är ofta smidigt att använda negativa rester för att förenkla kalkyler.

Exempel: $13 \pmod{14}$ kan skrivas som $-1 \pmod{14}$.

Eftersom $(-1)^{jämnt} = 1$ och $(-1)^{udda} = -1$ underlättar detta potensräkning avsevärt.

5. Tillämpningsområden

Diofantiska ekvationer: Lösa $ax + by = c$.
Delbarhetsproblem: Bevisa egenskaper hos talföljder.
Kryptografi: Grunden för RSA-algoritmen.
Kontrollnummer: Validering av personnummer och bankkortnummer via Luhn-algoritmen.

Subtraktion

$13 - 16 = - 3 \equiv 2 (\mod 5)$ $13-16=-3\equiv 2{\pmod {5}}$

Om vi ersätter talen ovan med andra tal som är kongruenta med de första så får vi samma svar

$13 \equiv 3 (\mod 5)$ $13\equiv 3{\pmod {5}}$

$16 \equiv 1 (\mod 5)$ $16\equiv 1{\pmod {5}}$

$3 - 1 = 2 \equiv - 3 (\mod 5)$ $3-1=2\equiv -3{\pmod {5}}$

Multiplikation

$13 \times 16 = 208 \equiv 3 (\mod 5)$ $13\times 16=208\equiv 3{\pmod {5}}$

Om vi ersätter talen ovan med andra tal som är kongruenta med de första så får vi samma svar

$13 \equiv 3 (\mod 5)$ $13\equiv 3{\pmod {5}}$

$16 \equiv 1 (\mod 5)$ $16\equiv 1{\pmod {5}}$

$3 \times 1 = 3 \equiv 208 (\mod 5)$ $3\times 1=3\equiv 208{\pmod {5}}$

Division

För division fordras viss försiktighet, vilket t.ex. illustreras av att $5 \cdot 9 \equiv 5 \cdot 3 (\mod 10)$ $5\cdot 9\equiv 5\cdot 3{\pmod {10}}$ , men $9 ≢ 3 (\mod 10)$ $9\not \equiv 3{\pmod {10}}$ ; det gäller emellertid att om $a, b, m, n$ $a,b,m,n$ är heltal, och $a m \equiv b m (\mod n)$ $am\equiv bm{\pmod {n}}$ , så $a \equiv b (\mod n / d)$ $a\equiv b{\pmod {n/d}}$ där $d$ $d$ är den största gemensamma delaren till $m$ $m$ och $n$ $n$ . Speciellt gäller att om $a m \equiv b m (\mod n)$ $am\equiv bm{\pmod {n}}$ , så $a \equiv b (\mod n)$ $a\equiv b{\pmod {n}}$ närhelst $m$ $m$ och $n$ $n$ är relativt prima (saknar gemensamma delare större än 1).