Modulär aritmetik

Från Wikipedia
Hoppa till: navigering, sök

Modulär aritmetik eller modulorä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. Man kan också skriva a \equiv_n b.

a och b är kongruenta modulo 0 om och endast om a = b. Detta triviala fslags kongruens bortser man ofta från, och förutsätter då i stället att n är nollskilt, alltså inte är likamed 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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

  • 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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

Addition[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

Som tidigare nämnts, fungerar division bara i vissa fall, varfö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[redigera | redigera wikitext]

Referenser[redigera | redigera wikitext]

Böcker[redigera | redigera wikitext]

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

Webbkällor[redigera | redigera wikitext]

Venn A intersect B.svg Matematikportalen – portalen för matematik på svenskspråkiga Wikipedia.