Обратный элемент в кольце по модулю
В модулярной арифметике, нельзя так просто взять и поделить одно число, на другое. Но мы знаем, что деление эквивалентно умножению на обратное число, поэтому необходимо научиться находить обратное число по модулю. Напомню:
a * a^(-1) = 1 mod m
Понятно, что для нуля обратного элемента не существует никогда; для остальных же элементов обратный может как существовать, так и нет. Утверждается, что обратный существует только для тех элементов a, которые взаимно просты с модулем m.
Теорема Эйлера
Если a и m взаимно просты, то a^(phi(m)) = 1 mod m
Малая теорема Ферма
Если m — простое число и a — целое число, не делящееся на m, то a^(m − 1) − 1 делится на m.
Это можно переформулировать для вычисления обратных чисел, для простого m справедливо: a^(m - 1) = 1 mod m, следовательно a^(-1) mod m = a^(m - 2) mod m
Соответственно можно найти обратный элемент с помощью быстрого возведения в степень.
// обратный элемент в кольце по модулю int reverseElement(int x, int mod) { int f = getEuler(mod); return binpowmod(x, f - 1, mod); } // проверка существования обратного элемента bool isReverseElement(int x, int mod) { return gcd(x, mod) == 1; } // обратный элемент в кольце по простому модулю int reverseElement(int x, int mod) { return binpowmod(x, mod - 2, mod); } |
|
|
Задача
Решим простую задачу на понимание. Необходимо вычислить следующее выражение A**B**C % M; A, B, C <= 10**12; GCD(A, M) == 1
Легко видеть, что степень числа A необходимо подсчитать по модулю phi(M). Возводим B в степень C по модулю phi(M), потом возводим в эту степень A по модулю M.
10. Расширенный алгоритм Евклида. Диофантовы уравнения
Факт. если gcd(a, b) == g, то найдутся x и y, такие что a * x + b * y == g
Заметим также, что решений бесконечно много: можно x увеличить на b*y, а y уменьшить на a*x, и равенство при этом не изменится.
Сначала напишем код - потом докажем его корректность, и этим сразу докажем, что решение всегда есть.
int gcdex(int a, int b, int & x, int & y) { if (b == 0) { x = 1; y = 0; return a; } int x1, y1; int g = gcd(b, a % b, x1, y1); x = y1; y = x1 - (a / b) * y1; return g; } |
Рассмотрим базовый случай, b == 0, тогда значение НОДа и решение уравнения является тривиальным. Пусть у нас есть решение
x1, y1 для пары b * x1 + a % b * y1 = g
нужно найти a * x + b * y = g
распишем взятие остатка в виде формулы a % b = a - a // b * b, где за два слеша обозначено целочисленное деление (с округлением вниз) скобки. Подставим в формулу:
b * x1 + (a - a // b * b) * y1 = g -> b * x1 + a * y1 - a // b * b * y1 = g ->
a * y1 + b * (x1 - a // b * y1) = g, что и требовалось доказать.