Modularna aritmetika

**Modularna aritmetika** predstavlja aritmetički sistem kod koga se brojevi *vraćaju u krug*, nakon što dostignu određenu vrednost – **modulo**. Modularnu aritmetiku je uveo Karl Fridrih Gaus u svom čuvenom delu *[[Disquisitiones Arithmeticae]]*, objavljenom 1801.

Opštepoznata primena modularne aritmetike je u 24-časovnom merenju vremena: dan traje od ponoći do sledeće ponoći, i podeljen je na 24 časa, od 0 do 23. Ako je u određenom trenutku 19:00 časova (sedam uveče), osam sati kasnije vreme ne iznosi 27:00 (kao kod uobičajenog sabiranja: 19 + 8 = 27), već je tada 03:00 (narednog dana). Isto, ako je u određenom trenutku podne (12:00), i od tog trenutka je protekao 21 čas, sat će pokazivati 09:00 narednog dana, a ne 33:00 (kao kod uobičajenog sabiranja). Kako časovi ponovo počinju od 00 nakon što prođu 24 sata, ovde se radi o aritmetici po *modulu* 24 – brojevi *ponovo počinju od nule* nakon što dostignu 24.

## Relacija kongruencije
Modularna aritmetika se matematički može posmatrati uvođenjem relacije kongruencije na skupu celih brojeva, koja je kompatibilna sa operacijama prstena celih brojeva: sabiranje, oduzimanje, i množenje. Za fiksirani moduo *n*, definisana je na sledeći način.

Dva cela broja *a* i *b* su **kongruentna** po **modulu** *n*, ako je njihova razlika (a−b) ceo broj koji je umnožak (sadržalac) od *n*. Ako je ovo tačno, zapisuje se
:*a*  *b* (**mod** *n*).

Ovaj matematički iskaz se čita: "*a* je kongruentno sa *b* po **modulu** *n*".

Na primer,
:38  14 (**mod** 12)
jer je 38 − 14 = 24, što je umnožak (sadržalac) broja 12. Za pozitivno *n* i nenegativne *a* i *b*, kongruencija *a* i *b* se takođe može posmatrati i kao tvrđenje da ova dva broja imaju isti ostatak nakon deljenja modulom *n*. Tako,
:38  14 (**mod** 12)
Jer kad se podele brojem 12, oba broja daju ostatak 2.

Napomena u vezi notacije: Pošto je uobičajeno da se istovremeno razmatra nekoliko relacija kongruencije za različite module, i moduli se uključuju u notaciju. Uprkos ovom ternarnom zapisu, relacija kongruencije po datom modulu je binarna. Ovo bi bilo jasnije kada bi se koristio zapis *a* n *b* umesto tradicionalnog zapisa.

Slede svojstva koja čine ovu relaciju relacijom kongruencije (u odnosu na sabiranje, oduzimanje i množenje).

Ako *a*1  *b*1 (**mod** *n*) i *a*2  *b*2 (**mod** *n*), onda:
* (*a*1 + *a*2)  (*b*1 + *b*2) (**mod** *n*)
* (*a*1 − *a*2)  (*b*1 − *b*2) (**mod** *n*)
* (*a*1*a*2)  (*b*1*b*2) (**mod** *n*).

## Prsten klasa kongruencije
Kao i svaka relacija kongruencije, i kongruencija po modulu *n* je relacija ekvivalencije, i klasa ekvivalencije celog broja *a*, koja se označava sa [*a*]*n*, je skup { ..., *a* − 2*n*, *a* − *n*, *a*, *a* + *n*, *a* + 2*n*, ...}. Ovaj skup, koji se sastoji od celih brojeva kongruentnih sa *a* po modulu *n*, se naziva **klasom kongruencije** ili **klasom ostatka** od *a* po modulu *n*. Još jedna notacija za ovu klasu kongruencije, koja zahteva da je iz konteksta jasno o kom modulu se radi, je \hat{a}.

Skup klasa kongruencije po modulu *n* se označava kao **Z**/*n***Z** i definiše se kao:

:**Z**/*n***Z** = { [*a*]*n* | *a*  **Z**}, gde **Z** = {..., −2, −1, 0, 1, 2, ...}.

Kada *n* ≠ 0, **Z**/*n***Z** ima |*n*| elemenata, i može se zapisati kao:

:**Z**/*n***Z** = { [0]*n*, [1]*n*, [2]*n*, ..., [|*n*|−1]*n* }

