Modulaarinen aritmetiikka

**Modulaarinen aritmetiikka** (lyhyemmin **modulaariaritmetiikka**, joskus myös *kello­taulu­aritmetiikka*), on kokonaislukuja käsittelevä matemaattisen lukuteorian haara, jossa luvut korvataan niillä jako­jäännöksillä (oikeastaan residyillä), jotka saadaan jaettaessa luku tietyllä vakiolla, *moduluksella*. Täten luvut ikään "kiertävät kehää" määrä­välein, saavuttaessaan tämä vakion.

Nykyaikaisen lähestymis­tavan modulaariselle aritmetiikalle kehitti Carl Friedrich Gauss teoksessaan *[[Disquisitiones Arithmeticae]]*, joka julkaistiin vuonna 1801.

Tutun esi­merkin modu­laari­sen aritme­tiikan käyttö­yhteydestä muodostavat kello­ajat. Kun käytetään 12 tunnin kello­aika­järjestelmää, johon tavalliset kellotaulut yhä perustuvat, kuusi tuntia kello 9:n jälkeen kello on 3. Tavallisessa yhteenlaskussa tosin saataisiin tulokseksi 9 + 6 = 15, mutta kello 12:n jälkeen kello­ajat alkavat uudestaan alusta, sillä vuorokausi on jaettu kahteen 12 tunnin jaksoon. Näin ollen tunnit noudattavat modu­laarista aritme­tiikkaa *modulo* 12. Nykyisin useimmissa maissa käytetään kuitenkin viralli­sesti 24 tunnin järjes­telmää, jossa kello­ajat alkavat uudestaan alusta vasta klo 24:n jälkeen. Jos kello on nyt 12, se on 3 tunnin kuluttua 15, mutta 21 tunnin kuluttua 9 seuraavana päivänä. Tällöin on siis kyseessä modu­laari­nen aritme­tiikka *modulo* 24.

## Kongruenssirelaatio

Modulaarista aritme­tiikkaa voidaan käsitellä mate­maatti­sesti ottamalla käyttöön kokonaislukujen kongruenssirelaatio, joka on yhteen­sopiva kokonais­lukujen renkaan lasku­toimitusten — yhteen-, vähennys- ja kertolaskun — kanssa. Jos valitaan jokin posi­tiivinen kokonais­luku *n*, kahden kokonais­luvun *a* ja *b* sanotaan olevan *kongruentteja *modulo&nbsp;n*, mikä merkitään:

:<math>a \equiv b \pmod n,\,</math>

jos niiden erotus on [[jaollisuus|jaollinen]] *n*:llä.

Esimerkiksi

:<math>38 \equiv 14 \pmod {12}\,</math>

koska 38&nbsp;−&nbsp;14&nbsp;=&nbsp;24, joka on jaollinen 12:lla.

Sama pätee nega­tiivisille kokonais­luvuille:

:<math> -8 \equiv 7 \pmod 5.\,</math>
:<math> 2 \equiv -3 \pmod 5.\,</math>
:<math> -3 \equiv -8 \pmod 5.\,</math>

Luku *n* on kongruenssi­relaation *modulus*.

Jos sekä *a* että *b* ovat posi­tiivisia, ne ovat kongru­entteja modulo *n*, jos ja vain jos niiden [[jakojäännös|jakoj­äännökset]] *n*:llä jaettaessa ovat samat.  Niinpä esi­merkiksi

:<math>38 \equiv 14 \pmod {12}\,</math>

koska lukujen 38 ja 14 jako­jäännös 12:lla jaettaessa on sama, 2.

Merkintä­tavasta on huomattava, että koska samassa yhteydessä saatetaan käyttää useita kongruenssi­relaatioita, joilla on eri modulus, merkinnässä on mukana myös modulus. Vaikka merkintä­tapa näin ollen viittaa siihen, että kyseessä olisi [[kolmipaikkainen relaatio]], kongruenssi annetun moduluksen suhteen on kaksi­paikkainen on [[binäärirelaatio]].

