Modularna aritmetika

Modularna aritmetika predstavlja aritmetički sistem kod koga se brojevi vraćaju u krug, kada 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 pošto prođu 24 sata, ovde se radi o aritmetici po modulu 24 – brojevi ponovo počinju od nule kada dostignu 24.

Uvod i definicija

Motivacija

U vektorskom prostoru, skup skalara je polje i deluje na vektore skalarnim množenjem, podložno određenim aksiomima kao što je distributivni zakon. U modulu, skalari treba da budu samo prsten, tako da koncept modula predstavlja značajnu generalizaciju. U komutativnoj algebri, ideali i količnik prstenova su moduli, tako da se mnogi argumenti o idealima ili količniku prstenova mogu kombinovati u jedan argument o modulima. U nekomutativnoj algebri, razlika između levih ideala, ideala i modula postaje sve izraženija, iako se neki uslovi teorije prstena mogu izraziti ili o levim idealima ili o levim modulima.

Veliki deo teorije modula sastoji se od proširenja što je moguće više poželjnih svojstava vektorskih prostora na oblast modula preko prstena koji se „dobro ponaša“, kao što je domen glavnog ideala. Međutim, moduli mogu biti dosta komplikovaniji od vektorskih prostora; na primer, nemaju svi moduli osnovu, te čak i za one koji imaju (slobodni moduli) broj elemenata u bazi ne mora biti isti za sve baze (to jest da možda nemaju jedinstven rang) ako osnovni prsten ne zadovoljava uslov invarijantnog osnovnog broja, za razliku od vektorskih prostora, koji uvek imaju (moguće beskonačnu) osnovu čija je kardinalnost tada jedinstvena. (Ove poslednje dve tvrdnje zahtevaju aksiom izbora uopšte, ali ne u slučaju konačno-dimenzionalnih prostora, ili određenih beskonačno-dimenzionalnih prostora koji se dobro ponašaju kao što su L^p prostori.)

Formalna definicija

Pretpostavimo da je R prsten, a 1 njegov multiplikativni identitet. Levi R-modul M sastoji se od abelove grupe (M, +) i operacije · : R × M → M takve da za svako r, s u R i x, y u M, imamo

1. $r\cdot (x+y)=r\cdot x+r\cdot y$
2. $(r+s)\cdot x=r\cdot x+s\cdot x$
3. $(rs)\cdot x=r\cdot (s\cdot x)$
4. $1\cdot x=x.$

Operacija · se naziva skalarno množenje. Često je simbol · izostavljen, ali u ovom članku se koristi i rezerviše jukstapozicija za množenje u R. Može se napisati _RM da bi se naglasilo da je M levi R-modul. Desni R-modul M_R je slično definisan u smislu operacije · : M × R → M.

Autori koji ne zahtevaju da prstenovi budu jedinstveni izostavljaju uslov 4 u gornjoj definiciji; oni bi gore definisane strukture nazvali „unitalnim levim R-modulima“. U ovom članku, u skladu sa glosarom teorije prstenova, pretpostavlja se da su svi prstenovi i moduli jedinstveni.

(R,S)-bimodul je abelova grupa zajedno sa levim skalarnim množenjem · elementima R i desnim skalarnim množenjem ∗ elementima iz S, čineći ga istovremeno levim R-modulom i desnim S-modulom, zadovoljavajući dodatni uslov (r · x) ∗ s = r ⋅ (x ∗ s) za svako r u R, x u M, i s u S.

Ako je R komutativan, onda su levi R-moduli isti kao i desni R-moduli i jednostavno se nazivaju R-moduli.

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 modul 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.

Osobine kongruencije

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

Propozicija 1

• Neka su $a,a',b,b'$ celi brojevi te $n$ prirodan broj. Neka je

$a\equiv a'(mod\ n)$ i $b\equiv b'(mod\ n)$ tada vredi

1. $a+b\equiv a'+b'(mod\ n)$
2. $a-b\equiv a'-b'(mod\ n)$
3. $a\times b\equiv a'\times b'(mod\ n)$

Dokaz

Neka je $a-a'=mn$ i $b-b'=m'n$.

$ab-a'b'=ab-ab'+ab'-a'b'=a(b-b')+(a-a')b'=am'n+b'mn$

$n$ deli $ab-a'b'$ te je $ab\equiv a'b'(mod\ n)$

• Neka su $a,b,c$ celi brojevi i $n$ prirodan broj. Neka su brojevi $a$ i $n$ relativno prosti.

Tada vredi $ab\equiv ac(mod\ n)=>b\equiv c(mod\ n)$

Dokaz

Kako su $a$ i $n$ relativno prosti, postoje celi brojevi $x$ i $y$ takvi da je $ax+ny=1$. Iz kongruencije $ab\equiv ac(mod\ n)$ => postoji celi broj $k$ takav da je $a(b-c)=nk$. Množenjem prethodne jednakosti sa $x$, iz $ax=1-ny$ dobija se $(b-c)-ny(b-c)=nkx$. Očito $n$ deli $b-c$ te je $b\equiv c(mod\ n)$

Ova tvrdnja ne vredi generalno, tj. ako $a$ i $n$ nisu relativno prosti.

Primer

• $60\equiv 20(mod\ 5)$ tačno
• $6\equiv 2(mod\ 5)$ nije tačno

Propozicija 2

Neka je $ax\equiv ay(mod\ n)$ Tada vredi i $x\equiv y(mod\ n/d)$, gde je $d=(a,n)$.

Dokaz

