Modulär aritmetik

Modulär aritmetik är ett område inom aritmetiken. Två tal a och b sägs vara kongruenta modulo n om de har samma rest vid division med n. En annan, ekvivalent definition, är att n delar differensen mellan a och b.

Detta betecknas $a \equiv b \pmod n$. Man kan också skriva $a \equiv_n b$.

$a \equiv b \pmod n \Leftrightarrow a, b$ har samma rest vid division med n $\Leftrightarrow n | a-b$

Exempel

$9 \equiv 5 \pmod 4$

eftersom 9 och 5 båda ger resten 1 vid division med 4.

$10 \equiv 0 \pmod 2$

eftersom 10 och 0 ger samma rest (0) vid division med 2.

Generaliseringar

Om man låter $(n)$ beteckna delmängden $\{\ldots, -2n, -n, 0, n, 2n, \ldots\}$ av Z, så kan ovanstående definition formuleras $x \equiv y \pmod{n} \Leftrightarrow x - y \in (n)$. Den avgörande egenskapen hos $(n)$ är att den är ett ideal. Man låter ofta $x \equiv y \pmod{Y}$ betyda $x-y\in Y$ där $Y$ är ett ideal i en ring $X$, eller allmännare Y är en delmodul av en modul X. Mängden av ekvivalensklasser till denna relation betecknas $X/Y$, och kallas en kvotring (respektive kvotmodul, kvotgrupp, kvotrum och så vidare).

Moduloräkning

Moduloräkning (även kallat kongruensräkning) är ett område inom elementär algebra. Relationen kongruens modulo används bland annat för datoraritmetik och inom kryptering.

Två tal a och b är kongruenta modulo n om de ger samma rest vid division med n (a,b och n är heltal, n är större eller lika med 2).

Detta betecknas $a \equiv b \pmod n$. Man kan också skriva $a \equiv_n b$.

Om a och b inte är kongruenta modulo n, säger vi att talen är inkongruenta.

Vilket betecknas $a \not \equiv b \pmod n$

Exempel

• $9 \equiv 4 \pmod 5$, Resten kan i båda fallen bli 4 vid division med 5
• $24 \equiv 17 \pmod 7$, Resten kan i båda fallen bli 3 vid division med 7
• $7 \not \equiv 4 \pmod 6$, Resten blir olika vid division med 6

De fyra räknesätten

Vid moduloräkning fungerar addition, subtraktion och multiplikation som vanligt. Division fungerar bara i vissa fall, därför bör man undvika det, istället kan man förkorta enligt angiven moduloklass och sedan multiplicera för att ta sig runt problemet.

Bevis

Låt n vara ett positivt heltal. Antag att heltalen $a_1, a_2$ samt $b_1, b_2$ uppfyller

$a_1\equiv a_2 \pmod n$ och $b_1\equiv b_2 \pmod n$

Per definition vet vi att $n|(a_1-a_2)$ och $n|(b_1-b_2)$

Det betyder att det finns heltal x och y sådana att

$a_1 - a_2 = nx$

och

$b_1 - b_2 = ny$

Nu följer

$(a_1+b_1)-(a_2+b_2)=(a_1-a_2)+(b_1-b_2)$

$=nx+ny$

$=n(x+y)$

Alltså gäller $n|(a_1+b_1)-(a_2+b_2)$, vilket betyder att

$a_1+b_1\equiv a_2+b_2 \pmod n$

Vidare,

$a_1b_1-a_2b_2=a_1b_1-a_1b_2+a_1b_2-a_2b_2$

$=a_1(b_1-b_2)+(a_1-a_2)b_2$

$a_1ny+nxb_2$

$n(ya_1+xb_2)$

Och därmed $n|(ya_1+xb_2)$

Det vill säga

$a_1b_1 \equiv a_2b_2 \pmod n$

Beviset bekräftar addition och därmed subtraktion. Samt multiplikation vid moduloräkning.

Exempel

Addition

$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 \pmod 5$

$16 \equiv 1 \pmod 5$

$3 + 1 = 4 \equiv 29 \pmod 5$

Subtraktion

$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 \pmod 5$

$16 \equiv 1 \pmod 5$

$3 - 1 = 2 \equiv -3 \pmod 5$

Multiplikation

$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 \pmod 5$

$16 \equiv 1 \pmod 5$

$3 \times 1 = 3 \equiv 208 \pmod 5$

Division

Som tidigare nämnts, så fungerar division bara i vissa fall, därför bör man undvika det. Istället kan man förkorta enligt angiven moduloklass och sedan multiplicera för att ta sig runt problemet.

Se även

• Kinesiska restklassatsen

Referenser

Böcker

A. Asratian, A. Björn, B. O. Turesson (2007). Diskret Matematik. Linköping: Matematiska institutionen, Linköpings Universitet 

Webbkällor

• Peterholgersson.se/ (hämtad 2008-05-12)