Поиск обратного элемента в кольце по модулю

Поиск обратного элемента в кольце по модулю

       Рассмотрим уравнение a * x + m * y = 1, где m модуль, a - некоторое взаимно простое с m число. Это линейное диофантово уравнение второго порядка. Как показано в ранее, из условия gcd(a,m) = 1 следует, что это уравнение имеет решение, которое можно найти с помощью Расширенного алгоритма Евклида (отсюда же, кстати говоря, следует, что когда gcd(a,m)!= 1, решения, а потому и обратного элемента, не существует).

       С другой стороны, если мы возьмём от обеих частей уравнения остаток по модулю m, то получим a * x = 1 mod m, а значит переменная x будет содержать в себе число обратное a.

       Поэтому код для решения будет такой (учтём, что нам будет найдено какое-то решение уравнение, x не обязательно в диапазоне от 0 до m).

Диофантово уравнение I порядка

Пусть необходимо решить уравнение:

a * x = b mod m; a, b, m - известные, x - неизвестное

Если gcd(a, m) = 1, то решением будет x = a^(-1) * b, причём оно единственное.

Если a и m не взаимно просты, то решение будет существовать не всегда (например 2 * x = 1 mod 4).

       Пусть g = gcd(a, m), тогда, если b не делится на g, то решения не существует. В самом деле, при любом x левая часть уравнения, т. е. (a * x) % m, всегда делится на g, в то время как правая часть на него не делится, откуда и следует, что решений нет.

Если же b делится на g, то, разделив обе части уравнения на это g (т. е. разделив a, b и m на g), мы придём к новому уравнению:

a' * x = b' mod m', в котором a' и m' уже будут взаимно просты, а такое уравнение мы уже научились решать. Обозначим его решение через x'.

Понятно, что это x' будет также являться и решением исходного уравнения. Однако если g > 1, то оно будет не единственным решением. Можно показать, что исходное уравнение будет иметь ровно g решений, и они будут иметь вид:

x_i = (x' + i * m') mod m, i = 0... (g-1)

Подводя итог, можно сказать, что количество решений линейного модульного уравнения равно либо g, либо нулю.