Kongruenssi­relaation yhteen­sopivuus perus­lasku­toimitusten kanssa merkitsee sitä, että se noudattaa seuraavia lakeja:

Jos

:<math>a_1 \equiv b_1 \pmod n</math>

ja

:<math>a_2 \equiv b_2 \pmod n,</math>

niin:

*<math>a_1 + a_2 \equiv b_1 + b_2 \pmod n\,</math>
*<math>a_1 - a_2 \equiv b_1 - b_2 \pmod n\,</math>

Nämä lait pätisivät siinäkin tapauksessa, että teoria laajenne­ttaisiin käsittämään kaikki [[reaaliluku|reaali­luvut]], toisin sanoen vaikka luvut <math>a_1, a_2, b_1, b_2, n\,</math> eivät kaikki olisikaan kokonais­lukuja, mutta kongruenssi määriteltäisiin reaali­luvuille muutoin samaan tapaan kuin edellä. Seuraava ominaisuus pätee kuitenkin vain, jos ne kaikki ovat kokonais­lukuja:

*<math> a_1 a_2 \equiv b_1 b_2 \pmod n.\,</math>

==Jakojäännökset==

Modulaarisen aritme­tiikan käsite liittyy läheisesti [[jakoyhtälö]]ön ja siinä esiintyvään [[jakojäännös|jako­jäännökseen]].  Jako­jäännöksen määrittä­mistä nimite­täänkin joskus *modulo-operaatioksi*, ja joskus näkee käytet­tävän sellaistakin merkintää kuin  . Erona jako­yhtälöön verrattuna on kongruenssin käsite, jolle käytetään merkintää "≡" [[yhtäläisyysmerkki|yhtäläisyys­merkin]] "=" asemesta. Lukujen kongruenssi on [[ekvivalenssirelaatio]], johon liittyviä [[ekvivalenssiluokka|ekvivalenssi­luokkia]] sanotaan [[jäännösluokka|jäännös­luokiksi]]. Kunkin jäännös­luokan edustajaksi valitaan tavallisesti sen pienin ei-nega­tiivinen luku, esimerkiksi  . Tätä sanotaan myös [[residy]]ksi. Tästä seuraa, että vaikka on oikein merkitä   , ja , on väärin merkitä  (missä "=" esiintyy "≡" -merkin sijasta).

Jokainen [[positiivinen luku|positiivinen]] kokonais­luku kuuluu kongruenssi­relaatiossa siihen jäännös­luokkaan, jonka edustajana on sen jako­jäännös moduluksella jaettaessa. Tällöin siis residy on sama kuin jako­jäännös. [[Negatiivinen luku|Nega­tiivisten]] kokonais­lukujen tapauksessa asia on kuitenkin toisin, koska jako­jäännös tavalliseen tapaan laskettuna on tällöin nega­tiivinen. Niinpä esi­merkiksi luvun -17 jako­jäännös 12:lla jaettaessa on -5 (sillä ), 
mutta kongruenssi­relaatiossa luvut -17 ja -5 kuuluvat ekvi­valenssi­luokkaan, jota edustamaan valitaan luku 7. Tämä on siis luvun -17 residy 12:lla jaettaessa.

Tietokoneiden [[ohjelmointikieli]]ssä jako­jäännös­operaatiolel käytetään yleensä merkintää "%" (esi­merkiksi
[[C (ohjelmointikieli)|C:ssä]], [[Java]]ssa, [[Perl]]issä ja [[Python (ohjelmointikieli)|Pythonissa]]) tai "mod"
(esimerkiksi [[Pascal (ohjelmointikieli)|Pascalissa]], [[BASIC]]issa, [[SQL]];ssä ja [[Haskell]]issa), poikkeuksena muun muassa [[Excel]]. Nämä antavat tulokseksi jako­jäännöksen sillä tavoin, että esimerkiksi C++:ssa tulos on negatiivinen, jos ensimmäinen argumentti (jaettava) on negatiivinen, ja Pythonissa, jos toinen argumentti (jakaja) on nega­tiivinen.  Joissakin ohjelmointi­kielissä, esimerkiksi [[Ruby]]ssa, on lisäksi erikseen funktio "modulo", joka palauttaa residyn jako­jäännöksen sijasta.

