Just like a regular multiplicative inverse, where b is the inverse of a if 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 a and c is 1.
Then, on the right with calculations reading from bottom to top, linear combinations are done to get the equation 1 = a • b + c • k
where b is the modular multiplicative inverse of a, and k is a constant.
Please enter two positive integers c and 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.