Обратный элемент в кольце по модулю

Обратный элемент в кольце по модулю

       В модулярной арифметике, нельзя так просто взять и поделить одно число, на другое. Но мы знаем, что деление эквивалентно умножению на обратное число, поэтому необходимо научиться находить обратное число по модулю. Напомню:

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, что и требовалось доказать.