Javascript required
Skip to content Skip to sidebar Skip to footer

Show Whether a System of Linear Congruences Has No Solution

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

axb (mod m)

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

  1. the remainder when ax is divided by m is b,
  2. a*x % m == b in C code,
  3. axb is divisible by m, or
  4. 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.

  1. How many solutions does axb (mod m) have?
  2. 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 axb (mod m) in a standard form. We assume a > 0. If not, replace axb (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 axb (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

For daily tweets on algebra and other math, follow @AlgebraFact on Twitter.

AlgebraFact logo

Show Whether a System of Linear Congruences Has No Solution

Source: https://www.johndcook.com/blog/2008/12/10/solving-linear-congruences/