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:

${\displaystyle a\equiv b{\pmod {n}},\,}$

jos niiden erotus on jaollinen n:llä.

Esimerkiksi

${\displaystyle 38\equiv 14{\pmod {12}}\,}$

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

Sama pätee nega­tiivisille kokonais­luvuille:

${\displaystyle -8\equiv 7{\pmod {5}}.\,}$

${\displaystyle 2\equiv -3{\pmod {5}}.\,}$

${\displaystyle -3\equiv -8{\pmod {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

${\displaystyle 38\equiv 14{\pmod {12}}\,}$

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

${\displaystyle a_{1}\equiv b_{1}{\pmod {n}}}$

ja

${\displaystyle a_{2}\equiv b_{2}{\pmod {n}},}$

niin:

• ${\displaystyle a_{1}+a_{2}\equiv b_{1}+b_{2}{\pmod {n}}\,}$
• ${\displaystyle a_{1}-a_{2}\equiv b_{1}-b_{2}{\pmod {n}}\,}$

Nämä lait pätisivät siinäkin tapauksessa, että teoria laajenne­ttaisiin käsittämään kaikki reaali­luvut, toisin sanoen vaikka luvut ${\displaystyle a_{1},a_{2},b_{1},b_{2},n\,}$ 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:

• ${\displaystyle a_{1}a_{2}\equiv b_{1}b_{2}{\pmod {n}}.\,}$

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 2 = 14 (mod 12). 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 38 ≡ 2 (mod 12). Tätä sanotaan myös residyksi. Tästä seuraa, että vaikka on oikein merkitä 38 ≡ 14 (mod 12), ja 2 ≡ 14 (mod 12), on väärin merkitä 38 = 14 (mod 12) (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ä −5 ≡ −17 (mod 12)), 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 38 ≡ 14 mod 12 tai 2 = 14 mod 12, tai ne merkitään moduluksen ympärille, esimerkiksi or 38 ≡ 14 mod (12). Sellaistakin merkintää kuin 38(mod 12) 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 > 0, niin kun jako­jäännös b on laskettu

${\displaystyle b=a-\left\lfloor {\frac {a}{n}}\right\rfloor \times n,}$

missä ${\displaystyle \left\lfloor {\frac {a}{n}}\right\rfloor \,}$ on suurin kokonais­luku, joka on pienempi tai yhtä suuri kuin ${\displaystyle {\frac {a}{n}}}$, niin

${\displaystyle {\begin{array}{lcl}a\equiv b{\pmod {n}}{\text{ and,}}\\0\leq b<n.\end{array}}}$

Jos sen sijaan on muodostettava b, joka on välillä −n ≤ b < 0, on

${\displaystyle b=a-\left\lfloor {\frac {a}{n}}\right\rfloor \times n-n.}$

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.^[1]

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.^[2] 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 φ-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.^[3]. 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 ${\displaystyle {\overline {a}}_{n}}$. Siihen kuuluvat luvut ${\displaystyle \left\{\ldots ,a-2n,a-n,a,a+n,a+2n,\ldots \right\}}$. 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ää ${\displaystyle \displaystyle [a]}$.

Kokonaisluvut modulo n

Jäännösluokkien joukkoa modulo n sanotaan kokonais­luvuiksi modulo n, ja sille käytetään merkintää ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$, ${\displaystyle \mathbb {Z} /n}$ tai joskus myös ${\displaystyle \mathbb {Z} _{n}}$. Merkintää ${\displaystyle \mathbb {Z} _{n}}$ ei kuitenkaan suositella, koska se saattaa sekaantua n-adisten lukujen joukkoon. Jäännös­luokkien joukko määritellään seuraavasti.

${\displaystyle \mathbb {Z} /n\mathbb {Z} =\left\{{\overline {a}}_{n}|a\in \mathbb {Z} \right\}.}$

Kun n ≠ 0, joukolla ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ on n alkiota ja se voidaan esittää muodossa

${\displaystyle \mathbb {Z} /n\mathbb {Z} =\left\{{\overline {0}}_{n},{\overline {1}}_{n},{\overline {2}}_{n},\ldots ,{\overline {n-1}}_{n}\right\}.}$

Kun n = 0, joukko ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ei ole tyhjä, sitä vastoin sen on ${\displaystyle \mathbb {Z} }$, sillä ${\displaystyle {\overline {a}}_{0}=\left\{a\right\}}$.

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

• ${\displaystyle {\overline {a}}_{n}+{\overline {b}}_{n}={\overline {(a+b)}}_{n}}$
• ${\displaystyle {\overline {a}}_{n}-{\overline {b}}_{n}={\overline {(a-b)}}_{n}}$
• ${\displaystyle {\overline {a}}_{n}{\overline {b}}_{n}={\overline {(ab)}}_{n}.}$

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

Varustettuna näillä lasku­toimituksilla ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ on kommutatiivinen rengas, jota kutstuaan jäännösluokkarenkaaksi. Esimerkiksi renkaalle ${\displaystyle \mathbb {Z} /24\mathbb {Z} }$, pätee

${\displaystyle {\overline {12}}_{24}+{\overline {21}}_{24}={\overline {9}}_{24}}$

kuten 24-tuntisen kellon aritmetiikassa.

Merkintää ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ käytetään, koska kyseessä on ${\displaystyle \mathbb {Z} }$:n tekijärengas ideaalin ${\displaystyle n\mathbb {Z} }$ suhteen, jonka muodostavat kaikki n:llä jaolliset kokonais­luvut, missä ${\displaystyle 0\mathbb {Z} }$ on yksialkioinen joukko ${\displaystyle \left\{0\right\}}$. Niinpä ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ on kunta, jos ${\displaystyle n\mathbb {Z} }$ on maksimaalinen ideaali, toisin sanoen, jos ${\displaystyle n}$ on alkuluku.

Joukko-opin termein jäännösluokka ${\displaystyle {\overline {a}}_{n}}$ on a:n sivuluokka tekijäryhmässä ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$, joka on syklinen ryhmä.^[4]

Joukolla ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ 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 ${\displaystyle \mathbb {Z} /0\mathbb {Z} }$. Kuten edellä jo todettiin, se on isomorfinen kokonais­lukujen renkaan ${\displaystyle \mathbb {Z} }$ 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.^[5]

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.

Tämä artikkeli tai sen osa on tuotu vieraskielisestä lähteestä ja käännös on keskeneräinen. Voit auttaa Wikipediaa tekemällä käännöksen loppuun.

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.

Tämä artikkeli tai sen osa on tuotu vieraskielisestä lähteestä ja käännös on keskeneräinen. Voit auttaa Wikipediaa tekemällä käännöksen loppuun.

Tämä artikkeli tai sen osa on käännetty tai siihen on haettu tietoja muunkielisen Wikipedian artikkelista.
Alkuperäinen artikkeli: en:Modular arithmetics

Lähteet

• Modular Arithmetic Encyclopædia Britannica.
• Tom M. Apostol: ”5, 6”, Introduction to analytic number theory, Undergraduate Texts in Mathematics. New York, Heidelberg: Springer-Verlag, 1975. ISBN 978-0-387-90163-3.
• Maarten Bullynck "Modular Arithmetic before C.F. Gauss. Systematisations and discussions on remainder problems in 18th century Germany (Arkistoitu – Internet Archive)"
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.3: Modular arithmetic, pp. 862–868.
• Anthony Gioia, Number Theory, an Introduction Reprint (2001) Dover. ISBN 0-486-41449-3
• T. Sengadir: Discrete Mathematics and Combinatorics. Pearson Education India. ISBN 978-81-317-1405-8.

Viitteet

Kirjallisuutta

• ”Congruence”, Encyclopedia of Mathematics. Springer, 2001. ISBN 978-1-55608-010-4.

Aiheesta muualla

Wikimedia Commonsissa on kuvia tai muita tiedostoja aiheesta Modulaarinen aritmetiikka.

• modular art Modulaarisen aritmetiikan sovelluksia taiteessa
• Modular Arithmetics Wolfram MathWorld.
• artikkeli modulaarisesta aritmetiikasta GIMPS-wikissä (Arkistoitu – Internet Archive)
• Modular Arithmetic and patterns in addition and multiplication tables
• Whitney Music Box—an audio/video demonstration of integer modular math