Just like a regular multiplicative inverse, where
b is the inverse of
a • b = 1,
b is a modular multiplicative inverse of
a mod c if
a • b = 1 mod c. Below, on the left with calculations reading from top to bottom,
the Extended Euclidean Algorithm is used to confirm that the greatest common divisor of
Then, on the right with calculations reading from bottom to top, linear combinations are done to get the equation
1 = a • b + c • k
b is the modular multiplicative inverse of
k is a constant.
Please enter two positive integers
a less than 50,000,000 and without commas into the two respective boxes below.
Note: This algorithm works particularly well with prime
c values, because every number between 1 and
c will have a multiplicative inverse. Some large prime values within range are: 49999759, 49999883 and 49999991.