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

Izvor: Wikipedia

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

Релација конгруенције[uredi - уреди]

Модуларна аритметика се математички може посматрати увођењем релације конгруенције на скупу целих бројева, која је компатибилна са операцијама прстена целих бројева: сабирање, одузимање, и множење. За фиксирани модуо -{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}- уместо традиционалног записа.

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

Ако -{a1 b1 (mod n)}- и -{a2 b2 (mod n)}-, онда:

  • -{(a1 + a2) (b1 + b2) (mod n)}-
  • -{(a1a2) (b1b2) (mod n)}-
  • -{(a1a2) (b1b2) (mod n).}-

Прстен класа конгруенције[uredi - уреди]

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

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

-{Z/nZ = { [a]n | a Z}}-, где -{Z }-= {..., −2, −1, 0, 1, 2, ...}.

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

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

Када -{n = 0, Z/nZ}- нема нула елементе; већ је изоморфно са -{Z}-, јер [-{a}-]0 = {-{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]24 + [21]24 = [9]24}-,

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

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

Остаци[uredi - уреди]

Концепт модуларне аритметике је повезан са концептом остатка при дељењу. Операција налажења остатка је позната као операција модула, и понекад се записује као "-{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)" у рачунарству.

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

Примене[uredi - уреди]

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

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

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

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

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

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

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

Литература[uredi - уреди]

  • -{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.}-

Види још[uredi - уреди]

Спољашње везе[uredi - уреди]