Модуларна аритметика

Модуларна аритметика представља аритметички систем код кога се бројеви враћају у круг, када достигну одређену вредност – модуло. Модуларну аритметику је увео Карл Фридрих Гаус у свом чувеном делу Disquisitiones Arithmeticae, објављеном 1801.

Општепозната примена модуларне аритметике је у 24-часовном мерењу времена: дан траје од поноћи до следеће поноћи, и подељен је на 24 часа, од 0 до 23. Ако је у одређеном тренутку 19:00 часова (седам увече), осам сати касније време не износи 27:00 (као код уобичајеног сабирања: 19 + 8 = 27), већ је тада 03:00 (наредног дана). Исто, ако је у одређеном тренутку подне (12:00), и од тог тренутка је протекао 21 час, сат ће показивати 09:00 наредног дана, а не 33:00 (као код уобичајеног сабирања). Како часови поново почињу од 00 пошто прођу 24 сата, овде се ради о аритметици по модулу 24 – бројеви поново почињу од нуле када достигну 24.

Релација конгруенције

Модуларна аритметика се математички може посматрати увођењем релације конгруенције на скупу целих бројева, која је компатибилна са операцијама прстена целих бројева: сабирање, одузимање, и множење. За фиксирани модул n, дефинисана је на следећи начин.

Два цела броја a и b су конгруентна по модулу n, ако је њихова разлика (a−b) цео број који је умножак (садржалац) од n. Ако је ово тачно, записује се

a ≡ b (mod n).

Овај математички исказ се чита: "a је конгруентно са b по модулу n".

На пример,

38 ≡ 14 (mod 12)

јер је 38 − 14 = 24, што је умножак (садржалац) броја 12. За позитивно n и ненегативне a и b, конгруенција a и b се такође може посматрати и као тврђење да ова два броја имају исти остатак након дељења модулом n. Тако,

38 ≡ 14 (mod 12)

Јер кад се поделе бројем 12, оба броја дају остатак 2.

Напомена у вези нотације: Пошто је уобичајено да се истовремено разматра неколико релација конгруенције за различите модуле, и модули се укључују у нотацију. Упркос овом тернарном запису, релација конгруенције по датом модулу је бинарна. Ово би било јасније када би се користио запис a ≡_n b уместо традиционалног записа.

Особине конгруенције

Следе својства која чине ову релацију релацијом конгруенције (у односу на сабирање, одузимање и множење).

Пропозиција 1

• Нека су $a,a',b,b'$ цели бројеви те $n$ природан број. Нека је

$a\equiv a'(mod\ n)$ и $b\equiv b'(mod\ n)$ тада вреди

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)$

Доказ

Нека је $a-a'=mn$ и $b-b'=m'n$.

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

$n$ дели $ab-a'b'$ те је $ab\equiv a'b'(mod\ n)$

• Нека су $a,b,c$ цели бројеви и $n$ природан број. Нека су бројеви $a$ и $n$ релативно прости.

Тада вреди $ab\equiv ac(mod\ n)=>b\equiv c(mod\ n)$

Доказ

Како су $a$ и $n$ релативно прости, постоје цели бројеви $x$ и $y$ такви да је $ax+ny=1$. Из конгруенције $ab\equiv ac(mod\ n)$ => постоји цели број $k$ такав да је $a(b-c)=nk$. Множењем претходне једнакости са $x$, из $ax=1-ny$ добија се $(b-c)-ny(b-c)=nkx$. Очито $n$ дели $b-c$ те је $b\equiv c(mod\ n)$

Ова тврдња не вреди генерално, тј. ако $a$ и $n$ нису релативно прости.

Пример

• $60\equiv 20(mod\ 5)$ тачно
• $6\equiv 2(mod\ 5)$ није тачно

Пропозиција 2

Нека је $ax\equiv ay(mod\ n)$ Тада вреди и $x\equiv y(mod\ n/d)$, где је $d=(a,n)$.

Доказ

