Solving Modular Congruences: A Guide

Daniel Liu

May, 2021

Introduction

This guide attempts to serve as a step-by-step explanation on how to solve modular congruences, a topic that many may find quite confusing. Before we begin, modular congruences are simply algebraic equations, but within the world of modular arithmetic. It deals with equalities such as $3x \equiv 7 (mod\ 17)$ , and encompasses solving techniques that one would not normally use when solving regular equations.

Chinese Remainder Theorem

The Chinese Remainder Theorem, CRT for short, essentially states that given a system of $n$ equations,

$x = a_1 (mod\ m_1)$

…

$x = a_n (mod\ m_n)$

there is a unique solution for $x$ mod $M$ , where $M = m_1 \times m_2 \times \dots \times m_n$ . Frankly, the formal statement for CRT makes very little sense at the beginning. Luckily, this theorem is very conceptual in nature, and most of the time when we solve modular congruences, we never even realize we are applying it.

A conscious and discrete application of CRT is relatively trivial for competitions like Mathcounts and the AMC 10, and therefore will not be covered in this guide.

But for those who ponder its use in modular congruences, know that it, from a broad perspective, tells us that a solution actually exists for a given congruence.

Solving Modular Congruences

Now that we have a rough idea of CRT and that solving a congruence is always possible, we proceed to find out exactly how to solve one of them. Let’s start off with an easy problem:

Example 1.1: Solve $9x \equiv 36 (mod\ 11)$ .

To solve this problem, we simply divide both sides by 9 to get that $x \equiv 4 (mod\ 11)$ , and that is our answer.

An important lesson to learn here is that we can only divide by 9 because 9 and 11 are relatively prime. This is a good thing to know and remember about modular arithmetic.

We now understand the basic idea of solving modular congruences and we move to a harder problem.

Example 1.2: Solve $9x \equiv 4 (mod\ 11)$ .

For this problem, we can’t divide both sides by some constant $c$ , so we are forced to find some other method of solving. What we do here is a clever use of mod properties- we simply subtract $11x$ from the left hand side, and still retain $4 (mod\ 11)$ . on our right hand side.

Now, we are left with $-2x \equiv 4 (mod\ 11)$ .

From here, simply divide both sides by $-2$ to get that $x \equiv -2 (mod\ 11)$ .

Example 1.3: Solve $9x \equiv 4 (mod\ 11)$ .

This problem is the exact same one as example 1.2, but we will use a different way to solve it.

Instead of using mod properties that only fit the specific problem, we seek a more generalized approach.

Our intent on finding a method of solving any modular congruence, not just the ones that have convenient and unique solutions to them, leads us to the concept of multiplicative inverses.

Multiplicative inverse: Denote the multiplicative inverse of some integer $a$ as ${a^{-1}}$ . Then for some integer $n$ such that $(a, n) = 1$ ,

$a \cdot a^{-1} \equiv 1 (mod\ n)$ .

For the problem above, we see that 9 and 11 are indeed relatively prime. From here, we want to find the multiplicative inverse of 9.

We first check 11 + 1, is that divisible by 9? Nope.

What about $2 \cdot 11 + 1$ ? Again, it is not. We keep on testing values equivalent to $1 (mod\ 11)$ until we get to 45.

Is 45 equal to $1 (mod\ 11)$ ? Yup. Is it divisible by 9? It is indeed. Therefore, we have found a multiplicative inverse of $9 (mod\ 11)$ : 5, since $5 \cdot 9 = 45$ .

Now what?

Taking wisdom from the previous problem, we multiply both sides by 5, to get that $45x \equiv 20 (mod\ 11)$ . Then, we simply subtract $44x$ from the left side because it is an integer multiple of 11, and when you take away an integer multiple of $n$ from $a (mod\ n)$ , you’re still left with $a (mod\ n)$ !

Therefore, we get that $x \equiv 20 (mod\ 11)$ , also equivalent to $-2 (mod\ 11)$ , the same answer we got last time.

Exercise 1.1: Solve $2x \equiv 4 (mod\ 5)$

