Modulaarinen aritmetiikka
Modulaarinen aritmetiikka (lyhyemmin modulaariaritmetiikka, joskus myös kellotauluaritmetiikka), on kokonaislukuja käsittelevä matemaattisen lukuteorian haara, jossa luvut korvataan niillä jakojää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ähestymistavan modulaariselle aritmetiikalle kehitti Carl Friedrich Gauss teoksessaan Disquisitiones Arithmeticae, joka julkaistiin vuonna 1801.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Clock_group.svg/250px-Clock_group.svg.png)
Tutun esimerkin modulaarisen aritmetiikan käyttöyhteydestä muodostavat kelloajat. Kun käytetään 12 tunnin kelloaikajä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 kelloajat alkavat uudestaan alusta, sillä vuorokausi on jaettu kahteen 12 tunnin jaksoon. Näin ollen tunnit noudattavat modulaarista aritmetiikkaa modulo 12. Nykyisin useimmissa maissa käytetään kuitenkin virallisesti 24 tunnin järjestelmää, jossa kelloajat 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ä modulaarinen aritmetiikka modulo 24.
Kongruenssirelaatio
Modulaarista aritmetiikkaa voidaan käsitellä matemaattisesti ottamalla käyttöön kokonaislukujen kongruenssirelaatio, joka on yhteensopiva kokonaislukujen renkaan laskutoimitusten — yhteen-, vähennys- ja kertolaskun — kanssa. Jos valitaan jokin positiivinen kokonaisluku n, kahden kokonaisluvun a ja b sanotaan olevan kongruentteja modulo n, mikä merkitään:
jos niiden erotus on jaollinen n:llä.
Esimerkiksi
koska 38 − 14 = 24, joka on jaollinen 12:lla.
Sama pätee negatiivisille kokonaisluvuille:
Luku n on kongruenssirelaation modulus.
Jos sekä a että b ovat positiivisia, ne ovat kongruentteja modulo n, jos ja vain jos niiden jakojäännökset n:llä jaettaessa ovat samat. Niinpä esimerkiksi
koska lukujen 38 ja 14 jakojäännös 12:lla jaettaessa on sama, 2.
Merkintätavasta on huomattava, että koska samassa yhteydessä saatetaan käyttää useita kongruenssirelaatioita, 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 kaksipaikkainen on binäärirelaatio.
Kongruenssirelaation yhteensopivuus peruslaskutoimitusten kanssa merkitsee sitä, että se noudattaa seuraavia lakeja:
Jos
ja
niin:
Nämä lait pätisivät siinäkin tapauksessa, että teoria laajennettaisiin käsittämään kaikki reaaliluvut, toisin sanoen vaikka luvut eivät kaikki olisikaan kokonaislukuja, mutta kongruenssi määriteltäisiin reaaliluvuille muutoin samaan tapaan kuin edellä. Seuraava ominaisuus pätee kuitenkin vain, jos ne kaikki ovat kokonaislukuja:
Jakojäännökset
Modulaarisen aritmetiikan käsite liittyy läheisesti jakoyhtälöön ja siinä esiintyvään jakojäännökseen. Jakojäännöksen määrittämistä nimitetäänkin joskus modulo-operaatioksi, ja joskus näkee käytettävän sellaistakin merkintää kuin 2 = 14 (mod 12). Erona jakoyhtälöön verrattuna on kongruenssin käsite, jolle käytetään merkintää "≡" yhtäläisyysmerkin "=" asemesta. Lukujen kongruenssi on ekvivalenssirelaatio, johon liittyviä ekvivalenssiluokkia sanotaan jäännösluokiksi. Kunkin jäännösluokan edustajaksi valitaan tavallisesti sen pienin ei-negatiivinen 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 kokonaisluku kuuluu kongruenssirelaatiossa siihen jäännösluokkaan, jonka edustajana on sen jakojäännös moduluksella jaettaessa. Tällöin siis residy on sama kuin jakojäännös. Negatiivisten kokonaislukujen tapauksessa asia on kuitenkin toisin, koska jakojäännös tavalliseen tapaan laskettuna on tällöin negatiivinen. Niinpä esimerkiksi luvun -17 jakojäännös 12:lla jaettaessa on -5 (sillä −5 ≡ −17 (mod 12)), mutta kongruenssirelaatiossa luvut -17 ja -5 kuuluvat ekvivalenssiluokkaan, jota edustamaan valitaan luku 7. Tämä on siis luvun -17 residy 12:lla jaettaessa.
Tietokoneiden ohjelmointikielissä jakojäännösoperaatiolel käytetään yleensä merkintää "%" (esimerkiksi C:ssä, Javassa, Perlissä ja Pythonissa) tai "mod" (esimerkiksi Pascalissa, BASICissa, SQL;ssä ja Haskellissa), poikkeuksena muun muassa Excel. Nämä antavat tulokseksi jakojää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 negatiivinen. Joissakin ohjelmointikielissä, esimerkiksi Rubyssa, on lisäksi erikseen funktio "modulo", joka palauttaa residyn jakojäännöksen sijasta.
Sulkumerkit 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 yksiselitteinen, ellei sen merkitys ilmene asiayhteydestä.
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 jakojäännös b on laskettu
missä on suurin kokonaisluku, joka on pienempi tai yhtä suuri kuin , niin
Jos sen sijaan on muodostettava b, joka on välillä −n ≤ b < 0, on
Jäännösluokkasysteemit
Jokaista jäännösluokkaa 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ösluokkaan, eivät myöskään ole kongruentteja modulo n. Lisäksi jokainen kokonaisluku kuuluu yhteen ja vain yhteen jäännösluokkaan modulo n.[1]
Kokonaislukujen joukkoa {0, 1, 2, ..., n - 1} sanotaan pienimmäksi jäännösluokkasysteemiksi modulo n. Mitä tahansa n kokonaisluvun joukko, jossa mitkään kaksi eri lukua eivät ole keskenään kongruentteja modulo n, sanotaan täydelliseksi jäännösluokkasysteemiksi modulo n.
On selvää, että pienin jäännösluokkasysteemi on täydellinen jäännösluokkasysteemi ja että täydellinen jäännösluokkasysteemi on joukko, johon kuuluu yksi edustaja kustakin jäännösluokasta modulo n.[2] Pienin jäännösluokkasysteemi modulo 4 on {0, 1, 2, 3}. Muita täydellisiä jäännösluokkasysteemejä 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ösluokkasysteemejä modulo 4:
- {-5,0,6,22} sillä 6 on kongruentti 22:n kanssa modulo 4.
- {5,15} sillä täydellisessä jäännösluokkasysteemissä modulo 4 täytyy olla tasan 4 keskenään epäkongruenttia lukua.
Redusoidut jäännösluokkasysteemit
Jokainen kokonaislukujen φ(n) joukko, missä φ(n) tarkoittaa Eulerin φ-funktiota ja missä nämä luvut ovat suhteellisia alkulukuja n:n kanssa ja joista mitkään kaksi eivät ole kongruentteja modulo n, on redusoitu jäännösluokkasysteemi modulo n.[3]. Edellä mainittu esimerkki, {5,15}, on redusoitu jäännösluokkasysteemi modulo 4.
Jäännösluokat
Kongruenssi modulo n on ekvivalenssirelaatio, ja ekvivalenssiluokkaa, johon kokonaisluku a kuuluu, merkitään . Siihen kuuluvat luvut . Tätä joukkoa, johon kuuluvat a:n kanssa kongruentit luvut modulo n, sanotaan a:n kongruenssiluokaksi tai jäännösluokaksi modulo n. Jos modulus n tunnetaan asiayhteydestä, sille voidaan käyttää myös merkintää .
Kokonaisluvut modulo n
Jäännösluokkien joukkoa modulo n sanotaan kokonaisluvuiksi modulo n, ja sille käytetään merkintää , tai joskus myös . Merkintää ei kuitenkaan suositella, koska se saattaa sekaantua n-adisten lukujen joukkoon. Jäännösluokkien joukko määritellään seuraavasti.
Kun n ≠ 0, joukolla on n alkiota ja se voidaan esittää muodossa
Kun n = 0, joukko ei ole tyhjä, sitä vastoin sen on , sillä .
Yhteen-, vähennys- ja kertolasku joukossa voidaan määritellä seuraavasti:
Edellä esitetystä seuraa, että tämä on hyvin määritelty.
Varustettuna näillä laskutoimituksilla on kommutatiivinen rengas, jota kutstuaan jäännösluokkarenkaaksi. Esimerkiksi renkaalle , pätee
kuten 24-tuntisen kellon aritmetiikassa.
Merkintää käytetään, koska kyseessä on :n tekijärengas ideaalin suhteen, jonka muodostavat kaikki n:llä jaolliset kokonaisluvut, missä on yksialkioinen joukko . Niinpä on kunta, jos on maksimaalinen ideaali, toisin sanoen, jos on alkuluku.
Joukko-opin termein jäännösluokka on a:n sivuluokka tekijäryhmässä , joka on syklinen ryhmä.[4]
Joukolla 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ösluokkaryhmän erikoistapauksena myös tapausta n = 0 eli joukkoa . Kuten edellä jo todettiin, se on isomorfinen kokonaislukujen renkaan 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, tietojenkäsittelytieteessä, kemiassa sekä jopa kuvataiteissa ja musiikissa.
Se on yksi lukuteorian peruspilareista, 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 numerotunnisteisiin kuuluu tarkistemerkki, joka yleensä määräytyy tunnisteen muiden numeroiden perusteella modulaarisen aritmetiikan keinoin. Esimerkiksi kansainvälisessä pankkitilin numerossa (IBAN käytetään modulaarista aritmetiikkaa modulo 97 pankkitilin numeroa syötettäessä mahdollisesti tehtävien virheiden paljastamiseen. Samaan tapaan suomalaisessa henkilötunnuksessa viimeinen numero on tarkistemerkki 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. |
Tietokonealgebrassa modulaarista aritmetiikkaa käytetään usein rajoitettaessa kokonaislukukerrointen suuruutta laskutoimitusten välivaiheissa. Kaikki tunnetut tehokkaat algoritmit polynomien jakamiseksi tekijöihin perustuvat modulaariseen aritmetiikkaan. 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 rationaaliluvuille.
Tietojenkäsittelytieteessä modulaarista aritmetiikka sovelletaan usein biteittäisessä laskutoimituksissa ja muissa toimituksissa, joissa käytetään kiinteän levyisiä, syklisiä tietorakenteita. Jakojäännösoperaatio sellaisena kuin se on valmiina monissa ohjelmointikielissä ja laskimissa on tässä yhteydessä usein käytetty modulaarisen aritmetiikan sovellus. Esimerkiksi XOR on kahden bitin summa modulo 2.
Musiikin teoriassa aritmetiikka modulo 12 liittyy läheisesti 12 sävelen tasavireiseen 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 laskutoimitusten tulosten tarkistamiseen voidaan helposti käyttää yhdeksänkoetta. Se perustuu modulaariseen aritmetiikkaan 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. Periaatteessa asia voidaan selvittää laskemalla, kuinka monta vuorokautta silloin on kulunut jostakin valitusta alkupäivästä, jota vastaava viikonpäivä tunnetaan, ja ottamalla tästä lukumäärästä jakojäännös 7:llä jaettaessa. Käytännöllisempiä menetelmiä tarjoavat kuitenkin Zellerin sääntö ja doomsday-sääntö, mutta nekin perustuvat modulaariseen aritmetiikkaan modulo 7.
Modulaarisella aritmetiikalla on sovelluksia oikeustieteessä, taloustieteessä, peliteoriassa ja muilla yhteiskuntatieteiden aloilla, varsinkin sovelluksissa, joissa resurssien kohdentaminen 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. |
![Käännös suomeksi](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2a/Translation_Latin_Alphabet.svg/60px-Translation_Latin_Alphabet.svg.png)
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
- ↑ Anthony J. Pettofrezzo, Donald R. Byrkit: Elements of Number Theory, s. 90. Englewood Cliffs: Prentice Hall, 1970. LCCN 77-81766.
- ↑ Calvin T. Long: Elementary Introduction to Number Theory (2. painos), s. 78. Lexington: D.C Heath and Company, 1972. LCCN 77-171950.
- ↑ Long, s. 85
- ↑ "Zn is generated by 1" books.google.fi. Viitattu 23.8.2013.
- ↑ Tarkistusmerkkien laskentamenetelmiä tarkistusmerkit.teppovuori.fi. 17.8.2013. Viitattu 23.8.2013.
Kirjallisuutta
- ”Congruence”, Encyclopedia of Mathematics. Springer, 2001. ISBN 978-1-55608-010-4.
Aiheesta muualla
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png)
- 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