A linear congruence is the problem of finding an integer *x* satisfying

*ax* ≡ *b* (mod *m*)

for specified integers *a*, *b*, and *m*. This problem could be restated as finding *x* such that

- the remainder when
*ax* is divided by *m* is *b*,
`a*x % m == b `

in C code,
*ax* – *b* is divisible by *m*, or
- in base m,
*ax* ends in *b*.

Two solutions are considered the same if they differ by a multiple of *m*. (It’s easy to see that *x* is a solution if and only if *x* + *km* is a solution for all integers *k*.)

For example, we may want to solve 7*x* ≡ 3 (mod 10). It turns out *x* = 9 will do, and in fact that is the only solution. However, linear congruences don’t always have a unique solution. For example, 8*x* ≡ 3 (mod 10) has no solution; 8*x* is always an even integer and so it can never end in 3 in base 10. For another example, 8*x* ≡ 2 (mod 10) has two solutions, *x* = 4 and *x* = 9.

In this post, we answer two questions.

- How many solutions does
*ax* ≡ *b* (mod *m*) have?
- How can we compute them?

The answer to the first question depends on the greatest common divisor of *a* and *m*. Let *g* = gcd(*a*, *m*). If *b* is not divisible by *g*, there are no solutions. If *b* is divisible by *g*, there are *g* solutions.

So if *g* does divide *b* and there are solutions, how do we find them? The brute force solution would be to try each of the numbers 0, 1, 2, … *m*-1 and keep track of the ones that work. That works in theory, but it is impractical for large *m*. Cryptography applications, for example, require solving congruences where *m* is extremely large and brute force solutions are impossible.

First, suppose *a* and *m* are relatively prime. That is, assume *g* = gcd(*a*, *m*) = 1. We first put the congruence *ax* ≡ *b* (mod *m*) in a standard form. We assume *a* > 0. If not, replace *ax* ≡ *b* (mod *m*) with –*ax* ≡ –*b* (mod *m*). Also, we assume *a* < *m*. If not, subtract multiples of *m* from *a* until *a* < *m*.

Now solve *my* ≡ –*b* (mod *a*). This is progress because this new problem is solving a congruence with a smaller modulus since *a* < *m*. If *y* solves this new congruence, then *x* = (*my* + *b*)/*a* solves the original congruence. We can repeat this process recursively until we get to a congruence that is trivial to solve. The algorithm can be formalized into a procedure suitable for programming. The result is closely related to the Euclidean algorithm.

Now what if the numbers *a* and *m* are not relatively prime? Then first solve the congruence (*a*/*g*)*y* ≡ (*b*/*g*) (mod (*m*/*g*)) using the algorithm above. Then the solutions to *ax* ≡ *b* (mod *m*) are *x* = *y* + *tm*/*g* where t = 0, 1, 2, …, *g*-1.

Here are a couple examples.

First, let’s solve 7*x* ≡ 13 (mod 100). Since 7 and 100 are relatively prime, there is a unique solution. The algorithm says we should solve 100*y* ≡ -13(mod 7). Since 100 ≡ 2 (mod 7) and -13 ≡ 1 (mod 7), this problem reduces to solving 2*y* ≡ 1 (mod 7), which is small enough to solve by simply sticking in numbers. We find *y* = 4. Then *x* = (100*4 + 13)/7 = 59. You can verify that 7*59 = 413 so 7*59 ≡ 13 (mod 100). In general, we may have to apply the algorithm multiple times until we get down to a problem small enough to solve easily.

Now let’s find all solutions to 50*x* ≡ 65 (mod 105). Since gcd(50, 105) = 5 and 65 is divisible by 5, there are 5 solutions. So we first solve 10*x* ≡ 13 (mod 21). The algorithm above says we can solve this by first solving 21*y* ≡ -13 (mod 10), which reduces immediately to *y* ≡ 7 (mod 10), and so we take *y* = 7. This says we can take *x* = (105*7 + 65)/50 = 16. The complete set of solutions to our original congruence can be found by adding multiples of 105/5 = 21. So the solutions are 16, 37, 58, 79, and 100.

I intend to write posts in the future about how to solve simultaneous systems of linear congruences and how to solve quadratic congruences.

**Update**: Here are the posts I intended to write: systems of congruences, quadratic congruences.