Exercise 1.2: Solve $2x \equiv 3 (mod\ 5$

☆Exercise 1.3: Solve $2x \equiv 4 (mod\ 8)$

As demonstrated in example 1.3, using multiplicative inverses can be extremely helpful in solving modular congruences, especially the more complex ones. But that’s only true if a multiplicative inverse can be found in the first place. How would we systematically be able to find one without guess and check?

Finding Multiplicative Inverses

Now that we have a decent idea of what a multiplicative inverse actually is, and have some sense of how to apply it, we need to create a reliable, systematic way of finding a multiplicative inverse of a modular congruence.

Let’s use example 1.3 as a model to get us started. Our goal is to find a multiple of 9 that is one greater than a multiple of 11. How would we use algebra to express this? We can use the equation $9m = 11n + 1$ , with $m$ and $n$ being integers.

But here’s the problem: how would we find solutions to that equation without guess and check?

Well let’s play with the numbers a bit to see what we can do. First off, is there anything we can factor? Not really. 9 and 11 are relatively prime, as intended, so there is nothing we can do with them.

Now we try to move things around. What if we brought the $11n$ term to the left side? Let’s see what will happen.

We get that $9m - 11n = 1$ .

Yikes. How would we solve this?

But don’t give up yet; let’s think a bit more about this. That minus sign is a bit wacky, its presence makes it difficult to even guess and check. Let’s turn it into a plus sign with some algebra:

$9m + 11n = 1$

We can do this because $n$ doesn’t have to be positive. When it’s negative, the minus becomes a plus, and at the end, all we have to do is reverse the sign of $11n$ when $n$ is negative to get a positive version.

For example, as we found earlier, $11\cdot (-4)$ in the expression $9\cdot5 + 11\cdot (-4)$ correlates to positive 44.

But back to the equation $9m + 11n = 1$ . looks kind of familiar. Hm. What might it be?

As stated earlier, $m$ and $n$ have to be integers, so we are looking for integer solutions.

Wait. Isn’t there some sort of concept that deals only with integer solutions? Yes, Diophantine equations!

We can simply find solutions using the Euclidean algorithm process taught in this handout, if solving by guess-and-check is too hard.

Now, let’s look at an example.

Example 2.1: Solve $23x \equiv 67 (mod\ 71)$ .

Clearly, we can’t really guess-and-check our way out of this one. As done previously, we look for a solution satisfying $23m = 71n + 1$ for integers $m$ and $n$ .

Following in the last example’s footsteps, we convert this equation into a diophantine equation: $23m - 71n = 1$ , which turns into $23m + 71n = 1$ since $n$ can be positive or negative.

Now we solve using the Euclidean algorithm process:

$71 = 23 \times 3 + 2$

$\to$

$23 = 2 \times 11 + 1$

$\to$

$1 = 23 - 2 \times 11$

$= 23 - 11\times (71 - 23 \times 3)$

$=34 \times 23 -11 \times 71$

All of this calculation tells us one thing: 34 and 23 are multiplicative inverses. This is because $34 \times 23 \equiv 1 (mod\ 11)$ .

Remark: Don’t get lost in the calculation. Always remember the ultimate goal and know how to interpret the final result correctly, or else confusion will very quickly arise. As we saw above, the 11 in $11 \times 71$ had little use to us, and we therefore ignored it and only paid attention to what we wanted, the 34.

Therefore, from here, we multiply both sides by 34:

$782x \equiv 2278 (mod\ 71)$

$\to$

$782x \equiv 6 (mod\ 71)$

We follow the previous example and subtract from both sides, to get that

$x \equiv 6 (mod\ 71)$

This problem took quite a bit of calculation and algebra to solve, but ultimately we have succeeded in our goal and have found a general process for solving modular congruences.

Modular Congruences: The General Method

The general solution to the congruence $a \equiv b (mod\ n)$ is as follows:

Set $a \equiv 1 (mod\ n)$ .
Turn the congruence into a diophantine equation involving $a$ and $n$ , $ap + np = 1$ .
Solve the diophantine equation (click here for more on solving diophantine equations).
Use the results to find the multiplicative inverse of $a$ .
Multiply both sides of the congruence by the multiplicative inverse, now denoted as $m$ , to get $am \equiv c (mod\ n)$ .
Subtract $a(m - 1)$ from both sides of the equation, which is an integer $n$ , to get $a \equiv c (mod\ n)$ , the solution of the problem.

The past 8 pages of this guide was dedicated to finding a general solution that, ultimately, can be summed up in 6 simple steps. So why does this matter?

It matters because it’s a very good example of how the reasoning behind one single statement in mathematics can take days, months, or even years to derive.

Now although this guide is not meant to take several years to understand, 8 pages of reasoning simplified to 6 steps teaches an important lesson: Everyone can learn a theorem and apply it. There’s nothing much to it. But what makes the difference is understanding how the theorem was arrived upon in the first place.

Share this:

Related

Leave a comment Cancel reply