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

Мòдулна аритмèтика e система от алгебрични операции, дефинирани за остатъци при деление на фиксирано цяло положително число; система от аритметиката за цели числа, където числата циклично се „закръглят“ при достигане на определена стойност – модула.

Аритметичните операции с остатъци от числа по модул на фиксирана форма образуват модулната аритметика (аритметика по модул, модуларна аритметика, или часовникова аритметика), която се използва широко в математиката, информатиката и криптографията.

Сравняването на две цели числа по модула на естественото число $m$ е математическа операция, чрез която се проверява дали две избрани цели числа дават еднакъв остатък, когато се разделят на $m$. Всяко цяло число, когато е разделено на $m$, дава един от $m$ възможни остатъци: число от 0 до $m-1$; това означава, че всички цели числа могат да бъдат разделени на $m$ групи, всяка от които отговаря на определен остатък, когато е разделена на $m$. Тези групи се наричат ​​класове остатъци по модул $m$, а целите числа, съдържащи се в тях, се наричат ​​остатъци по модул $m$.

Съвременният подход към модулната аритметика е разработен от Карл Фридрих Гаус в книгата му Disquisitiones Arithmeticae, публикувана през 1801 г.

Отчитането на времето от този часовник използва аритметика по модул 12. Добавянето на 4 чàса към 9 часà дава 1 часà, тъй като 13 е равно на 1 по модул 12.

Познато използване на модулната аритметика е в
12-часовия часовник, при който денят е разделен на два 12-часови периода. Ако часът е 7:00 сега, тогава 8 часа по-късно ще бъде 3:00. Простото събиране би довело до 7 + 8 = 15, но 15:00 се чете като 3:00 на циферблата на часовника, защото часовниците се „закръглят“ на всеки 12 часа и числото на часа започва от нула, когато достигне 12. Казва се, че 15 съответства на 3 по модул 12, записано като 15 ≡ 3 (mod 12), така че 7 + 8 ≡ 3 (mod 12). По същия начин 8:00 представлява период от 8 часа и два пъти това ще даде 16:00, което се чете като 4:00 на циферблата на часовника, изписано като 2 × 8 ≡ 4 (mod 12).

История

Предпоставката за създаването на теорията на сравненията е възстановяването на трудовете на Диофант, които са публикувани в оригинал и с латински превод, благодарение на Клод Гаспар Баше де Мезириак, през 1621 г. Тяхното изследване e довело Пиер дьо Ферма до открития, които значително изпреварват времето си. Например, в писмо до Бернар де Бесси от 18 октомври 1640 г. той докладва без доказателство теорема, която по-късно става известна с името Малка теорема на Ферма. В съвременната си формулировка теоремата гласи, че ако $p$ е просто число и $a$ е цяло число, което не се дели на $p$, тогава

$a^{p-1}\equiv 1{\pmod {p}}$ .

Първото доказателство на тази теорема принадлежи на Лайбниц и той открива тази теорема независимо от Фермà не по-късно от 1683 г. и съобщава това с точното доказателство на Бернули. Освен това Лайбниц предлага прототипна формулировка на теоремата на Уилсън.

По-късно изследването на въпроси, свързани с теорията на числата и теорията на сравненията, е продължено от Ойлер, който въвежда квадратичния закон за взаимността и обобщава теоремата на Ферма, установявайки, че

$a^{\varphi (n)}\equiv 1{\pmod {n}},$

където $\varphi (n)$ е функцията на Ойлер.

Понятието и символното обозначение на сравненията са въведени от Гаус като важен инструмент за обосноваване на неговата аритметична теория, работата по която той започва през 1797 г. В началото на този период Гаус все още не е запознат с трудовете на своите предшественици, така че резултатите от работата му, изложени в първите три глави на книгата му „Аритметични изследвания“ (1801 г.), по същество вече са били известни, но методите, които той използва за доказателствата, се оказват абсолютно нови и от най-голямо значение за развитието на теорията на числата. Използвайки тези методи, Гаус трансформира цялата натрупана преди него информация, свързана с операциите за сравняване по модул, в последователна теория, която за първи път е представена в същата книга. В допълнение, той изучава сравненията на първа и втора степен, теорията на квадратичните остатъци и свързания с нея квадратичен закон за взаимността.

Съвпадане по модул

