Skip to main content
Logo image

Discrete Math for Shockers

John Hammond

Section 3.4 Multiplicative Inverses

Subsection

In our algebra and calculus classes, where we worked in \(\Q\) and \(\R\text{,}\) all non-zero numbers had multiplicative inverses. For example, \(5^{-1} = \frac15\) since \(5^{-1}\cdot 5 = 1\text{.}\) But \(\frac15 \not \in \Z\text{,}\) so it’s not an object that we can use in modular arithmetic.
When we’re working with only integers, in particular in congruence classes modulo an integer \(m\text{,}\) fractions aren’t a thing. Some numbers, though, do have multiplicative inverses. They’re special, and we explore them in this section.
Why do we care? At this point, the only algebraic equations we can solve are of the form \(x + b \equiv c\pmod{m}\text{.}\) The multiplicative inverses help us solve the algebraic, affine equations, \(ax + b \equiv c\pmod{m}\text{.}\)

Definition 3.4.1.

Let \(a\) be an integer and \(m\) a positive integer. We define a multiplicative inverse of \(a\) modulo \(m\) to be an integer \(b\) such that \(ab \equiv 1 \pmod{m}\text{.}\)

Example 3.4.2.

Since \(3 \cdot 5\equiv 1 \pmod{7}\text{,}\) we say that \(3\) is a multiplicative inverse of 5 modulo 7. Similarly, 5 is a multiplicative inverse of 3 modulo 7.
We say that \(3\) is a multiplicative inverse, rather than the multiplicative inverse, because every number in the congruence class \([3]_7\) is also an inverse! Observing that \(-4 \in [3]_7\text{,}\) and \(10\in [3]_7\text{,}\) we can check that:
  • \(\displaystyle 10 \cdot 5\equiv 1 \pmod{7}\)
  • \(\displaystyle (-4) \cdot 5 \equiv 1 \pmod{7} \)
  • etc

Example 3.4.3.

  1. Find every multiple of 4 modulo 9.
  2. Find the inverse of 4 modulo 9.
Video / Answer.
Solution.
Here’s the multiplication table. Remember to reduce modulo 9.
Table 3.4.4. Multiplication table of 4 modulo 9
* 1 2 3 4 5 6 7 8 9
4 4 8 3 7 2 6 1 5 0
The inverse of 4 modulo 9 is 7. Why? Because \(4\cdot 7 = 1 \pmod 9\text{.}\)

Example 3.4.5.

Solve the congruence \(4x \equiv 5 \pmod 9 \text{.}\)
Video / Answer.
Solution.
Given that above we found that the multiplicative inverse of 4 modulo 9 is 7, we need to multiply both sides by 7:
\begin{align*} 4x \amp \equiv 5 \pmod 9\\ 4^{-1}4x \amp \equiv 4^{-1} 5 \pmod 9\\ 1x \amp \equiv 7 \cdot 5 \pmod 9 \\ x \amp \equiv 35 \pmod 9 \\ x \amp \equiv 8 \pmod 9 \end{align*}

Example 3.4.6.

Let’s create a multiplication table modulo 9. The following Sage code does it for us. You can change the variable n to other numbers to quickly generate other multiplication tables.
The output is a table/matrix whose \(i, j\)th entry is \(i \cdot j \pmod{n}\text{.}\)
  1. What is the inverse of 7 modulo 9?
  2. Does 6 have an inverse modulo 9? Why or why not?
  3. What numbers are invertible modulo 9? What numbers are not?
Video / Answer.
Solution.
  1. The inverse of 7 modulo 9 is 4. Notice that in the 7 column, 4th row, we see an entry of 1; that tells us \(7\cdot 4 = 1\) and so they are inverses.
  2. 6 does not have an inverse modulo 9. See in the 6th column (or equivalently, 6th row), that there is never a value 1; no number multiplied by 6 gives 1.
  3. Any number that has a 1 in its row/column has an inverse. These are 1, 2, 4, 5, 7, 8. The other numbers: 3, 6 (and 0) do not have multiplicative inverses.
Computing a multiplication table is tedious if we just want to find a multiplicative inverse to solve a linear congruence. Similarly, guess-and-check is generally inefficient. Now we turn to a powerful fact that gives rise to an algorithm to find inverses.

Note 3.4.8.

  1. The inverse of \(a \text{ modulo } m\) is its Bézout coefficient in the equality
    \begin{equation*} {\gcd(a,m) = as + mt} \end{equation*}
  2. The inverse is also unique (up to congruence), but we won’t prove that here.

Example 3.4.10.

