решал задачки и столкнулся с проблемой,
Найдите 4 в −1 степени(mod11)
Впринципе на простых числах я понял
2^(−1)≡3(mod5)
А тут застрял думаю что получится 44
Вычисление обратного элемента в кольце по модулю с использованием расширенного алгоритма Евклида (max_algo)
def gcdex(a, b):
if a == 0 :
return b,0,1
gcd,x,y = gcdex(b%a, a)
return gcd, y - (b//a) * x, x
def invmod(a, m):
g, x, y = gcdex (a, m)
return None if g > 1 else (x % m + m) % m
print(invmod(4,11)) # result 3 (4 * 3) % 11 = 1
В общем случае ответ @MBo про расширенный алгоритм Евклида работает в большом классе колец, так называемых Евклидовых кольцах. Например, в кольцах многочленов над полями.
Но в частном случае циклических групп, когда известно разложение порядка группы на множители, можно пользоваться теоремой Эйлера. В вашем случае 4^10 == 1 (mod 11)
, следовательно 4^(-1) == 4^9 (mod 11) == 3 (mod 11)
.
Чуть более обще. Пусть n
- модуль, phi(n)
- функция Эйлера для n
, тогда a^(-1) == a^(phi(n)-1) (mod n)
.
Например, 4^(-1) (mod 21) == 4^11 (mod 21) == 16 (mod 21)
обратный элемент (в кольце) по модулю
?