Ако две цели числа $a$ и $b$ при деление на цяло число $m>1$ дават еднакви остатъци, те се наричат съвпадащи (или равноостатъчи) по модул на числото $m$ . Съвпадането по модул се нарича още сходство по модул или конгруенция по модул и се означава

$a\equiv b{\pmod {m}}$.

Скобите означават, че ${\pmod {m}}$ се отнася за цялото уравнение, а не само за дясната му страна $b$. Това означение не трябва да се бърка с означението „$b\mod m$“ без скоби, което се отнася до модулната операция: остатъкът от $b$, когато е разделено на $m$, т.е. $b\mod m$ обозначава уникалното цяло число $r$, така че 0 ≤ r < m и $r\equiv b{\pmod {m}}$.

Числата $a$ и $b$ са сходни по модул $m$, ако тяхната разлика е цяло число $k$ пъти $m$

$a-b=km$, т. е. се дели на цялото число $m>1$ без остатък.

Двете определения за съвпадане (сходство) по модул са идентични, което се доказва по следния начин. Отношението на сходство от втората дефиниция може да бъде записано като

$a=km+b$,

изрично показвайки връзката му с делението с остатък. Въпреки това тук не е необходимо $b$ да е остатъкът при деленето на $a$ на $m$. По-скоро $a\equiv b{\pmod {m}}$ от първото определение твърди, че $a$ и $b$ имат еднакъв остатък, когато са разделени на $m$:

$a=pm+r$,

$b=qm+r$,

където 0 ≤ r < m е общият остатък. Като се извадят тези два израза и се зададе $k=p-q$, се получава формулировката във второто определение: $a-b=km$.

Примери:
По модул 12 може да се твърди, че

$31\equiv 7{\pmod {12}}$

защото разликата 38 − 14 = 24 = 2 × 12 е кратна на 12. Еквивалентно, 38 и 14 имат един и същ остатък 2, когато се разделят на 12.

Определението за съвпадане по модул се прилага и за отрицателни стойности. Например:

${\begin{aligned}4&\equiv -2{\pmod {6}}\\-8&\equiv 7{\pmod {5}}\\-3&\equiv -17{\pmod {7}}.\end{aligned}}$

Свойства на съвпадането по модул

Основни свойства

За фиксирано естествено число $m$ съвпадането по модул $m$ има следните основни свойства:

• рефлексивност: за всяко цяло число $a$ е вярно $a\equiv a{\pmod {m}}$;
• симетричност: ако $a\equiv b{\pmod {m}}$, тогава $b\equiv a{\pmod {m}}$;
• транзитивност: ако $a\equiv b{\pmod {m}}$ и $b\equiv c{\pmod {m}}$, тогава $a\equiv c{\pmod {m}}$.

По този начин отношение на съвпадане по модул $m$ е отношение на еквивалентност в множеството от цели числа.

Разширени свойства

Ако a₁ ≡ b₁ (mod m), a₂ ≡ b₂ (mod m), ... , a_n ≡ b_n (mod m), или ако a ≡ b (mod m), тогава:

• a + k ≡ b + k (mod m) за всяко цяло число k (съвпадане на числа при увеличаване с еднаква сума)
• a − k ≡ b − k (mod m) за всяко цяло число k (съвпадане на числа при намаляване с еднаква разлика)
• k a ≡ k b (mod m) за всяко цяло число k (съвпадане на умножени числа)
• k a ≡ k b (mod km) за всяко цяло число k (съвпадане на умножени числа по умножен модул)
• a₁ + a₂ + ... + a_n≡ b₁ + b₂ + ... + b_n (mod m) (съвпадане при добавяне)
• a₁ − a₂ − ... − a_n≡ b₁ − b₂ − ... − b_n(mod m) (съвпадане при изваждане)
• a₁ a₂ ≡ b₁ b₂ (mod m) (съвпадане на произведения от числа)
• a^k ≡ b^k (mod m) за всяко неотрицателно цяло число k (съвпадане при степенуване)
• p(a) ≡ p(b) (mod m), за всеки полином p(x) с цели коефициенти (съвпадане на оценени полиноми)

Ако a ≡ b + k (mod m) за всяко цяло число k, тогава a − k ≡ b (mod m) (съвпадане на числа чрез увеличаване на едното или намаляване на другото с едно и също число)