Sulku­merkit jätetään joskus merkinnästä pois, esimerkiksi  tai , tai ne merkitään moduluksen ympärille, esimerkiksi or .  Sellaistakin merkintää kuin  näkee joskus käytettävän, mutta se ei ole yksi­selitteinen, ellei sen merkitys ilmene asia­yhteydestä.

===Jakojäännös funktiona ===

Laskutoimitus, jolla jakojäännös (residy) muodostetaan, voidaan esittää käyttä­mällä [[lattiafunktio]]ta.  Jos *b* ≡ *a* (mod *n*), missä *n* > 0, niin kun jako­jäännös *b* on laskettu
:<math>b = a - \left\lfloor \frac{a}{n} \right\rfloor \times n,</math>
missä <math>\left\lfloor \frac{a}{n} \right\rfloor \, </math> on suurin kokonais­luku, joka on pienempi tai yhtä suuri kuin <math>\frac{a}{n}</math>, niin
::<math>\begin{array}{lcl}
a \equiv b \pmod n \text{ and,}\\
0 \le b < n.
\end{array}</math>

Jos sen sijaan on muodostettava *b*, joka on välillä *−n* ≤ *b* < 0, on
:<math>b = a - \left\lfloor \frac{a}{n} \right\rfloor \times n - n.</math>

== Jäännösluokkasysteemit ==
Jokaista jäännös­luokkaa modulo *n* edustamaan voitaisiin valita mikä tahansa siihen kuuluva luku, vaikka yleensä sitä edustamaan valitaan pienin siihen kuuluva ei-negatiivinen luku. On huomattava, että mitkä tahansa kaksi lukua, jotka eivät kuulu samaan jäännös­luokkaan, eivät myöskään ole kongru­entteja modulo *n*. Lisäksi jokainen kokonais­luku kuuluu yhteen ja vain yhteen jäännös­luokkaan modulo *n*.

Kokonaislukujen joukkoa  {0, 1, 2, ..., *n* - 1} sanotaan *'pienimmäksi jäännös­luokka­systeemiksi modulo** ***n***.  Mitä tahansa ''n'' kokonais­luvun joukko, jossa mitkään kaksi eri lukua eivät ole keskenään kongru­entteja modulo ''n'', sanotaan **täydelliseksi jäännös­luokka­systeemiksi modulo** ***n***.

On selvää, että pienin jäännös­luokka­systeemi on täydellinen jäännös­luokka­systeemi ja että täydellinen jäännös­luokka­systeemi on joukko, johon kuuluu yksi edustaja kustakin jäännös­luokasta modulo ''n''. Pienin jäännös­luokka­systeemi modulo 4 on {0, 1, 2, 3}.  Muita täydellisiä jäännös­luokka­systeemejä modulo 4 ovat esimerkiksi:

*{1,2,3,4}
*{13,14,15,16}
*{-2,-1,0,1}
*{-13,4,17,18}
*{-5,0,6,21}
*{27,32,37,42}

Sitä vastoin esimerkiksi seuraavat joukot ''eivät'' ole täydellisiä jäännös­luokka­systeemejä modulo 4:

*{-5,0,6,22}  sillä 6 on kongruentti 22:n kanssa modulo 4.
*{5,15}  sillä täydellisessä jäännös­luokka­systeemissä modulo 4 täytyy olla tasan 4 keskenään epä­kongruenttia lukua.


