Lähdekoodi sivulle Modulaarinen aritmetiikka

'''Modulaarinen aritmetiikka''' (lyhyemmin '''modulaariaritmetiikka''', joskus myös ''kellotauluaritmetiikka''), on [[kokonaisluku]]ja käsittelevä [[matematiikka|matemaattisen]] [[lukuteoria]]n haara, jossa luvut korvataan niillä [[jakojäännös|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.

[[Tiedosto:Clock group.svg|thumb|right|Ajannäyttö tässä kellossa käyttää aritmetiikkaa modulo 12.]]
Tutun esimerkin modulaarisen aritmetiikan käyttöyhteydestä muodostavat kelloajat. Kun käytetään 12 [[tunti|tunnin]] kelloaikajärjestelmää, johon tavalliset [[kello]]taulut yhä perustuvat, kuusi tuntia kello 9:n jälkeen kello on 3. Tavallisessa [[yhteenlasku]]ssa 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 [[kokonaisluku]]jen [[kongruenssi (lukuteoria)|kongruenssirelaatio]], joka on yhteensopiva kokonaislukujen [[Rengas (matematiikka)|renkaan]] laskutoimitusten — [[yhteenlasku|yhteen-]], [[vähennyslasku|vähennys-]] ja [[kertolasku]]n — kanssa. Jos valitaan jokin positiivinen kokonaisluku ''n'', kahden kokonaisluvun ''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 negatiivisille kokonaisluvuille:

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

Luku ''n'' on kongruenssirelaation ''modulus''.

Jos sekä ''a'' että ''b'' ovat positiivisia, ne ovat kongruentteja modulo ''n'', jos ja vain jos niiden [[jakojäännös|jakojäännökset]] ''n'':llä jaettaessa ovat samat.  Niinpä esimerkiksi

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

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

:<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 laajennettaisiin käsittämään kaikki [[reaaliluku|reaaliluvut]], toisin sanoen vaikka luvut <math>a_1, a_2, b_1, b_2, n\,</math> 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:

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

==Jakojäännökset==

Modulaarisen aritmetiikan käsite liittyy läheisesti [[jakoyhtälö]]ön ja siinä esiintyvään [[jakojäännös|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  {{nowrap|1=2 = 14 (mod 12)}}. Erona jakoyhtälöön verrattuna on kongruenssin käsite, jolle käytetään merkintää "≡" [[yhtäläisyysmerkki|yhtäläisyysmerkin]] "=" asemesta. Lukujen kongruenssi on [[ekvivalenssirelaatio]], johon liittyviä [[ekvivalenssiluokka|ekvivalenssiluokkia]] sanotaan [[jäännösluokka|jäännösluokiksi]]. Kunkin jäännösluokan edustajaksi valitaan tavallisesti sen pienin ei-negatiivinen luku, esimerkiksi  {{nowrap|38 ≡ 2 (mod 12)}}. Tätä sanotaan myös [[residy]]ksi. Tästä seuraa, että vaikka on oikein merkitä   {{nowrap|38 ≡ 14 (mod 12)}}, ja {{nowrap|2 ≡ 14 (mod 12)}}, on väärin merkitä {{nowrap|1=38 = 14 (mod 12)}} (missä "=" esiintyy "≡" -merkin sijasta).

Jokainen [[positiivinen luku|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. [[Negatiivinen luku|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ä {{nowrap|−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 [[ohjelmointikieli]]ssä jakojäännösoperaatiolel käytetään yleensä merkintää "%" (esimerkiksi
[[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 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 [[Ruby]]ssa, on lisäksi erikseen funktio "modulo", joka palauttaa residyn jakojäännöksen sijasta.

Sulkumerkit jätetään joskus merkinnästä pois, esimerkiksi {{nowrap|38 ≡ 14 mod 12}} tai {{nowrap|1=2 = 14 mod 12}}, tai ne merkitään moduluksen ympärille, esimerkiksi or {{nowrap|38 ≡ 14 mod (12)}}.  Sellaistakin merkintää kuin {{nowrap|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ä [[lattiafunktio]]ta.  Jos ''b'' ≡ ''a'' (mod ''n''), missä ''n'' > 0, niin kun jakojää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 kokonaisluku, 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ö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''.<ref>{{kirjaviite | Tekijä = Anthony J. Pettofrezzo, Donald R. Byrkit | Nimeke = Elements of Number Theory | Sivu = 90 | Vuosi = 1970 | Julkaisupaikka = Englewood Cliffs | Julkaisija = Prentice Hall | Tunniste = LCCN 77-81766}}</ref>

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''.<ref>{{kirjaviite | Tekijä = Calvin T. Long | Nimeke = Elementary Introduction to Number Theory (2. painos) | Sivu = 78 | Vuosi = 1972 | Julkaisupaikka = Lexington | Julkaisija = D.C Heath and Company | Tunniste = LCCN 77-171950}}</ref> 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.
<!-- Älä muuta tätä esimerkkiä; siihen viitataan seuraavassa osiossa. -->

=== Redusoidut jäännösluokkasysteemit ===
Jokainen kokonaislukujen φ(''n'') joukko, missä φ(''n'') tarkoittaa [[Eulerin φ-funktio]]ta ja missä nämä luvut ovat 
[[suhteellinen alkuluku|suhteellisia alkulukuja]] ''n'':n kanssa ja joista mitkään kaksi eivät ole kongruentteja modulo ''n'', on '''redusoitu jäännösluokkasysteemi modulo''' '''''n'''''.<ref>Long, s. 85</ref>. Edellä mainittu esimerkki,  {5,15}, on redusoitu jäännösluokkasysteemi modulo 4.

==Jäännösluokat ==
Kongruenssi modulo '''n''' on [[ekvivalenssirelaatio]], ja [[ekvivalenssiluokka]]a, johon kokonaisluku ''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 '''kongruenssiluokaksi''' tai '''[[jäännösluokka|jäännösluokaksi]]''' modulo&nbsp;''n''. Jos modulus ''n'' tunnetaan asiayhteydestä, sille voidaan käyttää myös merkintää <math>\displaystyle [a]</math>.

==Kokonaisluvut modulo n==

Jäännösluokkien joukkoa modulo ''n'' sanotaan '''kokonaisluvuiksi 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ösluokkien 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ä laskutoimituksilla  <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 kokonaisluvut, 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ä]].<ref>{{verkkoviite | Osoite = http://books.google.fi/books?id=nglisrt9IewC&pg=PA293&dq=%22Zn+is+generated+by+1%22&redir_esc=y#v=onepage&q=%22Zn%20is%20generated%20by%201%22&f=false | Nimeke = "Zn is generated by 1" | Viitattu = 23.8.2013}}</ref>

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ösluokkaryhmän erikoistapauksena myös tapausta ''n'' = 0 eli joukkoa <math>\mathbb{Z}/0\mathbb{Z}</math>.  Kuten edellä jo todettiin, se on isomorfinen kokonaislukujen 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|tietojenkäsittelytieteessä]], [[kemia]]ssa sekä jopa [[kuvataide|kuvataiteissa]] ja [[musiikki|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 [[tarkiste]]merkki, 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ötunnus|henkilötunnuksessa]] viimeinen numero on tarkistemerkki modulo 31.<ref>{{verkkoviite | Osoite = http://tarkistusmerkit.teppovuori.fi/tarkmerk.htm | Nimeke = Tarkistusmerkkien laskentamenetelmiä | Kirjoittaja = Teppo Vuori | Ajankohta = 17.8.2013 | Viitattu = 23.8.2013}}</ref>

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.

{{käännettävä}}
<!--
In cryptography, modular arithmetic directly underpins [[public-key cryptography|public key]] systems such as [[RSA (algorithm)|RSA]] and [[Diffie-Hellman key exchange|Diffie-Hellman]], as well as providing [[finite field]]s which underlie [[elliptic curve]]s, and is used in a variety of [[symmetric key algorithm]]s including [[Advanced Encryption Standard|AES]], [[International Data Encryption Algorithm|IDEA]], and [[RC4]].-->

Tietokonealgebrassa modulaarista aritmetiikkaa käytetään usein rajoitettaessa kokonaislukukerrointen suuruutta laskutoimitusten välivaiheissa. Kaikki tunnetut tehokkaat [[algoritmi]]t [[polynomin jako tekijöihin|polynomien jakamiseksi tekijöihin]] perustuvat modulaariseen aritmetiikkaan. 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 rationaaliluvuille.

Tietojenkäsittelytieteessä modulaarista aritmetiikka sovelletaan usein [[biteittäinen laskutoimitus|biteittäisessä laskutoimituksissa]] ja muissa toimituksissa, joissa käytetään kiinteän levyisiä, syklisiä [[tietorakenne|tietorakenteita]]. Jakojäännösoperaatio sellaisena kuin se on valmiina monissa [[ohjelmointikieli]]ssä ja [[laskin|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 [[tasavireisyys|tasavireiseen]] 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 laskutoimitusten tulosten tarkistamiseen voidaan helposti käyttää [[yhdeksänkoe]]tta. 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 [[oikeustiede|oikeustieteessä]], [[taloustiede|taloustieteessä]], [[peliteoria]]ssa ja muilla [[yhteiskuntatieteet|yhteiskuntatieteiden aloilla]], varsinkin sovelluksissa, joissa resurssien kohdentaminen on keskeinen kysymys.
 
{{käännettävä}}
<!--
==Computational complexity==
Since modular arithmetic has such a wide range of applications, it is important to know how hard it is to solve a system of congruences. A linear system of congruences can be solved in [[polynomial time]] with a form of [[Gaussian elimination]], for details see [[linear congruence theorem]].  Algorithms, such as [[Montgomery reduction]], also exist to allow simple arithmetic operations, such as multiplication and [[Modular exponentiation|exponentiation modulo&nbsp;''n'']], to be performed efficiently on large numbers.

Solving a system of non-linear modular arithmetic equations is [[NP-complete]].<ref>{{cite book |first=M. R. |last=Garey |first2=D. S. |last2=Johnson |title=Computers and Intractability, a Guide to the  Theory of NP-Completeness |publisher=W. H. Freeman |year=1979 |isbn=0716710447 }}</ref>
-->

{{käännös|:en:Modular arithmetics}}

== Lähteet ==

* {{verkkoviite | Osoite = http://www.britannica.com/EBchecked/topic/920687/modular-arithmetic | Nimeke = Modular Arithmetic | Julkaisija = Encyclopædia Britannica}}
* {{kirjaviite | Tekijä = Tom M. Apostol | Nimeke = Introduction to analytic number theory, Undergraduate Texts in Mathematics | Luku = 5, 6 | Julkaisija = Springer-Verlag | Julkaisupaikka = New York, Heidelberg | Vuosi = 1975 | Tunniste = | Isbn = 978-0-387-90163-3}}
* 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] {{Wayback|1=http://www.kuttaka.org/Gauss_Modular.pdf |päiväys=20131102014013 }}"
* [[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.&nbsp;862–868.
* [http://genealogy.math.ndsu.nodak.edu/id.php?id=3545 Anthony Gioia], ''Number Theory, an Introduction'' Reprint (2001) Dover. {{ISBN|0-486-41449-3}}
* {{kirjaviite | Tekijä = T. Sengadir | Nimeke = Discrete Mathematics and Combinatorics | Julkaisija = Pearson Education India | Tunniste = | Isbn = 978-81-317-1405-8}}

=== Viitteet ===
{{viitteet}}

== Kirjallisuutta ==
* {{kirjaviite | Kirjoittaja = Michiel Hazewinkel | Luku = Congruence | Nimeke = Encyclopedia of Mathematics | Vuosi = 2001 | Julkaisija = Springer | Tunniste = | Isbn = 978-1-55608-010-4}}

==Aiheesta muualla==
{{commonscat}}
* [http://britton.disted.camosun.bc.ca/modart/jbmodart.htm modular art] Modulaarisen aritmetiikan sovelluksia taiteessa
* {{verkkoviite | Osoite = http://mathworld.wolfram.com/ModularArithmetic.html | Nimeke = Modular Arithmetics | Julkaisija = Wolfram MathWorld}}
* [http://mersennewiki.org/index.php/modular_arithmetic artikkeli modulaarisesta aritmetiikasta GIMPS-wikissä] {{Wayback|1=http://mersennewiki.org/index.php/modular_arithmetic |päiväys=20160220061222 }}
* [http://www.cut-the-knot.org/blue/Modulo.shtml Modular Arithmetic and patterns in addition and multiplication tables]
* [http://wheelof.com/whitney Whitney Music Box]—an audio/video demonstration of integer modular math

[[Luokka:Aritmetiikka]]
[[Luokka:Ryhmäteoria]]
[[Luokka:Rengasteoria]]
[[Luokka:Seulonnan keskeiset artikkelit]]