Към всяка част от съвпадането може да се добави цяло число, кратно на модула, т. е., ако числата $a$ и $b$ съвпадат по модул на някакво число $m$, то и $a+t_{1}$ съвпада с $b+t_{2}$ по модул $m$, където $t_{1}$ и $t_{2}$ са произволни цели числа, кратни на $m$:

$(a+t_{1})\equiv (b+t_{2}){\pmod {m}}$.

Ако a ≡ b (mod m), тогава обикновено е невярно, че k^a ≡ k^b (mod m). Вярно е обаче следното:

• Ако c ≡ d (mod φ(m)), където φ е функция на Ойлер, тогава a^c ≡ a^d (mod m) — при условие че a и m са взаимно прости числа.

Съвпаденията обаче не могат, най-общо казано, да бъдат разделени едно на друго или на други числа. Пример: $14\equiv 20{\pmod {6}}$, но като се намалят 2 пъти, се получава погрешно съвпадение: $7\equiv 10{\pmod {6}}$. За съкращения на съвпадения има следните правила:

• Ако a + k ≡ b + k (mod m), къдeто k е цяло число, тогава a ≡ b (mod m).
• Ако ka ≡ kb (mod m) и k е взаимнопросто с m /НОД${(k,m)=1}$/, тогава a ≡ b (mod m). Ако числото k не е взаимнопросто с модула, какъвто беше случаят в примера по-горе, тогава съвпадащите числа ka и kb не могат да бъдат намалени k пъти.
• Ако ka ≡ kb (mod km) и k ≠ 0, тогава a ≡ b (mod m).

Последното правило може да се използва за връзка между модулна аритметика и деление. Ако b е делител на a, тогава (a/b) mod m = (a mod bm) / b.

Обратното по модул число се определя от следните правила:

• Съществуване: Съществува означеното цяло число a⁻¹ такова, че aa⁻¹ ≡ 1 (mod m), ако и само ако a и m са взаимнопрости числа. Това цяло число a⁻¹ се нарича обратно по модул число на a по модул m.
• Ако a ≡ b (mod m) и a⁻¹ съществуват, тогава a⁻¹ ≡ b⁻¹ (mod m) (съвпадане с обратно по модул число, и, ако a = b, уникалност по модул m).
• Ако ax ≡ b (mod m) и a е взаимно просто с m, тогава решението на това линейно съответствие се дава от x ≡ a⁻¹b (mod m).

Обратното по модул число x ≡ a⁻¹ (mod m) може да бъде ефективно изчислено чрез решаване на уравнението на Безу ax + my = 1 for x, y – използвайки разширения Eвклидов алгоритъм.

По-специално, ако p е просто число, тогава a е взаимнопросто с p за всяко a, така че 0 < a < p; следователно Обратното по модул число съществува за всички a, които не съвпадат с нула по модул p.

Твърдения

Освен горните свойства, за съвпадането по модул са валидни следните твърдения:

• всеки две цели числа съвпадат по модул 1;
• ако числата $a$ и $b$ съвпадат по модул $m$, а числото $d$ е делител на $m$, тогава $a$ и $b$ съвпадат по модул $d$.

Доказателство

Нека

$a\equiv b{\pmod {m}}.$

Следователно

$a-b=mt,$ където $t$ е някакво цяло число.

Тъй като $d$ е делител на числото $m$, то

$m=cd$, където $c$ е някакво цяло число.

Следователно

$a-b=mt=(cd)t=qd,$ където $q=ct,$

и

$a\equiv b{\pmod {d}}$

по определение.

• Ако числата $a$ и $b$ съвпадат по $k$ модула ${m_{1},m_{2},...,m_{k}},$ то те съвпадат по модул, равен на най-малкото общо кратно на модулите ${m_{1},m_{2},...,m_{k}}$.

Доказателство

Нека

$a\equiv b{\pmod {m_{i}}},$ где $i=1,2,...,k.$

Следователно

$a-b=m_{i}t.$

Тъй като разликата $a-b$ е кратна на всяко $m_{i}$, то тя е кратна и на тяхното най-малко общо кратно.

Следствие:

За да съвпадат числата $a$ и $b$ по модул $m$, на който каноническото разложение на прости съмножители има вида

