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

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

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

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

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

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

Пример

Для сравнения имеем , поэтому по модулю 22 сравнение имеет два решения. Заменим 26 на 4, сравнимое с ним по модулю 22, и затем сократим все 3 числа на 2:

Поскольку 2 взаимно просто с модулем 11, то его можно обратить по модулю 11 и найти . Умножая сравнение на 6, получаем решение по модулю 11: , эквивалентное совокупности двух решений по модулю 22: и .

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

Пример

Решить сравнение . Тогда . Подставляя эти значения в формулу , получим два целочисленных решения: и . Окончательно принимаем положительное значение .