Modulær aritmetikk

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk
Crystal Clear app messenger.pngUoversatt: Denne artikkelen er ikke fullstendig oversatt til norsk.
Tidsregning på denne klokken bruker aritmetikk modulo 12.

Modulær aritmetikk er en aritmetikk for heltall som ble systematisert av Carl Friedrich Gauss på 1800-tallet. Den går også under navnet «klokkearitmetikk» ettersom tallrekken er begrenset av modulen. Regner vi for eksempel modulo 4, går tallrekken slik: 0, 1, 2, 3, 0, 1, 2, 3, 0, ...

En vanlig bruk av modulær aritmetikk er i tolv-timersklokken, hvor dagen er delt inn i to tolvtimersperioder. Hvis klokken er 7:00 nå, så vil den være 3:00 8 timer senere. Vanlig addisjon ville gi et annet resultat; 7 + 8 = 15, men dette er ikke riktig svar fordi klokketiden "går rundt" hver tolvte time, det finnes ingen "klokka 15" på et vanlig håndur. Det er som vi identifiserer 12 med 0. På samme måte, hvis klokken starter på 12:00 (middag) og 21 timer forløper, så vil klokken være 9:00 neste dag, ikke 33:00. Siden timetallene starter på nytt igjen straks etter å ha nådd 12, så er dette aritmetikk modulo 12. 12 er kongruent ikke bare til 12 selv, men også til 0, så tidspunktet kalt "12:00" kunne like gjerne kalles "0:00", siden 12 er kongruent til 0 modulo 12.

Modulo-operasjonen regner ut resten når to heltall deles på hverandre. Vi sier derfor at a \equiv b\pmod{n} når a gir b som rest når a deles på n. For eksempel er 17 \equiv 1\pmod{4} fordi 17 delt på 4 gir 1 i rest. I det første klokkeeksemplet over, sjekk at (7 + 8) delt med 12 gir 3 i rest.

For et positivt heltall Mal:Mvar, så sies to hele tall Mal:Mvar og Mal:Mvar å være kongruente modulo Mal:Mvar, skrives som

a \equiv b \pmod n,\,

hvis deres differens Mal:Mvar er et heltallig multiplum av Mal:Mvar (eller om Mal:Mvar deler Mal:Mvar). Tallet Mal:Mvar kalles modulus til kongruensen, mens hele tall kongruente til Mal:Mvar modulo Mal:Mvar skaper en mengde kalt kongruensklassen eller restklassen til det hele tallet Mal:Mvar, modulo Mal:Mvar.

Historie[rediger | rediger kilde]

Kongruensrelasjonen[rediger | rediger kilde]

Resten ved heltallsdivisjon[rediger | rediger kilde]

Funksjonsrepresentasjon av restoperasjonen[rediger | rediger kilde]

Kongruensklasser[rediger | rediger kilde]

Anvendelser[rediger | rediger kilde]

Beregningskompleksitet[rediger | rediger kilde]

Se også[rediger | rediger kilde]

Fotnoter[rediger | rediger kilde]

Litteratur[rediger | rediger kilde]

        
  • Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 71081766
        

Eksterne lenker[rediger | rediger kilde]

Automatiserte teorembevisere i modulær aritmetikk:

  • Spear
  • AAProver - Simple C++ framework easy to use in applications, supporting (among others) all integer operators present in languages such as C/C++/Java and arbitrary bit-width.