Congruences and their Properties

Section 4.2 Congruences and their Properties

Objectives

Define congruence modulo $n$ and show it is an equivalence relation.
Prove properties about congruence relations.

In part (d) of Checkpoint 4.1.6 you would have proven that $\equiv$ was an equivalence relation on the integers. This is an important relation that has several applications, so it is given a name.

Video: Congruence

Definition 4.2.1. Congruence.

Let $n$ be a natural number. We say that two integers $a$ and $b$ are congruent modulo $n$ if $n ∣ (a - b) .$ We denote this by writing

a \equiv b (\mod n) .

The number $n$ is called the modulus.

Example 4.2.2. Simple Example.

Since $6 \mid (55-13)\text{,}$ 55 and 13 are congruent modulo 6, and we write $55 \equiv 13 \Mod{6}\text{.}$

However $6 \nmid (30-11)$ so 30 and 11 are not congruent modulo 6, or $30 \not\equiv 11 \Mod{6}\text{.}$

Checkpoint 4.2.3. Congruent iff Same Remainder.

Show that two integers $a$ and $b$ are congruent modulo $n$ if and only if they have the same remainder when divided by $n\text{.}$

Hint

Use Theorem 1.3.2.

One real-life example is that of computing what day of the week it is, which uses congruence modulo $7 .$

week by Rohit Arun Rao from the Noun Project

Example 4.2.4. Days of the Week.

Modulo 7, the numbers 26 and 47 are congruent because $7 \mid (26-47)\text{.}$ This means 26 and 47 are ‘equivalent’ under this particular relation.

One way to see this is the fact that if today were Sunday, then 26 days from today it will be Friday, and 47 days from today is also a Friday. Abstracting only the property we care about (remainder when divided by 7) allows us to generate conclusions like this without having to manually count 47 days forward.

As another example, if today were Sunday, then we can confidently claim that 2020 days from today, it will be Thursday. This is because $2020 \equiv 4 \Mod{7}\text{,}$ and four days after Sunday is Thursday. (We've effectively removed as many 7's as possible to reduce the calculation.)

Checkpoint 4.2.5. New Relationship.

Today, two of your friends bought each other matching couple shirts to celebrate being in a relationship for 100 days. If today is Wednesday, what day did their relationship begin?

Definition 4.2.6. Congruence Class.

The equivalence classes of congruence modulo $n$ are called congruence classes or remainder classes, and they are the sets

Z_{n} = {[0], [1], [2], \dots, [n - 1]},

corresponding to the possible remainders when dividing by $n .$

Example 4.2.7. Modulo 5.

Modulo 5, the congruence classes are

\begin{align*} [0] \amp = \{\ldots,-10,-5,0,5,10,\ldots\}\\ [1] \amp = \{\ldots,-9,-4,1,6,11,\ldots\}\\ [2] \amp = \{\ldots,-8,-3,2,7,12,\ldots\}\\ [3] \amp = \{\ldots,-7,-2,3,8,13,\ldots\}\\ [4] \amp = \{\ldots,-6,-1,4,9,14,\ldots\} \end{align*}

Video: Properties of Congruence

Observe that if two numbers $a$ and $b$ are congruent modulo $n,$ then their difference $a - b$ is congruent to 0 modulo $n .$ This is because $a$ and $b$ are essentially the same when working modulo $n$ (the remainder is all that matters), so subtracting them will give ‘0’ in that framework.

We can perform addition and multiplication modulo $n$ as well.

Proposition 4.2.8. Modular Arithmetic.

Let $n$ be a natural number, and $a, b, r, s$ integers such that $a \equiv r (\mod n)$ and $b \equiv s (\mod n) .$ Then:

$a + b \equiv r + s (\mod n) .$
$a b \equiv r s (\mod n) .$
$a^{k} \equiv r^{k} (\mod n)$ for any $k \in N .$

Checkpoint 4.2.9. Prove Proposition 4.2.8.

Prove Proposition 4.2.8, using the definition of congruence.