$ax\equiv ay(mod\ n)=>$ postoji celi broj $k$ takav da vredi $ax-ay=kn.$ Odatle je ${\frac {a}{d}}(x-y)={\frac {nk}{d}}$, te je ${\frac {n}{d}}|{\frac {a}{d}}(x-y)$

Kako su ${\frac {n}{d}}$ i ${\frac {a}{d}}$ relativno prosti, jer nemaju zajedničkih prostih faktora, dobija se n $d|(x-y)$ čime je tvrdnja dokazana.

Propozicija 3

Neka je $n$ prirodan broj, te su $a$ i $b$ celi brojevi takvi da je $a\equiv b(mod\ n)=>$ Tada za polinom $p(x)$ sa celobrojnim koeficijentima vredi $p(a)\equiv p(b)(mod\ n)=>$

Dokaz

Primenom predhodnih propozicija na

$p(a)=\sum _{i=0}^{k}c_{i}a^{i}$ dobija se

$a^{i}\equiv b^{i}(mod\ n)$ te

$c_{i}a^{i}\equiv c_{i}b^{i}(mod\ n)$

saberu li se dobijene kongruencije dobija se

$p(a)=\sum _{i=0}^{k}c_{i}a^{i}\equiv \sum _{i=0}^{k}c_{i}b^{i}=p(b)$

Propozicija 4

Neka su $n_{1},n_{2},...n_{k}$ prirodni brojevi. Tada su sledeće tvrdnje ekvivalentne:

$a\equiv b(mod\ n_{i}),i=1,2,...k$

$a\equiv b(mod[n_{1},n_{2},...n_{k}$

Primer

Odrediti $x\in \mathbb {Z}$ za koji vredi

$341x\equiv 1(mod\ 17)$

$340:17=2$ (340 je deljivo sa 17) tj.

$340x\equiv 0(mod\ 17)$

Kako je $341x=340x+x$ dobija se

$341x\equiv x(mod\ 17)$

Datu kongruenciju zadovoljava svaki celi broj $x$ koji je kongruentan $1$ modulo $17$, tj. $x\in {\begin{Bmatrix}...,-33,-16,1,18,35,...\end{Bmatrix}}$.

Potpuni i redukovani sistem ostataka

Neka je $n$ prirodan broj veći od $1$. Skup $S={\begin{Bmatrix}a_{1},a_{2},...,a_{n}\end{Bmatrix}}$ se naziva potpuni sistem ostataka modulo $n$ ako za svaki celi broj $b$ postoji jedinstveni $a_{i}\in S$ za koji vredi $b\equiv a_{i}(mod\ n)$.

Svaki potpuni sistem ostataka modulo $n$ ima tačno $n$ elemenata. Takođe, svaki n-člani skup koji se sastoji od celih brojeva međusobno nekongruentnih modulo $n$ predstavlja jedan potpuni sustem ostataka modulo $n$.

Najčešće korišten potpun sistem ostataka modulo $n$ je skup ${\begin{Bmatrix}0,1,2,...,n-1\end{Bmatrix}}$

Ovo su neki od potpunih sistema ostataka modulo 5: ${\begin{Bmatrix}{0,1,2,3,4}\end{Bmatrix}}$, ${\begin{Bmatrix}{-2,-1,0,1,2}\end{Bmatrix}}$, ${\begin{Bmatrix}{1,2,3,4,5}\end{Bmatrix}}$, ${\begin{Bmatrix}{-10,-8,-4,13,39}\end{Bmatrix}}$

Postoji ih beskonačno mnogo.

Lema 1

Neka je ${\begin{Bmatrix}{a_{1},a_{2},...,a_{n}}\end{Bmatrix}}$ potpuni sistem ostataka modulo $n$. Tada je i ${\begin{Bmatrix}{b\times a_{1},b\times a_{2},...,b\times a_{n}}\end{Bmatrix}}$ potpuni sistem ostataka modulo $n$, za svaki celi broj $b$ za koji vredi $(b,n)=1$.

Lema 2

Neka su $a$ i $n$ prirodni brojevi. Kongruencija $ax\equiv b(mod\ n_{i}),i=1,2,...k$ ima rešenja ako i samo ako $d=(a,n)$ deli $b$. Ako je $x_{0}$ rešenje kongruencije ${\frac {a}{d}}x\equiv {\frac {b}{d}}(mod{\frac {n}{d}}$ tada su sva međusobno nekongruentna rešenja modulo $n$ polazne kongruencije data s $x_{0},x_{0}+{\frac {n}{d}},x_{0}+{\frac {2n}{d}},...x_{0}+{\frac {(d-1)n}{d}}$

Primer

Skupovi {1, 2, 3, 4} i {-2,-6, 6, 7} su redukovani sistemi ostataka modulo $5$, dok je {1, 5} redukovani sistem ostataka modulo $6$.

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:

a ∈ Z}, gde Z = {..., −2, −1, 0, 1, 2, ...}.

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

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.

Vidi još

• 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 978-0-387-90163-3
• John L. Berggren. "modular arithmetic". 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 "Modular Arithmetic before C.F. Gauss. Systematisations and discussions on remainder problems in 18th-century Germany"
• 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.
• Long, Calvin T. (1972). Elementary Introduction to Number Theory (2nd izd.). Lexington: D. C. Heath and Company. LCCN 77171950. 
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Elements of Number Theory. Englewood Cliffs: Prentice Hall. LCCN 71081766. 
• Sengadir, T. (2009). Discrete Mathematics and Combinatorics. Chennai, India: Pearson Education India. ISBN 978-81-317-1405-8. OCLC 778356123. 

Spoljašnje 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