Система остаточных классов - введение

Теоретико-числовая база построения системы остаточных классов

Напомним определение деления с остатком.

Определение

Говорят, что целое число $n$ делится на натуральное число $m$ с остатком, если имеется пара целых чисел $q$ и $r$, таких, что $n = m \cdot q+r$ и $0\le r<m$. $n$ называется делимым, $m$ - делителем, $q$ - неполным частным, $r$ - остатком.

Для целых чисел:

Определение

Говорят, что целое число $n \in Z$ делится на натуральное число $m \in Z$ с остатком, если имеется пара целых чисел $q$ и $r$, таких, что $n = m \cdot q+r$ и $0\le r<|m|$.

Пример:

48 при делении на 5 даёт остаток 3, т.к. $48=5\cdot 9+3$, $0\le 3<5$, -48 при делении на 5 даёт остаток 2, т.к. $-48=5\cdot (-10)+2$, $0\le 2<5$.

Сравнения и их основные свойства

Возьмём произвольное фиксированное натуральное число $m$ и будем рассматривать остатки при делении на $m$ различных целых чисел.

При рассмотрении свойств этих остатков и проведении операций над ними удобно ввести понятие сравнения по модулю.

Определение

Два целых числа $a$ и $b$ называются сравнимыми по модулю $m$, если их разность $a-b$ делится без остатка на $m$.

Символически сравнимость записывается в виде формулы (сравнения):

$a \equiv b \pmod{m}$

Число $m$ называется модулем сравнения.

Эквивалентная формулировка:

Определение

Целые числа $a$ и $b$ называются сравнимыми по модулю $m$, если остатки от деления этих чисел на $m$ равны.

Отношение сравнимости по модулю $m$ обладает свойствами рефлексивности, симметричности и транзитивности, т.е. является отношением эквивалентности.

Отнесём все целые числа, дающие при делении на $m$ один и тот же остаток в один класс, поэтому получится $m$ различных классов по модулю $m$. Множество всех чисел сравнимых с $a$ по модулю $m$ называется классом вычетов $a$ по модулю $m$.

Подробнее о свойствах сравнений и классах вычетов смотри Сравнения и их основные свойства

Теорема о делении с остатком. Алгоритм Евклида

Теорема о делении с остатком

Для любых целых a и b, $b \not= 0$, существует единственный набор целых чисел q и r, что a = bq + r и $0 \le r < |b|$, где |b| — модуль числа b.

На этой операции основан алгоритм Евклида нахождения наибольшего общего делителя двух целых чисел.

Алгоритм Евклида для целых чисел

Пусть $a$ и $b$ — целые числа, не равные одновременно нулю, и последовательность чисел

$a > b > r_1 > r_2 > r_3 > r_4 > \cdots >r_n$

определена тем, что каждое $r_k$ — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

$a = bq_0 + r_1$

$b = r_1q_1 + r_2$

$r_1 = r_2q_2 + r_3$

$\cdots$

$r_{k-2} = r_{k-1} q_{k-1} + r_k$

$\cdots$

$r_{n-2} = r_{n-1}q_{n-1}+ r_n$

$r_{n-1} = r_n q_n$

Тогда НОД(a,b), наибольший общий делитель $a$ и $b$, равен $r_n$, последнему ненулевому члену этой последовательности.

Существование таких $r_1, r_2, ...$, то есть возможность деления с остатком $a$ на $b$ для любого целого $a$ и целого $b\ne 0$, доказывается индукцией.

Корректность этого алгоритма вытекает из следующих двух утверждений:

• Пусть $a = bq + r$, тогда НОД ($a$, $b$) = НОД ($b$, $r$).
• НОД(0,$r$) = $r$ для любого ненулевого $r$ (так как 0 делится на любое целое число, кроме нуля).

Китайская теорема об остатках

