www.wikidata.uk-ua.nina.az

Модульна арифметика Мо дульна арифме тика це система арифметики цілих чисел в якій числа обертаються навколо деякого зна

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

Мо́дульна арифме́тика — це система арифметики цілих чисел, в якій числа «обертаються навколо» деякого значення — модуля.

Операції з часом на цих годинниках використовують правила арифметики по модулю 12. 9+4 ≡ 1 mod 12.

Найбільш відомий приклад модульної арифметики — це запис часу в 12-годинному форматі, в якому день ділиться на два 12-годинних періоди. Якщо зараз 9:00, то через 4 години на годиннику буде 1:00. Якщо просто додати, то 9 + 4 = 13, але це неправильна відповідь, тому що на годиннику по досягненні стрілки 12-ї години, замість 12:00 ми отримуємо 00:00. Тому правильна відповідь, що на годиннику буде 1:00.

Аналогічним чином, якщо годинник починає відлік о 12:00 (опівдні) і пройде 21 година, то час буде 9:00 наступного дня, а не 33:00. Оскільки годинник починає новий відлік часу після досягнення 12, то це буде арифметика за модулем 12. 12 відповідає не тільки значенню 12, але також і 0, так що час, який називається «12:00», також може бути названий «0:00», оскільки 0 ≡ 12 mod 12.

Ще один підхід до модульної арифметики пов'язаний з остачами від ділення цілих чисел на певне задане натуральне число. Фактично в ній розглядаються класи еквівалентності певного натурального числа.

У сучасному вигляді модульна арифметика була розвинута Гаусом в Disquisitiones Arithmeticae[en] (1801).

Рівність за модулем Редагувати

Два цілих числа a і b називаються рівними (конгруентними) за модулем n, якщо при цілочисельному діленні на n вони мають однакові остачі. Рівність чисел a і b за модулем n записують так:

Еквівалентні визначення:

  • Різниця a − b ділиться на n націло. Тобто a − b = kn, де k — якесь ціле число.
  • Число a може бути записано у вигляді a = b + kn, де k — якесь ціле число.

Наприклад:

Справді, 15 − 4 = 11 і 11 очевидно ділиться на 11.

Маємо 16 − 37 = −21 і −21 ділиться на 7 націло.

У цьому разі 16−(−5)=16+5=21 і 21 ділиться на 7.

Властивості, що виконуються для відношення рівності, виконуються також для рівності за модулем.

Якщо та , тоді:

Рівність за модулем як відношення еквівалентності Редагувати

З визначення рівності за модулем витікають такі властивості:

Тобто відношення рівності за модулем є відношенням еквівалентності на множині цілих чисел . Тоді розбивається на класи еквівалентності.

Клас еквівалентності відношення рівності за модулем n до якого належить число a позначається . Так як, , то додати n, теж саме, що і додати 0. Тому клас числа

Для прикладу, розглянемо відношення по модулю 2. , тоді і тільки тоді, коли їх різниця парне число. Це співвідношення призводить до двох класів еквівалентності: один клас, що складається з усіх парних чисел, та другий, який складається з усіх непарних чисел. Клас парних чисел позначається, як [0], непарних як [1]. Згідно з цим співвідношенням 8, 10 та 118 належать одному класу — .

Множина класів конгруентності за модулем позначається: (або, чи ) і за визначенням це:

Коли n ≠ 0, має n елементів, і може бути записано:

Для цих класів можна задати операції додавання, віднімання, множення:

Обґрунтованість цих означень випливає із властивостей попереднього розділу.

Кільце класів рівності за модулем Редагувати

Таким чином є комутативним кільцем. Наприклад в , маємо

Деякий елемент має обернений елемент тоді і лише тоді коли m i n є взаємно простими числами. Справді, якщо m i n є взаємно простими, то тоді існують такі, що Звідси:

Навпаки, якщо для деякого , то для деякого , що неможливо, враховуючи взаємну простоту m i n. Відповідно, якщо просте число, то є полем.

Розв'язування лінійних рівнянь Редагувати

Вікіпідручник має книгу на тему
Розв'язник вправ по дискретній математиці/Кодування/Модульна арифметика