Solve the linear congruences, if possible. Explain if there are no solutions, one solution, or infinitely many solutions.
  1. \(\displaystyle 11x \equiv 15 \pmod{20} \)
  2. \(\displaystyle 6x\equiv 4 \pmod{10}\)
  3. \(\displaystyle 8x\equiv 4 \pmod{28}\)
  4. \(\displaystyle 5x\equiv 4 \pmod{25}\)
Solution.
  1. First, since \(\gcd(11,20)=1\text{,}\) there is a unique solution to this recurrence. Using either the Euclidean Algorithm or guessing-and-checking, notice that \(11\cdot11=121\equiv 1\pmod{20}\text{,}\) so \(11^{-1} \equiv 11\pmod{20}\text{.}\) So we have:
    \begin{align*} 11x &\equiv 15\pmod{20} \\ 11\cdot11x &\equiv 11\cdot 15\pmod{20} \\ 1x &\equiv 165 \pmod{20} \\ x &\equiv 5 \pmod{20} \end{align*}
  2. Since \(\gcd(6,10) =2 \ne 1\text{,}\) there isn’t a unique solution! We can’t use the Euclidean Algorithm to find our inverse and instead have to rely on trial and error.
    Since \(6\cdot 4 = 24 \equiv 4 \pmod{10}\text{,}\) we have that 4 is one solution. Similarly, you can check that \(9\) is also a solution.
    This congruence has two solutions modulo 10, \(x=4\) and \(x=9\text{.}\)
  3. As above, since \(\gcd(8,28) = 4 \ne 1\text{,}\) so there isn’t a unique solution. Let’s see what happens when we do the multiplication:
    Table 3.4.11. Multiplication table of 8 modulo 28
    * 1 2 3 4 5 6 7 8
    8 8 16 24 4 12 20 0 8
    ... we could keep going... notice that as soon as we get back to \(8\text{,}\) we have gone in a loop! The values will repeat.
    Our first solution is \(x=4\text{,}\) then \(x=11\text{,}\) then \(x=18\text{,}\) and finally \(x=25\)
  4. Here, since \(\gcd(5, 25) = 5 \ne 1\text{,}\) again, no unique solution. Take a few moments to multiply values of 5 and notice it will never reach 4.
    There is no solution to this congruence!

Note 3.4.12. Solving systems with gcd other than 1.

As we hinted in the previous example, we have three possibilities for the congruence \(ax = b\pmod{m}\text{:}\)
  1. A unique solution if \(\gcd(a, m) = 1\)
  2. If \(\gcd(a, m) = d\text{,}\) the congruence will have \(d\) solutions if \(d \divides b\)
  3. And the system will have no solution if \(\gcd(a, m) = d\) and \(d \nmid b\)
If the congruence has a solution, the complete set of solutions reduced modulo \(m\) is given by:
\begin{gather*} x = x_0 + \dfrac{mt}{d} \end{gather*}
where \(\gcd(a,m) = d\text{,}\) \(x_0\) is an initial solution, and \(t\) runs through \(\Z_d\text{,}\) the set of remainders modulo d.
Take a moment to revisit the examples in Example 3.4.10 using this formula.

Example 3.4.13.

Give a complete list of the solutions to the following congruences:
  1. \(\displaystyle 8x = 20 \pmod{28} \)
  2. \(\displaystyle 21x = 14 \pmod{49}\)
Solution.
  1. We begin first by finding \(\gcd(8,28)=4\text{,}\) so there will not be a unique solution, but instead zero or four. Because \(4 \divides 20\text{,}\) there will be four solutions reduced modulo 28.
    Applying the method of solving congruences with multiple solutions, we need to find the first solution. Running through possible values of \(x = 0, 1, 2, 3\dots\text{,}\) we note that \(8\cdot 6 = 48 \equiv 20 \pmod{28}\) so that \(x_0=6\) is the first solution. Then all solutions will be of the form:
    \begin{gather*} x = 6 + \frac{28t}{4} \text{ for } t \in \Z_4 \end{gather*}
    Plug in the values \(t=0, 1, 2, 3\) to find the complete solution set of \(x=6, 13, 20, 27\)
  2. As above, first find \(\gcd(21, 49) = 7\text{.}\) Since \(7\divides 14\text{,}\) we have seven total solutions reduced modulo 49.
    To find the initial solution, test values of \(x=0, 1, 2, \dots\) to find the first solution is \(x_0 = 3\) Applying the formula we find all solutions to be:
    \begin{gather*} x = 3 + \dfrac{49t}{7} \text{ for } t \in \Z_7 \end{gather*}
    Plug in the values \(t=0, 1, 2, 3, 4, 5, 6\) to find the complete solution set of \(x=3, 10, 17, 24, 31, 38, 45\)