=== Redusoidut jäännösluokkasysteemit ===
Jokainen kokonais­lukujen φ(''n'') joukko, missä φ(''n'') tarkoittaa [[Eulerin φ-funktio]]ta ja missä nämä luvut ovat 
[[suhteellinen alkuluku|suhteellisia alku­lukuja]] ''n'':n kanssa ja joista mitkään kaksi eivät ole kongruentteja modulo ''n'', on **redusoitu jäännös­luokka­systeemi modulo** ***n***.. Edellä mainittu esimerkki,  {5,15}, on redusoitu jäännös­luokka­systeemi modulo 4.

==Jäännösluokat ==
Kongruenssi modulo **n** on [[ekvivalenssirelaatio]], ja [[ekvivalenssiluokka]]a, johon kokonais­luku ''a'' kuuluu, merkitään 
<math>\overline{a}_n</math>.  Siihen kuuluvat luvut <math>\left\{\ldots, a - 2n, a - n, a, a + n, a + 2n, \ldots \right\}</math>. 
Tätä joukkoa, johon kuuluvat ''a'':n kanssa kongruentit luvut modulo&nbsp;''n'', sanotaan a:n **kongruenssi­luokaksi** tai **jäännös­luokaksi** modulo&nbsp;''n''. Jos modulus ''n'' tunnetaan asia­yhteydestä, sille voidaan käyttää myös merkintää <math>\displaystyle [a]</math>.

==Kokonaisluvut modulo n==

Jäännösluokkien joukkoa modulo ''n'' sanotaan **kokonais­luvuiksi modulo n**, ja sille käytetään merkintää <math>\mathbb{Z}/n\mathbb{Z}</math>, <math>\mathbb{Z}/n</math> tai joskus myös <math>\mathbb{Z}_n</math>. Merkintää <math>\mathbb{Z}_n</math> ei kuitenkaan suositella, koska se saattaa sekaantua [[p-adiset luvut|n-adisten lukujen]] joukkoon.  Jäännös­luokkien joukko määritellään seuraavasti.

:<math>\mathbb{Z}/n\mathbb{Z} = \left\{ \overline{a}_n | a \in \mathbb{Z}\right\}. </math>

Kun ''n''&nbsp;≠&nbsp;0, joukolla <math>\mathbb{Z}/n\mathbb{Z}</math> on ''n'' alkiota ja se voidaan esittää muodossa

:<math>\mathbb{Z}/n\mathbb{Z} = \left\{ \overline{0}_n, \overline{1}_n, \overline{2}_n,\ldots, \overline{n-1}_n \right\}.</math>

Kun ''n'' = 0, joukko <math>\mathbb{Z}/n\mathbb{Z}</math> ei ole [[tyhjä joukko|tyhjä]], sitä vastoin sen on <math>\mathbb{Z}</math>, sillä <math>\overline{a}_0 = \left\{a\right\}</math>.

Yhteen-, vähennys- ja kertolasku joukossa <math>\mathbb{Z}/n\mathbb{Z}</math> voidaan määritellä seuraavasti:

* <math>\overline{a}_n + \overline{b}_n = \overline{(a + b)}_n</math>
* <math>\overline{a}_n - \overline{b}_n = \overline{(a - b)}_n</math>
* <math>\overline{a}_n \overline{b}_n = \overline{(ab)}_n.</math>

Edellä esitetystä seuraa, että tämä on hyvin määritelty.

Varustettuna näillä lasku­toimituksilla  <math>\mathbb{Z}/n\mathbb{Z}</math> on [[Kommutoiva rengas|kommutatiivinen rengas]], jota kutstuaan **jäännösluokkarenkaaksi*'. Esimerkiksi renkaalle <math>\mathbb{Z}/24\mathbb{Z}</math>, pätee
:<math>\overline{12}_{24} + \overline{21}_{24} = \overline{9}_{24}</math>
kuten 24-tuntisen kellon aritmetiikassa.

