Patrick Michalik

Finding a modular inverse of an integer

A modular multiplicative inverse of an integer aa under modulo mm is an integer bb such that

ab1 (mod m).ab\equiv1\space\left(\textrm{mod}\space m\right).

aa and bb must be coprime, meaning

gcd(a,b)=1.\textrm{gcd}\left(a,b\right)=1.

A common way of finding a modular multiplicative inverse of an integer is to use the extended Euclidean algorithm. To demonstrate this, let’s find a modular multiplicative inverse of 217 under modulo 32.

Pick the larger of the two numbers (217) and, using Euclidean division, divide it by the smaller one (32). Repeat this for the divisor (32) and the remainder obtained (25). Continue until you get a remainder of 1. This gives us

217=326+2532=251+725=73+47=41+34=31+1.\begin{aligned} 217&=32\cdot6+25\newline 32&=25\cdot1+7\newline 25&=7\cdot3+4\newline 7&=4\cdot1+3\newline 4&=3\cdot1+1. \end{aligned}

Next, express each remainder as a difference of the divident and a multiple of the divisor. That is, for each equation, subtract the product of the divisor and the quotient from both sides, and flip the equation:

25=2173267=32254=25733=741=43.\begin{aligned} 25&=217-32\cdot6\newline 7&=32-25\newline 4&=25-7\cdot3\newline 3&=7-4\newline 1&=4-3. \end{aligned}

Work backwards to express 1 as a sum of a multiple of the integer (217) and a multiple of the modulus (32):

1=43=4(74)=47+4=247=2(2573)7=2252737=22577=2257(3225)=225732+725=925732=9(217326)732=92179326732=2179+32(61).\begin{aligned} 1&=4-3\newline &=4-\left(7-4\right)\newline &=4-7+4\newline &=2\cdot4-7\newline &=2\cdot\left(25-7\cdot3\right)-7\newline &=2\cdot25-2\cdot7\cdot3-7\newline &=2\cdot25-7\cdot7\newline &=2\cdot25-7\cdot\left(32-25\right)\newline &=2\cdot25-7\cdot32+7\cdot25\newline &=9\cdot25-7\cdot32\newline &=9\cdot\left(217-32\cdot6\right)-7\cdot32\newline &=9\cdot217-9\cdot32\cdot6-7\cdot32\newline &=217\cdot9+32\cdot\left(-61\right). \end{aligned}

Transform the last equation to have a multiple of the integer (217) on one side, and a sum of 1 and a multiple of the modulus (32) on the other side. The resulting equation is

2179=1+3261,217\cdot9=1+32\cdot61,

which implies

21791 (mod 32).217\cdot9\equiv1\space\left(\textrm{mod}\space32\right).

Thus, a modular multiplicative inverse of 217 under modulo 32 is 9.

Of course, any number of the form 9+32k9+32k (kZk\in\mathbb{Z}) is a modular multiplicative inverse of 217 under modulo 32. Generally, the smallest positive modular multiplicative inverse is used. If your result is negative, add the modulus to it as many times as needed to obtain a positive number. If your result is greater than the modulus, subtract the modulus from it until the result is smaller than the modulus.

© 2018–2024 Patrick Michalik