4.3. Solving Congruences#

We know from Section 4.1.3 that working modulo a positive integer forms a special kind of equivalence relation known as a congruence relation. For example, \(4 \equiv 16 \bmod 6\) since \(6 \mid 16 - 4\).

Now, we look to include variables in equivalence relations and solve for those variables.

4.3.1. Linear Congruences#

A linear congruence is an equivalence of the form \(ax \equiv b \bmod m\) where \(x\) is a variable, \(a,b\) are positive integers, and \(m\) is the modulus.

The solution to such a congruence is all integers \(x\) which satisfy the congruence.

Solution to a linear congruence

\[ 2x \equiv 1 \mod 5 \]

By inspection we find that \(2 \cdot 3 = 6 \equiv 1 \mod 5\). Therefore, a solution this linear congruence is \(x = 3\). However, notice that \(x=8\) is also a solution since \(2\cdot 8 = 16 \equiv 1 \mod 5\).

In a linear congruence, there are infinitely many possible solutions. In the previouse example we saw that \(x=3\) and \(x=8\) were both solutions. In this case, since \(x=3\) was a solution, then so is every element in the congruence class of \(3\). Recall that the congruence class of \(3\) modulo \(5\) is defined as:

\[ \overline{3} = \{x \ |\ x \equiv 3 \mod 5\}. \]

Modular Inverses#

To solve an equation like \(ax = b\) over the reals, we would normally divide through by \(a\), assuming \(a \neq 0\), to get \(x = \frac{b}{a}\). This is equivalent to multiplying both sides by the multiplicative inverse of \(a\). A multiplicative inverse of a number is another number such that their product equals \(1\).

Over the real numbers we have \(a \cdot \frac{1}{a} = 1\) for any \(a\). Therefore, we can solve \(ax = b\) by multiplying both sides by \(\frac{1}{a}\).

Just as over the rational numbers or real numbers, there are (often, but not always) multiplicative inverses when working modulo a number. Given a number \(x\) and a modulus \(m\), the modular multiplicative inverse of \(x\) is another number \(a\) such that \(ax \equiv 1 \mod m\).

Modular inverse

Compute the inverse of \(3\) modulo \(7\).

\[\begin{split} 3a \equiv 1 \mod 7 \\[1em] 15 \equiv 1 \mod 7 \\[1em] \rightarrow a \equiv 5 \mod 7 \end{split}\]

Similar to linear congruences, there may be many modular inverses of a number. In the previous example, \(5\) was the modular inverse of \(3 \mod 7\). Any number in the congruence class of \(5\) modulo \(7\) is a multiplicative inverse. Moreover, any number in the congruence class of \(5\) modulo \(7\) is a multiplicative inverse of any number in the congruecne class of \(3\) modulo \(7\).

