Modulär aritmetik

Från Wikipedia
(Omdirigerad från Kongruens modulo)
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 , och ibland även .

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:

har samma rest vid division med n .

Exempel[redigera | redigera wikitext]

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

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

Generaliseringar[redigera | redigera wikitext]

Om man låter beteckna delmängden av Z, så kan ovanstående definition formuleras . Den avgörande egenskapen hos är att den är ett ideal. Man låter ofta betyda där är ett ideal i en ring , eller allmännare Y är en delmodul av en modul X. Mängden av ekvivalensklasser till denna relation betecknas , 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 . Man kan också skriva .

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

Vilket betecknas

Exempel[redigera | redigera wikitext]

  • , Resten kan i båda fallen bli 4 vid division med 5
  • , Resten kan i båda fallen bli 3 vid division med 7
  • , 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 emellertid under vissa förbehåll, se exempel nedan.

Bevis[redigera | redigera wikitext]

Låt n vara ett positivt heltal. Antag att heltalen samt uppfyller
och
Per definition vet vi att och
Det betyder att det finns heltal x och y sådana att
och
Nu följer
Alltså gäller , vilket betyder att
Vidare,
Och därmed
Det vill säga

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

Exempel[redigera | redigera wikitext]

Addition[redigera | redigera wikitext]

Om vi ersätter talen ovan med andra tal som är kongruenta med de första så får vi samma svar

Subtraktion[redigera | redigera wikitext]

Om vi ersätter talen ovan med andra tal som är kongruenta med de första så får vi samma svar

Multiplikation[redigera | redigera wikitext]

Om vi ersätter talen ovan med andra tal som är kongruenta med de första så får vi samma svar

Division[redigera | redigera wikitext]

För division fordras viss försiktighet, vilket t.ex. illustreras av att , men ; det gäller emellertid att om är heltal, och , så där är den största gemensamma delaren till och . Speciellt gäller att om , så närhelst och saknar gemensamma delare.

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.