Изворни код странице Модуларна аритметика

'''Модуларна аритметика''' представља аритметички систем код кога се бројеви ''враћају у круг'', када достигну одређену вредност – '''модуло'''. Модуларну аритметику је увео [[Карл Фридрих Гаус]] у свом чувеном делу ''-{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.

== Увод и дефиниција ==

=== Мотивација ===

У векторском простору, скуп [[скалар (математика)|скалара]] је [[поље (математика)|поље]] и делује на векторе скаларним множењем, подложно одређеним аксиомима као што је [[дистрибутивност|дистрибутивни закон]]. У модулу, скалари треба да буду само [[алгебарски прстен|прстен]], тако да концепт модула представља значајну генерализацију. У комутативној алгебри, [[идеал (математика)|идеали]] и [[quotient ring|количник прстенова]] су модули, тако да се многи аргументи о идеалима или количнику прстенова могу комбиновати у један аргумент о модулима. У некомутативној алгебри, разлика између левих идеала, идеала и модула постаје све израженија, иако се неки услови теорије прстена могу изразити или о левим идеалима или о левим модулима.

Велики део теорије модула састоји се од проширења што је могуће више пожељних својстава векторских простора на област модула преко прстена који се „[[well-behaved|добро понаша]]“, као што је [[principal ideal domain|домен главног идеала]]. Међутим, модули могу бити доста компликованији од векторских простора; на пример, немају сви модули [[база (линеарна алгебра)|основу]], те чак и за оне који имају ([[free module|слободни модули]]) број елемената у бази не мора бити исти за све базе (то јест да можда немају јединствен [[Free_module#Definition|ранг]]) ако основни прстен не задовољава услов [[invariant basis number|инваријантног основног броја]], за разлику од векторских простора, који увек имају (могуће бесконачну) основу чија је кардиналност тада јединствена. (Ове последње две тврдње захтевају [[аксиома избора|аксиом избора]] уопште, али не у случају коначно-димензионалних простора, или одређених бесконачно-димензионалних простора који се добро понашају као што су [[Lp space|L<sup>''p''</sup> простори]].)

=== Формална дефиниција ===

Претпоставимо да је ''R'' [[алгебарски прстен|прстен]], а 1 његов мултипликативни идентитет. Леви ''R''-модул ''M'' састоји се од [[абелова група|абелове групе]] {{nowrap|(''M'', +)}} и операције {{nowrap|'''·''' : ''R'' × ''M'' → ''M''}} такве да за свако ''r'', ''s'' у ''R'' и ''x'', ''y'' у ''M'', имамо

#<math> r \cdot ( x + y ) = r \cdot x + r \cdot y </math>
#<math> ( r + s ) \cdot x = r \cdot x + s \cdot x </math>
#<math> ( r s ) \cdot x = r \cdot ( s \cdot x ) </math>
#<math> 1 \cdot x = x .</math>

Операција · се назива ''скаларно множење''. Често је симбол · изостављен, али у овом чланку се користи и резервише јукстапозиција за множење у ''R''. Може се написати <sub>''R''</sub>''M'' да би се нагласило да је ''M'' леви ''R''-модул. Десни ''R''-модул ''M''<sub>''R''</sub> је слично дефинисан у смислу операције {{nowrap|· : ''M'' × ''R'' → ''M''}}.

Аутори који не захтевају да прстенови буду [[unital algebra|јединствени]] изостављају услов 4 у горњој дефиницији; они би горе дефинисане структуре назвали „униталним левим ''R''-модулима“. У овом чланку, у складу са [[glossary of ring theory|глосаром теорије прстенова]], претпоставља се да су сви прстенови и модули јединствени.<ref name="DummitFoote">{{cite book | title=Abstract Algebra | publisher=John Wiley & Sons, Inc. |author1=Dummit, David S.  |author2=Foote, Richard M.  | year=2004 | location=Hoboken, NJ | isbn=978-0-471-43334-7}}</ref>

(''R'',''S'')-[[bimodule|бимодул]] је абелова група заједно са левим скаларним множењем · елементима ''R'' и десним скаларним множењем ∗ елементима из ''S'', чинећи га истовремено левим ''R''-модулом и десним ''S''-модулом, задовољавајући додатни услов {{nowrap|1=(''r'' · ''x'') ∗ ''s'' = ''r'' ⋅ (''x'' ∗ ''s'')}} за свако ''r'' у ''R'', ''x'' у ''M'', и ''s'' у ''S''.

Ако је ''R'' [[комутативни прстен|комутативан]], онда су леви ''R''-модули исти као и десни ''R''-модули и једноставно се називају ''R''-модули.

== Релација конгруенције ==
Модуларна аритметика се математички може посматрати увођењем релације [[конгруенција|конгруенције]] на скупу [[цео број|целих бројева]], која је компатибилна са операцијама [[алгебарски прстен|прстена]] целих бројева: [[сабирање]], [[одузимање]], и [[множење]]. За фиксирани модул ''-{n}-'', дефинисана је на следећи начин.

Два цела броја ''-{a}-'' и ''-{b}-'' су '''конгруентна''' по '''модулу''' ''-{n}-'', ако је њихова разлика (-{a−b}-) цео број који је умножак (садржалац) од ''-{n}-''. Ако је ово тачно, записује се
:-{''a'' {{unicode|≡}} ''b'' ('''mod''' ''n''). }-

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

На пример,
:38 {{unicode|≡}} 14 ('''-{mod}-''' 12)
јер је 38 &minus; 14 = 24, што је умножак (садржалац) броја 12. За позитивно ''-{n}-'' и ненегативне ''-{a}-'' и ''-{b}-'', конгруенција ''-{a}-'' и ''-{b}-'' се такође може посматрати и као тврђење да ова два броја имају исти [[остатак (математика)|остатак]] након дељења модулом ''-{n}-''. Тако,
:38 {{unicode|≡}} 14 ('''-{mod}-''' 12)
Јер кад се поделе бројем 12, оба броја дају остатак 2.

Напомена у вези нотације: Пошто је уобичајено да се истовремено разматра неколико релација конгруенције за различите модуле, и модули се укључују у нотацију. Упркос овом тернарном запису, релација конгруенције по датом модулу је [[бинарна релација|бинарна]]. Ово би било јасније када би се користио запис ''-{a}-'' {{unicode|≡}}<sub>-{n}-</sub> ''-{b}-'' уместо традиционалног записа.

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

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

;Пропозиција 1
* Нека су <math>a, a', b, b'</math> цели бројеви те <math>n</math> природан број. Нека је
<math>a  \equiv a' (mod  \ n)</math> и <math>b  \equiv b' (mod  \ n)</math> тада вреди
#<math>a+b  \equiv a'+b' (mod  \ n)</math>
#<math>a-b  \equiv a'-b' (mod  \ n)</math>
#<math>a\times b  \equiv a'\times b' (mod  \ n)</math>

;Доказ
Нека је <math>a-a'= mn</math> и <math>b-b' = m'n</math>.
: <math>ab- a'b'= ab-ab'+ab'-a'b'=a(b-b')+(a- a')b'=am'n+ b'mn</math>
: <math>n</math> дели <math>ab- a'b'</math> те је <math>ab  \equiv a'b' (mod  \ n)</math>

* Нека су <math>a, b, c</math> цели бројеви и <math>n</math> природан број. Нека су бројеви <math>a</math> и <math>n</math> релативно прости.
Тада вреди 
<math>ab  \equiv ac (mod  \ n)=> b  \equiv c (mod  \ n)</math>

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

Ова тврдња не вреди генерално, тј. ако <math>a</math> и <math>n</math> нису релативно прости.
;Пример
*<math>60  \equiv 20 (mod  \ 5)</math> тачно
*<math>6  \equiv 2 (mod  \ 5)</math> није тачно

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

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

;Доказ

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

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

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

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

;Доказ 
Применом предходних пропозиција на
: <math>p(a)=\sum_{i=0}^k c_ia^i</math> добија се
: <math>a^i   \equiv b^ i (mod  \ n)</math> те
: <math>c_ia^i   \equiv c_ib^ i (mod  \ n)</math>

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

<math>p(a)=\sum_{i=0}^k c_ia^i \equiv  \sum_{i=0}^k c_ib^i =p(b)</math>

;Пропозиција 4
Нека су <math>n_1, n_2,... n_k</math> природни бројеви. Тада су следеће тврдње еквивалентне:

<math>a   \equiv b (mod  \ n_i),    i= 1, 2, ... k </math>

<math>a   \equiv b (mod  [ n_1, n_2,... n_k </math>

;Пример

Одредити <math>x \in  \Z</math> за који вреди

<math>341x   \equiv 1(mod  \ 17)</math>

<math>340:17=2</math> (340 је дељиво са 17) tj.

<math>340x  \equiv 0 (mod  \ 17)</math>

Како је
<math> 341x =340x+x</math> добија се

<math>341x  \equiv x (mod  \ 17)</math>

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

== Потпуни и редуковани систем остатака ==
Нека је <math>n</math> природан број већи од <math>1</math>. Скуп <math>S = \begin{Bmatrix}
a_1, a_2, ... , a_n
\end{Bmatrix}</math> се назива потпуни систем остатака модуло <math>n</math> ако за сваки цели број <math>b</math> постоји јединствени <math>a_i \in S</math> за који вреди
<math>b \equiv a_i (mod \ n)</math>.

Сваки потпуни систем остатака модуло <math>n</math> има тачно <math>n</math> елемената. Такође, сваки -{''n''}--члани скуп који се састоји од целих бројева међусобно неконгруентних модуло <math>n</math> представља један потпуни сустем остатака модуло <math>n</math>.

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

Ово су неки од потпуних система остатака модуло 5:
<math>\begin{Bmatrix}
  {0, 1, 2, 3, 4}
\end{Bmatrix}</math>, <math>\begin{Bmatrix}
  {-2,-1, 0, 1, 2}
\end{Bmatrix}</math>, <math>\begin{Bmatrix}
  {1, 2, 3, 4, 5}
\end{Bmatrix}</math>, <math>\begin{Bmatrix}
  {-10,-8,-4, 13, 39}
\end{Bmatrix}</math>

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

;Лема 1

Нека је <math>\begin{Bmatrix}
  {a_1, a_2, . . . , a_n}
\end{Bmatrix}</math> потпуни систем остатака модуло <math>n</math>. Тада је и <math>\begin{Bmatrix}
  {b \times a_1, b \times a_2, ... , b \times a_n}
\end{Bmatrix}</math> потпуни систем остатака модуло  <math>n</math>, за сваки цели број <math>b</math> за који вреди <math>(b, n) = 1</math>.

;Лема 2

Нека су <math>a</math> i <math>n</math> природни бројеви. Конгруенција <math>ax   \equiv b (mod  \ n_i), i = 1, 2, ... k </math> има решења ако и само ако <math>d = (a, n)</math> дели <math>b</math>. Ако је <math>x_0</math> решење конгруенције <math>\frac{a}{d}x \equiv  \frac{b}{d} (mod \frac{n}{d}</math> тада су сва међусобно неконгруентна решења модуло <math>n</math> полазне конгруенције дата с <math>x_0, x_0 + \frac{n}{d}, x_0 + \frac{2n}{d},...x_0 + \frac{(d-1)n}{d}
</math>
;Пример
Скупови {1, 2, 3, 4} и {-2,-6, 6, 7} су редуковани системи остатака модуло <math>5</math>, док је {1, 5} редуковани систем остатака модуло <math>6</math>.

== Прстен класа конгруенције ==
Као и свака релација конгруенције, и конгруенција по модулу ''-{n}-'' је [[релација еквиваленције]], и [[класа еквиваленције]] целог броја ''-{a}-'', која се означава са -{[''a'']<sub>''n''</sub>}-, је скуп { ..., ''-{a}-'' &minus; 2''-{n}-'', ''a'' &minus; ''-{n}-'', ''-{a}-'', ''-{a}-'' + ''-{n}-'', ''-{a}-'' + 2''-{n}-'', ...}. Овај скуп, који се састоји од целих бројева конгруентних са ''-{a}-'' по модулу ''-{n}-'', се назива '''класом конгруенције''' или '''класом остатка''' од ''-{a}-'' по модулу ''-{n}-''. Још једна нотација за ову класу конгруенције, која захтева да је из контекста јасно о ком модулу се ради, је <math>\hat{a}</math>.

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

:-{'''Z'''/''n'''''Z''' = { [''a'']<sub>''n''</sub> | ''a'' {{unicode|∈}} '''Z'''}}-, где -{'''Z''' }-= {..., −2, −1, 0, 1, 2, ...}.

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

:-{'''Z'''/''n'''''Z''' = { [0]<sub>''n''</sub>, [1]<sub>''n''</sub>, [2]<sub>''n''</sub>, ..., [|''n''|&minus;1]<sub>''n''</sub> } }-

Када -{''n'' = 0, '''Z'''/''n'''''Z'''}- нема нула елементе; већ је [[Изоморфизам (математика)|изоморфно]] са '''-{Z}-''', јер [''-{a}-'']<sub>0</sub> = {''-{a}-''}.

Можемо да дефинишемо сабирање, одузимање и множење на -{'''Z'''/''n'''''Z'''}- следећим правилима:
* -{[''a'']<sub>''n''</sub> + [''b'']<sub>''n''</sub> = [''a + b'']<sub>''n''</sub>}-
* -{[''a'']<sub>''n''</sub> − [''b'']<sub>''n''</sub> = [''a − b'']<sub>''n''</sub>}-
* -{[[''a'']<sub>''n''</sub> &times; [''b'']<sub>''n''</sub>]<sub>''n''</sub> = [''ab'']<sub>''n''</sub>}-

Верификација да је ово исправна дефиниција користи својства наведена горе.
 
На овај начин, -{'''Z'''/''n'''''Z'''}- постаје комутативни [[алгебарски прстен|прстен]]. На пример, у прстену -{'''Z'''/24'''Z'''}-, имамо
:-{[12]<sub>24</sub> + [21]<sub>24</sub> = [9]<sub>24</sub>}-,
као аритметику 24-часовног сата.

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

== Остаци ==
Концепт модуларне аритметике је повезан са концептом [[остатак (математика)|остатка]] при [[дељење|дељењу]].<ref>{{harvtxt|Pettofrezzo|Byrkit|1970|p=90}}</ref> Операција налажења остатка је позната као операција модула, и понекад се записује као "-{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}-'' (види спољашњу везу испод).

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

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

== Види још ==
* [[Коначно поље]]
* [[Циклична група]]
* [[Мултипликативна група целих бројева по модулу n]]
** [[Ојлерова теорема]]
** [[Мала Фермаова теорема]] - специјалан случај Ојлерове теореме.
** [[Кинеска теорема о остатку]]
** [[Лагранжова теорема (теорија група)|Лагранжова теорема]]

== Референце ==
{{reflist|30em}}

== Литература ==
{{Литература|30em}}
* ''-{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. [http://www.britannica.com/EBchecked/topic/920687/modular-arithmetic "modular arithmetic"]. [[Енциклопедија Британика|Encyclopædia Britannica]].
* {{Apostol IANT}}. 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. 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.&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}}.
* {{cite book |last=Long |first=Calvin T. |year=1972 |title=Elementary Introduction to Number Theory |url=https://archive.org/details/elementaryintrod0000long_m1z0_2ndedi |edition=2nd |publisher=[[D. C. Heath and Company]] |location=Lexington |lccn=77171950}}
* {{cite book |last1=Pettofrezzo |first1=Anthony J. |last2=Byrkit |first2=Donald R. |year=1970 |title=Elements of Number Theory |url=https://archive.org/details/elementsofnumber0000pett |url-access=registration |publisher=[[Prentice Hall]] |location=Englewood Cliffs |lccn=71081766}}
* {{cite book |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}}

{{Литература крај}}

== Спољашње везе ==
{{Commons category-lat|Modular arithmetic}}
* In this [https://web.archive.org/web/20060101075602/http://britton.disted.camosun.bc.ca/modart/jbmodart.htm модуларна уметност] чланак. Овде се може научити о примени модуларне аритметике у музици.
* [http://mathworld.wolfram.com/Congruence.html Конгруенција] на ''-{MathWorld}-''.
* An [https://web.archive.org/web/20160220061222/http://mersennewiki.org/index.php/Modular_arithmetic Чланак] о модуларној аритметици на ''-{GIMPS}-'' вики
* [http://www.cut-the-knot.org/blue/Modulo.shtml Модуларне аритметичке шеме у таблицама сабирања и множења]

{{нормативна контрола}}

[[Категорија:Модуларна аритметика|*]]
[[Категорија:Коначни прстенови]]
[[Категорија:Теорија група]]