4

решал задачки и столкнулся с проблемой,

Найдите 4 в −1 степени(mod11)

Впринципе на простых числах я понял

2^(−1)≡3(mod5)

А тут застрял думаю что получится 44

6
  • 2^(-1) == 3 % 5; 0.5 == 3; false Commented 22 июн. 2021 в 23:31
  • Неясно, что вам требуется. Может быть, обратный элемент (в кольце) по модулю?
    – MBo
    Commented 23 июн. 2021 в 2:18
  • Найти 4^(-1) mod(11) Commented 23 июн. 2021 в 3:57
  • Именно так, обратный элемент в кольце по модулю Commented 23 июн. 2021 в 3:58
  • Для таких маленьких значений - хоть перебором :)
    – Harry
    Commented 23 июн. 2021 в 15:05

2 ответа 2

6

Вычисление обратного элемента в кольце по модулю с использованием расширенного алгоритма Евклида (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
5

В общем случае ответ @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)

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.