Some basics of RMO Number Theory: II. Linear Congruences

II. Linear congruences:

It is obvious that every integer is congruent (mod m) to exactly one of the numbers:

0, 1, 2, 3, 4, …, (m-1). ——- Note 1.

For, we can express the integer in the form $qm+r$ , where $0 \leq r <m$ , and then, it is congruent to $r {\pmod m}$ . Obviously, there are other sets of numbers, besides the set in Note 1, which have the same property, e.g., any integer is congruent (mod 5) to exactly one of the numbers 0, 1, -1, 2, -2. Any such set of numbers is said to constitute a complete set of residues to the modulus m. Another way of expressing the definition is to say that a complete set of residues (mod m) is any set of m numbers, no two of which are congruent to one another.

A linear congruence, by analogy with a linear equation in elementary algebra, means a congruence of the form

$ax \equiv b {\pmod m}$ —- Note 2.

It is an important fact that any such congruence is soluble for x, provided that a is relatively prime to m. The simplest way of proving this is to observe that if x runs through the numbers of a complete set of residues, then the corresponding values of ax also constitute a complete set of residues. For there are m of these numbers, and no two of them are congruent, since $ax_{1} \equiv ax_{2} {\pmod m}$ would involve $x_{1} \equiv x_{2} {\pmod m}$ , by the cancellation of the factor a (permissible since a is relatively prime to m). Since the numbers ax form a complete set of residues, there will be exactly one of them congruent to the given number b.

As an example, consider the congruence $3x \equiv 5 {\pmod {11}}$ ,

If we give x the values 0, 1, 2, …, 10 (a complete set of residues to the modulus 11), 3x takes the values 0, 3, 6, …30. These form another complete set of residues (mod 11), and in fact, they are congruent respectively to

0, 3, 6, 9, 1, 4, 7, 10, 2, 5, 8.

The value 5 occurs when $x=9$ , and so $x=9$ is a solution of the congruence. Naturally, any number congruent to 9 (mod 11) will also satisfy the congruence; but, nevertheless, we say that the congruence has one solution, meaning that there is one solution in any complete set of residues. In other words, all solutions are mutually congruent. The same applies to the general congruence (Note 2); such a congruence (provided that a is relatively prime to m) is precisely equivalent to the congruence $x \equiv x_{0} {\pmod m}$ , where $x_{0}$ is one particular solution.

There is another way of looking at the linear congruence (in note 2). It is equivalent to the equation $ax = b + my$ , or $ax - my =b$ . It can be proved that such a linear diophantine equation is soluble for x and y if a and m are relatively prime, and that fact provides another proof of the existence of a solution of linear congruence. But, the proof given above is simpler, and illustrates the advant4ages gained by using the congruence notation.

The fact that the congruence (in note 2) has a unique solution, in the sense explained above, suggests that one may use this solution as an interpretation for the fraction $\frac{b}{a}$ to the modulus m. When we do this, we obtain an arithmetic (mod m) in which addition, subtraction and multiplication are always possible, and division is also possible if the divisor is relatively prime to m. In this arithmetic there are only a finite number of essentially distinct numbers, namely m of them, since two numbers which are mutually congruent (mod m) are treated as the same. If we take the modulus m to be 11, as an illustration, a few examples of “arithmetic mod 11” are :

$5 + 7 \equiv 1$ ; $5 \times 6 \equiv 8$ ; $\frac{5}{3} \equiv 9 \equiv -2$ .

Any relation connecting integers or fractions in the ordinary sense remains true when interpreted in this arithmetic. For example, the relation $\frac{1}{2} + \frac{2}{3} = \frac{7}{6}$

becomes (mod 11)

$6 + 8 \equiv 3$ ,

because the solution of $2x \equiv 1$ is $x \equiv 6$ , that of $3x \equiv 2$ is $x \equiv 8$ , and that of $6x \equiv 7$ is $x \equiv 3$ . Naturally the interpretation given to a fraction depends on the modulus, for instance $\frac{2}{3} = 8 {\pmod 11}$ , but $\frac{2}{3} \equiv 3 {\pmod 7}$ . The only limitation on such calculations is that just mentioned, namely that the denominator of any fraction must be relatively prime to the modulus. If the modulus is a prime (as in the above examples with 11), the limitation takes the very simple form that the denominator must not be congruent to 0 (mod m), and this is exactly analogous to the limitation in ordinary arithmetic that the denominator must not be equal to 0. We will say more about this later.