Ogled vira Modularna aritmetika

[[Slika:Clock_group.svg|desno|sličica|250x250_pik|Ustaljen čas na tej se lahko izvaja z uporabo aritmetičnega modula 12.]]
V [[Matematika|matematiki]] je '''modularna aritmetika''' sistem [[Aritmetika|aritmetike]] za [[Celo število|cela števila]], kjer se števila "ponovno vrtijo okoli", ko dosežejo določeno vrednost, ki se imenuje '''modulo''' (ali '''modul'''). Moderni približek modularni aritmetiki je uveljavil [[Carl Friedrich Gauss]] v svoji knjigi ''[[Disquisitiones Arithmeticae]]'', ki jo je izdal leta 1801.

Vsem poznana uporaba modularne aritmetike je [[12-urna ura]], kjer je dan razdeljen na dve 12-urni periodi. Če je sedaj ura 7:00, bo čez 8 ur enaka 3:00. Navadno seštevanje bi nam dalo rezultat {{Brez preloma|7 + 8 {{=}} 15}}, a to ne bo odgovor, ker se čas po uri "obrne naokoli" na vsakih 12 ur. Ker se številke na uri ponastavijo, ko pridejo do 12, ima ura aritmetični ''modul'' enak 12. Če to izrazimo s spodnjo definicijo, je 15 ''kongruentno'' 3 v modulu 12, torej je ([[24-urna ura|24-urni]]) čas "15:00" enak času "3:00" na uri.

== Definicije relacij v konguencah ==
Modularna aritmetika se lahko obravnava matematično z vpeljavo [[Kongruenčna relacija|kongruenčne relacije]] na [[Celo število|celih številih]], ki se da združiti z operacijami na celih številih: [[seštevanje]], [[odštevanje]] in [[množenje]]. Za naravno število {{Matematična formula|''n''}}, sta dve števili {{Matematična formula|''a''}} in {{Matematična formula|''b''}} ''{{Dfn|kongruentni v modulu&nbsp;{{math|n}}}}'', če je njuna razlika {{Matematična formula|''a'' − ''b''}} [[Večkratnik|celi večkratnik]] od {{Matematična formula|''n''}} (torej če obstaja tako celo število {{Matematična formula|''k''}}, da velja {{Matematična formula|1=''a'' − ''b'' = ''kn''}}). Ta [[kongruenčna relacija]] se običajno šteje, ko sta {{Matematična formula|''a''}} in {{Matematična formula|''b''}} celi števili, označi pa se jo z:

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

Oklepaji pomenijo, da {{Matematična formula|(mod ''n'')}} velja za celo enačbo, ne samo za desno stran (v tem primeru b).
Včasih se uporablja tudi {{Matematična formula|1==}} namesto {{Matematična formula|≡}}. Če se oklepaje izpusti, pomeni to v splošnem, da označuje "mod" [[Modulo|operacijo modulo]], ki se nanaša samo na desno stran, spremeni pa se tudi v enakost, da velja {{Matematična formula|0 ≤ ''a'' < ''n''}}.

Število {{Matematična formula|''n''}} se imenuje ''modul'' kongruence.

Kongruenčna relacija se lahko zapiše tudi kot

: <math>a = kn + b,</math>

kar eksplicitno prikaže [[Evklidsko deljenje]]. Kaj pa če {{Matematična formula|''b''}} ni ostanek števila {{Matematična formula|''a''}} pri deljenju z {{Matematična formula|''n''}}? Bolj natančno lahko relacijo {{Matematična formula|''a'' ≡ ''b'' mod ''n''}} opišemo tako, da morata tako {{Matematična formula|''a''}}, kot tudi {{Matematična formula|''b''}} imeti enak ostanek pri deljenju z {{Matematična formula|''n''}}. Torej

: <math>a = pn + r,</math>
: <math>b = qn + r,</math>

kjer je {{Matematična formula|0 ≤ ''r'' < ''n''}} skupni delitelj. Če odštejemo ta dva izraza, pridemo do prejšnje relacije:

: <math>a - b = kn,</math>

kjer definiramo {{Matematična formula|1=''k'' = ''p'' − ''q''.}}

