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

Мòдулна аритмèтика 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. Добавянето на 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 довело Пиер дьо Ферма до открития, които значително изпреварват времето си. Например, в писмо до Бернар де Бесси ^[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 a}$ и ${\displaystyle b}$ при деление на цяло число ${\displaystyle m>1}$ дават еднакви остатъци, те се наричат съвпадащи (или равноостатъчи) по модул на числото ${\displaystyle m}$ ^[6]. Съвпадането по модул се нарича още сходство по модул или конгруенция по модул и се означава

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

Скобите означават, че ${\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}$ и ${\displaystyle b}$ са сходни по модул ${\displaystyle m}$, ако тяхната разлика е цяло число ${\displaystyle k}$ пъти ${\displaystyle m}$

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

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

${\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\equiv b{\pmod {m}}.}$

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

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

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

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

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

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

и

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

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

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

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

Нека

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

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

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

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

Следствие:

За да съвпадат числата ${\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.

Източници

1. Вельшенбах, М. – Криптография на Си и C++ в действии. Глава 5. Модульная математика: вычисление в классах вычетов. М., изд. „Триумф“, 2004. ISBN 5-89392-083-X. с. 464, стр. 81—95. Посетен на 9.1.2024. (на руски)
2. Материалы международной научной конференции “Модулярная aрифметика” // Виртуальный компьютерный музей, 2005. Архивиран от оригинала на 2007-10-05. Посетен на 2010-07-31. (на руски)
3. Егоров А. А. Сравнения по модулю и арифметика остатков (статья) // журнал Квант. M., 5, 1970. с. 28—33. Архивиран от оригинала на 2016-03-04. Посетен на 9.1.2024. (на руски)
4. Френски математик, член на Френската академия на науките от 1666 г.
5. Вилейтнер, Г. История математики от Декарта до середины XIX. Глава III. Теория чисел. М., Государственное издательство физико-математической литературы, 1960. с. 69—84. Архивиран от оригинала на 2015-09-24. (на руски)
6. Степанов С. А. Сравнения. Глава 1. Основные понятия. М., «Знание», 1975. с. 3—9. Архивиран от оригинала на 2015-08-24. (на руски)
7. Сизый С. В. – §4. Теория сравнений // Лекции по теории чисел. — М.: Физматлит, 2008. — 192 с., с=88 — ISBN 978-5-9221-0741-9.
8. The Art of Problem Solving. 7. Т. 1. AoPS Incorporated, 2006. ISBN 0977304566. с. 44.
9. Сагалович Ю. Л. – Введение в алгебраические коды, — 2-е изд. — М.: ИППИ РАН, 2010. — 320 с., — ISBN 978-5-901158-14-2.
10. Бухштаб, А. А. Теория чисел. Глава 8. Классы. М., «Просвещение», 1966. с. 384, с. 77—78. Архивиран от оригинала на 2015-11-20. Посетен на 10.01.2024. (на руски)
11. Сагалович 2010, с. 29 – 32.
12. Сизый 2008, с. 87 – 88, 91.
13. Лидл Р.,, Нидеррайтер Г. Конечные поля. В 2-х тт. М., „Мир“, 1998. ISBN 5-03-000065-8. с. 430, с. 27 (Пример 1.37). Посетен на 01.01.2024. (на руски)
14. Нестеренко Ю. В. – Теория чисел. — М.: Издательский центр «Академия», 2008. — С. 132—133. — 272 с. — ISBN 9785769546464.