Importantly, Proposition 4.2.8 implies that in any congruence, we can replace any number with another number it is congruent to, and obtain an equivalent statement.

Example 4.2.10. Substituting Congruent Numbers.

Suppose we wanted to compute the remainder when 4133 is divided by 4. We first write $4133 = 4000 + 100 + 30 + 3\text{,}$ so that

\begin{equation*} 4000 + 100 + 30 + 3 \equiv 0 + 0 + 2 + 3 \Mod{4} \equiv 1 \Mod{4}\text{.} \end{equation*}

Hence the remainder when $4133$ is divided by $4$ is $1\text{.}$

Checkpoint 4.2.11. Modulo 9.

Show that an integer is congruent to the sum of its digits modulo 9.

Hint

The integer $a_ka_{k-1}\cdots a_2 a_1 a_0$ can be expressed as $a_k\left(10^k\right) + a_{k-1}\left(10^{k-1}\right) + \cdots + a_1(10) + a_0\text{.}$

Definition 4.2.12. The Modulo Operation.

Given two integers $a$ and $n,$ with $n \neq 0,$ the modulo operation denoted by

a \mod n,

read as $a$ modulo $n$ , is the remainder obtained from Theorem 1.3.2 when $a$ is divided by $n .$

Checkpoint 4.2.13. Compute Remainders.

Compute the following:

$\displaystyle 2139138 \mmod 9$
$\displaystyle 2^{1000} \mmod 7$
$\displaystyle 10! \mmod 17$

While Proposition 4.2.8 allows us to perform addition, subtraction and multiplication, when we try dividing we find that we run into some issues.

Example 4.2.14. Division is not as Nice.

We know that

\begin{equation*} 39 \equiv 123 \Mod{12}\text{.} \end{equation*}

If we divide both sides by 3, we would get

\begin{equation*} 13 \equiv 41 \Mod{12}\text{,} \end{equation*}

which is false. However $13 \equiv 41 \Mod{4}$ is true.

Proposition 4.2.15. Dividing both sides of a Congruence.

Let $n \in N$ and $a, b, d \in Z .$ If $a d \equiv b d (\mod n),$ then

a \equiv b (\mod \frac{n}{gcd (d, n)}) .

If $d$ and $n$ are relatively prime, then $a d \equiv b d (\mod n)$ implies

a \equiv b (\mod n) .

Proof.

Suppose that $ad \equiv bd \Mod{n}\text{.}$ This means $ad = bd + kn$ for some $k \in \mathbb{Z}\text{.}$

Since $\gcd(d,n)$ divides both $d$ and $n\text{,}$ we can divide through to get

\begin{equation*} a\cdot \dfrac{d}{\gcd(d,n)} = b\cdot \dfrac{d}{\gcd(d,n)} + k \cdot\dfrac{n}{\gcd(d,n)}\text{.} \end{equation*}

This is equivalent to

\begin{equation*} \dfrac{n}{\gcd(d,n)} \ \Biggl\vert \ (a-b)\left(\dfrac{d}{\gcd(d,n)}\right)\text{.} \end{equation*}

Since $\gcd\left(\dfrac{d}{\gcd(d,n)},\dfrac{n}{\gcd(d,n)}\right) = 1\text{,}$ we can apply the result of Checkpoint 1.3.13 to obtain

\begin{equation*} \dfrac{n}{\gcd(d,n)} \ \Biggl\vert \ (a-b)\text{,} \end{equation*}

or that $a \equiv b \Mod{\dfrac{n}{\gcd(d,n)}}\text{,}$ as desired.

If $\gcd(d,n) = 1\text{,}$ the statement reduces to $a \equiv b \Mod{n}\text{.}$

Checkpoint 4.2.16. Justify It.

Explain why

\begin{equation*} \gcd\left(\dfrac{d}{\gcd(d,n)},\dfrac{n}{\gcd(d,n)}\right) = 1 \end{equation*}

in the proof of Proposition 4.2.15.

Hint

Contradiction.

The second statement of Proposition 4.2.15 is also called the cancellation law, since it gives a condition under which one can divide both sides of a congruence by a number.