Congruences

Prerequisites: Divisibility, Division with remainder

Definition (congruence modulo )

Let , . We will say that and are congruent modulo if and give the same remainder when divided by . The notation is

Theorem (basic congruence properties)

\begin{cases} a_{1}\equiv a_{2} ~(\operatorname{mod} m) \ b_{1}\equiv b_{2} ~(\operatorname{mod} m) \end{cases} \implies a_{1}+b_{1} \equiv a_{2}+b_{2} ~(\operatorname{mod} m)

\begin{cases} a_{1}\equiv a_{2} ~(\operatorname{mod} m) \ b_{1}\equiv b_{2} ~(\operatorname{mod} m) \end{cases} \implies a_{1}b_{1} \equiv a_{2}b_{2} ~(\operatorname{mod} m)

Insight

Think of property (1) as a translation from the language of remainders to the language of divisibility. Most statements about congruences can be solved either by directly manipulating remainders or by translating them into divisibility statements.

Proof of property (1)

• Let us first show . If , then let and where and . Then

By definition, it follows that .

• Now let us show . If , then for some . Divide and by to get and where and . Then

By the division with remainder theorem there is a unique way to divide a number with remainder. But we already have which satisfies the restrictions imposed on division with remainder. Therefore,

Then , which, by definition, means that .

Proof of property (2)

Let us assume that and . Using property (1), this is equivalent to and . Then, using properties of divisibility, we get that . Reorganize the summands to get . Translating back using property (1) we get the desired .

Exercise

Prove property (2) by explicitly dividing by with remainder and using the definition of congruences itself. Apply it to specific examples to get a better understanding.

Comment

It is important to mention that the proposed proof of property (3) is not essentially any different from the shorter “nicer” proof of (2): it is more “down to the ground”, but you are actually using the exact same statements hidden behind remainder comparison.

Proof of property (3)

We will perform a direct proof using remainders here to illustrate the point about translating between remainders and divisibility. Let us assume that and . This means that , , , and (the subscript notations are just for clarity, as labeling them just as, say, would cause more confusion in the process) with the usual restrictions on quotients and remainders. Then

One would be tempted to say that is then the remainder of dividing by , but this is actually not always true as could have “overshot” over the admissible limit . However, we can say at least that and have the same remainder when divided by (this is essentially the "" proof of (1), but without using the word “congruence”). Similarly, one can show that and have the same remainder when divided by . But we have and because of the given congruences, so

Therefore, .

Exercise

Prove property (3) using the property (1) translation to divisibility and properties of divisibility.