=== Primeri ===
Na primer

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

ker je {{Matematična formula|38 − 14 {{=}} 24}}, kar je večkratnik od 12, ali, ekvivalentno, ker imata tako 38, kot tudi 14 enak ostanek 2 pri deljenju z 12.

Enako pravilo velja tudi za negativne vrednosti:

: <math> \begin{align}
-8 &\equiv 7 \pmod 5\\
2 &\equiv -3 \pmod 5\\
 -3 &\equiv -8 \pmod 5.
\end{align}</math>

Ker se lahko pogosto pojavi več relacij, kjer so različni moduli naenkrat, smo v zgornji sistem vedno zapisali modulo. Kongruenčna relacija za dani modul velja za  [[binarna relacija|binarno relacijo]].

== Lastnosti ==
Kongruenčna relacija zadovolji vsem pogojem za [[Ekvivalenčna relacija|ekvivalenčno relacijo]]:

* Refleksivnost: {{Matematična formula|''a'' ≡ ''a'' (mod ''n'')}}
* Simetrija: {{Matematična formula|''a'' ≡ ''b'' (mod ''n'')}} če {{Matematična formula|''b'' ≡ ''a'' (mod ''n'')}} za vse {{Matematična formula|''a''}}, {{Matematična formula|''b''}} in {{Matematična formula|''n''}}.
* Tranzitivnost: Če {{Matematična formula|''a'' ≡ ''b'' (mod ''n'')}} in {{Matematična formula|''b'' ≡ ''c'' (mod ''n'')}}, potem {{Matematična formula|''a'' ≡ ''c'' (mod ''n'')}}

Če velja {{Matematična formula|''a''<sub>1</sub> ≡ ''b''<sub>1</sub> (mod ''n'')}} in {{Matematična formula|''a''<sub>2</sub> ≡ ''b''<sub>2</sub> (mod ''n''),}} ali če velja {{Matematična formula|''a'' ≡ ''b'' (mod ''n''),}} potem:

* {{Matematična formula|''a'' + ''k'' ≡ ''b'' + ''k'' (mod ''n'')}} za katerokoli celo število {{Matematična formula|''k''}} (kar se sklada s premikom)
* {{Matematična formula|''k a'' ≡ ''k b'' (mod ''n'')}} za katerokoli celo število {{Matematična formula|''k''}} (kar je skladno s povečanjem)
* {{Matematična formula|''a''<sub>1</sub> + ''a''<sub>2</sub> ≡ ''b''<sub>1</sub> + ''b''<sub>2</sub> (mod ''n'')}} (skladno s seštevanjem)
* {{Matematična formula|''a''<sub>1</sub> – ''a''<sub>2</sub> ≡ ''b''<sub>1</sub> – ''b''<sub>2</sub> (mod ''n'')}} (skladno z odštevanjem)
* {{Matematična formula|''a''<sub>1</sub> ''a''<sub>2</sub> ≡ ''b''<sub>1</sub> ''b''<sub>2</sub> (mod ''n'')}} (skladno z množenjem)
* {{Matematična formula|''a''<sup>''k''</sup> ≡ ''b''<sup>''k''</sup> (mod ''n'')}} za katerokoli nenegativno celo število {{Matematična formula|''k''}} (skladno s potenciranjem)
* {{Matematična formula|''p''(''a'') ≡ ''p''(''b'') (mod ''n'')}}, za katerikoli [[polinom]] {{Matematična formula|''p''(''x'')}} s celimi koeficienti (kar je skladno s polinomsko evaluacijo)

Če je {{Matematična formula|''a'' ≡ ''b'' (mod ''n'')}}, potem v splošnem ni pravilno {{Matematična formula|''k<sup>a</sup>'' ≡ ''k<sup>b</sup>'' (mod ''n'')}}. A to velja, če velja sledeči pogoj:

* Če velja {{Matematična formula|''c'' ≡ ''d'' (mod ''φ''(''n'')),}} kjer je {{Matematična formula|''φ''}} [[Eulerjeva funkcija fi|Eulerjeva funkcija]], potem {{Matematična formula|''a''<sup>''c''</sup> ≡ ''a''<sup>''d''</sup> (mod ''n'')}}, če je {{Matematična formula|''a''}} [[Tuje število|tuja]] z {{Matematična formula|''n''}}

