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.