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

Мòдулна аритмèтика 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(\mathrm{mod}p)$ .

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

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

$a^{\phi (n)}\equiv 1(\mathrm{mod}n),$

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

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

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

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

$a\equiv b(\mathrm{mod}m)$.

Скобите означават, че $(\mathrm{mod}m)$ се отнася за цялото уравнение, а не само за дясната му страна $b$. Това означение не трябва да се бърка с означението „$bmodm$“ без скоби, което се отнася до модулната операция: остатъкът от $b$, когато е разделено на $m$, т.е. $bmodm$ обозначава уникалното цяло число $r$, така че Шаблон:Math и $r\equiv b(\mathrm{mod}m)$.

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

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

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

$a=km+b$,

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

$a=pm+r$,

$b=qm+r$,

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

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

$31\equiv 7(\mathrm{mod}12)$

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

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

$\begin{array}{cc}4& \equiv -2(\mathrm{mod}6)\\ -8& \equiv 7(\mathrm{mod}5)\\ -3& \equiv -17(\mathrm{mod}7).\end{array}$

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

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

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

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

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

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

Ако Шаблон:Math, Шаблон:Math, ... , Шаблон:Math, или ако Шаблон:Math, тогава:

• Шаблон:Math за всяко цяло число Шаблон:Math (съвпадане на числа при увеличаване с еднаква сума)
• Шаблон:Math за всяко цяло число Шаблон:Math (съвпадане на числа при намаляване с еднаква разлика)
• Шаблон:Math за всяко цяло число Шаблон:Math (съвпадане на умножени числа)
• Шаблон:Math за всяко цяло число Шаблон:Math (съвпадане на умножени числа по умножен модул)
• Шаблон:Math (съвпадане при добавяне)
• Шаблон:Math (съвпадане при изваждане)
• Шаблон:Math (съвпадане на произведения от числа)
• Шаблон:Math за всяко неотрицателно цяло число Шаблон:Math (съвпадане при степенуване)
• Шаблон:Math, за всеки полином Шаблон:Math с цели коефициенти (съвпадане на оценени полиноми)

Ако Шаблон:Math за всяко цяло число Шаблон:Math, тогава Шаблон:Math (съвпадане на числа чрез увеличаване на едното или намаляване на другото с едно и също число)

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

$(a+t_1)\equiv (b+t_2)(\mathrm{mod}m)$.

Ако Шаблон:Math, тогава обикновено е невярно, че Шаблон:Math. Вярно е обаче следното:

• Ако Шаблон:Math където Шаблон:Math е функция на Ойлер, тогава Шаблон:Math — при условие че Шаблон:Math и Шаблон:Math са взаимно прости числа.

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

• Ако Шаблон:Math, къдeто Шаблон:Math е цяло число, тогава Шаблон:Math.
• Ако Шаблон:Math и Шаблон:Math е взаимнопросто с Шаблон:Math /НОД$(k,m)=1$/, тогава Шаблон:Math. Ако числото Шаблон:Math не е взаимнопросто с модула, какъвто беше случаят в примера по-горе, тогава съвпадащите числа Шаблон:Math и Шаблон:Math не могат да бъдат намалени Шаблон:Math пъти.
• Ако Шаблон:Math и Шаблон:Math, тогава Шаблон:Math.

Последното правило може да се използва за връзка между модулна аритметика и деление. Ако Шаблон:Math е делител на Шаблон:Math, тогава Шаблон:Math.

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

• Съществуване: Съществува означеното цяло число Шаблон:Math такова, че Шаблон:Math, ако и само ако Шаблон:Math и Шаблон:Math са взаимнопрости числа. Това цяло число Шаблон:Math се нарича обратно по модул число на Шаблон:Math по модул Шаблон:Math.
• Ако Шаблон:Math и Шаблон:Math съществуват, тогава Шаблон:Math (съвпадане с обратно по модул число, и, ако Шаблон:Math, уникалност по модул Шаблон:Math).
• Ако Шаблон:Math и Шаблон:Math е взаимно просто с Шаблон:Math, тогава решението на това линейно съответствие се дава от Шаблон:Math.

Обратното по модул число Шаблон:Math може да бъде ефективно изчислено чрез решаване на уравнението на Безу Шаблон:Math for Шаблон:Math, Шаблон:Math – използвайки разширения Eвклидов алгоритъм.

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

Твърдения

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

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

• Ако числата $a$ и $b$ съвпадат по $k$ модула $m_1,m_2,...,m_k,$ то те съвпадат по модул, равен на най-малкото общо кратно на модулите $m_1,m_2,...,m_k$.

Следствие:

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

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

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

