Skip to main content

Section 4.3 Solving Congruences

Video: Solving Congruences

When we are asked to solve for x in an equation like 2x2+4=36, we know that we need to look for all values of x that satisfy that equation (x=±4). What if we are asked to solve for x given a congruence?

Solve for \(x\) in the congruence \(2x \equiv 4 \Mod{9}\text{.}\)

Before looking at the solution, try it yourself first! What value(s) of \(x\) will satisfy the congruence?

Solution

We need to find all values of \(x\) so that \(9 \mid (2x - 4)\text{,}\) or \(9 \mid 2(x-2)\text{.}\)

Since \(\gcd(2,9) = 1\text{,}\) by Checkpoint 1.3.13 we have \(9 \mid (x-2)\text{,}\) which means \(x \equiv 2 \Mod{9}\text{.}\)

Note that this is no different from applying Proposition 4.2.15 directly: since \(\gcd(2,9) = 1\text{,}\) we can safely divide both sides by 2 to obtain \(x \equiv 2 \Mod{9}\text{.}\)

This means that the congruence class \([2]\) is the solution to \(2x \equiv 4 \Mod{9}\text{,}\) or that all integers in \(\{\ldots,-16,-7,2,11,\ldots\}\) satisfy the congruence.

The final answer in the above example is typical of solutions to congruences: since we are working modulo n, answers will be congruence classes from {[0],[1],…,[n−1]}. Hence when asked to solve for x given a congruence, you should express your answer as a congruence class ([2]), or as a statement of congruence like x≡2 (mod 9), which makes the modulus explicit.

Solve the congruence

\begin{equation*} 2x \equiv 6 \Mod{10}\text{,} \end{equation*}

and express your answer using congruence classes of the original modulus.

Solution

We can apply Proposition 4.2.15 here to divide through by 2, and we get

\begin{equation*} x \equiv 3 \Mod{5}\text{.} \end{equation*}

Modulo 10, this is the same as

\begin{equation*} x \equiv 3 \Mod{10} \text{ and } x \equiv 8 \Mod{10}\text{.} \end{equation*}

So the original congruence has two solutions in \(\{[0],[1],\ldots,[9]\}\text{,}\) namely \([3]\) and \([8]\text{.}\)

Solve each congruence for \(x\text{,}\) paying special attention to your usage of Proposition 4.2.15.

  1. \(\displaystyle 3x \equiv 9 \Mod{10}\)
  2. \(\displaystyle 5x + 2 \equiv 27 \Mod{15}\)
  3. \(\displaystyle -11x - 3 \equiv 30 \Mod{7}\)

Proposition 4.2.15 cannot be used to solve the congruence

\begin{equation*} 2x \equiv 3 \Mod{7} \end{equation*}

since we cannot divide both sides by 2.

Solve the congruence by trial-and-error.

Hint

There are only 7 congruence classes to check, since we are working modulo 7.

Video: Multiplicative Inverses

We've seen that dividing both sides by a constant is not always possible. Recall instead that in the real numbers, division by a nonzero number x is the same as multiplication by its reciprocal 1x. The number 1x is sometimes called the inverse of x since they ‘cancel’ each other out when multplied together.

We define a similar concept for modular arithmetic.

Definition 4.3.5. Multiplicative Inverse.

Given natural numbers a,n such that gcd(a,n)=1, the number b is called a multiplicative inverse of a modulo n if

ab≡1 (mod n).

We can denote this inverse as a−1=b, or by a−1 (mod n) to make the modulus explicit.

In Definition 4.3.5 we are really saying that any number in [b] is a multiplicative inverse of a modulo n, though we will usually be interested in finding that specific inverse that is also in the set {0,1,…,n−1}. This can now be used when solving congruences of the form

ax≡b (mod n)

where a∤b. Instead of dividing both sides by a (which can't always be done), we multiply both sides by the inverse of a.

Show that modulo 7, any number in \([4]\) is a multiplicative inverse of 2. Then use this fact to solve the congruence

\begin{equation*} 2x \equiv 3 \Mod{7} \end{equation*}

from Checkpoint 4.3.4.

You may have noticed that in Definition 4.3.5 we required that gcd(a,n)=1 holds. Without this condition, could one still obtain an inverse of a modulo n? Before expanding the next exercise try exploring this idea with pairs of values of a and n that aren't relatively prime.

Let \(a, n \in \mathbb{N}\text{.}\) Prove that \(a\) has an inverse modulo \(n\) if and only if \(\gcd(a,n) = 1\text{.}\)

Hint

Prove both directions separately. Theorem 1.3.7 will be useful in both cases.

For brevity, we make use of the following terminology for integers that have inverses under a particular modulus.

Definition 4.3.8. Unit Modulo n.
If a,n∈N such that a has an inverse modulo n, then a is said to be a unit modulo n.

Given \(a, n \in \mathbb{N}\) such that \(\gcd(a,n) = 1\text{,}\) prove that the multiplicative inverse of \(a\) modulo \(n\) is unique (up to congruence class).

Hint

Assume that \(c\) and \(d\) are both multiplicative inverses of \(a\) modulo \(n\text{.}\) Show that \(c \equiv d \Mod{n}\text{.}\)

Use the previous exercise to argue that

\begin{equation*} ax \equiv b \Mod{n} \end{equation*}

has a unique solution (up to congruence class) if \(\gcd(a,n) = 1\text{.}\)

Does the converse hold? That is, if we know that

\begin{equation*} ax \equiv b \Mod{n} \end{equation*}

has a unique solution, can we conclude that \(\gcd(a,n) = 1\text{?}\)

Solve the congruences:

  1. \(\displaystyle 5x - 7 \equiv 9 \Mod{11}\)
  2. \(\displaystyle 3 - 2x \equiv 3 - 5x \Mod{7}\)
  3. \(\displaystyle 21x + 35 \equiv 9 \Mod{19}\)

Since \(\gcd(6,16) \gt 1\text{,}\) the number 6 has no multiplicative inverse modulo 16. Solve the congruences

\begin{equation*} 6x \equiv 3 \Mod{16} \end{equation*}

and

\begin{equation*} 6x \equiv 4 \Mod{16}\text{.} \end{equation*}

How many solutions do you get for each one (modulo 16)?