We can use modular inverses to solve linear congruences. Let \(a'\) be the inverse of \(a\) modulo \(m\). Then, we have the following:

\[\begin{split} ax &\equiv b \mod m \\[1em] a'ax &\equiv a'bx \mod m \\[1em] x &\equiv a'b \mod m \end{split}\]

Modular inverses may not exist

It may happen that certain numbers do not have multiplciative inverses modulo a particular modulus.

Consider \(2\) modulo \(6\). It does not have an inverse. We can verify this by attempting to multiply \(2\) by each of \(0, 1, 2, 3, 4, 5\).

\[\begin{split} 2 \cdot 0 \equiv 0 \mod 6 \\[1em] 2 \cdot 1 \equiv 2 \mod 6 \\[1em] 2 \cdot 2 \equiv 4 \mod 6 \\[1em] 2 \cdot 3 \equiv 0 \mod 6 \\[1em] 2 \cdot 4 \equiv 2 \mod 6 \\[1em] 2 \cdot 5 \equiv 4 \mod 6 \\[1em] \end{split}\]

Theorem 4.3.1 will establish when modular inverses exist.

But when do they not exist? In this case it is because \(\gcd(2,6) \neq 1\). Because of that fact, \(2\) is called a zero-divisor for arithmeitc modulo \(m\).

Computing Modular Inverses#

Finding the modular inverse of a number can be very challenging. It is easy to find by inspection the inverse of \(3 \bmod 8\) (it is \(3\) itself since \(3\cdot3 = 9 \equiv 1 \bmod 8\)).

However, can you find the inverse of \(151 \bmod 951\)?.

An algorithmic process exists to compute modular inverses using the Euclidean algorithm and Bézout relations. This is based on the following theorem.

Theorem 4.3.1

If \(a\) and \(m\) are relatively prime integers with \(m > 1\), then there exists a unique modular inverse \(x\) of \(a\) modulo \(m\) satisfying \(0 < x < m\).

Proof:

We first prove the exitence of \(x\). By hypothesis we have \(\gcd(a,m) = 1\). Therefore, By Bézout’s theorem there exists integers \(s\) and \(t\) such that \(sa + tm = 1\).

We have:

\[\begin{split} 1 - sa = tm \\[1em] m \mid (1 - sa) \\[1em] 1 \equiv sa \bmod m \end{split}\]

Therefore, \(s = x\) is the modular inverse of \(m\).

Next, we show uniqueness. Assume there exists another modular inverse \(b\) of \(a\). By the definition of modular inverses we have \(xa \equiv 1 \bmod m\) and \(ba \equiv 1 \bmod m\). Therefore, \(xa \equiv ba \bmod m\).

From Theorem 4.2.10, we have \(x \equiv b \bmod m\) since \(\gcd(a,m) = 1\). Therefore, \(x\) is unique for \(0 < x < m\). \(\blacksquare\)

The previous theorem establishes criteria for a modular inverse to exist. The proof of this theorem suggests how to compute the inverses: we compute a Bézout relation betwen the modulus and the number to invert.

Computing an easy modular inverse

Find the inverse of \(3\) modulo \(7\).

Since \(\gcd(3,7) = 1\), an inverse must exist. From Euclidean division we have \(7 = 2\cdot3 + 1\) and thus \(-2\cdot3 + 1\cdot 7 = 1\). Hence, \(-2\) is the Bézout coefficient of \(3\) and \(-2 \equiv 5 \bmod 7\) is the modular inverse of \(3\).

Computing a hard modular inverse

Find the inverse of \(151\) modulo \(951\).

Using the Euclidean algorithm we find:

\[\begin{split} 951 &= 6\cdot 151 + 45 \\[1em] 151 &= 3\cdot 45 + 16 \\[1em] 45 &= 2\cdot 16 + 13 \\[1em] 16 &= 1\cdot 13 + 3 \\[1em] 13 &= 4\cdot 3 + 1 \\[1em] 3 &= 3\cdot 1 + 0 \end{split}\]

Therefore, \(\gcd(951,151) = 1\). Morevoer, we can find a Bézout relation between \(951\) and \(151\) via back substitution:

\[\begin{split} 1 &= 13 - 4\cdot3 \\[1em] 1 &= 13 - 4 (16 - 1 \cdot 13) = -4\cdot 16 + 5\cdot 13\\[1em] 1 &= -4\cdot 16 +5 (45 - 2\cdot 16) = 5\cdot 45 -14 \cdot 16 \\[1em] 1 &= 5\cdot 45 -14 (151 - 3\cdot45) = -14\cdot 151 47\cdot 45\\[1em] 1 &= -14\cdot 151 + 47 (951 - 6\cdot 151) = -296\cdot151 + 47\cdot 951 \\[1em] \end{split}\]

Therefore, the modular inverse of \(151\) modulo \(951\) is \(-296 \equiv 655 \bmod 951\).

Using inverses to solve linear congruences

Solve the following linear congruence by first computing an inverse.

\[ 57x \equiv 13 \bmod 67 \]

Using inverses to solve linear congruences

First find the inverse of \(57\) modulo \(67\). Use the Euclidean algorithm:

\[\begin{split} 67 &= 1 \cdot 57 + 10 \\[1em] 57 &= 5\cdot 10 + 7 \\[1em] 10 &= 1\cdot 7 + 3 \\[1em] 7 &= 2\cdot 3 + 1 \\[1em] 3 &= 3\cdot 1 + 0 \end{split}\]

We have \(\gcd(67,57) = 1\) so a modular inverse exists. Then compute the Bézout coefficients:

\[\begin{split} 1 &= 7 - 2\cdot 3 \\[1em] 1 &= 7 - 2(10 - 1\cdot 7) = -2\cdot 10 + 3\cdot 7\\[1em] 1 &= -2\cdot 10 + 3(57 - 5\cdot10) = 3\cdot 57 - 17\cdot 10 \\[1em] 1 &= 3\cdot 57 - 17(67 - 1\cdot 57) = -17\cdot 67 + 20 \cdot 57 \end{split}\]

The inverse of \(57\) modulo \(67\) is \(20\). This yields:

\[\begin{split} 57x \equiv 13 \mod 67 \\[1em] 20(57x) \equiv 20\cdot 13 \mod 67 \\[1em] 1\cdot x \equiv 260 \mod 67 \\[1em] x \equiv 59 \mod 67 \\[1em] \end{split}\]

4.3.2. Systems of Linear Congruences#

Consider a system of linear congruences.

\[\begin{split} \left\{ \begin{array}{l}x \equiv 3 \mod 7 \\[1em] x \equiv 6 \mod 13 \end{array}\right. \end{split}\]

Could we find a value of \(x\) that simultaneously satisfies both of these equations?

By inspection, one could find that \(45\) is a possible solution. Indeed, \(7 \mid (45 -3) = 42\) and \(13 \mid (45 - 6) = 39\).

Is there an algorithmic process to find such an \(x\)? Yes!

Chinese Remainder Theorem#

Theorem 4.3.2 (Chinese Remainder Theorem)

Let \(m,n\) be two co-prime integers greater than \(1\). Then,

\[\begin{split} \left\{ \begin{array}{l}x \equiv a \mod m \\[1em] x \equiv b \mod n \end{array}\right. \end{split}\]

has a unique solution modulo \(m\cdot n\).

Proof:

Since \(m\) and \(n\) are co-prime, by the Bézout theorem there exists integers \(s,t\) such that:

\[ sm + tn = 1 \]

Then, notice that \(x = bsm + atn\) satisfies the linear congruences:

\[\begin{split} x &= bsm + atn \\[1em] &= bsm + a(1 - sm) \\[1em] &= bsm + a - asm \\[1em] &\equiv a \mod m \\[1em] \end{split}\]
\[\begin{split} x &= bsm + atn \\[1em] &= b(1-tn) + atn \\[1em] &= b - btn + atn \\[1em] &\equiv b \mod n \end{split}\]

Now consider uniqueness. Let \(x = y\) and \(x = z\) be two solutions of this system. Then, \(y\) and \(z\) must give the same remainder when divided by \(m\) or divided by \(n\). Therefore, \(m \mid y - z\) and \(n \mid y - z\).

Since \(m\) and \(n\) are co-prime, it follows that \(m\cdot n \mid y -z\) (see Exercise 4.18). Therefore \(y \equiv z \bmod m\cdot n\). \(\blacksquare\)

Let’s try an example.

A system of linear congruences.

Find all integers \(x\), \(0 \leq x < 15\) such that:

\[\begin{split} \left\{ \begin{array}{l}x \equiv 1 \mod 3 \\[1em] x \equiv 2 \mod 5 \end{array}\right. \end{split}\]

Since \(3\) and \(5\) are co-prime, Chinese Remainder Theorem states there exists a unique solution modulo \(15\). Therefore, there is exactly one solution \(x\) with \(0 \leq x < 15\).

Apply the Euclidean algorithm to find \(s,t\) such that \(3s + 5t = 1\). Or, by inspection, we see \(3(2) + 5(-1) = 1\) implies \(s = 2\), \(t = -1\).

Therefore, \(x = 2(3s) + 1(5t) = 2(3)(2) + 1(5)(-1) = 7 \equiv 7 \bmod 15\).

Solve a system of linear congruences

Solve the system of linear congurences presented at the beggining of this section for \(0 \leq x < 91\) using the Chinese Remainder Theorem.

\[\begin{split} \left\{ \begin{array}{l}x \equiv 3 \mod 7 \\[1em] x \equiv 6 \mod 13 \end{array}\right. \end{split}\]

Solve a system of linear congruences

Surely \(7\) and \(13\) are co-prime since they are both prime. Therefore, there exists \(s,t\) such that \(7s + 13t = 1\). By inspection we see \(s = 2\) and \(t = -1\).

Therefore, a solution is \(x = 6(7s) + 3(13t) = 84 - 39 = 45\).

We verify this by seeing that \(7 \mid 45 - 3 = 42\) and \(13 \mod 45 - 6 = 39\).

4.3.3. Exercises#

Exercise 4.17

Find the multiplicative inverse of:

  1. \(8\) modulo \(17\).

  2. \(9\) modulo \(23\).

  3. \(11\) modulo \(71\).

Exercise 4.18

Prove the following lemma.

Lemma 4.3.3

Let \(m\) and \(n\) be co-prime integers.

For any integer \(x\) such that \(m \mid x\) and \(n \mid x\), then \(mn \mid x\).

Exercise 4.19

Solve the following linear congruences. Give the unique positive solution which is less than the modulus.

  1. \(x \equiv 12 \mod 7\)

  2. \(2x \equiv 12 \mod 7\)

  3. \(13x \equiv 15 \mod 23\)

Exercise 4.20

Solve the following system of linear congruences for \(0 \leq x < 77\).

\[\begin{split} \left\{ \begin{array}{l}3x \equiv 2 \mod 11 \\[1em] 4x \equiv 6 \mod 7 \end{array}\right. \end{split}\]

Exercise 4.21

Solve the following system of linear congruences for \(0 \leq x < 221\).

\[\begin{split} \left\{ \begin{array}{l}4x \equiv 11 \mod 13 \\[1em] 2x \equiv 7 \mod 17 \end{array}\right. \end{split}\]