Задание

Заполните пропуски.

Два целых числа, разность которых кратна данному натуральному числу m, называются сравнимыми по модулю m. (Слово «модуль» происходит от латинского modulus, что по-русски означает «мера», «величина».) Утверждение «a сравнимо с b по модулю m» обычно записывают в виде a ≡ b (mod m), и называют сравнением. Вот примеры сравнений: 5 ≡ 1 (mod 2), 48 ≡ 0 (mod 6), 16 ≡ 9 (mod 5). Сравнение по модулю 1 выполняется для любых двух целых чисел, так как всякое число кратно 1. Два числа сравнимы по модулю 2, если они одной четности, т.е. либо оба четны, либо оба нечетны. Определение сравнения было сформулировано в книге К. Ф. «Арифметические исследования». Эту работу, написанную на латинском языке, начали печатать в 1797 г., но книга вышла в свет лишь в 1801 г. из-за того, что процесс книгопечатания в то время был чрезвычайно трудоемким и длительным. Первый раздел книги Гаусса так и называется: «О сравнении чисел вообще». Сравнениями очень удобно пользоваться в тех случаях, когда достаточно знать в каких-либо исследованиях числа с точностью до кратных некоторого числа. Например, если нас интересует, на какую цифру оканчивается куб целого числа a, то нам достаточно знать a лишь с точностью до кратных числа 10, и можно пользоваться сравнениями по модулю 10.

Определение сравнений.

Определение. Если а и b — два числа и их разность а - b на натуральное число m, то говорят, что a и b по модулю m.

Мы выражаем это записью a  ≡  b (mod m), (1) которая читается так: а сравнимо с b по модулю m.

m мы предполагаем натуральным; он называется модулем сравнения. Наше высказывание (1) означает, что a - b = mk, где k — целое число.

Пример 1.

1) 23 ≡ 8 (mod 5), так как 23 - 8 = 15 = 5 ∙ 3;

2) 47 ≡ 11 (mod 9), так как 47 - 11 = 36 = 9 ∙ 4;

3) -11 ≡ 5 (mod 8), так как - 11 - 5 = - 16 = 8 ∙ (-2);

4) 81 ≡ 0 (mod 27), так как 81 - 0 = 81 = 27 ∙ 3.

Пример 2

Вычислить элемент, обратный а по mod n, если a = 9; n = 29.

Решение: Воспользуемся расширенным алгоритмом Евклида: 29 = 9 ∙ 3 + 2; 9 = 2 ∙ 4 + 1; 2 = 1 ∙ 2 + 0.

Обратный ход: 1 = 9 - 2 ∙ 4 = 9 ∙ 1 - (29 - 9 ∙ 3) ∙ 4 = 9 ∙ 13 - 29 ∙ 4.

Проверка: 13 ∙ 9 = 117. 117 ≡ 1 (mod( 29)).

Ответ: обратный элемент равен 13.