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

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

   Сравнение двух целых чисел по модулю натурального числа m — математическая операция, позволяющая ответить на вопрос о том, дают ли два выбранных целых числа при делении на m один и тот же остаток.

    Любое целое число при делении на m дает один из m возможных остатков: число от 0 до m-1; это значит, что все целые числа можно разделить на m групп, каждая из которых отвечает определённому остатку от деления на m.

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

Арифметические операции с остатками чисел по фиксированному модулю образуют модульную арифметику или модулярную арифметику, которая широко применяется в математике, информатике и криптографии.

История

Предпосылкой к созданию теории сравнений стало восстановление сочинений Диофанта, которые были выпущены в подлиннике и с латинским переводом, благодаря Баше де Мезириаку, в 1621 году. Их изучение привело Ферма к открытиям, которые по значению существенно опередили своё время. Например, в письме к Френиклю де Бесси 18 октября 1640 года он сообщил без доказательства теорему, впоследствии получившую название малой теоремы Ферма.                                                                                    В современной формулировке теорема утверждает, что если p - простое число  и a - целое число, не делящееся на p , то   [pic 1]

Первое доказательство этой теоремы принадлежит Лейбницу, причём он открыл указанную теорему независимо от Ферма не позднее 1683 года и сообщил об этом с приведением точного доказательства Бернулли. Кроме этого, Лейбницем был предложен прообраз формулировки теоремы Вильсона.

Позже изучение вопросов, посвященных теории чисел и теории сравнений, было продолжено Эйлером, который ввел квадратичный закон взаимности и обобщил теорему Ферма, установив, что

[pic 2][pic 3]

где ϕ(n) — функция Эйлера.

Понятие и символьное обозначение сравнений было введено Гауссом, как важный инструмент для обоснования его арифметической теории, работа над которой была начата им в 1797 году. В начале этого периода Гауссу ещё не были известны труды его предшественников, поэтому результаты его работы, изложенные в первых трёх главах его книги «Арифметические исследования» (1801 год), были в основном уже известны, однако методы, которые он использовал для доказательств, оказались абсолютно новыми, имеющими высшую важность для развития теории чисел. Используя эти методы Гаусс преобразовал все накопленные до него сведения, связанные с операциями сравнения по модулю, в стройную теорию, которая впервые была изложена в этой же книге. Кроме этого, он исследовал сравнения первой и второй степени, теорию квадратичных вычетов и связанный с ней квадратичный закон взаимности.

Определения

Если два целых числа a и b при делении на m дают одинаковые остатки, то они называются сравнимыми (или равноостаточными) по модулю числа m.

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

[pic 4]

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

Определение сравнимости чисел  a и b  по модулю m равносильно любому из следующих утверждений:

разность чисел a и b делится на  m без остатка;

число a может быть представлено в виде a=b+km, где k — некоторое целое число.

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

Необходимость условий 1 и 2 доказывается следующим образом: