CMSC 27100 — Lecture 12

Solving linear congruences

One might ask whether there is any integer $m$ for which $\mathbb Z_m$ has a multiplicative inverse for all non-zero elements. Our discussion about prime numbers gives us a hint. But first, we need the following useful fact.

If $a$ and $m$ are relatively prime and $a \gt 1$, then the multiplicative inverse of $a$ modulo $m$ is unique.

This is not hard to show using the usual trick of considering two inverses, say $b$ and $c$, for $a$ and arriving at the fact that $b \equiv c$. Then, together with the property that elements that are relatively prime with the modulus have multiplicative inverses, we get the following useful fact.

If $p$ is prime and $a \neq 0 \pmod p$, then $a$ has a multiplicative inverse mod $p$.

This is easy to see since every integer $2, \dots, m-1$ aren’t divisors of $p$ and therefore share no common divisors with $p$.

When it exists, we denote the multiplicative inverse of $a$ by $a^{-1}$.

Up until now, we’ve been working in $\mathbb Z$, where “division” “doesn’t work”. However, we’ve proved sufficient conditions to create structures where “division” does work in a sense, in that multiplicative inverses are guaranteed to exist for every element. This means that we can solve linear equations like $$6x \equiv 144 \pmod{17}$$ using our usual algebraic techniques. In fact, assuming we were working with the same modulus, it’s not hard to solve a system of equations in the usual way.

Technically speaking, these aren’t equations because the items aren’t being equated; we call these congruences instead.

So let’s solve this congruence. Just like with ordinary equations, there are a few approaches we can take. One thing we might try is to compute $144 \pmod{17}$. Some quick math tells us that $144 \equiv 8 \pmod{17}$. This means we have $6x \equiv 8 \pmod{17}$. Now, we want to isolate the $x$, so we need to “divide” by 6. This amounts to finding an element $y$ such that $6y \equiv 1 \pmod{17}$. Doing some quick math, we get $6 \times 3 \equiv 18 \equiv 1 \pmod{17}$. This gives us $x \equiv 8 \times 3 \equiv 24 \equiv 7 \pmod{17}$.

Alternatively, we could have gotten rid of the 6 first and then solved the remaining congruence. This means we begin by multiplying both sides by 3 to get \[x \equiv 144 \times 3 \equiv 432 \equiv 7 \pmod{17}.\]

Now, you might look at this and go: wait a second, why couldn’t we have just looked for an appropriate $x$ that satisfied $6x \equiv 8 \pmod{17}$? And that is a valid approach—in fact, for non-linear congruences, that is often the best you can hope to do. But the ability to deploy algebra in the way that we’re used to may help us solve more complicated problems.

Before, we said that a structure where we have addition and multiplication is called a ring. But what happens when we have a ring that supports “division”, or more accurately, multiplicative inverses? These structures are called fields. So the integers, $\mathbb Z$ can be said to form a ring with addition and multiplication, while $\mathbb Z_p$, the integers modulo a prime $p$, are a field. Another example of a field is the rational numbers, $\mathbb Q$.

Chinese Remainder Theorem

So far, we’ve been dealing with $\mathbb Z_p$ for prime $p$ because of all the nice properties we get from it, but what if we really happen to want to work within $\mathbb Z_m$, where $m$ is not prime?

This sounds like playing with fire because, as we showed, we could get stuck when trying to solve our congruence since we may try to find an inverse for our element and there is none. Alternatively, there may be more than one solution.

Consider $6x \equiv 2 \pmod 8$. Since $\gcd(6,8) \gt 1$, 6 doesn’t have an inverse modulo 8. However, a quick search reveals that $x \equiv 3 \pmod 8$ is a solution to our congruence, since $6 \times 3 \equiv 18 \equiv 2 \pmod 8$. Since we found a solution, we will likely want to stop, but it turns out this isn’t the only solution. If we keep going, we find that $6 \times 7 \equiv 42 \equiv 2 \pmod 8$. So there are two possible solutions for $x$ (7 is the last one, since the next number we’d test is $8 \equiv 0 \pmod 8$ and we start over).

What we will show is that if we can break up the modulus $m$ into relatively prime factors, then we are still able to find a solution and that this solution is unique. That is, to solve $x \equiv a \pmod m$, if $m = m_1 \cdot m_2$ where $m_1$ and $m_2$ are relatively prime, then we can simply solve the simultaneous congruences \begin{align*} x &\equiv a \pmod{m_1} \\ x &\equiv a \pmod{m_2} \end{align*} instead and get our answer. The question then is how to solve simultaneous congruences under different moduli.

For all integers $a_1$ and $a_2$, and positive integers $m_1$ and $m_2$, if $\gcd(m_1, m_2) = 1$, then the simultaneous linear congruences \begin{align*} x &\equiv a_1 \pmod{m_1} \\ x &\equiv a_2 \pmod{m_2} \end{align*} have a unique solution modulo $m_1 m_2$. That is, if $x = n$ is one particular solution, then the solutions are given by the set of all integers such that \[x \equiv n \pmod{m_1 m_2}.\]

The origins of this problem are due to Sunzi, a Chinese mathematician from the third century AD and who happens to have the same name as the author of The Art of War but is not the same person. He first posed the following problem and theorem which solves it. \begin{align*} x &\equiv 2 &\pmod 3 \\ x &\equiv 3 &\pmod 5 \\ x &\equiv 2 &\pmod 7 \end{align*} The English name of the theorem is largely due to L.E. Dickson in the 1920s, who discovered it through earlier translated work. Dickson was a faculty member in the math department here—the Dickson Instructors are named after him.

Here is a quick example before we get into the proof. Consider the simulatneous congruences \begin{align*} x &\equiv 2 &\pmod 3 \\ x &\equiv 3 &\pmod 5 \end{align*}

Since $\gcd(3,5) = 1$, the Chinese Remainder Theorem tells us the solutions are unique modulo 15. Since the numbers are small enough, we can simply run through them: 3, 8, and 13 are integers between 0 and 14 that are congruent to $3 \pmod 5$.

Now, for each of these, we note that $3 \equiv 0 \pmod 3$, $8 \equiv 2 \pmod 3$, and $13 \equiv 1 \pmod 3$, so we can conclude that our desired solution is $8 \pmod{15}$.

Let’s proceed with the proof of the Chinese Remainder Theorem.

Let $a_1, a_2$ be arbitrary integers and let $m_1, m_2$ be arbitrary positive integers with $\gcd(m_1, m_2) = 1$. Since $\gcd(m_1, m_2) = 1$, by Bézout’s lemma, there exist integers $b$ and $c$ such that \[1 = bm_1 + cm_2.\] We claim that our solution to the simultaneous congruences is the integer \[x = a_1cm_2 + a_2 b m_1.\]

First, we make the following observations: \begin{align*} 1 &\equiv bm_1 + cm_2 \equiv bm_1 \pmod{m_2} &\text{and} \\ 1 &\equiv bm_1 + cm_2 \equiv cm_2 \pmod{m_1}. \end{align*} In other words, $b$ is the multiplicative inverse for $m_1$ modulo $m_2$ and $c$ is the multiplicative inverse for $m_2$ modulo $m_1$. (In fact, we showed this exact relationship that we got from Bézout’s identity when proving the existence of multiplicative inverses)

Then to verify our claim, we see that \begin{align*} x &\equiv a_1 c m_2 + a_2 b m_1 &\pmod{m_1} \\ &\equiv a_1 \cdot 1 + 0 &\pmod{m_1} \\ &\equiv a_1 &\pmod{m_1} \\ \\ x &\equiv a_1 c m_2 + a_2 b m_1 &\pmod{m_2} \\ &\equiv 0 + a_2 \cdot 1 &\pmod{m_2} \\ &\equiv a_2 &\pmod{m_2} \end{align*}

We say that $x$ is the solution modulo $m_1 m_2$, since all integers that are congruent to $x$ will also satisfy the simultaneous congruences.

