Modulär aritmetik

${\displaystyle 9\equiv 5{\pmod {4}}}$ 

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

${\displaystyle 10\equiv 0{\pmod {2}}}$ 

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

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

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å 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 ${\displaystyle a\equiv b{\pmod {n}}}$ . Man kan också skriva ${\displaystyle a\equiv _{n}b}$ .

Om a och b inte är kongruenta modulo n, säger vi att talen är inkongruenta, vilket betecknas ${\displaystyle a\not \equiv b{\pmod {n}}}$ 

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

Vid moduloräkning fungerar addition, subtraktion och multiplikation som vanligt. Division fungerar emellertid bara med vissa förbehåll, se exempel nedan.

Låt n vara ett positivt heltal. Antag att heltalen ${\displaystyle a_{1},a_{2}}$  samt ${\displaystyle b_{1},b_{2}}$  uppfyller

${\displaystyle a_{1}\equiv a_{2}{\pmod {n}}}$  och ${\displaystyle b_{1}\equiv b_{2}{\pmod {n}}}$ 

Per definition vet vi att ${\displaystyle n|(a_{1}-a_{2})}$  och ${\displaystyle n|(b_{1}-b_{2})}$ 

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

${\displaystyle a_{1}-a_{2}=nx}$ 

och

${\displaystyle b_{1}-b_{2}=ny}$ 

Nu följer

${\displaystyle (a_{1}+b_{1})-(a_{2}+b_{2})=(a_{1}-a_{2})+(b_{1}-b_{2})}$ 

${\displaystyle =nx+ny}$ 

${\displaystyle =n(x+y)}$ 

Alltså gäller ${\displaystyle n|(a_{1}+b_{1})-(a_{2}+b_{2})}$ , vilket betyder att

${\displaystyle a_{1}+b_{1}\equiv a_{2}+b_{2}{\pmod {n}}}$ 

Beviset ovan bekräftar giltigheten för addition, och därmed även för subtraktion.

Vidare,

${\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}}$ 

${\displaystyle =a_{1}(b_{1}-b_{2})+(a_{1}-a_{2})b_{2}}$ 

${\displaystyle =a_{1}ny+nxb_{2}}$  (se ovan under additionsbeviset)

${\displaystyle =n(ya_{1}+xb_{2})}$ 

Och därmed ${\displaystyle n|(a_{1}b_{1}-a_{2}b_{2})}$ 

Det vill säga

${\displaystyle a_{1}b_{1}\equiv a_{2}b_{2}{\pmod {n}}}$ 

Detta bevisar giltigheten för multiplikation vid moduloräkning.

${\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

${\displaystyle 13\equiv 3{\pmod {5}}}$ 

${\displaystyle 16\equiv 1{\pmod {5}}}$ 

${\displaystyle 3+1=4\equiv 29{\pmod {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

${\displaystyle 13\equiv 3{\pmod {5}}}$ 

${\displaystyle 16\equiv 1{\pmod {5}}}$ 

${\displaystyle 3-1=2\equiv -3{\pmod {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

${\displaystyle 13\equiv 3{\pmod {5}}}$ 

${\displaystyle 16\equiv 1{\pmod {5}}}$ 

${\displaystyle 3\times 1=3\equiv 208{\pmod {5}}}$ 

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

• Kinesiska restklassatsen

• Asratian, Armen S., 1951- (2014). Diskret matematik. Univ. OCLC 941144531. http://worldcat.org/oclc/941144531. Läst 14 juni 2019 

•   Wikimedia Commons har media som rör Modulär aritmetik.
  Bilder & media