Модульная арифметика | это... Что такое Модульная арифметика? (original) (raw)

Сравнение по модулю натурального числа — отношение эквивалентности на множестве целых чисел, связанное с делимостью. Оно даёт возможность работать с системой чисел, более простой чем целые числа, в которой значения «зацикливаются» (повторяются) после достижения определенного значения.

В дискретной математике, для сравнений по модулю используется также термин модульная (или модулярная) арифметика.

Содержание

1 Определения
2 Свойства
3 Классы вычетов
4 Решение сравнений
- 4.1 Сравнения первой степени
- 4.2 Сравнения второй степени
5 История
6 Ссылки

Определения

Говорят, что два целых числа a и b сравнимы по модулю натурального числа n, если при делении на n они дают одинаковые остатки.

Эквивалентные формулировки: a и b сравнимы по модулю n, если их разность a - b делится на n, или если a может быть представлено в виде a = b + k n, где k — некоторое целое число.

Пример: 32 и −10 сравнимы по модулю 7, так как 32 = 7∙4 + 4, −10 = 7∙(-2) + 4.

Утверждение «a и b сравнимы по модулю _n_» записывается в виде:

$a\equiv b\pmod n.$

Свойства

Отношение сравнения является отношением эквивалентности и обладает многими свойствами обычных равенств. Например, их можно складывать и перемножать: если

$a_1 \equiv b_1 \pmod n; \qquad a_2 \equiv b_2 \pmod n,$

то

$a_1a_2 \equiv b_1b_2 \pmod n; \qquad a_1+a_2 \equiv b_1+b_2 \pmod n.$

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

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

Другие свойства:

Классы вычетов

Множество всех чисел, сравнимых с a по модулю n называется классом вычетов a по модулю n, и обычно обозначается [_a_]n или $\bar a_n$ . Таким образом, сравнение $a\equiv b\pmod n$ равносильно равенству классов вычетов [_a_]n = [_b_]n.

Поскольку сравнение по модулю n является отношением эквивалентности на множестве целых чисел $\mathbb{Z}$ , то классы вычетов по модулю n представляют собой классы эквивалентности; их количество равно n. Множество всех классов вычетов по модулю n обозначается $\mathbb{Z}_n$ или $\mathbb{Z}/n\mathbb{Z}$ .

Операции сложения и умножения на $\mathbb{Z}$ индуцируют соответствующие операции на множестве $\mathbb{Z}_n$ :

[_a_]n + [_b_]n = [a + _b_]n

$[a]_n\cdot [b]_n=[a\cdot b]_n$

Относительно этих операций множество $\mathbb{Z}_n$ является конечным кольцом, а если n простое — конечным полем.

Решение сравнений

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

В теории чисел, криптографии и других областях науки часто возникает задача отыскания решений сравнения первой степени вида:

$ax \equiv b\pmod {m}.$

Решение такого сравнения начинается с вычисления НОД(a, m)=d. При этом возможны 2 случая:

Если b не кратно d, то у сравнения нет решений.
Если b кратно d, то у сравнения существует единственное решение по модулю m / d, или, что то же самое, d решений по модулю m. В этом случае в результате сокращения исходного сравнения на d получается сравнение:

$a_1 x \equiv b_1\pmod {m_1}$

где _a_1 = a / d, _b_1 = b / d и _m_1 = m / d являются целыми числами, причем _a_1 и _m_1 взаимно просты. Поэтому число _a_1 можно обратить по модулю _m_1, то есть найти такое число c, что $c\cdot a_1\equiv 1\pmod{m_1}$ (другими словами, $c \equiv a_1^{-1}\pmod{m_1}$ ). Теперь решение находится умножением полученного сравнения на c:

$x \equiv c a_1 x\equiv c b_1\equiv a_1^{-1} b_1\pmod {m_1}.$

Практическое вычисление значения c можно осуществить разными способами: с помощью теоремы Эйлера, алгоритма Евклида, теории цепных дробей (см. алгоритм) и др. В частности, теорема Эйлера позволяет записать значение c в виде:

$c \equiv a_1^{-1}\equiv a_1^{\varphi(m_1)-1}\pmod {m_1}.$

Пример: решим уравнение $4x\equiv 26\pmod {22}$ . Здесь d = 2, поэтому по модулю 22 сравнение имеет два решения. Заменим 26 на 4, сравнимое с ним по модулю 22, и затем сократим все 3 числа на 2:

$2x \equiv 2\pmod {11}$

Поскольку 2 взаимно просто с модулем 11, можно сократить левую и правую части на 2. В итоге получаем одно решение по модулю 11: $x\equiv 1\pmod {11}$ , эквивалентное двум решениям по модулю 22: $x\equiv 1\pmod {22};\ x\equiv 12\pmod {22}$ .

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

Решение сравнений второй степени сводится к выяснению, является ли данное число квадратичным вычетом (с помощью квадратичного закона взаимности) и последующему вычислению квадратного корня по данному модулю.

История

В значительной степени теория делимости и вычетов была создана Эйлером. Сравнения по модулю впервые использовались Гауссом в его книге «Арифметические исследования», 1801 год. Он же предложил утвердившуюся в математике символику для сравнений.

Ссылки

Вейль А., Основы теории чисел, М.:Мир, 1972.
Виленкин Н. Я., Сравнения и классы вычетов, Квант, № 10, 1978.
Виноградов И. М., Основы теории чисел, М.: ГИТТЛ, 1952.

Wikimedia Foundation.2010.