Сравнения, система вычетов, решение линейных систем по модулю

Эта статья находится в разработке!

Сравнения по модулю

Будем рассматривать целые числа в связи с остатками от деления их на данное целое число m, которое назовем модулем. Каждому целому числу отвечает определенный остаток от деления его на m. Если двум целым a и b отвечает один и тот же остаток r, то они называются сравнимыми по модулю m.

Сравнимость для a и b записывается так :
[math]a \equiv b(mod \text{ } m)[/math]

Сравнимость чисел a и b по модулю m равносильна:

• 1. Возможности представить a в форме [math]\Huge{a = b + mt}[/math], где t - целое.
• 2. Делимости [math]\Huge{a - b}[/math] на m.

Арифметика сравнений

Свойства сравнений

• 1. Два числа, сравнимые с третьим сравнимы между собой. [math]a \equiv c(mod \text{ }m) \text{, } b \equiv c(mod \text{ }m) \Rightarrow a \equiv b(mod \text{ }m)[/math]
• 2. Сравнения можно почленно складывать. [math] a_1 + a_2 + a_3 \equiv b_1 + b_2 + b_3(mod \text{ }m)[/math]
• 3. Сравнения можно почленно перемножать. [math] a_1a_2a_3 \equiv b_1b_2b_3(mod \text{ }m)[/math]
• 4. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.
• 5. Обе части сравнения можно умножить на одно и тоже число.
• 6. Обе части сравнения и модуль можно разделить на их общий делитель.
• 7. Если сравнение [math]a\equiv b[/math] имеет место по нескольким модулям, то оно имеет место и по модулю равному НОК этих модулей.
• 8. Если сравнение имеет место по модулю m, то оно имеет место и по модулю d, равному любому делителю числа m.
• 9. Если одна часть сравнения и модуль делятся на некоторое число, то и другая сторона сравнения должна делится на это число.
• 10. Если [math]a \equiv b(mod \text{ }m) [/math], то [math](a,m) = (b,m) [/math].

Полная и приведенная система вычетов

Числа равноостаточные(сравнимые по модулю m) образуют класс чисел по модулю m. Из такого определения следует, что всем числам класса отвечает один остаток r, и мы получим все числа класса, если в форме [math]mt + r [/math] заставим t пробегать все целые числа. Таким образом для каждого значения остатка имеется свой класс чисел.

Любое число класса называется вычетом по модулю m. Вычет получаемый при [math] t = 0[/math], равный самому остатку r, называется наименьшим неотрицательным вычетом.

Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов по этому модулю.

Согласно 10-му свойству сравнений, числа одного класса по модулю m имеют одинаковый НОД. Особенно важны классы, содержащие числа, взаимно простые с модулем. Взяв вычет от каждого такого класса, получим приведенную систему вычетов по модулю m.

Решение линейных систем по модулю

Пусть [math] (a, b) = d [/math]. Сравнение [math] ax \equiv b(mod \text{ }m)[/math] невозможно, если b не делится на d. При b, кратном d, сравнение имеет d решений.

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

Пусть [math] n = n_1 n_2 \ldots n_k [/math], где [math] n_i [/math] - попарно взаимно простые числа. Рассмотрим соответствие [math] a \rightarrow (a_1 , a_2 , \ldots , a_k) [/math], где [math] a_i = a(mod \text{ }n)[/math]. Такое соответствие является однозначным, для любого а ([math] 0 \le a \le n [/math]).
Неконструктивное доказательство :
[math] x-y \rightarrow (0 , 0 , \ldots , 0) \Leftrightarrow (x-y) \vdots m_i [/math], значит [math] x \equiv y(mod \text{ } \prod n_i )[/math]. То есть разных наборов всего n.

Теорема Ферма

[math] a^p \equiv a(mod \text{ }p)[/math], где p — простое. Доказательство.

• 1. [math] a \vdots p[/math], тогда, очевидно, [math] a^p \vdots p[/math].
• 2. Рассмотрим случай a не кратного p. Рассмотрим приведенную систему вычетов [math] r_1, r_2, \ldots , r_{p-1} [/math].

Система [math] ar_1, ar_2, \ldots , ar_{p-1} [/math] задает те же вычеты, только в другом порядке, таким образом [math] \prod_{i=1}^{p-1} ar_i \equiv \prod_{i=1}^{p-1} r_i (mod \text{ }p) [/math], сократив лишнее, получаем [math] a^{p-1} \equiv 1(mod \text{ }p)[/math]. Домножив обе части на a, получим теорему в изначально представленном виде.

Теорема Вильсона

p — простое [math] \Leftrightarrow (p-1)! \equiv -1(mod \text{ }p)[/math] Доказательство:

• [math] \Leftarrow [/math] Если p — не простое, тогда [math] (p-1)! \vdots p [/math] (кроме [math] p = 4 [/math]),но -1, в любом случае, мы не получим.
• [math] \Rightarrow [/math]