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₁ ≡ b₁ (mod n) i a₂ ≡ b₂ (mod n), onda:

• (a₁ + a₂) ≡ (b₁ + b₂) (mod n)
• (a₁ − a₂) ≡ (b₁ − b₂) (mod n)
• (a₁a₂) ≡ (b₁b₂) (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 − 2n, a − n, a, a + n, a + 2n, ...}. 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/nZ i definiše se kao:

Z/nZ = { [a]_n | a ∈ Z}, gde Z = {..., −2, −1, 0, 1, 2, ...}.

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

Z/nZ = { [0]_n, [1]_n, [2]_n, ..., [|n|−1]_n }

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

Možemo da definišemo sabiranje, oduzimanje i množenje na Z/nZ sledećim pravilima:

• [a]_n + [b]_n = [a + b]_n
• [a]_n − [b]_n = [a − b]_n
• [[a]_n × [b]_n]_n = [ab]_n

Verifikacija da je ovo ispravna definicija koristi svojstva navedena gore.

Na ovaj način, Z/nZ postaje komutativni prsten. Na primer, u prstenu Z/24Z, imamo

[12]₂₄ + [21]₂₄ = [9]₂₄,

kao aritmetiku 24-časovnog sata.

Skup Z/nZ 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/0Z (š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. ISBN 0-387-90163-9
• 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.

Eksterni linkovi

Modularna aritmetika na Wikimedijinoj ostavi

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