# Congruence Theorems (and Their Proofs)

We discuss congruence theorems on the integers by proving several elementary lemmas. Modular arithmetic and least positive residues is also discussed.

## Introduction to Congruence Theorems

A modern treatment of congruences was introduced by Carl Friedrich Gauss. Congruence, or modular arithmetic, arises naturally in common everyday situations. For example, odometers usually work modulo 100,000 and utility meters often operate modulo 1000. In trigonometry, it is common to work in degrees, that is modulo 360 degrees, and indeed, it is common to work in minutes and seconds both of which are working modulo 60.

Definition. Let $n$ be a positive integer. Integers $a$ and $b$ are congruent modulo $n$ if $a-b$ is divisible by $n$ and is denoted by $a \equiv b \pmod{n}.$

Notice $24\equiv 4 \pmod{5}$ since $5$ divides $(24-4)$ but $24\equiv 3 \pmod{5}$ is not true since $5$ doe snot divide $(24-3).$ Also, $111\equiv 9 \pmod{40}$ since $40|(111-9)$ and $111\equiv 8 \pmod{40}$ is not true since $40$ does not divide $(111-8).$

## Congruence is an Equivalence Relation

Next we show that congruence modulo $n$ is an equivalence relation on the set of integers.

Theorem. For each positive integer $n$, congruence modulo $n$ is an equivalence relation on the set of integers.

Proof. If $a$ is an integer, then $a\equiv a \pmod{n}$ since $n|(a-a)$ and so $\equiv$ is reflexive. If $a$ and $b$ are integers and $a\equiv b \pmod{n},$ then $b\equiv a \pmod{n}$ since $$n|(b-a) \Longleftrightarrow n|(a-b)$$ and so the relation $\equiv$ is symmetric. Finally, if $a, b$ and $c$ are integers, $a\equiv b \pmod{n},$ and $b\equiv c \pmod{n},$ then $a\equiv c \pmod{n}$ because $n|(b-a)$ and $n|(c-b)$ implies $n|(a-c)$ and so the relation $\equiv$ is also transitive.

## Congruence Characterization

The next theorem states that if two integers are congruence modulo $n$, then their difference is a multiple of $n$.

Theorem. If $a$ and $b$ are integers, then $a\equiv b\pmod{n}$ if and only if there exists an integer $k$ such that $a=b+k n.$

Proof. If $a\equiv b \pmod{n},$ then $n|(a-b)$ and this means there exists an integer $k$ such that $k n=a-b$ and so $a=b+k n.$ Conversely, if there is an integer $k$ such that $a=b+k n,$ then $n|(a-b)$; and so $a\equiv b \pmod{n}.$

Lemma. For all integers $a$, $b$, $c$, and $d$, if $a\equiv c \pmod{n}$ and $b\equiv d \pmod{n},$ then $a\pm b\equiv c\pm d \pmod{n}$ and $a b\equiv c d \pmod{n}.$

Proof. If $a\equiv c \pmod{n}$ and $b\equiv d \pmod{n},$ then $n|a-c$ and $n|b-d.$ It follows that, $n|(a\pm b)-(c\pm d)$ and thus $a\pm b\equiv c\pm d \pmod{n}.$ It also follows that, $n|(a b-c b)$ and $n|(c b-c d);$ thus $n|(a b-c d).$ Therefore, $a b\equiv c d \pmod{n}.$

## Congruence Lemmas

From above know that congruence is an equivalence relations. The next two lemmas state that congruence is compatible with addition and multiplication. These lemmas are important for additional congruence theorems later.

Lemma. For all integers $a$, $c$, and $d$, if $a+c\equiv a+d \pmod{n},$ then $c\equiv d \pmod{n}.$

Proof. If $a+c\equiv a+d \pmod{n},$ then $n|(a+c)-(a+d)$ and so $n|c-d$ which means $c\equiv d \pmod{n}.$

Lemma. For all integers $a$, $c$, and $d$, if $a c\equiv a d \pmod{n}$ and $(a,n)=1,$ then $c\equiv d \pmod{n}.$

Proof. If $a c\equiv a d \pmod{n},$ then $n|(a c-a d)$ which means $n|a(c-d).$ Since $(a,n)=1,$ it follow that $n|(c-d)$ and so $c\equiv d \pmod{n}.$

Lemma. For all integers $a$, there exists an integer $h$ such that $a h\equiv 1 \pmod{n}$ if and only if $(a,n)=1.$

Proof. If $(a,n)=1,$ then there exists integers $s$ and $t$ such that $s a+t n=1.$ Let $h=s,$ then $a h\equiv 1 \pmod{n}$ as desired. Conversely, if there is such a $h$ then $a h=1+q n$ for some $q.$ Thus, $a h+(-q) n=1$ and so $(a,n)=1.$

Lemma. For all integers $a$, $b$, and $c$, if $a c\equiv b c \pmod{n},$ then $a\equiv b \pmod{n/(c,n)}.$

Proof. If $a c\equiv b c \pmod{n},$ we know that $n|(a c-b c)=c(a-b).$ Thus there exists an integer $k$ such that $c(a-b)=k n$ and dividing both sides by $d=(c,n),$ we have $(c/d)(a-b)=k(n/d).$ Because $(n/d,c/d)=1$ it follows that $(n/d)|(a-b).$ Therefore, $a\equiv b \pmod{n/(c,n)}.$

Lemma. For all integers $a$ and $b$, if $k,n>0$ and $a\equiv b \pmod{n},$ then $a^k\equiv b^k \pmod{n}.$

Proof. Because $a\equiv b \pmod{n}$ we have by definition, $n|(a-b)$ and since $$a^k-b^k=(a-b)\left(a^{k-1}+a^{k-2}b+\cdot \cdot \cdot +a b^{k-2}+b^{k-1}\right)$$ we see that $(a-b)\left|\left(a^k-b^k\right)\right.;$ whence $n\left|\left(a^k-b^k\right).\right.$ Therefore, $a^k\equiv b^k \pmod{n}.$

## Least Positive Residues

Definition. Given a modulus $n$ and an integer $a$ the least positive residue of $a$ modulo $n$ is the smallest positive integer $r$ such that $a\equiv r \pmod{n}.$

For example, the remainder of $n$ when divided by 9 is the same as the remainder of the sum of its digits when divided by 9 which follows from writing $$n = d_t10^t+d_{t-1}10^{t-1}+ \cdots +d_110+d_0$$ where $0\leq d_i\leq 9$ by noting that $10^k\equiv 1 \pmod{9}$ for any $k.$ Notice also that the remainder of $n$ when divided by 11 is the same as the remainder of the alternating sum of its digits when divided by 11 which follows from writing $n$ in decimal form and noting that $10^k\equiv (-1)^k \pmod{11}$ for any $k.$

## Modular Arithmetic

Let $\{0,1,2, \ldots ,n-1\}$ be a complete set of equivalence class representatives on $\mathbb{Z}$ for congruence modulo $n,$ then define $$\mathbb{Z}_n\text{:=}\{,,, \ldots ,[n-1]\}$$ and prescribe the operation $+$ on $\mathbb{Z}_n$ by $[a]+[b] = [a+b].$ Arithmetic using this operation is referred to as modular arithmetic.

The operation $+$ is a well-defined binary operation; meaning, if $[a]=[b]$ and $[c]=[d]$ in $\mathbb{Z}_n$, then $$[a] +[b]=[a+b]=[c+d]=[c]+[d]$$ which follows from $a\equiv b \pmod{n}$ and $c\equiv d \pmod{n} \Rightarrow a+c\equiv b+d \pmod{n}.$

For example, the arithmetic tables for $\mathbb{Z}_{6}$ are
\begin{equation*}
\begin{array}{c|cccccc}
& 0 & 1 & 2 & 3 & 4 & 5 \\ \hline
0 & 0 & 1 & 2 & 3 & 4 & 5 \\
1 & 1 & 2 & 3 & 4 & 5 & 0 \\
2 & 2 & 3 & 4 & 5 & 0 & 1 \\
3 & 3 & 4 & 5 & 0 & 1 & 2 \\
4 & 4 & 5 & 0 & 1 & 2 & 3 \\
5 & 5 & 0 & 1 & 2 & 3 & 4
\end{array}
\end{equation*} \begin{equation*}
\begin{array}{c|cccccc}
\times & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline
0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 2 & 3 & 4 & 5 \\
2 & 0 & 2 & 4 & 0 & 2 & 4 \\
3 & 0 & 3 & 0 & 4 & 1 & 2 \\
4 & 0 & 4 & 2 & 0 & 1 & 2 \\
5 & 0 & 5 & 4 & 3 & 2 & 1
\end{array}
\end{equation*}

## Properties of Modular Arithmetic

Here are a few more important congruence theorems.

Theorem. Let $n$ be a positive integer, then $+$ is associative and commutative, each element has an inverse, and $$ is the identity element.

Proof. By the definition of $+$ and the use of associativity in the integers, it follows that \begin{align*} [a]+([b]+[c])& =[a]+[b+c] =[a+(b+c)]=[(a+b)+c] \\ &=[a+b]+[c]=([a]+[b])+[c] \end{align*} for any $[a],$ $[b],$ and $[c]\in \mathbb{Z}_n.$ The element $$ is the identity because $$[a] +=[a+0] [a]$$ for any $[a]\in \mathbb{Z}_n.$ For every element $[a]$ of $\mathbb{Z}_n$ there is an inverse because $$[a] +[-a] =[a+(-a)]=$$ and indeed $[-a]\in \mathbb{Z}_n.$ Commutativity follows since $$[a]+[b]=[a+b]=[b+a]=[b]+[a]$$ for $[a]$, $[b]\in \mathbb{Z}_n.$

Theorem. Let $n$ be a positive integer. Then $\{0,1,2, \ldots ,n-1\}$ is complete set of equivalence class representatives on $\mathbb{Z}$ for congruence modulo $n$.

Proof. Given an integer $x,$ the Division Algorithm yields unique integers $q$ and $r$ such that $x=n q+r$ and $0\leq r<n.$ Then $x\equiv r \pmod{n}$ and so $x$ is congruent to at least one of ${0,1,2,\text{..},n-1}.$ In fact $r$ is unique because otherwise, say $x\equiv s \pmod{n}$ and $x=n t+s$ with $0\leq s<n$ for some $t,$ would contradict the uniqueness of the Division Algorithm.

## Exercises on Congruence Theorems

Exercise. Show that each of the following congruences hold.

$(1) \quad 13\equiv 1 \pmod{2}$

$(2) \quad -2\equiv 1 \pmod{3}$

$(3) \quad 22\equiv 7 \pmod{5}$

$(4) \quad -3\equiv 30 \pmod{11}$

$(5) \quad 91\equiv 0 \pmod{13}$

$(6) \quad 111\equiv -9 \pmod{40}$

$(7) \quad 69\equiv 62 \pmod{7}$

$(8) \quad 666\equiv 0 \pmod{37}$

$(9) \quad 166\equiv 13 \pmod{17}$

Exercise. Determine whether each of the following pairs of integers is congruent modulo 7.

$(1) \quad 1,15$

$(2) \quad -1,8$

$(3) \quad 0,42$

$(4) \quad -9,5$

$(5) \quad 2,99$

$(6) \quad -1,699$

Exercise. Show that if $a$ is an even integer, then $a^2\equiv 0 \pmod{4},$ and if $a$ is an odd integer then $a^2\equiv 1 \pmod{4}.$

Exercise. Show that if $a$ is an odd integer, then $a^2\equiv 1 \pmod{8}.$

Exercise. Show that if $a, b, m,$ and $n$ are integers such that $m>0,$ $n>0,$ $n|m,$ and $a\equiv b \pmod{m},$ then $a\equiv b \pmod{n}.$

Exercise. Show that if $a, b, c,$ and $m$ are integers such that $c>0,$ $m>0,$ and $a\equiv b \pmod{m},$ then $a c\equiv b c \pmod{m c}.$

## Additional Exercises on Congruence Theorems

Exercise. Show that if $a, b,$ and $c$ are integers such that $c>0,$ such that $a\equiv b \pmod{c},$ then $(a,c)=(b,c).$