Za pokrajšanje skupnih členov, poznamo sledeča pravila:

* Če je {{Matematična formula|''a'' + ''k'' ≡ ''b'' + ''k'' (mod ''n'')}} za katerokoli celo število {{Matematična formula|''k''}}, potem je {{Matematična formula|''a'' ≡ ''b'' (mod ''n'')}}
* Če je {{Matematična formula|''k a'' ≡ ''k b'' (mod ''n'')}} in sta si {{Matematična formula|''k''}} in {{Matematična formula|''n''}} tuji si števili, potem je {{Matematična formula|''a'' ≡ ''b'' (mod ''n'')}}

[[Modularni multiplikativni inverz]] je definiran s sledečimi pravili:

* Obstoj: obstaja celo število, ki je označeno z {{Matematična formula|''a''<sup>–1</sup>}}, da velja {{Matematična formula|''aa''<sup>–1</sup> ≡ 1 (mod ''n'')}} če in samo če je {{Matematična formula|''a''}} tuje z {{Matematična formula|''n''}}. To število {{Matematična formula|''a''<sup>–1</sup>}} se imenuje ''modularni multiplikativni inverz'' modula {{Matematična formula|''n''}}.
* Če je {{Matematična formula|''a'' ≡ ''b'' (mod ''n'')}} in obstaja {{Matematična formula|''a''<sup>–1</sup>}}, potem je {{Matematična formula|''a''<sup>–1</sup> ≡ ''b''<sup>–1</sup> (mod ''n'')}} (skladno z multiplikativnim inverzom in če ima {{Matematična formula|1=''a'' = ''b''}} edinstven modul {{Matematična formula|''n''}})
* Če je {{Matematična formula|''a x'' ≡ ''b'' (mod ''n'')}} in {{Matematična formula|''a''}} je tuje {{Matematična formula|''n''}}, potem je rešitev te linearne kongruence podana z {{Matematična formula|''x'' ≡ ''a''<sup>–1</sup>''b'' (mod ''n'')}}

Multiplikativni inverz {{Matematična formula|''x'' ≡ ''a''<sup>–1</sup> (mod ''n'')}}  se lahko učinkovito izračuna z uporabo [[Bézoutova identiteta|Bézoutove identitete]] <math>ax + ny = 1</math> za <math>x,y</math> z uporabo [[Razširjeni Evklidov algoritem|razširjenega Evklidovega algoritma]]. V posebnem, če je {{Matematična formula|''p''}} praštevilo, potem sta si {{Matematična formula|''a''}} in {{Matematična formula|''p''}} tuji za vsak {{Matematična formula|''a''}}, da velja {{Matematična formula|0 < ''a'' < ''p''}}; torej multiplikativni inverz obstaja za vse {{Matematična formula|''a''}}, ki niso kongruentni ničelnemu modulu {{Matematična formula|''p''}}.

Nekaj nekaterih bolj naprednih lastnosti kongruenčnih relacij je zbranih tukaj:

