Modular Multiplicative Inverse


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.