$m=\prod _{i=1}^{d}p_{i}^{\alpha _{i}}$,

необходимо и достатъчно е условието

$a\equiv b{\pmod {p_{i}^{\alpha _{i}}}},$ където $i=1,2,\ldots ,d$.

Усъвършенствани свойства

Някои от по-усъвършенстваните свойства на съвпаданията по модул са следните:

• Малка теорема на Ферма: Ако p е просто число и не дели a, тогава $a^{p-1}\equiv 1{\pmod {p}}$.
• Теорема на Ойлер: Ако a и n са взаимно прости, тогава $a^{\varphi (n)}\equiv 1{\pmod {n}}$, където φ е функцията на Ойлер.
• Просто следствие от малката теорема на Ферма е, че ако p е просто число, тогава a⁻¹ ≡ a^p−2 (mod p) е обратното по модул число на 0 < a < p. По-общо, от теоремата на Ойлер, ако a и n са взаимно прости, тогава a⁻¹ ≡ a^φ(n)−1 (mod n).
• Друго просто следствие е, че ако a ≡ b (mod φ(n)), където φ е функцията на Ойлер, тогава k^a ≡ k^b (mod n), при условие че k е взаимнопросто с n.
• Теорема на Уилсън: p е просто тогава и само ако (p − 1)! ≡ −1 (mod p).
• Китайска теорема за остатъците: За всяко a, b и взаимнопрости m, n съществува уникален x (mod mn), такъв че x ≡ a (mod m) и x ≡ b (mod n). Всъщност x ≡ b m_n⁻¹ m + a n_m⁻¹ n (mod mn), където m_n⁻¹ е обратното на m по модул n и n_m⁻¹ е обратното на n по модул m.
• Теорема на Лагранж: Съвпадането f (x) ≡ 0 (mod p), където p е просто число и f (x) = a₀ xⁿ + ... + a_n е полином с цели коефициенти, така че a₀ ≠ 0 (mod p), има най-много n корена.
• Примитивен корен по модул n: Число g е примитивен корен по модул n, ако за всяко цяло число a, взаимнопросто с n, съществува цяло число k, такова че g^k ≡ a (mod n). Примитивен корен по модул n съществува тогава и само ако n е равно на 2, 4, p^k или 2p^k, където p е нечетно просто число и k е положително цяло число. Ако съществува примитивен корен по модул n, тогава има точно φ(φ(n)) такива примитивни корени, където φ е функцията на Ойлер.
• Квадратичен остатък: Цялото число a е квадратичен остатък по модул n, ако съществува цяло число x, такова че x² ≡ a (mod n). Критерият на Ойлер твърди, че ако p е нечетно просто число и a не е кратно на p, тогава a е квадратичен остатък по модул p тогава и само ако

  a^(p−1)/2 ≡ 1 (mod p).

Свързани определения

Класове остатъци

Множеството от всички числа, съвпадащи с $a$ по модул $m$, т. е. $a+km$, където $k$ е всяко цяло число, се нарича остатъчен клас или клас на остатъците на $a$ по модул $m$ и обикновено се обозначава $[a]_{m}$ или ${\bar {a}}_{m}$. По този начин сходството $a\equiv b{\pmod {m}}$ е еквивалентно на равенството на остатъчните класове $[a]_{m}=[b]_{m}$ и това обяснява защо "=" често се използва вместо "≡" в този контекст.

Всеки остатъчен клас по модул $m$ съдържа точно едно цяло число в диапазона 0, ..., m − 1. По този начин тези $m$ цели числа са представители на техните съответни остатъчни класове. Обикновено е по-лесно да се работи с отделни цели числа, отколкото с множества от цели числа; най-често разглежданите представители, а не техните остатъчни класове. Всяко число от класа на остатъците се нарича остатък по модул $m$: по-точно, уникалното цяло число $k$, такова че 0 ≤ k < m и k ≡ a (mod m), се нарича остатък на $a$ по модул $m$.