* [[Fermatov mali izrek]]: Če je {{Matematična formula|''p''}} praštevilo in ne deli {{Matematična formula|''a''}}, potem {{Matematična formula|''a'' <sup>''p'' – 1</sup> ≡ 1 (mod ''p'')}}.
* [[Eulerjev izrek]]: Če sta si {{Matematična formula|''a''}} in {{Matematična formula|''n''}} tuji si števili, potem velja {{Matematična formula|''a'' <sup>''φ''(''n'')</sup> ≡ 1 (mod ''n'')}}, kjer je {{Matematična formula|''φ''}} [[Eulerjeva funkcija fi]]
* Preprosta posledica Fermatovega malega izreka je: če je {{Matematična formula|''p''}} praštevilo, potem je {{Matematična formula|''a''<sup>−1</sup> ≡ ''a'' <sup>''p'' − 2</sup> (mod ''p'')}} multiplikativni inverz od {{Matematična formula|0 < ''a'' < ''p''}}. Še bolj splošno iz Eulerjevega izreka: če sta si {{Matematična formula|''a''}} in {{Matematična formula|''n''}} tuji, potem je {{Matematična formula|''a''<sup>−1</sup> ≡ ''a'' <sup>''φ''(''n'') − 1</sup> (mod ''n'')}}.
* Druga preprosta posledica je, da če velja {{Matematična formula|''a'' ≡ ''b'' (mod ''φ''(''n'')),}} kjer je {{Matematična formula|''φ''}} Eulerjeva fi funkcija, potem velja {{Matematična formula|''k''<sup>''a''</sup> ≡ ''k''<sup>''b''</sup> (mod ''n'')}}, kjer je {{Matematična formula|''k''}} [[Tuje število|tuje]] z {{Matematična formula|''n''}}.
* [[Wilsonov izrek]]: {{Matematična formula|''p''}} je praštevilo, če in samo če velja {{Matematična formula|(''p'' − 1)! ≡ −1 (mod ''p'')}}.
* [[Kitajski izrek o ostankih]]: Za katerakoli {{Matematična formula|''a''}} in {{Matematična formula|''b''}} ter tuji števili {{Matematična formula|''m''}} in {{Matematična formula|''n''}}, obstaja unikatno celo število {{Matematična formula|''x'' (mod ''mn'')}}, da velja {{Matematična formula|''x'' ≡ ''a'' (mod ''m'')}} in {{Matematična formula|''x'' ≡ ''b'' (mod ''n'')}}. Velja tudi {{Matematična formula|''x'' ≡ ''b m''<sub>''n''</sub><sup>–1</sup> ''m'' + ''a n''<sub>''m''</sub><sup>–1</sup> ''n'' (mod ''mn'')}}, kjer je {{Matematična formula|''m''<sub>''n''</sub><sup>−1</sup>}} inverz od {{Matematična formula|''m''}} modulo {{Matematična formula|''n''}} in {{Matematična formula|''n''<sub>''m''</sub><sup>−1</sup>}} je inverz od {{Matematična formula|''n''}} modulo {{Matematična formula|''m''}}.
* [[Lagrangeov izrek (teorija števil)|Lagrangeov izrek]]: Kongruenca {{Matematična formula|''f'' (''x'') ≡ 0 (mod ''p'')}}, kjer je {{Matematična formula|''p''}} praštevilo in {{Matematična formula|''f'' (''x'') {{=}} ''a''<sub>0</sub> ''x''<sup>''n''</sup> + ... + ''a''<sub>''n''</sub>}} je [[polinom]] s celimi koeficienti, da ima {{Matematična formula|''a''<sub>0</sub> &ne; 0 (mod ''p'')}} največ {{Matematična formula|''n''}} korenov.
* [[Primitivni koren modula n]]: Število {{Matematična formula|''g''}} je primitivni koren modula {{Matematična formula|''n''}}, če obstaja za vsako celo število {{Matematična formula|''a''}}, ki je tuje {{Matematična formula|''n''}}, neko celo število {{Matematična formula|''k''}}, da velja {{Matematična formula|''g''<sup>''k''</sup> ≡ ''a'' (mod ''n'')}}. Primitivni koren modula {{Matematična formula|''n''}} obstaja če in samo če je {{Matematična formula|''n''}} enak {{Matematična formula|2, 4, ''p''<sup>''k''</sup>}} ali {{Matematična formula|2''p''<sup>''k''</sup>}}, kjer je {{Matematična formula|''p''}} liho praštevilo in je {{Matematična formula|''k''}} naravno število. Če obstaja primitivni koren modula {{Matematična formula|''n''}}, potem obstaja natanko {{Matematična formula|''φ''(''φ''(''n''))}} takšnih primitivnih korenov, kjer je {{Matematična formula|''φ''}} Eulerjeva fi funkcija.
* [[Kvadratični ostanek]]: Celo število {{Matematična formula|''a''}} je kvadratični ostanek modula {{Matematična formula|''n''}}, če obstaja tako celo število {{Matematična formula|''x''}}, da velja {{Matematična formula|''x''<sup>2</sup> ≡ ''a'' (mod ''n'')}}. [[Eulerjev kriterij]] nam pravi, da če je {{Matematična formula|''p''}} liho praštevilo in a ni večkratnik od p, potem je {{Matematična formula|''a''}} kvadratični ostanek modula {{Matematična formula|''p''}} če in samo če