Exercise. Find the least positive residue of $1!+2!+3!+\cdots +100!$ modulo each of the following integers.

$(1) \quad 2$

$(2) \quad 12$

$(3) \quad 7$

$(4) \quad 25$

Exercise. Find the least residue of $a$ modulo $n.$

$(1) \quad a=1348, n=45$

$(2) \quad a=341123, n=234$

$(3) \quad a=809834, n=112$

$(4) \quad a=20934, n=29$

$(5) \quad a=20034, n=23$

$(6) \quad a=3407, n=128$

$(7) \quad a=29976, n=134$

$(8) \quad a=34534, n=93$

$(9) \quad a=345996, n=238$

$(10) \quad a=88629, n=34$

$(11) \quad a=929001, n=222$

$(12) \quad a=987559, n=367$

Exercise. Construct tables for addition modulo 8, subtraction modulo 8, and multiplication modulo 8.

Exercise. What can you conclude if $a^2\equiv b^2 \pmod{p},$ where $a$ and $b$ are integers and $p$ is prime?

Exercise. Show that if $n$ is odd positive integer, then $1+2+3+\cdots +(n-1)\equiv 0 \pmod{n}.$

Exercise. Show by mathematical induction that if $n$ is a positive integer, then $4^n\equiv 1+3n \pmod{9}.$

Exercise. Show by mathematical induction that if $n$ is a positive integer, then $5^n\equiv 1+4n \pmod{16}.$

Exercise. Determine which of the following are true:

$(1) \quad 7\equiv -34 \pmod{9}$

$(2) \quad -50\equiv 2 \pmod{13}$

$(3) \quad 17\equiv 62 \pmod{90}$

$(4) \quad -73\equiv -29 \pmod{128}$

Exercise. Find the least residue of $b$ modulo $m$ given:

$(1) \quad m=41,522;$ $b=-16,115$

$(2) \quad m=91,631;$ $b=-2152$

$(3) \quad m=63;$ $b=752\cdot 571$

$(4) \quad m=51;$ $b=414\cdot 566$

Exercise. What is the least residue of $100^6$ modulo $49?$ What is the least residue of $49^4$ modulo $23?$

## More Exercises on Congruence Theorems

Exercise. Show that the following statements are true or determine if they are false by providing a counterexample.

(1) If $a\equiv b \pmod{n}$ and $m|n$ then $a\equiv b \pmod{m}.$

(2) If $a\equiv b \pmod{n}$ and $c>0,$ then $c a\equiv c b \pmod{c n}.$

(3) If $a\equiv b \pmod{n}$ and the integers $a, b,n$ are divisible by $d>0,$ then $a/d\equiv b/d \pmod{n/d}.$

(4) If $a^2\equiv b^2 \pmod{n}$ then $a\equiv b \pmod{n}.$

(5) If $a\equiv b \pmod{n}$ then $(a,n)=(b,n).$

Exercise. Show that $53^{103}+103^{53}$ is divisible by $39$.

Exercise. Show that $111^{333}+333^{111}$ is divisible by $7$.

Exercise. Show by mathematical induction that if $n$ is a positive integer, then $5^n\equiv 1+4n \pmod{16}$.

Exercise. What can you conclude if $a^2\equiv b^2 \pmod{p}$, where $a$ and $b$ are integers and $p$ is prime?

Exercise. Show that if $n$ is an odd positive integer, then $1+2+3+\cdots +(n-1)\equiv 0 \pmod{n}.$ Is this statement true if $n$ is even?

Exercise. Show that if $n$ is an odd integer or if $n$ is a positive integer divisible by $4$, then $$1^3+2^3+3^3+\cdots +(n-1)^3\equiv 0 \pmod{n}.$$ Is this statement true if $n$ is not divisible by $4$?

Exercise. For which positive integers $n$ is it true that $$1^2+2^2+3^2+\cdots +(n-1)^2\equiv 0 \pmod{n}.$$

Exercise. Construct the multiplication and addition tables for modular arithmetic for $n=6.$

Exercise. Prove that if $a\equiv b (\text{mod} m)$ then $a^k\equiv b^k (\text{mod} m)$ for every positive integer $k.$