Нека за определеност $r$ е остатъкът от деленето на който и да е от представителите на избрания клас на $m$, тогава всяко число $q$ от този клас остатъци може да бъде представено като $q=mt+r$, където $t$ е цяло число. Остатъкът, равен на остатъка $r$ ($q=r$ при $t=0$) се нарича най-малък неотрицателен остатък, а остатъкът $\rho$ ($q=\rho$), най-малкият по абсолютна стойност, се нарича абсолютно най-малък остатък. За $r<{\frac {m}{2}}$ се получава $\rho =r$, в противен случай $\rho =r-m$.
Ако $m$ е четно и $r={\frac {m}{2}}$, тогава $\rho =-{\frac {m}{2}}$.

Тъй като съвпадането по модул $m$ е отношение на еквивалентност на множеството от цели числа $\mathbb {Z}$, тогава класовете остатъци по модул $m$ са класове на еквивалентност и техният брой е равен на $m$. Класът на еквивалентност по модул $m$ на цялото число $a$ е множеството от всички цели числа от формàта $a+km$, където $k$ е всяко цяло число.

Множеството от всички класове остатъци по модул $m$ се означава със $\mathbb {Z} _{m}$ или $\mathbb {Z} /m\mathbb {Z}$ или $\mathbb {Z} /(m)$.

Операциите събиране и умножение на $\mathbb {Z}$ индуцират съответните операции върху множеството $\mathbb {Z} _{m}$:

$[a]_{m}+[b]_{m}=[a+b]_{m}$;

$[a]_{m}\cdot [b]_{m}=[a\cdot b]_{m}$.

По отношение на тези операции множеството $\mathbb {Z} _{m}$ е краен пръстен, а за простото число $m$ е крайно поле.

Задачи

1. Да се докаже, че 5 и 26 май са в един и същи ден от седмицата.
Доказателство: За да са двете числа от месеца в един ден от седмицата, трябва да съвпадат по модул 7 и така да се различават с цял брой седмици, т. е. разликата между тях да се дели на 7 без остатък: (26 – 5):7 = 21:7 = 3.

2. Ако 9 май е четвъртък, какъв ден от седмицата е 26 май?
Решение: Сравняват се двете числа по модул 7:
9 = 1 х 7 + 2 ; 26 = 3 х 7 + 5. Вторият остатък е по-голям от първия с 3. Следователно като ден от седмицата 26 май е 3 дни след четвъртък – в неделя.

3. Колко градуса реално е разликата между ъглите 415° и 756°?
Решение: Ъглите се изменят периодично и стойностите им се повтарят през 360°. Двата ъгъла се сравняват по модул 360:
415° = 1.360° + 55° и 415° ≡ 55° (mod 360);
756° = 2.360° + 36° и 756° ≡ 36° (mod 360);
Разликата между ъглите реално е 55° – 36° = 19°.

4. Да се изчисли без калкулатор разликата tg 405° – cos 420°.
Решение: Тригонометричните функции са периодични и се редуцират до стандартни стойности за ъгли 0°, 30°, 45°, 60°, 90°, 180° или 270° чрез сходство по модул, което в случая достига до равенство.
Функцията тангенс е периодична с период 180° и се трансформира по модул 180:
tg 405° = tg (2.180° + 45°) = tg 45° = 1 ;
Функцията косинус е периодична с период 360° и се трансформира по модул 360:
cos 420° = cos (1.360° + 60°) = cos 60° = sin 30° = 1/2 ;
tg 405° – cos 420° = 1 – 1/2 = 1/2.

5. Използването на сходства по модул улеснява получаването на различни признаци за делимост. Задача: Да се изведе признак, че естественото число $N$ се дели на 7. Записва се $N$ във формата $10a+b$ (т.е. отделя се цифрата на единиците $b$). Условието, че $N$ се дели на 7, може да бъде записано като: $10a+b\equiv 0{\pmod {7}}$. Умножава се това сходство по $-2$:

$-20a-2b\equiv 0{\pmod {7}}$.

Прибавя се вляво числото $21a$, кратно на модула:

$a-2b\equiv 0{\pmod {7}}$.

От тук следва следния признак за делимост на 7: трябва да се извади два пъти броя на единиците от броя на десетиците, след което се повтаря тази операция, докато се получи двуцифрено или едноцифрено число; ако то се дели на 7, тогава и даденото число се дели. Например нека $N=22624$. Алгоритъм за проверка:

$N_{1}=2262-2\cdot 4=2254;\ N_{2}=225-2\cdot 4=217;N_{3}=21-2\cdot 7=7$

Извод: 22624 се дели на 7.