:: <math>a^{\frac{p-1}{2}} \equiv 1 \pmod p.</math>

== Kongruenčni razredi ==
Kot katerakoli kongruenčna relacija, je kongruenčni modulo {{Matematična formula|''n''}} [[ekvivalenčna relacija]] ter [[ekvivalenčni razred]] celega števila {{Matematična formula|''a''}}, ki se označi z {{Matematična formula|{{overline|''a''}}{{sub|''n''}}}}, je množica {{Matematična formula|&#123;… , ''a'' − 2''n'', ''a'' − ''n'', ''a'', ''a'' + ''n'', ''a'' + 2''n'', …&#125;}}. Ta množica, ki jo sestavljajo cela števila, ki so kongruentna {{Matematična formula|''a''}}&nbsp;po modulu&nbsp;{{Matematična formula|''n''}}, se imenuje '''kongruenčni razred''' ali '''razred ostankov''' ali preprosto '''ostanek''' celega števila {{Matematična formula|''a''}}, po modulu&nbsp;{{Matematična formula|''n''}}. Če je modulo {{Matematična formula|''n''}} razpoznaven iz besedila, se lahko ta ostanek označi z {{Matematična formula|[''a'']}}.

== Primeri implementacij ==
Spodaj so tri dokaj hitre funkcije v jeziku C, dve za izvajanje modularnih množenj in ena za izvajanje modularnega potenciranja na neoznačenih celih (naravnih) številih, ki niso večja od 63 bitov.

Algoritemski način za izračunanje <math>a \cdot b \pmod m</math>:<syntaxhighlight lang="c">
uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
   uint64_t d = 0, mp2 = m >> 1;
   int i;
   if (a >= m) a %= m;
   if (b >= m) b %= m;
   for (i = 0; i < 64; ++i)
   {
       d = (d > mp2) ? (d << 1) - m : d << 1;
       if (a & 0x8000000000000000ULL)
           d += b;
       if (d >= m) d -= m;
       a <<= 1;
   }
   return d;
}
</syntaxhighlight>Na računalnikih, kjer je mogoča tudi [[razširjena natančnost]] z najmanj 64 biti mantise (kot recimo tip [[long double]] na večini x86 C prevajalnikih), se lahko uporabi sledeča implementacija, saj po trdih komponentah množenje [[Plavajoča vejica|plavajoče vejice]] vodi v obdržane najbolj zanesljive bite, medtem ko množenje celih števil vodi v obdržane najmanj zanesljive bite:<syntaxhighlight lang="c">
uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
   long double x;
   uint64_t c;
   int64_t r;
   if (a >= m) a %= m;
   if (b >= m) b %= m;
   x = a;
   c = x * b / m;
   r = (int64_t)(a * b - c * m) % (int64_t)m;
   return r < 0 ? r + m : r;
}
</syntaxhighlight>Spodnja je C funkcija za izvajanje modularnega potenciranja, ki uporablja funkcijo {{Matematična formula|''mul_mod''}}, ki je bila implementirana zgoraj.

Algoritemski način za izračunanje <math>a^b \pmod m</math>:<syntaxhighlight lang="c">
uint64_t pow_mod(uint64_t a, uint64_t b, uint64_t m)
{
    uint64_t r = m==1?0:1;
    while (b > 0) {
        if (b & 1)
            r = mul_mod(r, a, m);
        b = b >> 1;
        a = mul_mod(a, a, m);
    }
    return r;
}
</syntaxhighlight>A da bi vse zgornje poti delovale, ne sme {{Matematična formula|''m''}} prekoračiti 63 bitov.

