56
$\begingroup$

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,

7 Answers 7

55
  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}.$$

  • 1
    @Arturo Magidin: Thanks, it's a lot of work :(. I thought it's just a simple calculation.2011-03-06
  • 4
    @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...2011-03-06
  • 2
    @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.2011-03-06
  • 1
    @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?2011-03-06
  • 0
    @Arturo Magidin: Yes, I thought exactly like you said, because in the book that I read, it does not show step by step. It just jumps right to the answer.2011-03-06
  • 2
    the euclidean algorithm is simple and easily programed...2011-03-06
  • 1
    @Chan: Just for your information: the Euclidean Algorithm is considered a *very fast* algorithm; certainly faster than factoring and many other calculations that one often needs to do. In fact, many factoring algorithms work by making educated guesses and then computing gcds by using the Euclidean Algorithm in the hope of getting a nontrivial factor that way, precisely because the Euclidean Algorithm is so efficient.2011-03-06
  • 0
    @Arturo Magidin: Thanks, I really didn't know the the Euclidean Algorithm was that fast. I will practice it more. By the way, could you take a look at my update?2011-03-06
  • 0
    @Arturo: It should be emphasized that the "play with fractions" method may fail for composite moduli. See the link to "Gauss's method" in my answer.2011-03-06
  • 0
    @Arturo Magidin: Thank you very much for your update answer. I really appreciate it.2011-03-07
  • 0
    @Bill: Thanks for the heads-up.2011-03-07
  • 0
    @BillDubuque You said the method "may fail with composite moduli", but OP explicitly said that "the only thing to be _careful_ of is that you should only multiply and divide by things _relatively prime to the modulus_". It was clearly emphasized. If you follow what he said, you'll never have any problems with composite moduli.2015-01-28
  • 0
    @user314 The point is that if you apply what I call [Gauss's algorithm](http://math.stackexchange.com/a/174687/242) for non-prime moduli then it may fail due to occurrence of non-invertible denominators, and there may be no way to workaround that. You can find many worked examples in [my posts.](http://www.google.com/search?q=site:math.stackexchange.com+dubuque+%22gauss%27s+algorithm%22) Note: the name "Gauss's algorithm", and its *fractional* interpretation are due to me.2015-01-28
  • 0
    @BillDubuque I'm repeating: he clearly emphasized that "_you should only multiply and divide by things relatively prime to the modulus_". If you do that, the method will never fail for composite moduli. You were wrong in saying that the exact method described by Arturo (method 2.) may fail.2015-01-28
  • 0
    @user314 Arturo and I refer to a *specific algorithm* that I extracted out of a proof *Disq. Arith*. We are not referring to *arbitrary* modular manipulation of fractions. Said algorithm may or may not succeed in computing inverses wrt composite moduli. Follow the links to learn more.2015-01-28
  • 0
    @BillDubuque All we need (to use the method) is two facts: 1) $\frac{1}{b}\equiv \frac{c}{bc}\pmod m$ whenever $(b,m)=1, (c,m)=1$; 2) $b\equiv d\pmod m\implies \frac{1}{b}\equiv\frac{1}{d}\pmod m$ whenever $(b,m)=1$. I can prove them if you wish. None of them require $m$ being composite and they are the only ones used in the method.2015-01-28
  • 0
    @BillDubuque And I can also prove that the method can always produce the actual inverse: $b^{-1}\mod m$ is defined (where $(b,m)=1$), and so I can always find a number $a=b^{-1}\mod m$ such that $\frac{1}{b}\equiv\frac{a}{ba}\equiv a\pmod m$ (we know that $(a,m)=1$).2015-01-28
  • 0
    @user314 Please tell how your algorithm computes $\,1/7\pmod{30}\ \ $2015-01-28
  • 0
    @BillDubuque $\frac{1}{7}\equiv\frac{1\cdot 13}{7\cdot 13}\equiv \frac{13}{91}\equiv \frac{13}{1}\equiv 13\pmod {30}$.2015-01-28
  • 0
    @user314 And what *algorithm* did you use? Where did $13$ come from? You simply pulled the inverse out of a hat, like magic!2015-01-28
  • 0
    @BillDubuque I didn't read that the method requires you to multiply by a number that makes the reduction as minimal as possible. Though you can still do this using the actual method: $\frac{1}{7}\equiv\frac{7}{49}\equiv\frac{7}{19}\equiv\frac{49}{133}\equiv\frac{19}{13}\equiv\frac{133}{91}\equiv\frac{13}{1}\equiv 13\pmod{30}$.2015-01-28
  • 0
    @user314 The method I attribute to Gauss is a (deterministic) *algorithm*. There are indeed plenty of (non-algorithmic) ways to "fiddle" with fractions to compute inverses etc (see my posts for many examples). But these are not *algorithms*. My comment to Arturo refers to the specific *algorithm* that I named after Gauss (which Arturo learned from me here or on sci.math).2015-01-28
  • 0
    @ArturoMagidin Good exposition. Maybe you could complete your part one mentioning, for the OP, the Extended Euclidean Algorithm which provides a brainless (and deterministic) process to get the coefficients of a Bezout relation.2016-10-10
  • 0
    This might be outdated, but thanks for this amazing comment. This method will save me a lot of time when finding multiplicative inverses. +12016-12-12
