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 7x ≡ 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, 8x ≡ 3 (mod 10) has no solution; 8x is always an even integer and so it can never end in 3 in base 10. For another example, 8x ≡ 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 7x ≡ 13 (mod 100). Since 7 and 100 are relatively prime, there is a unique solution. The algorithm says we should solve 100y ≡ −13(mod 7). Since 100 ≡ 2 (mod 7) and −13 ≡ 1 (mod 7), this problem reduces to solving 2y ≡ 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 50x ≡ 65 (mod 105). Since gcd(50, 105) = 5 and 65 is divisible by 5, there are 5 solutions. So we first solve 10x ≡ 13 (mod 21). The algorithm above says we can solve this by first solving 21y ≡ -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.
Related: Applied number theory
I enjoyed your article but impore you to give more examples in simpler forms
thank you for explaining this thoroughly and easy to understand
first place that I’ve understood it, after looking through my book and all over the internet
most likely will be coming back here in the future
Thank you! This was really helpful. One or two coding examples would’ve been great, though =P
this really helpful for my project. Thanks a bunch
Really well written, thanks so much!