== Glej tudi ==
{{Div col|colwidth=25em}}
* [[Booleanov obroč]]
* [[Krožno blažilnik]]
* [[Deljenje (matematika)]]
* [[Končno polje]]
* [[Legendrov simbol]]
* [[Modularno potenciranje]]
* [[Pisanova perioda]] (Fibonaccijevo zaporedje modula ''n'')
* [[Primitivni koren modula n]]
* [[Kvadratna recipročnost]]
* [[Kvadratni ostanek]]
* [[Racionalna rekonstrukcija (matematika)]]
* [[Zmanjšani sistem ostankov]]
* [[Aritmetika serijskih števil]] (poseben primer modularne aritmetike)
* [[Booleanova algebra dveh elementov]]
* Področja, ki se nanašajo na teorijo grup za modularno aritmetiko:
** [[Ciklična grupa]]
** [[Multiplikativna grupa celih števil modula n]]
* Ostali pomembni izreki, ki se nanašajo na modularno aritmetiko:
** [[Carmichaelova funkcija|Carmichaelov izrek]]
** [[Kitajski izrek o ostankih]]
** [[Eulerjev izrek]]
** [[Fermatov mali izrek]] (posebni primer Eulerjevega izreka)
** [[Lagrangeov izrek (teorija grup)|Lagrangeov izrek]]
** [[Thueova lema]]
{{Div col end}}

== Sklici ==
{{Sklici}}

== Viri ==

* John L. Berggren. [http://www.britannica.com/EBchecked/topic/920687/modular-arithmetic "modular arithmetic"]. [[Enciklopedija Britannica|Encyclopædia Britannica]].
* Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR 0434929, Zbl 0335.10001. See in particular chapters 5 and 6 for a review of basic modular arithmetic.
* Maarten Bullynck "[https://web.archive.org/web/20131102014013/http://www.kuttaka.org/Gauss_Modular.pdf Modular Arithmetic before C.F. Gauss.] [https://web.archive.org/web/20131102014013/http://www.kuttaka.org/Gauss_Modular.pdf Systematisations and discussions on remainder problems in 18th-century Germany]"
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald Rivest|Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{ISBN|0-262-03293-7}}[[International Standard Book Number|ISBN]]&nbsp;[[Special:BookSources/0-262-03293-7|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}}[[International Standard Book Number|ISBN]]&nbsp;[[Special:BookSources/0-486-41449-3|0-486-41449-3]].
* {{Navedi knjigo|last=Long|first=Calvin T.|year=1972|title=Elementary Introduction to Number Theory|url=https://archive.org/details/elementaryintrod0000long_m1z0_2ndedi|edition=2.|publisher=[[D. C. Heath and Company]]|location=Lexington|lccn=77171950}}
* {{Navedi knjigo|last=Pettofrezzo|first=Anthony J.|last2=Byrkit|first2=Donald R.|year=1970|title=Elements of Number Theory|url=https://archive.org/details/elementsofnumber0000pett|publisher=[[Prentice Hall]]|location=Englewood Cliffs|lccn=71081766}}
* {{Navedi knjigo|last=Sengadir|first=T.|title=Discrete Mathematics and Combinatorics|year=2009|publisher=Pearson Education India|location=Chennai, India|isbn=978-81-317-1405-8|oclc=778356123}}

== Zunanje povezave ==

* Hazewinkel, Michiel, ed. (2001) [1994], "Congruence", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, <nowiki>ISBN 978-1-55608-010-4</nowiki>
* V tem [https://web.archive.org/web/20060101075602/http://britton.disted.camosun.bc.ca/modart/jbmodart.htm članku o modularni umetnosti] se lahko vsak nauči nekaj o uporabi modularne aritmetike v umetnosti.
* {{MathWorld|urlname=ModularArithmetic|title=Modular Arithmetic}}
* [https://web.archive.org/web/20160220061222/http://mersennewiki.org/index.php/Modular_arithmetic Članek] o modularni aritmetiki na wikiju GIMPS
* [http://www.cut-the-knot.org/blue/Modulo.shtml Modularna aritmetika in vzorci v seštevanju in tabele množenja]

[[Kategorija:Teorija grup]]
[[Kategorija:Končni kolobarji]]
[[Kategorija:Modularna aritmetika]]