Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For example: $$7x \equiv 1 \pmod{31} $$ In this example, the inverse of $7$ 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,

share|improve this question

5 Answers 5

up vote 22 down vote accepted
  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}.$$

share|improve this answer
    
@Arturo Magidin: Thanks, it's a lot of work :(. I thought it's just a simple calculation. –  Chan Mar 6 '11 at 23:38
    
@Chan: Your definition of "a lot of work" needs revising, if you plan on studying more number theory and maths. The above is surprising little work, in my estimation... –  Arturo Magidin Mar 6 '11 at 23:40
    
@Arturo Magidin: Thanks for the advice. However, I have many other things that I want to study. I like Number Theory, but also Geometry, Computer Graphics, Algorithm, C++, Ruby, Compiler, AI..., plus my school classes. I wish a day could have 48 hours. –  Chan Mar 6 '11 at 23:43
    
@Chan: Trust me, you aren't the only one making that wish. But I really don't know what it is you think that the above methods are "a lot of work". Even the Euclidean algorithm method works, in this case, in two simple steps. Did you hope that just a sum and a product would do it every time? –  Arturo Magidin Mar 6 '11 at 23:45
1  
the euclidean algorithm is simple and easily programed... –  yoyo Mar 6 '11 at 23:48

We know that $(7,31) = 1$. So you can use the extended Euclidean algorithm. In particular, you can find two integers $s,t$ such that $7s+31t = 1$. So $7s \equiv 1 \pmod {31}$.

share|improve this answer
    
Thanks for the idea. –  Chan Mar 6 '11 at 23:39

A hint: Try to use Fermats Little theorem:

$a^{p-1}=1 \mod p$ for $p$ prime, and all $a\in \mathbb{Z}$.

share|improve this answer
1  
7^29 mod 31 certainly works in this case, but for larger numbers it might be a bit of an effort compared with the Euclidean algorithm, and it would get more complicated by involving Euler's totient function for a non-prime modulus. –  Henry Mar 6 '11 at 23:57

We can visualize the solution to $7x \equiv 1 \pmod{31}$ as the intersection of the two "lines"

$\ \ \ \ \ y \equiv 7x \pmod{31}$ and $y \equiv 1 \pmod{31}$.

The first line is closed under addition and subtraction, since it passes through the origin. If $(x_1, y_1)$ and $(x_2, y_2)$ are points on the line $y \equiv 7x \pmod{31}$, then so are $(x_1+x_2, y_1+y_2)$ and $(x_1-x_2, y_1-y_2)$.

To find a point where the lines intersect, we start with the two points $(1, 7)$ and $(0,31)$ on the first line, and repeatedly subtract one point from another until the $y$-coordinate is 1.

$\ \ \ \ \ (0,31) - (1,7) = (-1, 24)$

$\ \ \ \ \ (-1, 24) - (1,7) = (-2, 17)$

$\ \ \ \ \ (-2, 17) - (1, 7) = (-3, 10)$

$\ \ \ \ \ (-3, 10) - (1, 7) = (-4, 3)$

$\ \ \ \ \ (1,7) - (-4, 3) = (5, 4)$

$\ \ \ \ \ (5,4) - (-4, 3) = (9,1)$

Therefore, $x \equiv 9 \pmod{31}$.

You can speed up this procedure by subtracting a multiple of one point from another point instead. This leads to the Euclidean algorithm.

share|improve this answer

There are many methods, e.g. the extended Euclidean algorithm, or Gauss's special case for computing inverses mod primes, or, by Euler-Fermat $\rm\ (a,m)=1 \Rightarrow\ a^{-1} \equiv a^{\phi(m)-1}\ \ (mod\ m)\:.$ The latter yields a simple closed form for CRT (Chinese Remainder Theorem)

$\quad$ If $\rm\,\ (m,n)=1\,\ $ then $\rm\quad \begin{eqnarray}\rm x\!&\equiv&\rm a\ \ (mod\ m)\\ \rm x\!&\equiv&\rm b\ \ (mod\ n)\end{eqnarray} \iff\ x\equiv a\,n^{\phi(m)}\!+b\,m^{\phi(n)}\ \ (mod\ mn)$

More generally see the Peirce decomposition.

share|improve this answer
    
Many thanks! –  Chan Mar 6 '11 at 23:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.