Kada *n* = 0, **Z**/*n***Z** nema nula elemente; već je izomorfno sa **Z**, jer [*a*]0 = {*a*}.

Možemo da definišemo sabiranje, oduzimanje i množenje na **Z**/*n***Z** sledećim pravilima:
* [*a*]*n* + [*b*]*n* = [*a + b*]*n*
* [*a*]*n* − [*b*]*n* = [*a − b*]*n*
* prsten. Na primer, u prstenu **Z**/24**Z**, imamo
:[12]24 + [21]24 = [9]24,
kao aritmetiku 24-časovnog sata.

Skup **Z**/*n***Z** ima brojna važna matematička svojstva koja su značajna za razne grane matematike.
Umesto isključivanja specijalnog slučaja *n* = 0, korisnije je da se uključi **Z**/0**Z** (što je, kao što je već pomenuto, izomorfno prstenu **Z** celih brojeva), na primer, kada se razmatra karakteristika prstena.

## Ostaci
Koncept modularne aritmetike je povezan sa konceptom ostatka pri deljenju. Operacija nalaženja ostatka je poznata kao operacija modula, i ponekad se zapisuje kao "mod", pa pišemo "14 **mod** 12 = 2". Ovo značenje simbola "mod" je blago ali značajno drugačije od onog uvedenog u ovom članku; tačno je reći "38 ≡ 14 (**mod** 12)", ali nije tačno reći "38 = 14 **mod** 12" – 38 je kongruentno sa 14 po modulu 12, ali ostatak od 14 podeljeno sa 12 je 2, ne 38. Da bi se izbegli nesporazumi, relacija kongruencije se nekad zapisuje kao *modulo* umesto *mod* npr. "38 ≡ 14 (**modulo** 12)" u računarstvu.

Kada se radi sa modularnom aritmetikom, svaka klasa ekvivalencije se obično predstavlja njenim najmanjim nenegativnim članom.

## Primene
Modularna aritmetika ima primenu u teoriji brojeva, teoriji grupa, teoriji prstena, apstraktnoj algebri, kriptografiji, računarstvu, i vizuelnim umetnostima i muzici.

Modularna aritmetika spada u osnove teorije brojeva i dotiče gotovo svaki aspekt njenog proučavanja. Pruža ključne primere za teoriju grupa, teoriju prstena i apstraktnu algebru.

U kriptografiji modularna aritmetika pruža direktnu osnovu za sisteme sa javnim ključem, kao što je RSA, a osim toga daje konačna polja za eliptičke krive i koristi se u mnogim algoritmima sa simetričnim ključem, uključujući AES, IDEA, i RC4.

U računarstvu, modularna aritmetika se često koristi kod bitovskih operacija i drugih operacija koje se tiču cikličnih, i struktura podataka fiksne širine. Modulo operacija, koja je implementirana u mnogim programskim jezicima i kalkulatorima, je primena modularne aritmetike koja se često koristi u ovom kontekstu.

U vizuelnim umetnostima modularna aritmetika se može koristiti za pravljenje umetničkih šara baziranih na tablicama množenja i sabiranja po modulu *n* (vidi spoljašnju vezu ispod).

U opštijem smislu, modularna aritmetika ima primene u disciplinama kao što su prava, ekonomija, (npr. teorija igara) i drugim oblastima društvenih nauka gde proporcionalno deljenje i alokacija resursa igra centralnu ulogu u analizi.

Neki neurolozi (kao na primer Oliver Saks) imaju teorije da takozvani idioti savanti koriste urođenu modularnu aritmetiku da računaju kompleksne probleme, kao što je dan u nedelji koji će pasti na neki udaljeni datum.

## Povezano
* Konačno polje
* Ciklična grupa
* Multiplikativna grupa celih brojeva po modulu n
** Ojlerova teorema
** Mala Fermaova teorema – specijalan slučaj Ojlerove teoreme.
** Kineska teorema o ostatku
** Lagranžova teorema

## Literatura
* *Tom M. Apostol, Introduction to Analytic Number Theory, (1976) Springer-Verlag, New York. See in particular chapters 5 and 6 for a review of basic modular arithmetic. *
* *Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Section 31.3: Modular arithmetic, pp.862–868.*

## Vanjske veze

* In this modularna umetnost članak. Ovde se može naučiti o primeni modularne aritmetike u muzici.
* Kongruencija na *MathWorld*.
* An Članak  o modularnoj aritmetici na *GIMPS* viki
* Modularne aritmetičke šeme u tablicama sabiranja i množenja