Exercises Exercises

1.

Solve the congruence:
  1. \(\displaystyle 3x + 4 \equiv 7 \pmod 8 \)
  2. \(\displaystyle 9x \equiv 4 \pmod{22}\)
  3. \(\displaystyle 5x + 14 \equiv 0 \pmod{26}\)
Solution.
  1. \(\displaystyle x \equiv 1 \pmod 8\)
  2. \(\displaystyle x \equiv 20 \pmod{22}\)
  3. \(\displaystyle x \equiv 18 \pmod{26}\)

2.

Find all solutions to the congruence (there could be more than one):
  1. \(\displaystyle 3x \equiv6 \pmod 9 \)
  2. \(\displaystyle 4x \equiv 3 \pmod 8 \)
Solution.
Here, since the coefficient of \(x\) isn’t relatively prime to the modulus there are either multiple answers per modulus or no solution.
  1. Each of \(x \equiv 2 \pmod{9}\text{,}\) \(x\equiv 5 \pmod{9}\text{,}\) and \(x \equiv 8 \pmod{9}\) satisfy the given equation. We can summarize this as \(x \equiv 2 \pmod{3}\)
  2. There is no solution to this equality. No multiple of 4 will ever have a remainder of 3 modulo 8.

3.

Solve the following congruences. If none exists, explain why. If there are one or more solutions, give a complete list of solution(s).
  1. \(\displaystyle 3x - 4 = 15 \pmod{26}\)
  2. \(\displaystyle 13 x - 3 = 4 \pmod{26}\)
  3. \(\displaystyle 8x=16\pmod{426}\)
  4. \(\displaystyle 8x=16\pmod{425}\)
  5. \(\displaystyle 8x=21\pmod{426}\)
Solution.
  1. Since \(\gcd(3,26) = 1\text{,}\) there is a unique inverse. Using the Euclidean Algorithm we find that \(3^{-1} \equiv 9 \pmod{26}\text{.}\) Doing the algebra:
    \begin{align*} 3x \amp= 19 \pmod{26}\\ (3^{-1})3x \amp=(3^{-1}) 19 \pmod{26}\\ x \amp\equiv (9) 19 \pmod{26}\\ x \amp\equiv 171 \pmod{26}\\ x \amp\equiv 15 \pmod{26} \end{align*}
    is the unique solution.
  2. Here \(\gcd(13, 26) = 2\) so there is no unique solution. Instead, there are either no solutions or two solutions! But since the gcd doesn’t divide \(7\text{,}\) there are in fact no solutions to this congruence.
  3. Since \(\gcd(8, 426) = 2\text{.}\) Like the previous question there are either no solutions or two solutions. This time since the gcd does divide 16, we will have two solutions! The first is obviously \(x=2\text{,}\) and the second will be, applying Note 3.4.12:
    \begin{align*} x \amp= 2 + \dfrac{426}{2}\\ \amp= 215 \end{align*}
  4. This time the modulus is 425, so we have \(\gcd(425, 8) = 1\) meaning a unique solution exists the system. The Euclidean algorithm finds that \(8^{-1} = -53 \pmod{425}\text{,}\) and solving the expression gives:
    \begin{align*} 8x \amp= 16 \pmod{426}\\ (8^{-1})8x \amp=(8^{-1}) 16 \pmod{425}\\ x \amp\equiv (-53) 16 \pmod{425}\\ x \amp\equiv -848 \pmod{425}\\ x \amp\equiv 2 \pmod{425} \end{align*}
    ... which actually is both obvious and hilarious. It shows that even if we don’t notice the obvious solution, the method will give us the correct result!
  5. This time, as before, \(\gcd(8, 426) = 2\text{,}\) so there are either zero or two solutions. But since there the gcd doesn’t divide \(23\text{,}\) there is no solution to the congruence.

4.

Play around with making multiplication tables of various moduli in the Sage code in example.
  1. What condition is required for a number \(a\) to have an inverse modulo \(n\text{?}\)
  2. What is a condition on \(n\) for every element to have an inverse modulo \(n\text{?}\)
  3. If there are more than one solution to \(ax = b\pmod{n}\text{,}\) what is the relationship between each solution?
Solution.
  1. To have an inverse modulo \(n\text{,}\) a number \(a\) must be relatively prime to \(n\)
  2. To have the property that every number has an inverse modulo \(n\text{,}\) the number \(n\) must be prime
  3. Not a solution, but a hint - take each example and exercise that had multiple solutions and subtract the solutions. What do you notice?
<Prev^TopNext>