Фундаментальным положением, лежащим в основе модулярного представления чисел, является китайская теорема об остатках (Chinese Remainder Theorem - CRT). Например, эта теорема гарантирует, что при правильном выборе модулей СОК каждое число из динамического диапазона имеет в СОК единственное представление, и по этому представлению можно определить представленное число. В своей первоначальной формулировке эта теорема была доказана китайским математиком Сунь-Цзы приблизительно в 100 г. н.э. В современной формулировке теорема звучит так:

Теорема

Пусть $p_1, p_2, \ldots, p_k$ - попарно взаимно простые числа, большие 1, и пусть $p = p_1 \cdot p_2 \cdot \ldots \cdot p_k$. Тогда существует единственное неотрицательное решение по модулю $p$ следующей системы сравнений:

$x \equiv a_1 \pmod{p_1}$,

$x \equiv a_2 \pmod{p_2}$,

$\ldots$,

$x \equiv a_k \pmod{p_k}$.

Другими словами, отображение, которое каждому целому числу $x$, $0\le x <p$, ставит в соответствие кортеж $a_1, a_2,\ldots, a_k$, где $x \equiv a_i \pmod{p_i}, i = 1, \ldots k$ является биекцией кольца $Z_P$ на декартово произведение $Z_{p_1} \times Z_{p_2} \times \ldots \times Z_{p_k}$ колец $Z_{p_1}, Z_{p_2}, \ldots, Z_{p_k}$.

Подробности и доказательство теоремы смотри Китайская теорема об остатках.

Смотри также Китайская теорема об остатках(КТО II), Китайская теорема об остатках (КТО III).

Теоремы Эйлера и Ферма, их роль в вычислении мультипликативных обратных элементов по заданному модулю

Определение

Функция Эйлера $phi (n)$ — это количество чисел от $1$ до $n$, взаимно простых с $n$.

Т.е. это количество таких натуральных чисел из отрезка [1; n], наибольший общий делитель (НОД) которых с $n$ равен единице.

Tеоремa Эйлера

Если $a$ и $p$ взаимно просты, то $a^{phi(p)} \equiv 1 \pmod p$, где $phi (n)$ - функция Эйлера.

В частном случае, когда $m$ простое, теорема Эйлера превращается в так называемую малую теорему Ферма: Частным случаем теоремы Эйлера является малая теорема Ферма.

Малая теорема Ферма

Если $p$ - простое число и $a$ - произвольное целое число, не делящееся на $p$, то $a^{p-1} \equiv 1 \pmod p$.

Смотри Функция Эйлера, Вычисление мультипликативных обратных элементов по заданному модулю.

Числа Мерсенна, Ферма и операции над ними

При рассмотрении отдельных классов простых чисел интерес представляет вопрос о простых числах специального вида, например, числа Мерсенна или числа Ферма.

Определение

Числа Мерсенна — числа вида $M_n = 2^n - 1$, где $n$ — натуральное число. Названы в честь французского математика Марена Мерсенна.

Иногда числами Мерсенна называют только числа $M_n$ с нечетными или простыми индексами n.

Множества простых чисел в этих последовательностях совпадают, а потому понятие простого числа Мерсенна не зависит от того, как именно определяются числа Мерсенна.

При простых значениях n = p число может оказаться простым, но может быть составным. Например, при $p = 2, 3, 5, 7, 13, 17, 19$ мы получаем простые числа Мерсенна: $3, 7, 31, 127, 8191, 131071$, а при $p = 11, 23, 29$ числа $2^p - 1$ - составные.

Определение

Числа Ферма — числа вида $F_n=2^{2^n}+1$, где n — неотрицательное целое число.

При $n = 0, 1, 2, 3, 4$ числа Ферма простые: $3, 5, 17, 257, 65537$.

Все числа Мерсенна и Ферма – взаимно простые.

Для модулей СОК вида $M_n = 2^n - 1$, $M_n = 2^n + 1$ легко реализуется преобразование и арифметические операции. Поэтому эффективно выбирать модули СОК в виде чисел Мерсенна и Ферма.

Смотри Числа Мерсенна и Ферма.