$a\equiv b(\mathrm{mod}{p}_i^{{\alpha }_i}),$ където $i=1,2,\dots ,d$.

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

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

• Малка теорема на Ферма: Ако Шаблон:Math е просто число и не дели Шаблон:Math, тогава $a^{p-1}\equiv 1(\mathrm{mod}p)$.
• Теорема на Ойлер: Ако Шаблон:Math и Шаблон:Math са взаимно прости, тогава $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$, където Шаблон:Math е функцията на Ойлер.
• Просто следствие от малката теорема на Ферма е, че ако Шаблон:Math е просто число, тогава Шаблон:Math е обратното по модул число на Шаблон:Math. По-общо, от теоремата на Ойлер, ако Шаблон:Math и Шаблон:Math са взаимно прости, тогава Шаблон:Math.
• Друго просто следствие е, че ако Шаблон:Math, където Шаблон:Math е функцията на Ойлер, тогава Шаблон:Math, при условие че Шаблон:Math е взаимнопросто с Шаблон:Math.
• Теорема на Уилсън: Шаблон:Math е просто тогава и само ако Шаблон:Math.
• Китайска теорема за остатъците: За всяко Шаблон:Math, Шаблон:Math и взаимнопрости Шаблон:Math, Шаблон:Math съществува уникален Шаблон:Math, такъв че Шаблон:Math и Шаблон:Math. Всъщност Шаблон:Math, където Шаблон:Math е обратното на Шаблон:Math по модул Шаблон:Math и Шаблон:Math е обратното на Шаблон:Math по модул Шаблон:Math.
• Теорема на Лагранж: Съвпадането Шаблон:Math, където Шаблон:Math е просто число и Шаблон:Math е полином с цели коефициенти, така че Шаблон:Math, има най-много Шаблон:Math корена.
• [[:ru:Первообразный корень (теория чисел)|Примитивен корен по модул Шаблон:Math]]: Число Шаблон:Math е примитивен корен по модул Шаблон:Math, ако за всяко цяло число Шаблон:Math, взаимнопросто с Шаблон:Math, съществува цяло число Шаблон:Math, такова че Шаблон:Math. Примитивен корен по модул Шаблон:Math съществува тогава и само ако Шаблон:Math е равно на Шаблон:Math или Шаблон:Math, където Шаблон:Math е нечетно просто число и Шаблон:Math е положително цяло число. Ако съществува примитивен корен по модул Шаблон:Math, тогава има точно Шаблон:Math такива примитивни корени, където Шаблон:Math е функцията на Ойлер.
• Квадратичен остатък: Цялото число Шаблон:Math е квадратичен остатък по модул Шаблон:Math, ако съществува цяло число Шаблон:Math, такова че Шаблон:Math. Критерият на Ойлер твърди, че ако Шаблон:Math е нечетно просто число и Шаблон:Math не е кратно на Шаблон:Math, тогава Шаблон:Math е квадратичен остатък по модул Шаблон:Math тогава и само ако

  Шаблон:Math.

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

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

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

Всеки остатъчен клас по модул $m$ съдържа точно едно цяло число в диапазона Шаблон:Math. По този начин тези $m$ цели числа са представители на техните съответни остатъчни класове. Обикновено е по-лесно да се работи с отделни цели числа, отколкото с множества от цели числа; най-често разглежданите представители, а не техните остатъчни класове. Всяко число от класа на остатъците се нарича остатък по модул $m$: по-точно, уникалното цяло число $k$, такова че Шаблон:Math и Шаблон:Math, се нарича остатък на $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}$. Шаблон:Sfn

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

Множеството от всички класове остатъци по модул $m$ се означава със ${\mathbb{Z}}_m$ или $\mathbb{Z}/m\mathbb{Z}$ Шаблон:Sfn или $\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. Да се изчисли без калкулатор разликата Шаблон:Math.
Решение: Тригонометричните функции са периодични и се редуцират до стандартни стойности за ъгли 0°, 30°, 45°, 60°, 90°, 180° или 270° чрез сходство по модул, което в случая достига до равенство.
Функцията тангенс е периодична с период 180° и се трансформира по модул 180:
Шаблон:Math = Шаблон:Math = Шаблон:Math = Шаблон:Math ;
Функцията косинус е периодична с период 360° и се трансформира по модул 360:
Шаблон:Math = Шаблон:Math = Шаблон:Math = Шаблон:Math = Шаблон:Math ;
Шаблон:Math = Шаблон:Math = Шаблон:Math.

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

$-20a-2b\equiv 0(\mathrm{mod}7)$.

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

$a-2b\equiv 0(\mathrm{mod}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.