Уравнение ax≡b по модулю n имеет решение тогда и только тогда, когда d=НОД(a,n) делит b. Если это так, разделите a, b и n на d, чтобы получить уравнение с обратимым коэффициентом. Оно имеет одно решение по модулю n/d и d различных решений по модулю n. Деление коэффициента при сохранении исходного модуля обычно приводит к потере решений. Разложение на простые множители дает еще один инструмент делимости: если n^k должно быть кратно произведению степеней простых p^a, то степень каждого простого в n должна быть не менее ceil(a/k). Эти минимальные показатели независимо порождают наименьшее положительное допустимое n. Для n⁴, кратного 2⁷·3⁵, n должно содержать 2² и 3², поэтому наименьшее значение — 36. Это условие показателей простых, а не сравнение, решаемое через модульное деление.
Расширенный алгоритм Евклида выражает НОД(a,n) как ua+vn. Когда НОД равен 1, u является обратным элементом a по модулю n. Выберите представителя в требуемом диапазоне после приведения. Для 7 и 26, 1=15·7−4·26, поэтому 15 — обратный элемент к 7 по модулю 26; проверьте произведение, чтобы избежать ошибки знака.
Для взаимно простых положительных модулей m,n китайская теорема об остатках дает ровно одно решение по модулю mn для каждой пары условий вычета. Подставьте x=r+mk во второе сравнение и решите относительно k. Если модули не являются взаимно простыми, их значения вычета должны совпадать по модулю НОД(m,n); при согласованности единственность достигается по модулю наименьшего общего кратного, а не произведения.
Тотивент Эйлера phi(n) подсчитывает вычеты, взаимно простые с n. Для различных простых делителей p, phi(n)=n умножить на произведение (1−1/p). Теорема Эйлера дает a^phi(n)≡1 только тогда, когда gcd(a,n)=1. Частный случай — малая теорема Ферма. Уменьшайте показатели степеней только после проверки этого условия; необратимый элемент может стать нулем при повторном возведении в степень.
