Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
Modular Multiplicative Inverse
def greatest_common_divisor_extended(a, b):
擴展歐幾里得算法 (Extended Euclidean algorithm)
if b == 0:
return a, 1, 0
gcd, y, x = greatest_common_divisor_extended(b, a % b)
return gcd, x, y - (a // b) * x
def inverse_modular(a, b):
Mod 反元素 (Modular Multiplicative Inverse)
gcd, x, y = greatest_common_divisor_extended(a, b)
return x % b
a, b = 43, 26
c = inverse_modular(a, b)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.