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.

Reference: The Higher Arithmetic, H. Davenport, 8th edition.

Shared for my students/readers who love to read expository articles….


Nalin Pithwa.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.