Модулна аритметика – Уикипедия

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

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

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

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

Познато използване на модулната аритметика е в
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 довело Пиер дьо Ферма до открития, които значително изпреварват времето си. Например, в писмо до Бернар де Бесси ^[4] от 18 октомври 1640 г. той докладва без доказателство теорема, която по-късно става известна с името Малка теорема на Ферма. В съвременната си формулировка теоремата гласи, че ако ${\displaystyle p}$ е просто число и ${\displaystyle a}$ е цяло число, което не се дели на ${\displaystyle p}$, тогава

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

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

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

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

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

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

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

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

${\displaystyle a=km+b}$,

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

${\displaystyle a=pm+r}$,

${\displaystyle b=qm+r}$,

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

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

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

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

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

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

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

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

По този начин отношение на съвпадане по модул ${\displaystyle m}$ е отношение на еквивалентност в множеството от цели числа. ^[7]

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

• 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) (съвпадане на числа чрез увеличаване на едното или намаляване на другото с едно и също число)

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

${\displaystyle (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 са взаимно прости числа.

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

• Ако a + k ≡ b + k (mod m), къдeто k е цяло число, тогава a ≡ b (mod m).
• Ако ka ≡ kb (mod m) и k е взаимнопросто с m /НОД${\displaystyle {(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;
• ако числата ${\displaystyle a}$ и ${\displaystyle b}$ съвпадат по модул ${\displaystyle m}$, а числото ${\displaystyle d}$ е делител на ${\displaystyle m}$, тогава ${\displaystyle a}$ и ${\displaystyle b}$ съвпадат по модул ${\displaystyle d}$.

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

Следствие:

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

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

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

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

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

• Малка теорема на Ферма: Ако p е просто число и не дели a, тогава ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$.
• Теорема на Ойлер: Ако a и n са взаимно прости, тогава ${\displaystyle 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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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