How to find the inverse modulo mm?

For example:
7x \equiv 1 \pmod{31}
In this example, the modular inverse of 7 with respect to 31 is 9. How can we find out that 9? What are the steps that I need to do?

Update
If I have a general modulo equation:
5x + 1 \equiv 2 \pmod{6}

What is the fastest way to solve it? My initial thought was:
5x + 1 \equiv 2 \pmod{6}
\Leftrightarrow 5x + 1 – 1\equiv 2 – 1 \pmod{6}
\Leftrightarrow 5x \equiv 1 \pmod{6}

Then solve for the inverse of 5 modulo 6. Is it a right approach?

Thanks.

Answer

  1. One method is simply the Euclidean algorithm:
    \begin{align*}
    31 &= 4(7) + 3\\\
    7 &= 2(3) + 1.
    \end{align*}

    So 1 = 7 – 2(3) = 7 – 2(31 – 4(7)) = 9(7) – 2(31). Viewing the equation 1 = 9(7) -2(31) modulo 31 gives 1 \equiv 9(7)\pmod{31}, so the multiplicative inverse of 7 modulo 31 is 9. This works in any situation where you want to find the multiplicative inverse of a modulo m, provided of course that such a thing exists (i.e., \gcd(a,m) = 1). The Euclidean Algorithm gives you a constructive way of finding r and s such that ar+ms = \gcd(a,m), but if you manage to find r and s some other way, that will do it too. As soon as you have ar+ms=1, that means that r is the modular inverse of a modulo m, since the equation immediately yields ar\equiv 1 \pmod{m}.

  2. Another method is to play with fractions Gauss’s method:
    \frac{1}{7} = \frac{1\times 5}{7\times 5} = \frac{5}{35} = \frac{5}{4} = \frac{5\times 8}{4\times 8} = \frac{40}{32} = \frac{9}{1}.
    Here, you reduce modulo 31 where appropriate, and the only thing to be careful of is that you should only multiply and divide by things relatively prime to the modulus. Here, since 31 is prime, this is easy. At each step, I just multiplied by the smallest number that would yield a reduction; so first I multiplied by 5 because that’s the smallest multiple of 7 that is larger than 32, and later I multiplied by 8 because it was the smallest multiple of 4 that is larger than 32. Added: As Bill notes, the method may fail for composite moduli.

Both of the above methods work for general modulus, not just for a prime modulus (though Method 2 may fail in that situation); of course, you can only find multiplicative inverses if the number is relatively prime to the modulus.

Update. Yes, your method for general linear congruences is the standard one. We have a very straightforward method for solving congruences of the form ax \equiv b\pmod{m},
namely, it has solutions if and only if \gcd(a,m)|b, in which case it has exactly \gcd(a,m) solutions modulo m.

To solve such equations, you first consider the case with \gcd(a,m)=1, in which case ax\equiv b\pmod{m} is solved either by finding the multiplicative inverse of a modulo m, or as I did in method 2 above looking at \frac{b}{a}.

Once you know how to solve them in the case where \gcd(a,m)=1, you can take the general case of \gcd(a,m) = d, and from
ax\equiv b\pmod{m}
go to
\frac{a}{d}x \equiv \frac{b}{d}\pmod{\frac{m}{d}},
to get the unique solution \mathbf{x}_0. Once you have that unique solution, you get all solutions to the original congruence by considering
\mathbf{x}_0,\quad \mathbf{x}_0 + \frac{m}{d},\quad \mathbf{x}_0 + \frac{2m}{d},\quad\ldots, \mathbf{x}_0 + \frac{(d-1)m}{d}.

Attribution
Source : Link , Question Author : Chan , Answer Author : Bill Dubuque

Leave a Comment