Merkintää <math>\mathbb{Z}/n\mathbb{Z}</math> käytetään, koska kyseessä on <math>\mathbb{Z}</math>:n [[tekijärengas]] [[ideaali (rengasteoria)|ideaalin]] <math>n\mathbb{Z}</math> suhteen, jonka muodostavat kaikki *n*:llä jaolliset kokonais­luvut, missä <math>0\mathbb{Z}</math> on yksialkioinen joukko <math>\left\{0\right\}</math>. Niinpä <math>\mathbb{Z}/n\mathbb{Z}</math> on [[kunta (matematiikka)|kunta]], jos <math>n\mathbb{Z}</math> on [[maksimaalinen ideaali]], toisin sanoen, jos <math>n</math> on [[alkuluku]].

Joukko-opin termein jäännösluokka  <math>\overline{a}_n</math> on *a*:n [[sivuluokka]] [[tekijäryhmä]]ssä <math>\mathbb{Z}/n\mathbb{Z}</math>, joka on [[syklinen ryhmä]].

Joukolla <math>\mathbb{Z}/n\mathbb{Z}</math> on monia huomattavia matemaattisia ominaisuuksia, joilla on perustava merkitys monilla matematiikan aloilla.

Monissa yhteyksissä, esimerkiksi renkaan [[karakteristika]]a käsiteltäessä, on sopivaa pitää jäännös­luokka­ryhmän erikoistapauksena myös tapausta *n* = 0 eli joukkoa <math>\mathbb{Z}/0\mathbb{Z}</math>.  Kuten edellä jo todettiin, se on isomorfinen kokonais­lukujen renkaan <math>\mathbb{Z}</math> kanssa.

Kun *n* on alkuluku, kokonaislukujen joukko modulo *n* muodostaa samalla [[äärellinen kunta|äärellisen kunnan]].

==Sovelluksia==

Modulaarista aritmetiikkaa sovelletaan [[lukuteoria]]ssa, [[ryhmäteoria]]ssa, [[rengasteoria]]ssa, [[solmuteoria]]ssa, [[abstrakti algebra|abstraktissa algebrassa]], [[tietokonealgebra]]ssa, [[kryptografia]]ssa, [[tietojenkäsittelytiede|tietojen­käsittely­tieteessä]], [[kemia]]ssa sekä jopa [[kuvataide|kuva­taiteissa]] ja [[musiikki|musiikissa]].

Se on yksi lukuteorian perus­pilareista, joka liittyy lähesti tämän matematiikan haaran kaikkiin kysymyksiin, ja se tarjoaa hyviä esimerkkejä ryhmä- ja rengasteorian sekä abstraktin algebran käsitteistä.

