Сравнение по модулю
Сравне́ние двух целых чисел по мо́дулю натурального числа — математическая операция, позволяющая ответить на вопрос о том, дают ли два выбранных целых числа при делении на один и тот же остаток. Любое целое число при делении на даёт один из возможных остатков: число от 0 до ; это значит, что все целые числа можно разделить на групп, каждая из которых отвечает определённому остатку от деления на . Эти группы называются классами вычетов по модулю , а содержащиеся в них целые числа — вычетами по модулю .
Арифметические операции с остатками чисел по фиксированному модулю образуют мо́дульную арифме́тику или модуля́рную арифметику[1][2], которая широко применяется в математике, информатике и криптографии[3].
Предпосылкой к созданию теории сравнений стало восстановление сочинений Диофанта, которые были выпущены в подлиннике и с латинским переводом, благодаря Баше де Мезириаку, в 1621 году. Их изучение привело Ферма́ к открытиям, которые по значению существенно опередили своё время. Например, в письме к Френиклю де Бесси[4] 18 октября 1640 года он сообщил без доказательства теорему, впоследствии получившую название малой теоремы Ферма. В современной формулировке теорема утверждает, что если — простое число и — целое число, не делящееся на , то
Первое доказательство этой теоремы принадлежит Лейбницу, причём он открыл указанную теорему независимо от Ферма́ не позднее 1683 года и сообщил об этом с приведением точного доказательства Бернулли. Кроме этого, Лейбницем был предложен прообраз формулировки теоремы Вильсона.
Позже изучение вопросов, посвященных теории чисел и теории сравнений, было продолжено Эйлером, который ввел квадратичный закон взаимности и обобщил теорему Ферма, установив, что
где — функция Эйлера.