$ax\equiv ay(mod\ n)=>$ постоји цели број $k$ такав да вреди $ax-ay=kn.$ Одатле је ${\frac {a}{d}}(x-y)={\frac {nk}{d}}$, те је ${\frac {n}{d}}|{\frac {a}{d}}(x-y)$

Како су ${\frac {n}{d}}$ и ${\frac {a}{d}}$ релативно прости, јер немају заједничких простих фактора, добија се n $d|(x-y)$ чиме је тврдња доказана.

Пропозиција 3

Нека је $n$ природан број, те су $a$ и $b$ цели бројеви такви да је $a\equiv b(mod\ n)=>$ Тада за полином $p(x)$ са целобројним коефицијентима вреди $p(a)\equiv p(b)(mod\ n)=>$

Доказ

Применом предходних пропозиција на

$p(a)=\sum _{i=0}^{k}c_{i}a^{i}$ добија се

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

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

саберу ли се добијене конгруенције добија се

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

Пропозиција 4

Нека су $n_{1},n_{2},...n_{k}$ природни бројеви. Тада су следеће тврдње еквивалентне:

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

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

Пример

Одредити $x\in \mathbb {Z}$ за који вреди

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

$340:17=2$ (340 је дељиво са 17) tj.

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

Како је $341x=340x+x$ добија се

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

Дату конгруенцију задовољава сваки цели број $x$ који је конгруентан $1$ modulo $17$, тј. $x\in {\begin{Bmatrix}...,-33,-16,1,18,35,...\end{Bmatrix}}$.

Потпуни и редуковани систем остатака

Нека је $n$ природан број већи од $1$. Скуп $S={\begin{Bmatrix}a_{1},a_{2},...,a_{n}\end{Bmatrix}}$ се назива потпуни систем остатака модуло $n$ ако за сваки цели број $b$ постоји јединствени $a_{i}\in S$ за који вреди $b\equiv a_{i}(mod\ n)$.

Сваки потпуни систем остатака модуло $n$ има тачно $n$ елемената. Такође, сваки n-члани скуп који се састоји од целих бројева међусобно неконгруентних модуло $n$ представља један потпуни сустем остатака модуло $n$.

Најчешће кориштен потпун систем остатака модуло $n$ је скуп ${\begin{Bmatrix}0,1,2,...,n-1\end{Bmatrix}}$

Ово су неки од потпуних система остатака модуло 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}}$

Постоји их бесконачно много.

Лема 1

Нека је ${\begin{Bmatrix}{a_{1},a_{2},...,a_{n}}\end{Bmatrix}}$ потпуни систем остатака модуло $n$. Тада је и ${\begin{Bmatrix}{b\times a_{1},b\times a_{2},...,b\times a_{n}}\end{Bmatrix}}$ потпуни систем остатака модуло $n$, за сваки цели број $b$ за који вреди $(b,n)=1$.

Лема 2

Нека су $a$ i $n$ природни бројеви. Конгруенција $ax\equiv b(mod\ n_{i}),i=1,2,...k$ има решења ако и само ако $d=(a,n)$ дели $b$. Ако је $x_{0}$ решење конгруенције ${\frac {a}{d}}x\equiv {\frac {b}{d}}(mod{\frac {n}{d}}$ тада су сва међусобно неконгруентна решења модуло $n$ полазне конгруенције дата с $x_{0},x_{0}+{\frac {n}{d}},x_{0}+{\frac {2n}{d}},...x_{0}+{\frac {(d-1)n}{d}}$

Пример

Скупови {1, 2, 3, 4} и {-2,-6, 6, 7} су редуковани системи остатака модуло $5$, док је {1, 5} редуковани систем остатака модуло $6$.

Прстен класа конгруенције

Као и свака релација конгруенције, и конгруенција по модулу n је релација еквиваленције, и класа еквиваленције целог броја a, која се означава са [a]_n, је скуп { ..., a − 2n, a − n, a, a + n, a + 2n, ...}. Овај скуп, који се састоји од целих бројева конгруентних са a по модулу n, се назива класом конгруенције или класом остатка од a по модулу n. Још једна нотација за ову класу конгруенције, која захтева да је из контекста јасно о ком модулу се ради, је ${\hat {a}}$.

Скуп класа конгруенције по модулу n се означава као Z/nZ и дефинише се као:

a ∈ Z}, где Z = {..., −2, −1, 0, 1, 2, ...}.

Када n ≠ 0, Z/nZ има |n| елемената, и може се записати као:

n|−1]_n }

Када n = 0, Z/nZ нема нула елементе; већ је изоморфно са Z, јер [a]₀ = {a}.

Можемо да дефинишемо сабирање, одузимање и множење на Z/nZ следећим правилима:

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

Верификација да је ово исправна дефиниција користи својства наведена горе.

На овај начин, Z/nZ постаје комутативни прстен. На пример, у прстену Z/24Z, имамо

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

као аритметику 24-часовног сата.

Скуп Z/nZ има бројна важна математичка својства која су значајна за разне гране математике. Уместо искључивања специјалног случаја n = 0, корисније је да се укључи Z/0Z (што је, као што је већ поменуто, изоморфно прстену Z целих бројева), на пример, када се разматра карактеристика прстена.

Остаци

Концепт модуларне аритметике је повезан са концептом остатка при дељењу. Операција налажења остатка је позната као операција модула, и понекад се записује као "mod", па пишемо "14 mod 12 = 2". Ово значење симбола "mod" је благо али значајно другачије од оног уведеног у овом чланку; тачно је рећи "38 ≡ 14 (mod 12)", али није тачно рећи "38 = 14 mod 12" – 38 је конгруентно са 14 по модулу 12, али остатак од 14 подељено са 12 је 2, не 38. Да би се избегли неспоразуми, релација конгруенције се некад записује као modulo уместо mod нпр. "38 ≡ 14 (modulo 12)" у рачунарству.

Када се ради са модуларном аритметиком, свака класа еквиваленције се обично представља њеним најмањим ненегативним чланом.

Примене

Модуларна аритметика има примену у теорији бројева, теорији група, теорији прстена, апстрактној алгебри, криптографији, рачунарству, и визуелним уметностима и музици.

Модуларна аритметика спада у основе теорије бројева и дотиче готово сваки аспект њеног проучавања. Пружа кључне примере за теорију група, теорију прстена и апстрактну алгебру.

У криптографији модуларна аритметика пружа директну основу за системе са јавним кључем, као што је РСА, а осим тога даје коначна поља за елиптичке криве и користи се у многим алгоритмима са симетричним кључем, укључујући АЕС, ИДЕА, и РЦ4.

У рачунарству, модуларна аритметика се често користи код битовских операција и других операција које се тичу цикличних, и структура података фиксне ширине. Модуло операција, која је имплементирана у многим програмским језицима и калкулаторима, је примена модуларне аритметике која се често користи у овом контексту.

У визуелним уметностима модуларна аритметика се може користити за прављење уметничких шара базираних на таблицама множења и сабирања по модулу n (види спољашњу везу испод).

У општијем смислу, модуларна аритметика има примене у дисциплинама као што су права, економија, (нпр. теорија игара) и другим областима друштвених наука где пропорционално дељење и алокација ресурса игра централну улогу у анализи.

Неки неуролози (као на пример Оливер Сакс) имају теорије да такозвани идиоти саванти користе урођену модуларну аритметику да рачунају комплексне проблеме, као што је дан у недељи који ће пасти на неки удаљени датум.

Види још

• Коначно поље
• Циклична група
• Мултипликативна група целих бројева по модулу n
  • Ојлерова теорема
  • Мала Фермаова теорема - специјалан случај Ојлерове теореме.
  • Кинеска теорема о остатку
  • Лагранжова теорема

Литература

• 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 изд.). 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. 

Спољашње везе

• In this модуларна уметност чланак. Овде се може научити о примени модуларне аритметике у музици.
• Конгруенција на MathWorld.
• An Чланак о модуларној аритметици на GIMPS вики
• Модуларне аритметичке шеме у таблицама сабирања и множења