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 n", mikä merkitään:
formula_1
jos niiden erotus on jaollinen "n":llä.
Esimerkiksi
formula_2
koska 38 − 14 = 24, joka on jaollinen 12:lla.
Sama pätee nega­tiivisille kokonais­luvuille:
formula_3
formula_4
formula_5
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ökset "n":llä jaettaessa ovat samat. Niinpä esi­merkiksi
formula_2
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
formula_7
ja
formula_8
niin:
Nämä lait pätisivät siinäkin tapauksessa, että teoria laajenne­ttaisiin käsittämään kaikki reaali­luvut, toisin sanoen vaikka luvut formula_11 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:
Jakojäännökset.
Modulaarisen aritme­tiikan käsite liittyy läheisesti jakoyhtälöön ja siinä esiintyvään 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äisyys­merkin "=" asemesta. Lukujen kongruenssi on ekvivalenssirelaatio, johon liittyviä ekvivalenssi­luokkia sanotaan jäännös­luokiksi. Kunkin jäännös­luokan edustajaksi valitaan tavallisesti sen pienin ei-nega­tiivinen luku, esimerkiksi . Tätä sanotaan myös residyksi. Tästä seuraa, että vaikka on oikein merkitä , ja , on väärin merkitä (missä "=" esiintyy "≡" -merkin sijasta).
Jokainen 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. 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 ohjelmointikielissä jako­jäännös­operaatiolel käytetään yleensä merkintää "%" (esi­merkiksi
C:ssä, Javassa, Perlissä ja Pythonissa) tai "mod"
(esimerkiksi Pascalissa, BASICissa, SQL;ssä ja Haskellissa), 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 Rubyssa, 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ä lattiafunktiota. Jos "b" ≡ "a" (mod "n"), missä "n" &gt; 0, niin kun jako­jäännös "b" on laskettu
formula_13
missä formula_14 on suurin kokonais­luku, joka on pienempi tai yhtä suuri kuin formula_15, niin
formula_16
Jos sen sijaan on muodostettava "b", joka on välillä "−n" ≤ "b" &lt; 0, on
formula_17
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:
Sitä vastoin esimerkiksi seuraavat joukot "eivät" ole täydellisiä jäännös­luokka­systeemejä modulo 4:
Redusoidut jäännösluokkasysteemit.
Jokainen kokonais­lukujen φ("n") joukko, missä φ("n") tarkoittaa Eulerin φ-funktiota ja missä nämä luvut ovat 
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 ekvivalenssiluokkaa, johon kokonais­luku "a" kuuluu, merkitään 
formula_18. Siihen kuuluvat luvut formula_19. 
Tätä joukkoa, johon kuuluvat "a":n kanssa kongruentit luvut modulo "n", sanotaan a:n kongruenssi­luokaksi tai jäännös­luokaksi modulo "n". Jos modulus "n" tunnetaan asia­yhteydestä, sille voidaan käyttää myös merkintää formula_20.
Kokonaisluvut modulo n.
Jäännösluokkien joukkoa modulo "n" sanotaan kokonais­luvuiksi modulo n, ja sille käytetään merkintää formula_21, formula_22 tai joskus myös formula_23. Merkintää formula_23 ei kuitenkaan suositella, koska se saattaa sekaantua n-adisten lukujen joukkoon. Jäännös­luokkien joukko määritellään seuraavasti.
formula_25
Kun "n" ≠ 0, joukolla formula_21 on "n" alkiota ja se voidaan esittää muodossa
formula_27
Kun "n" = 0, joukko formula_21 ei ole tyhjä, sitä vastoin sen on formula_29, sillä formula_30.
Yhteen-, vähennys- ja kertolasku joukossa formula_21 voidaan määritellä seuraavasti:
Edellä esitetystä seuraa, että tämä on hyvin määritelty.
Varustettuna näillä lasku­toimituksilla formula_21 on kommutatiivinen rengas, jota kutstuaan jäännösluokkarenkaaksi. Esimerkiksi renkaalle formula_36, pätee
formula_37
kuten 24-tuntisen kellon aritmetiikassa.
Merkintää formula_21 käytetään, koska kyseessä on formula_29:n tekijärengas ideaalin formula_40 suhteen, jonka muodostavat kaikki "n":llä jaolliset kokonais­luvut, missä formula_41 on yksialkioinen joukko formula_42. Niinpä formula_21 on kunta, jos formula_40 on maksimaalinen ideaali, toisin sanoen, jos formula_45 on alkuluku.
Joukko-opin termein jäännösluokka formula_18 on "a":n sivuluokka tekijäryhmässä formula_21, joka on syklinen ryhmä.
Joukolla formula_21 on monia huomattavia matemaattisia ominaisuuksia, joilla on perustava merkitys monilla matematiikan aloilla.
Monissa yhteyksissä, esimerkiksi renkaan karakteristikaa käsiteltäessä, on sopivaa pitää jäännös­luokka­ryhmän erikoistapauksena myös tapausta "n" = 0 eli joukkoa formula_49. Kuten edellä jo todettiin, se on isomorfinen kokonais­lukujen renkaan formula_29 kanssa.
Kun "n" on alkuluku, kokonaislukujen joukko modulo "n" muodostaa samalla äärellisen kunnan.
Sovelluksia.
Modulaarista aritmetiikkaa sovelletaan lukuteoriassa, ryhmäteoriassa, rengasteoriassa, solmuteoriassa, abstraktissa algebrassa, tietokonealgebrassa, kryptografiassa, tietojen­käsittely­tieteessä, kemiassa sekä jopa kuva­taiteissa ja 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 tarkistemerkki, 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ö­tunnuksessa viimeinen numero on tarkiste­merkki modulo 31.
Kemikaalien CAS-numeron 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 algoritmit polynomien jakamiseksi tekijöihin perustuvat modu­laariseen aritme­tiikkaan. Siihen perustuvat myös tehokkaimmat menetelmät polynomien suurimman yhteisen tekijän löytämiseksi sekä monet lineaarialgebran ja Gröbnerin baasin algoritmit kokonais- ja rationaali­luvuille.
Tietojenkäsittelytieteessä modulaarista aritmetiikka sovelletaan usein biteittäisessä lasku­toimituksissa ja muissa toimituksissa, joissa käytetään kiinteän levyisiä, syklisiä tieto­rakenteita. Jako­jäännös­operaatio sellaisena kuin se on valmiina monissa ohjelmointikielissä ja 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 tasa­vireiseen järjestelmään, jossa eri oktaavien vastaavilla sävelillä on samat nimet ja enharmoniset sävelet samastetaan (toisin sanoen oktaavin päässä toisistaan olevat sävelet, joiden 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änkoetta. 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 oikeustieteessä, taloustieteessä, peliteoriassa ja muilla yhteis­kunta­tieteiden aloilla, varsinkin sovelluksissa, joissa resurssien kohden­ta­minen on keskeinen kysymys.