Лінійне рівняння записується у вигляді

Розв'язок можна отримати безпосередньо діленням або за допомогою формули

Функція  — функція Ейлера, яка дорівнює кількості натуральних чисел, не більших n і взаємно простих з ним.

Якщо НСД , порівняння або має не єдиний розв'язок, або не має розв'язків. Як легко побачити, порівняння

не має розв'язків на множині натуральних чисел.

Інше порівняння

має два розв'язки

Див. також Редагувати

Джерела Редагувати

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Mo dulna arifme tika ce sistema arifmetiki cilih chisel v yakij chisla obertayutsya navkolo deyakogo znachennya modulya Operaciyi z chasom na cih godinnikah vikoristovuyut pravila arifmetiki po modulyu 12 9 4 1 mod 12 Najbilsh vidomij priklad modulnoyi arifmetiki ce zapis chasu v 12 godinnomu formati v yakomu den dilitsya na dva 12 godinnih periodi Yaksho zaraz 9 00 to cherez 4 godini na godinniku bude 1 00 Yaksho prosto dodati to 9 4 13 ale ce nepravilna vidpovid tomu sho na godinniku po dosyagnenni strilki 12 yi godini zamist 12 00 mi otrimuyemo 00 00 Tomu pravilna vidpovid sho na godinniku bude 1 00 Analogichnim chinom yaksho godinnik pochinaye vidlik o 12 00 opivdni i projde 21 godina to chas bude 9 00 nastupnogo dnya a ne 33 00 Oskilki godinnik pochinaye novij vidlik chasu pislya dosyagnennya 12 to ce bude arifmetika za modulem 12 12 vidpovidaye ne tilki znachennyu 12 ale takozh i 0 tak sho chas yakij nazivayetsya 12 00 takozh mozhe buti nazvanij 0 00 oskilki 0 12 mod 12 She odin pidhid do modulnoyi arifmetiki pov yazanij z ostachami vid dilennya cilih chisel na pevne zadane naturalne chislo Faktichno v nij rozglyadayutsya klasi ekvivalentnosti pevnogo naturalnogo chisla U suchasnomu viglyadi modulna arifmetika bula rozvinuta Gausom v Disquisitiones Arithmeticae en 1801 Zmist 1 Rivnist za modulem 2 Rivnist za modulem yak vidnoshennya ekvivalentnosti 3 Kilce klasiv rivnosti za modulem 4 Rozv yazuvannya linijnih rivnyan 5 Div takozh 6 DzherelaRivnist za modulem RedaguvatiDva cilih chisla a i b nazivayutsya rivnimi kongruentnimi za modulem n yaksho pri cilochiselnomu dilenni na n voni mayut odnakovi ostachi Rivnist chisel a i b za modulem n zapisuyut tak a b mod n displaystyle a equiv b pmod n nbsp Ekvivalentni viznachennya Riznicya a b dilitsya na n nacilo Tobto a b kn de k yakes cile chislo Chislo a mozhe buti zapisano u viglyadi a b kn de k yakes cile chislo Napriklad 15 4 mod 11 displaystyle 15 equiv 4 pmod 11 nbsp Spravdi 15 4 11 i 11 ochevidno dilitsya na 11 16 37 mod 7 displaystyle 16 equiv 37 pmod 7 nbsp Mayemo 16 37 21 i 21 dilitsya na 7 nacilo 16 5 mod 7 displaystyle 16 equiv 5 pmod 7 nbsp U comu razi 16 5 16 5 21 i 21 dilitsya na 7 Vlastivosti sho vikonuyutsya dlya vidnoshennya rivnosti vikonuyutsya takozh dlya rivnosti za modulem Yaksho a 1 b 1 mod n displaystyle a 1 equiv b 1 pmod n nbsp ta a 2 b 2 mod n displaystyle a 2 equiv b 2 pmod n nbsp todi a 1 a 2 b 1 b 2 mod n displaystyle a 1 a 2 equiv b 1 b 2 pmod n nbsp a 1 a 2 b 1 b 2 mod n displaystyle a 1 a 2 equiv b 1 b 2 pmod n nbsp a 1 a 2 b 1 b 2 mod n displaystyle a 1 a 2 equiv b 1 b 2 pmod n nbsp Dovedennya Spravdi nehaj a 1 l n k b 1 m n k a 2 s n r b 2 t n r displaystyle a 1 ln k b 1 mn k a 2 sn r b 2 tn r nbsp Todi a 1 a 2 l s n k r k r mod n displaystyle a 1 a 2 l s n k r equiv k r pmod n nbsp i b 1 b 2 m t n k r k r mod n displaystyle b 1 b 2 m t n k r equiv k r pmod n nbsp Takozh a 1 a 2 l s n k r k r mod n displaystyle a 1 a 2 l s n k r equiv k r pmod n nbsp i b 1 b 2 m t n k r k r mod n displaystyle b 1 b 2 m t n k r equiv k r pmod n nbsp U vipadku dobutku a 1 a 2 l s n 2 l r s k n k r k r mod n displaystyle a 1 a 2 ls n 2 lr sk n kr equiv kr pmod n nbsp i b 1 b 2 m t n 2 m r t k n k r k r mod n displaystyle b 1 b 2 mt n 2 mr tk n kr equiv kr pmod n nbsp V usih troh vipadkah bachimo sho ostatochni virazi rivni Rivnist za modulem yak vidnoshennya ekvivalentnosti RedaguvatiZ viznachennya rivnosti za modulem vitikayut taki vlastivosti refleksivnist a a mod n displaystyle a equiv a pmod n nbsp simetrichnist a b mod n b a mod n displaystyle a equiv b pmod n quad iff quad b equiv a pmod n nbsp tranzitivnist yaksho a b mod n displaystyle a equiv b pmod n nbsp ta b c mod n displaystyle b equiv c pmod n nbsp to takozh a c mod n displaystyle a equiv c pmod n nbsp Tobto vidnoshennya rivnosti za modulem ye vidnoshennyam ekvivalentnosti na mnozhini cilih chisel Z displaystyle mathbb Z nbsp Todi Z displaystyle mathbb Z nbsp rozbivayetsya na klasi ekvivalentnosti Klas ekvivalentnosti vidnoshennya rivnosti za modulem n do yakogo nalezhit chislo a poznachayetsya a n displaystyle overline a n nbsp Tak yak n 0 mod n displaystyle n equiv 0 pmod n nbsp to dodati n tezh same sho i dodati 0 Tomu klas chisla a n a a n a 2 n a 3 n a 2 n a n a a n a 2 n displaystyle overline a n left a a pm n a pm 2n a pm 3n ldots right left ldots a 2n a n a a n a 2n ldots right nbsp Dlya prikladu rozglyanemo vidnoshennya po modulyu 2 a b mod 2 displaystyle a equiv b pmod 2 nbsp todi i tilki todi koli yih riznicya a b displaystyle a b nbsp parne chislo Ce spivvidnoshennya prizvodit do dvoh klasiv ekvivalentnosti odin klas sho skladayetsya z usih parnih chisel ta drugij yakij skladayetsya z usih neparnih chisel Klas parnih chisel poznachayetsya yak 0 neparnih yak 1 Zgidno z cim spivvidnoshennyam 8 10 ta 118 nalezhat odnomu klasu 0 0 2 0 2 4 6 displaystyle 0 overline 0 2 left 0 pm 2 pm 4 pm 6 ldots right nbsp Mnozhina klasiv kongruentnosti za modulem n displaystyle n nbsp poznachayetsya Z n Z displaystyle mathbb Z n mathbb Z nbsp abo Z n displaystyle mathbb Z n nbsp chi Z n displaystyle mathbb Z n nbsp i za viznachennyam ce Z n Z a n a Z displaystyle mathbb Z n mathbb Z left overline a n a in mathbb Z right nbsp Koli n 0 Z n Z displaystyle mathbb Z n mathbb Z nbsp maye n elementiv i mozhe buti zapisano Z n Z 0 n 1 n 2 n n 1 n displaystyle mathbb Z n mathbb Z left overline 0 n overline 1 n overline 2 n ldots overline n 1 n right nbsp Dlya cih klasiv mozhna zadati operaciyi dodavannya vidnimannya mnozhennya a n b n a b n displaystyle overline a n overline b n overline a b n nbsp a n b n a b n displaystyle overline a n overline b n overline a b n nbsp a n b n a b n displaystyle overline a n overline b n overline ab n nbsp Obgruntovanist cih oznachen viplivaye iz vlastivostej poperednogo rozdilu Kilce klasiv rivnosti za modulem RedaguvatiTakim chinom Z n Z displaystyle mathbb Z n mathbb Z nbsp ye komutativnim kilcem Napriklad v Z 24 Z displaystyle mathbb Z 24 mathbb Z nbsp mayemo 12 24 21 24 9 24 displaystyle overline 12 24 overline 21 24 overline 9 24 nbsp Deyakij element m n displaystyle overline m n nbsp maye obernenij element todi i lishe todi koli m i n ye vzayemno prostimi chislami Spravdi yaksho m i n ye vzayemno prostimi to todi isnuyut a b Z displaystyle a b in mathbb Z nbsp taki sho a n b m 1 displaystyle an bm 1 nbsp Zvidsi a n b m 1 mod n displaystyle an bm equiv 1 pmod n nbsp i yak naslidok b m 1 mod n displaystyle bm equiv 1 pmod n nbsp Navpaki yaksho b m 1 mod n displaystyle bm equiv 1 pmod n nbsp dlya deyakogo b displaystyle b nbsp to a n b m 1 displaystyle an bm 1 nbsp dlya deyakogo a displaystyle a nbsp sho nemozhlivo vrahovuyuchi vzayemnu prostotu m i n Vidpovidno yaksho n displaystyle n nbsp proste chislo to Z n Z displaystyle mathbb Z n mathbb Z nbsp ye polem Rozv yazuvannya linijnih rivnyan RedaguvatiVikipidruchnik maye knigu na temu Rozv yaznik vprav po diskretnij matematici Koduvannya Modulna arifmetikaLinijne rivnyannya zapisuyetsya u viglyadi a x b mod n displaystyle a cdot x equiv b pmod n nbsp Rozv yazok mozhna otrimati bezposeredno dilennyam x b a mod n displaystyle x equiv frac b a pmod n nbsp abo za dopomogoyu formuli x b a f n 1 mod n displaystyle x equiv b cdot a varphi n 1 pmod n nbsp yaksho NSD a n 1 displaystyle a n 1 nbsp tobto vzayemno prosti chisla Funkciya f n displaystyle varphi n nbsp funkciya Ejlera yaka dorivnyuye kilkosti naturalnih chisel ne bilshih n i vzayemno prostih z nim Yaksho NSD a n 1 displaystyle a n not 1 nbsp porivnyannya abo maye ne yedinij rozv yazok abo ne maye rozv yazkiv Yak legko pobachiti porivnyannya 2 x 3 mod 4 displaystyle 2 cdot x equiv 3 pmod 4 nbsp ne maye rozv yazkiv na mnozhini naturalnih chisel Inshe porivnyannya 4 x 6 mod 22 displaystyle 4 cdot x equiv 6 pmod 22 nbsp maye dva rozv yazki x 7 x 18 displaystyle x 7 x 18 nbsp Div takozh RedaguvatiDilennya z ostacheyu Kvadratichnij zakon vzayemnosti Ostacha Podilnist Simvol Lezhandra Simvol YakobiDzherela RedaguvatiDrozd Yu A 1997 Teoriya algebrichnih chisel Kiyiv RVC Kiyivskij universitet s 82 ISBN 966 594 019 8 ukr Vinogradov I M Osnovy teorii chisel Arhivovano 17 grudnya 2004 u Wayback Machine M GITTL 1952 Vilenkin N Ya Sravneniya i klassy vychetov Arhivovano 4 listopada 2007 u Wayback Machine Kvant 10 1978 Otrimano z https uk wikipedia org w index php title Modulna arifmetika amp oldid 38139072