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

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

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

Ако a₁ ≡ b₁ (mod n) и a₂ ≡ b₂ (mod n), онда:

• (a₁ + a₂) ≡ (b₁ + b₂) (mod n)
• (a₁ − a₂) ≡ (b₁ − b₂) (mod n)
• (a₁a₂) ≡ (b₁b₂) (mod n).

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

Као и свака релација конгруенције, и конгруенција по модулу 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 (види спољашњу везу испод).

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

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

Литература

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

Види још

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

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

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