Moniin eri yhteyksissä käytettäviin numero­tunnisteisiin kuuluu [[tarkiste]]merkki, joka yleensä määräytyy tunnisteen muiden numeroiden perusteella modulaarisen aritmetiikan keinoin. Esimerkiksi kansain­välisessä pankki­tilin numerossa ([[IBAN]] käytetään modu­laarista aritme­tiikkaa modulo 97 pankki­tilin numeroa syötettäessä mahdollisesti tehtävien virheiden paljastamiseen. Samaan tapaan suomalaisessa [[henkilötunnus|henkilö­tunnuksessa]] viimeinen numero on tarkiste­merkki modulo 31.

Kemikaalien [[CAS-numero]]n viimeinen numero on niin ikään tarkistemerkki. Se lasketaan kertomalla tunnisteen kummankin osan viimeinen numero 1:llä, toiseksi viimeinen 2:lla ja niin edelleen ja ottamalla näin saatujen lukujen summasta jakojäännös modulo 10.




Tietokone­algebrassa modulaarista aritmetiikkaa käytetään usein rajoitettaessa kokonais­luku­kerrointen suuruutta lasku­toimitusten väli­vaiheissa. Kaikki tunnetut tehokkaat [[algoritmi]]t [[polynomin jako tekijöihin|polynomien jakamiseksi tekijöihin]] perustuvat modu­laariseen aritme­tiikkaan. Siihen perustuvat myös tehokkaimmat menetelmät polynomien [[suurin yhteinen tekijä|suurimman yhteisen tekijän]] löytämiseksi sekä monet [[lineaarialgebra]]n ja [[Gröbnerin baasi]]n algoritmit kokonais- ja rationaali­luvuille.

Tietojenkäsittelytieteessä modulaarista aritmetiikka sovelletaan usein [[biteittäinen laskutoimitus|biteittäisessä lasku­toimituksissa]] ja muissa toimituksissa, joissa käytetään kiinteän levyisiä, syklisiä [[tietorakenne|tieto­rakenteita]]. Jako­jäännös­operaatio sellaisena kuin se on valmiina monissa [[ohjelmointikieli]]ssä ja [[laskin|laskimissa]] on tässä yhteydessä usein käytetty modu­laarisen aritme­tiikan sovellus. Esimerkiksi [[XOR]] on kahden bitin summa modulo 2.

Musiikin teoriassa aritmetiikka modulo 12 liittyy läheisesti 12 sävelen [[tasavireisyys|tasa­vireiseen]] järjestelmään, jossa eri [[oktaavi]]en vastaavilla sävelillä on samat nimet ja [[enharmoniset sävelet]] samastetaan (toisin sanoen oktaavin päässä toisistaan olevat sävelet, joiden [[taajuus|taajuuksien]] suhde
on 1:2 tai 2:1 käsitetään ekvivalenteiksi eikä esimerkiksi [[cis]]:n ja [[des]]:n välille tehdä eroa.)

Käsin suoritettujen lasku­toimitusten tulosten tarkistamiseen voidaan helposti käyttää [[yhdeksänkoe]]tta. Se perustuu modu­laariseen aritme­tiikkaan modulo 9 ja erityisesti siihen, että  10 ≡ 1 (mod 9).

Aritmetiikkaan modulo 7 perustuvat menetelmät, joilla voidaan laskea, miksi [[viikonpäivä]]ksi jokin päivä­määrä sattuu. Peri­aatteessa asia voidaan selvittää laskemalla, kuinka monta vuoro­kautta silloin on kulunut jostakin valitusta alku­päivästä, jota vastaava viikon­päivä tunnetaan, ja ottamalla tästä luku­määrästä jako­jäännös 7:llä jaettaessa. Käytän­nölli­sempiä menetelmiä tarjoavat kuitenkin [[Zellerin sääntö]] ja [[doomsday]]-sääntö, mutta nekin perustuvat modu­laari­seen arit­me­tiikkaan modulo 7.

Modulaarisella aritmetiikalla on sovelluksia [[oikeustiede|oikeustieteessä]], [[taloustiede|taloustieteessä]], [[peliteoria]]ssa ja muilla [[yhteiskuntatieteet|yhteis­kunta­tieteiden aloilla]], varsinkin sovelluksissa, joissa resurssien kohden­ta­minen on keskeinen kysymys.
 





== Lähteet ==

* 
* 
* Maarten Bullynck "[http://www.kuttaka.org/Gauss_Modular.pdf Modular Arithmetic before C.F. Gauss. Systematisations and discussions on remainder problems in 18th century Germany] "
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. *Introduction to Algorithms*, Second Edition. MIT Press and McGraw-Hill, 2001. . Section 31.3: Modular arithmetic, pp.&nbsp;862–868.
* [http://genealogy.math.ndsu.nodak.edu/id.php?id=3545 Anthony Gioia], *Number Theory, an Introduction'' Reprint (2001) Dover. 
* 

### Viitteet

## Kirjallisuutta
* 

## Aiheesta muualla

* modular art Modulaarisen aritmetiikan sovelluksia taiteessa
* 
* artikkeli modulaarisesta aritmetiikasta GIMPS-wikissä 
* Modular Arithmetic and patterns in addition and multiplication tables
* Whitney Music Box—an audio/video demonstration of integer modular math