Modulär aritmetik, moduloräkning eller kongruensräkning är ett område inom aritmetiken, där man räknar med ett begränsat antal tal. Andra tal räknas som jämlika ("kongruenta") med ett av dessa, nämligen med det av talen som blir rest vid division med antalet tal man räknar med.
Den modulära aritmetiken används bland annat inom kryptologin.
I den modulära matematiken analyseras och används kongruensrelationen. 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 ≡ b ( mod n ) {\displaystyle a\equiv b{\pmod {n}}} , och ibland även a ≡ n b {\displaystyle 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 ≡ b ( mod n ) ⇔ a , b {\displaystyle a\equiv b{\pmod {n}}\Leftrightarrow a,b} har samma rest vid division med n ⇔ n | ( a − b ) {\displaystyle \Leftrightarrow n|(a-b)} .eftersom 9 och 5 båda ger resten 1 vid division med 4.
10 ≡ 0 ( mod 2 ) {\displaystyle 10\equiv 0{\pmod {2}}}eftersom 10 och 0 ger samma rest (0) vid division med 2.
Om man låter ( n ) {\displaystyle (n)} Z, så kan ovanstående definition formuleras x ≡ y ( mod n ) ⇔ x − y ∈ ( n ) {\displaystyle x\equiv y{\pmod {n}}\Leftrightarrow x-y\in (n)} . Den avgörande egenskapen hos ( n ) {\displaystyle (n)} är att den är ett ideal. Man låter ofta x ≡ y ( mod Y ) {\displaystyle x\equiv y{\pmod {Y}}} betyda x − y ∈ Y {\displaystyle x-y\in Y} där Y {\displaystyle Y} är ett ideal i en ring X {\displaystyle X} , eller allmännare Y är en delmodul av en modul X. Mängden av ekvivalensklasser till denna relation betecknas X / Y {\displaystyle X/Y} , och kallas en kvotring (respektive kvotmodul, kvotgrupp, kvotrum och så vidare).
beteckna delmängden { … , − 2 n , − n , 0 , n , 2 n , … } {\displaystyle \{\ldots ,-2n,-n,0,n,2n,\ldots \}} avModulorä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å heltal a och b är kongruenta modulo n om de ger samma rest vid division med n (ett heltal som är större än eller lika med 2).
Detta betecknas a ≡ b ( mod n ) {\displaystyle a\equiv b{\pmod {n}}}
. Man kan också skriva a ≡ n b {\displaystyle a\equiv _{n}b} .Om a och b inte är kongruenta modulo n, säger vi att talen är inkongruenta, vilket betecknas a ≢ b ( mod n ) {\displaystyle a\not \equiv b{\pmod {n}}}
Vid moduloräkning fungerar addition, subtraktion och multiplikation som vanligt. Division fungerar emellertid bara med vissa förbehåll, se exempel nedan.
Beviset ovan bekräftar giltigheten för addition, och därmed även för subtraktion.
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 {\displaystyle 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 {\displaystyle =a_{1}(b_{1}-b_{2})+(a_{1}-a_{2})b_{2}} = a 1 n y + n x b 2 {\displaystyle =a_{1}ny+nxb_{2}} (se ovan under additionsbeviset) = n ( y a 1 + x b 2 ) {\displaystyle =n(ya_{1}+xb_{2})} Och därmed n | ( a 1 b 1 − a 2 b 2 ) {\displaystyle n|(a_{1}b_{1}-a_{2}b_{2})} Det vill säga a 1 b 1 ≡ a 2 b 2 ( mod n ) {\displaystyle a_{1}b_{1}\equiv a_{2}b_{2}{\pmod {n}}}Detta bevisar giltigheten för multiplikation vid moduloräkning.
Exempel Addition13 + 16 = 29 ≡ 4 ( mod 5 ) {\displaystyle 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 ≡ 3 ( mod 5 ) {\displaystyle 13\equiv 3{\pmod {5}}}
16 ≡ 1 ( mod 5 ) {\displaystyle 16\equiv 1{\pmod {5}}}
3 + 1 = 4 ≡ 29 ( mod 5 ) {\displaystyle 3+1=4\equiv 29{\pmod {5}}}
Subtraktion13 − 16 = − 3 ≡ 2 ( mod 5 ) {\displaystyle 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 ≡ 3 ( mod 5 ) {\displaystyle 13\equiv 3{\pmod {5}}}
16 ≡ 1 ( mod 5 ) {\displaystyle 16\equiv 1{\pmod {5}}}
3 − 1 = 2 ≡ − 3 ( mod 5 ) {\displaystyle 3-1=2\equiv -3{\pmod {5}}}
Multiplikation13 × 16 = 208 ≡ 3 ( mod 5 ) {\displaystyle 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 ≡ 3 ( mod 5 ) {\displaystyle 13\equiv 3{\pmod {5}}}
16 ≡ 1 ( mod 5 ) {\displaystyle 16\equiv 1{\pmod {5}}}
3 × 1 = 3 ≡ 208 ( mod 5 ) {\displaystyle 3\times 1=3\equiv 208{\pmod {5}}}
DivisionFör division fordras viss försiktighet, vilket t.ex. illustreras av att 5 ⋅ 9 ≡ 5 ⋅ 3 ( mod 10 ) {\displaystyle 5\cdot 9\equiv 5\cdot 3{\pmod {10}}} största gemensamma delaren till m {\displaystyle m} och n {\displaystyle n} . Speciellt gäller att om a m ≡ b m ( mod n ) {\displaystyle am\equiv bm{\pmod {n}}} , så a ≡ b ( mod n ) {\displaystyle a\equiv b{\pmod {n}}} närhelst m {\displaystyle m} och n {\displaystyle n} är relativt prima (saknar gemensamma delare större än 1).
, men 9 ≢ 3 ( mod 10 ) {\displaystyle 9\not \equiv 3{\pmod {10}}} ; det gäller emellertid att om a , b , m , n {\displaystyle a,b,m,n} är heltal, och a m ≡ b m ( mod n ) {\displaystyle am\equiv bm{\pmod {n}}} , så a ≡ b ( mod n / d ) {\displaystyle a\equiv b{\pmod {n/d}}} där d {\displaystyle d} är den