11

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}$.

10

A hint: Try to use Fermats Little theorem:

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

  • 3
    [7^29 mod 31](http://www.wolframalpha.com/input/?i=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.2011-03-06
6

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.

1

There are many methods available, e.g. the extended Euclidean algorithm, $ $ or a special case of Euclid's algorithm that computes inverses modulo primes that I call Gauss's algorithm; $ $ or, $ $ by Euler-Fermat $\rm\,\ (a,m)=1 \Rightarrow\ a^{-1} \equiv a^{\phi(m)-1}\pmod 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\ m\,n)$

More generally see the Peirce decomposition.

  • 0
    @BillDubuque can we invert if totient is unknown?2017-09-01
  • 0
    @777 Yes, see the other two methods I mentioned above.2017-09-01
  • 0
    @BillDubuque which ones? all seems to use factorization of $m$ or $\phi(m)$ and nothing avoids these.2017-09-01
  • 0
    @777 The extended Euclidean algorithm and Gauss's algorithm do not use factorization. Follow the links to learn these methods.2017-09-01
  • 0
    @BillDubuque so both these methods do not need factorization of $m$ or knowledge of $\phi(m)$. Then doesn't that help to get decryption key $d$ in RSA from encryption key $e$?2017-09-01
  • 0
    @777 If we know $\,\phi(n)\,$ (or a multiple) then it is fast. But no fast was of computing $\phi(n)\,$ is known.2017-09-02
  • 0
    @BillDubuque then what about 'can we invert if totient is unknown or factorization is unknown?'?2017-09-02
  • 0
    @777 The inverse depends on the modulus, e.g. $\!\bmod{\,2n\!-\!1}\!:\,\ 2^{-1}\equiv n\,$ by $\,2n\equiv 1\ \ $2017-09-02
1

An alternative way to solve would be to use the fast powering algorithm.

$a^{-1}≡a^{p-2} \mod p$ for $p$, $a\in \mathbb{Z}$.

$7^{-1} \mod 31 = 7^{29} \mod 31 ≡ 9 \mod 31$

According to An Introduction to Mathematical Cryptography by Hoffstein et al, in practice this is about the same time complexity as the extended Euclidean algorithm given in other answers.

Before using the fast powering algorithm I would first check to see if a and p are relatively prime, so that you know an inverse exists before performing the calculation.

0

The Arithmetical Progression f(n) = a + (n-1)d has only a finite number of terms for any modulus d and where a is the "initial" value, f(1), even when n is allowed to range over ℤ, so no holds barred trying negative values to quickly reach a coefficient of 1 or a -1.

In this example all moduli are to 31, starting from coefficient 7 one possibility is:

7x ≡ 1

⇒ -24x ≡ 32 (subtracting the modulus on the left and adding the modulus to the right)
⇒  -3x ≡ 4 (∵ gcd (12, 31) = 1)
⇒ -30x ≡ 40
⇒   1x ≡ 9

The above is an application of congruence article in the chapter on theory of numbers in Higher Algebra By H.S. Hall and S.R. Knight May 1887 (pdf probably available online).