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

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

  и   тада вреди

  1.  
  2.  
  3.  
Доказ

Нека је   и  .

 
  дели   те је  
  • Нека су   цели бројеви и   природан број. Нека су бројеви   и   релативно прости.

Тада вреди  

Доказ

Како су   и   релативно прости, постоје цели бројеви   и   такви да је  . Из конгруенције   => постоји цели број   такав да је  . Множењем претходне једнакости са  , из   добија се  . Очито   дели   те је  

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

Пример
  •   тачно
  •   није тачно
Пропозиција 2

Нека је   Тада вреди и  , где је  .

Доказ

  постоји цели број   такав да вреди   Одатле је  , те је  

Како су   и   релативно прости, јер немају заједничких простих фактора, добија се n   чиме је тврдња доказана.

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

Нека је   природан број, те су   и   цели бројеви такви да је   Тада за полином   са целобројним коефицијентима вреди  

Доказ

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

  добија се
  те
 

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

 

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

Нека су   природни бројеви. Тада су следеће тврдње еквивалентне:

 

 

Пример

Одредити   за који вреди

 

  (340 је дељиво са 17) tj.

 

Како је   добија се

 

Дату конгруенцију задовољава сваки цели број   који је конгруентан   modulo  , тј.  .

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

Нека је   природан број већи од  . Скуп   се назива потпуни систем остатака модуло   ако за сваки цели број   постоји јединствени   за који вреди  .

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

Најчешће кориштен потпун систем остатака модуло   је скуп  

Ово су неки од потпуних система остатака модуло 5:  ,  ,  ,  

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

Лема 1

Нека је   потпуни систем остатака модуло  . Тада је и   потпуни систем остатака модуло  , за сваки цели број   за који вреди  .

Лема 2

Нека су   i   природни бројеви. Конгруенција   има решења ако и само ако   дели  . Ако је   решење конгруенције   тада су сва међусобно неконгруентна решења модуло   полазне конгруенције дата с  

Пример

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

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

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

Скуп класа конгруенције по модулу 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]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 целих бројева), на пример, када се разматра карактеристика прстена.

Остаци уреди

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

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

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

Види још уреди

Референце уреди

Литература уреди

Спољашње везе уреди