To see that our solution is unique, suppose we have two solutions $x_1$ and $x_2$. In other words, $x_1$ and $x_2$ are both integers that satisfy $x \equiv a_1 \pmod{m_1}$ and $x \equiv a_2 \pmod{m_2}$. In this case, $x_1$ and $x_2$ are also congruent to each other modulo both of $m_1$ and $m_2$, so we have $m_1 \mid x_1 - x_2$ and $m_2 \mid x_1 - x_2$ by definition.

Notice that the setup here has $x_1$ and $x_2$ satisfying the simultaneous congruences, but there is nothing that says that they must be congruent modulo $m_1 m_2$ so that is what we need to show. Here, we will rely on the following theorem:

If $a$ and $b$ are relatively prime, and $a \mid n$ and $b \mid n$, then $ab \mid n$.

Since $m_1$ and $m_2$ are relatively prime, $m_1 \mid x_1 - x_2$, and $m_2 \mid x_1 - x_2$, we must also ahve that $m_1 m_2 \mid x_1 - x_2$ via the above theorem. But that is exactly the definition of congruence modulo $m_1 m_2$. Therefore, we have $x_1 \equiv x_2 \pmod{m_1 m_2}$.

While proof above was fairly straightforward, it seems like it doesn’t really tell us how to find the solution. However, upon closer examination, we’ll find some methods buried underneath. Notice that $b$ and $c$ are the integers that we obtain from Bézout’s identity. This means that they are computable via the Extended Euclidean Algorithm.

However, we didn’t cover the EEA, so what other observations can we make? Recall the proof of the existence of multiplicative inverses in modulo $m$. In that proof, we also used Bézout’s identity when we had $\gcd(a,m) = 1$. From this, we gather that $b$ is actually the inverse of $m_1$ modulo $m_2$ and $c$ is the inverse of $m_2$ modulo $m_1$.

Recall the simultaneous congruences \begin{align*} x &\equiv 2 &\pmod 3 \\ x &\equiv 3 &\pmod 5 \end{align*}

We had already shown that the solution is $8 \pmod{15}$. Taking this result, we can apply it to the original problem of Sunzi: \begin{align*} x &\equiv 2 &\pmod 3 \\ x &\equiv 3 &\pmod 5 \\ x &\equiv 2 &\pmod 7 \end{align*} Since we showed that $x \equiv 8 \pmod{15}$ satisfies the first two congruences, solving these three simultaneous congruences amounts to solving the congruences \begin{align*} x &\equiv 8 &\pmod{15} \\ x &\equiv 2 &\pmod 7 \end{align*} Since $\gcd(7,15) = 1$, we can simply apply the CRT again.

One can generalize this result to multiple moduli.

Let $a_1, a_2, \dots, a_k$ be integers and suppose that $m_1, m_2, \dots, m_k$ are $k$ pairwise positive relatively prime moduli. Then the system of equations \begin{align*} x & \equiv a_1 & \pmod{m_1} \\ x & \equiv a_2 & \pmod{m_2} \\ & \vdots \\ x & \equiv a_k & \pmod{m_k} \end{align*} has a unique solution modulo $m_1 \cdot m_2 \cdots m_k$.

We won’t prove this—all it takes is applying induction to our earlier proof. Instead, we return to the motivating problem we started out with.

For all integers $a$ and positive integers $m_1, m_2$, if $\gcd(m_1, m_2) = 1$, then the simultaneous congruences \begin{align*} x & \equiv a & \pmod{m_1} \\ x & \equiv a & \pmod{m_2} \end{align*} have the same solutions as $x \equiv a \pmod{m_1 m_2}$.

Let $a, m_1, m_2$ be arbitrary with $\gcd(m_1, m_2) = 1$. By the Chinese Remainder Theorem, there exists a solution to the simultaneous congruences, say $x \equiv n \pmod{m_1m_2}$.

We observe that $n = a$ is a possible solution for this congruence, since $a \equiv a \pmod{m_1}$ and $a \equiv a \pmod{m_2}$. So we have that $n \equiv a \pmod{m_1 m_2}$.