Modulär aritmetik

Matematiska operationer v • r
Addition (+)
term + term addend + addend	=	summa
Subtraktion (−)
term − term minuend − subtrahend	=	differens
Multiplikation (× eller ·)
faktor × faktor multiplikator × multiplikand	=	produkt
Division (÷ eller /)
täljare / nämnare dividend / divisor	=	kvot
Moduloräkning (mod)
dividend mod divisor	=	rest
Exponentiering (^)
bas^exponent	=	potens
n:te roten (√)
^grad√radikand	=	rot
Logaritm (log)
log_bas(potens)	=	exponent

Modulär aritmetik, moduloräkning eller kongruensräkning är ett område inom aritmetiken, där kongruensrelationen analyseras och används. Två tal a och b sägs vara kongruenta modulo n om n delar differensen mellan a och b, vilket för alla nollskilda n är ekvivalent med att de har samma principala rest vid division med n. Detta betecknas $a\equiv b{\pmod {n}}$ , och ibland även $a\equiv _{n}b$ .

Talen a och b är kongruenta modulo 0 om och endast om a = b. Detta triviala slags kongruens bortser man ofta från, och förutsätter då i stället att n är nollskilt, alltså inte är lika med noll. Under det extraantagandet kan man formellt beskriva definitionen och dess grundläggande egenskaper så här:

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 emellertid under vissa förbehåll, se exempel nedan.

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_{1}b_{1}-a_{2}b_{2}=a_{1}b_{1}-a_{1}b_{2}+a_{1}b_{2}-a_{2}b_{2}

=a_{1}(b_{1}-b_{2})+(a_{1}-a_{2})b_{2}

a_{1}ny+nxb_{2}

n(ya_{1}+xb_{2})

Och därmed

n|(ya_{1}+xb_{2})

Det vill säga

a_{1}b_{1}\equiv a_{2}b_{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

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