Theorem 1 (Fermat’s Little Theorem). Let $p$ be a prime. Then for any integer $a$, $$a^p\equiv a\mod p$$ and for any integer $a$ not divisible by $p$,
$$a^{p-1}\equiv 1\mod
p.$$

Proof. We prove the second statement first. Suppose that $p\not| a$. If
$i\equiv j\mod p$ then clearly $ai\equiv aj\mod p$. Conversely, if
$ai\equiv aj\mod p$ then $$p|ai-aj=a(i-j).$$ Since $(a,p)=1$, $p|i-j$, i.e., $i\equiv j\mod p$. So, $0a,1a,2a,\cdots,(p-1)a$ are a complete set of residues $\mod p$, that is, they are rearrangement of $0,1,2,\cdots,p-1$ when considered $\mod p$. Hence, $$(p-1)!a^{p-1}\equiv(p-1)!\mod p,$$
i.e., $p|(p-1)!(a^{p-1}-1)$. Since $p\not|(p-1)!$ then $p|a^{p-1}-1$, i.e., $$a^{p-1}\equiv 1\mod p.$$ If $a$ is divisible by $p$, then clearly
$$a^p\equiv a\mod p$$ since either side is congruent to $0\mod p$.

Corollary 2. If $p\not| a$ and if $n\equiv m\mod p-1$ then $$a^n\equiv a^m\mod p.$$

Proof. Say $n>m$. Since $n\equiv m\mod p-1$, $$n=m+(p-1)c$$ for some $c\in\mathbb{Z}$. By Fermat’s Little Theorem (Theorem 1),
$$a^{p-1}\equiv 1\mod p$$ and so
$$a^{c(p-1)}\equiv 1\mod p\Longrightarrow a^n=a^{m+(p-1)c}\equiv a^m\mod p.$$

Example. Find the last base-$7$ digit in $2^{1000000}$.

Solution: Let $p=7$. Since $1000000$ leaves a remainder of $4$ when divided by $p-1=6$, $$1000000\equiv 4\mod 6=7-1$$ and $7\not|2$. By Corollary 2, $$2^{1000000}\equiv 2^4=16\equiv 2\mod 7.$$
Thus, $2$ is the answer.

Lemma 3. If $a\equiv b\mod m$, $a\equiv b\mod n$, and
$(m,n)=1$, then $a\equiv b\mod mn$.

Proof. Since $a\equiv b\mod m$, $b-a=md$ for some $d\in\mathbb{Z}$.
\begin{align*} a\equiv b\mod n&\Longrightarrow n|md\\ &\Longrightarrow n|d\ \mbox{since}\ (m,n)=1\\ &\Longrightarrow d=ns\ \mbox{for some}\ s\in\mathbb{Z}\\ &\Longrightarrow b-a=mns\\ &\Longrightarrow a\equiv b\mod mn. \end{align*}

Definition (Euler phi function).
For any positive integer $n$, $\phi(n)$ is defined to be the number
of integers $a$, $1\leq a\leq n$, such that $(a,n)=1$. The function
$\phi$ is called the Euler phi function.

Example. $\phi(1)=1$ by definition.

To calculate $\phi(6)$, we write all positive integers that are
less than or equal to $6$ and then cross out the ones that are not
relatively prime to $6$. Counting the remaining numbers will give
$\phi(6)$: $$1,\not 2,\not 3,\not 4,5,\not 6.$$ Hence, $\phi(6)=2$.

Since $7$ is a prime number, any positive integer that are less than
$7$ are relatively prime to $7$, so $\phi(7)=6$. In general, if $p$
is a prime number then \begin{equation}\label{eq:phiprime} \phi(p)=p-1.\end{equation}

In order to calculate $\phi(12)$, we write $$1,\not 2,\not 3,\not 4,5,\not 6,7,\not 8,\not 9,\not 10,11,\not 12$$ Thus, $\phi(12)=4$.

As one can easily imagine, if a number $n$ gets bigger, computing
$\phi(n)$ will become really a hardship.

The following theorem provides a short cut to computing $\phi(n)$.

Theorem 4. If $k$ and $a$ are positive integers such that all primes dividing
$k$ also divide $a$, then \begin{equation}\label{eq:phi}\phi(ka)=k\phi(a).\end{equation}

Proof. We first write all positive integers that are less than or equal to $ka$: $$\begin{array}{cccc}
1 & 2 & \cdots & a\\a+1 & a+2 & \cdots & 2a\\& & \vdots &\\(k-1)a+1 & (k-1)a+2 & \cdots & ka\end{array}$$ and then cross out the entries that are not relatively prime to $ka$. It is easy to see that this amounts to crossing out everything not relatively prime to $a$. Clearly, any prime that divides $a$ divides $ka$. Conversely, if a prime divides $ka$, then it divides $k$ or $a$. If the prime divides $k$ then by the assumption, it divides $a$ as well. By Theorem 5 here, the pattern of crossing out is the same in each row. Since there are $\phi(a)$ entries left in the first row, there must be $k\phi(a)$ entries left in all. So, $$\phi(ka)=k\phi(a).$$

It would be also interesting to study the relationship between $\phi(pa)$ and $\phi(a)$ when $p\not|a$. First note that if $(a,n)>1$ then clearly $(pa,n)>1$ but the converse need not be true. If a prime number $q>1$ divides $pa$ then $q|p$ or $q|a$. If $q|p$ then $q=p$. That is, if $(pa,n)>1$ then $p|n$ or $(a,n)>1$. After crossing out all $n$ such that $(a,n)>1$, $p\phi(a)$ integers left and yet more to be eliminated, namely, the multiples of $p$, $1p,2p,\cdots,ap$. Of these, those $kp$ such that $(k,a)>1$ have
already been eliminated, and there are just $\phi(a)$ more to cross out. Thus, \begin{align*} \phi(pa)&=p\phi(a)-\phi(a)\\ &=(p-1)\phi(a). \end{align*} Hence, we proved the following theorem.

Theorem 5. Let $a$ be a positive integer and $p$ a prime such that $p\not|a$. Then \begin{equation}\label{eq:phi2}\phi(pa)=(p-1)\phi(a).\end{equation}

Example. \begin{align*} \phi(10^6)&=\phi(10^5\cdot 10)\\ &=10^5\phi(10)\ \mbox{by \eqref{eq:phi}}\\ &=10^5\phi(2\cdot 5)\\ &=10^5(2-1)\phi(5)\ \mbox{by \eqref{eq:phi2}}\\ &=10^5\cdot 4 \ \mbox{by \eqref{eq:phiprime}}\\&=400,000.\\\phi(60)&=\phi(2^2\cdot 3\cdot 5)\\ &=2\phi(2\cdot 3\cdot 5) \ \mbox{by \eqref{eq:phi}}\\ &=2\cdot(2-1)\phi(3\cdot 5) \ \mbox{by \eqref{eq:phi2}}\\ &=2(3-1)\phi(5)\ \mbox{by \eqref{eq:phi2}}\\ &=16 \ \mbox{by \eqref{eq:phiprime}}.\\ \phi(62)&=\phi(2\cdot 31)\\ &=(2-1)\phi(31)\ \mbox{by \eqref{eq:phi2}}\\ &=30\ \mbox{by \eqref{eq:phiprime}}. \end{align*}

Theorem 6. Let $p$ be a prime and $\alpha$ a positive integer. Then
\begin{equation}\label{eq:phiprime2}\phi(p^\alpha)=p^\alpha\left(1-\frac{1}{p}\right).\end{equation}

Proof. It follows immediately from \eqref{eq:phi} and \eqref{eq:phiprime}.\begin{align*}\phi(p^\alpha)&=p\phi(p^{\alpha-1})\\ &=p^2\phi(p^{\alpha-2})\\ &=\cdots\\ &=p^{\alpha-1}\phi(p)\\ &=p^{\alpha-1}(p-1)\\ &=p^{\alpha}\left(1-\frac{1}{p}\right). \end{align*}

Theorem 7 (Chinese Remainder Theorem) Suppose that we want to solve a system of congruences to different moduli: \begin{equation}\begin{aligned}x&\equiv a_1\mod m_1,\\x&\equiv a_2\mod m_2,\\&\cdots\ \ \ \ \ \cdots\\x&\equiv a_r\mod m_r.\end{aligned}\label{eq:congsys}\end{equation}
Suppose that each pair of moduli is relatively prime: $(m_i,m_j)=1$ for $i\ne j$. Then there exists a simultaneous solution $x$ to all of the congruences, and any two solutions are congruent to one another modulo $M=m_1m_2\cdots m_r$.

Proof. First we prove uniqueness modulo $M$. Suppose that $x’$ and $x^{\prime\prime}$
are two solutions to the system of congruences \eqref{eq:congsys}. Let $x=x’-x^{\prime\prime}$. Then for all $i=1,\cdots,r$,\begin{align*}x’&\equiv a_i\mod m_i,\\ x^{\prime\prime}&\equiv a_i\mod m_i.\end{align*}This implies that \begin{align*} x=x’-x^{\prime\prime}\equiv 0\mod m_i&\Longrightarrow x\equiv 0\mod M\ \mbox{by Lemma 3}\\&\Longrightarrow x’\equiv x^{\prime\prime}\mod M. \end{align*} We now show how to construct a solution $x$. For each $i=1,\cdots,r$, define $M_i:=M/m_i$. Then $(m_i,M_i)=1$, so by Bézout’s Lemma there exist $y,z\in\mathbb{Z}$ such that $$M_iy+m_iz=1.$$ This implies that $$M_iy\equiv 1\mod m_i.$$ Write $y:=N_i$, i.e., $$M_iN_i\equiv 1\mod m_i.$$ Set $$x:=\sum_{i=1}^ra_iM_iN_i.$$ Since $m_i|M_j$ whenever $i\ne j$, $$x\equiv a_iM_iN_i\equiv a_i\mod m_i.$$

The reason Theorem 7 is called the Chinese Remainder Theorem is that its oldest reference was found in a 3rd century AD (Tang Dynasty) Chinese math book called Sunzi Suanjing (孫子算經). The book title’s literal translation is Master Sun’s Book of Arithmetic. Not much is know for the author Sunzi or Sun Tzu (孫子) but one thing for sure is he is not the same person as the famous Chinese military strategist who was the author of The Art of War. In the book Sunzi Suanjing, the following question is mentioned: “Han Xing asks how many soldiers are in his army. If you let them parade in 3 rows of soldiers, 2 soldiers will be left. If you let them parade in 5 rows of soldiers, 3 will be left. And in 7 rows of soldiers, 2 will be left. How many soldiers are there?” This question can be formulated as solving a system of linear congruences in the following example.

Example. Solve the system of linear congruences \begin{align*}x&\equiv 2\mod 3\\x&\equiv 3\mod 5\\x&\equiv 2\mod 7\end{align*}

Solution. Let $m_1=3$, $m_2=5$, and $m_3=7$. Let $M=m_1m_2m_3=105$ and \begin{align*}M_1&=\frac{M}{m_1}=35\\M_2&=\frac{M}{m_2}=21\\M_3&=\frac{M}{m_3}=15\end{align*} Since $(M_i,m_i)=1$, $M_iy_i+m_iz_i=1$ has a solution for each $i=1,2,3$. They can be found as $y_1=-1$, $y_2=y_3=1$. Let $N_i=y_i$ for each $i=1,2,3$ and $a_1=2$, $a_2=3$, and $a_3=2$. Then $x=\sum_ia_iM_iN_i=23$ is a solution to the system and the general solution is $x=23+105k$. This does not answer Han Xing’s question. His army could have had as little as 23 or as large as 128,233,373 (for $k=1221270$) or more.

Corollary 8. The Euler phi function is multiplicative, i.e., $$\phi(mn)=\phi(m)\phi(n)$$ whenever $(m,n)=1$.

Proof. We must count the number of integers between $0$ and $mn-1$ which have no common factor with $mn$. For each $0\leq j\leq mn-1$, let $j_1$ be its least nonnegative residue$\mod m$ (i.e., $0\leq j_1<m$ and $j\equiv j_1\mod m$) and $j_2$ be its least nonnegative residue$\mod n$ (i.e., $0\leq j_2<n$ and $j\equiv j_2\mod n$). It follows from the Chinese Remainder Theorem (Theorem 7) that for each pair $j_1,j_2$ there is one and only one $j$ between $0$ and $mn-1$ for which $$j\equiv j_1\mod m,\ j\equiv j_2\mod n.$$ Notice that $j$ has no common factor with $mn$ if and only if it has no common factor with $m$ (which is equivalent to $j_1$ having no common factor with $m$) and $j$ has no common factor with $n$ (which is equivalent to $j_2$ having no common factor with $n$). Thus, the $j$’s which we must count are in $1:1$ correspondence with the pairs $j_1,j_2$ for which $$0\leq j_1<m,\ (j_1,m)=1;\ 0\leq j_2<n,(j_2,n)=1.$$ The number of possible $j_1$’s is $\phi(m)$ and the number of possible $j_2$’s is $\phi(n)$. So, the number of pairs is $\phi(m)\phi(n)$.

Corollary 9. For any positive integer $n$,\begin{equation}\phi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right).\end{equation}

Proof. Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$ be the prime factorization of $n$. Then by Corollary 8, \begin{align*}\phi(n)&=\phi(p_1^{\alpha_1})\phi(p_2^{\alpha_2})\cdots\phi(p_r^{\alpha_r})\\ &=p_1^{\alpha_1}\left(1-\frac{1}{p_1}\right)p_2^{\alpha_2}\left(1-\frac{1}{p_2}\right)\cdots p_r^{\alpha_r}\left(1-\frac{1}{p_r}\right)\ \mbox{by \eqref{eq:phiprime2}}\\&=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_r}\right)\\&=n\prod_{p|n}\left(1-\frac{1}{p}\right).\end{align*}

Example. \begin{align*}\phi(60)&=\phi(2^2\cdot 3\cdot 5)\\&=60\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\\&=16.\\\phi(62)&=\phi(2\cdot 31)\\ &=62\left(1-\frac{1}{2}\right)\left(1-\frac{1}{31}\right)\\&=30.\\\phi(360)&=\phi(2^3\cdot 3^2\cdot 5)\\&=360\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\\&=96.\end{align*}

The following theorem is a generalization of Fermat’s Little Theorem
(Theorem 1) due to Euler.

Theorem 10 (Euler-Fermat Theorem). If $(a,m)=1$ then \begin{equation}\label{eq:euler} a^{\phi(m)}\equiv 1\mod m.\end{equation}

Proof. First consider the case when $m$ is a prime power, say $m=p^\alpha$.
We use induction on $\alpha$. The case $\alpha=1$ is precisely Fermat’s Little Theorem. Suppose that $\alpha\geq 2$ and the formula
\eqref{eq:euler} holds for the $(\alpha-1)$-st power of $p$. Then \begin{align*} \phi(p^{\alpha-1})&=p^{\alpha-1}\left(1-\frac{1}{p}\right)\\&=p^{\alpha-1}-p^{\alpha-2}\end{align*} and \begin{align*}a^{\phi(p^{\alpha-1})}&=a^{p^{\alpha-1}-p^{\alpha-2}}\\&\equiv 1\mod p^{\alpha-1}.\end{align*} That is,
$$a^{p^{\alpha-1}-p^{\alpha-2}}=1+p^{\alpha-1}b\ \mbox{for some}\ b\in\mathbb{Z}.$$ Thus, \begin{align*}a^{\phi(p^\alpha)}&=(a^{p^{\alpha-1}-p^{\alpha-2}})^p\\&=(1+p^{\alpha-1}b)^p.\end{align*} Note that the binomial coefficients of $(1+x)^p$ are each divisible by $p$ except in the $1$ and $x^p$ in the ends. This means the binomial coefficients of $(1+p^{\alpha-1}b)^p$ are each divisible by $p^\alpha$ except in the $1$ and $p^{p(\alpha-1)}b^p$ in the ends. Now, $$p^{p(\alpha-1)}b^p=p^\alpha p^{p(\alpha-1)-\alpha}b^p.$$ Since $p$ is a prime, $p\geq 2$. So, \begin{align*}p(\alpha-1)-\alpha&\geq 2(\alpha-1)-\alpha\\&=\alpha-2\geq 0\ \mbox{by assumption}.\end{align*}This means $p^{p(\alpha-1)}b^p$ is also divisible by $p^\alpha$. Hence, $$a^{\phi(p^\alpha)}\equiv 1\mod p^\alpha.$$ Let $m=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$ be the prime factorization of $m$. Then by the multiplicity of $\phi$ (Corollary 8), \begin{align*}\phi(m)&=\phi(p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r})\\&=\phi(p_1^{\alpha_1})\cdots \phi(p_r^{\alpha_r}).\end{align*} For each $i=1,\cdots,r$, $$a^{\phi(p_i^{\alpha_i})}\equiv 1\mod p_i^{\alpha_i}.$$
Let $M_i:=\phi(m)/\phi(p_i^{\alpha_i})$ for $i=1,\cdots,r$. Then \begin{align*} a^{\phi(m)}&=a^{\phi(p_1^{\alpha_1})\cdots \phi(p_r^{\alpha_r})}\\&=(a^{\phi(p_i^{\alpha_i})})^{M_i}\\&\equiv 1\mod p_i^{\alpha_i}.\end{align*}
Since $(p_i^{\alpha_i},p_j^{\alpha_j})=1$ if $i\ne j$, $$a^{\phi(m)}\equiv 1\mod m=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$$ by Lemma 3.

Remark. Suppose that $a$ is any positive integer such that $(a,105)=1$.
\begin{align*}\phi(105)&=\phi(3\cdot 5\cdot 7)\\&=105\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\left(1-\frac{1}{7}\right)\\&=48.\end{align*}So, by Euler’s Theorem (Theorem 10) $$a^{48}\equiv 1\mod 105.$$ As we have seen in the proof of Theorem 10, there is a smaller power of $a$ which gives $1\mod m=105=3\cdot 5\cdot 7$. \begin{align*}a^{\phi(3)}=a^2\equiv 1\mod 3,\\ a^{\phi(5)}=a^4\equiv 1\mod 5,\\ a^{\phi(7)}=a^6\equiv 1\mod 7.\end{align*}
The least common multiple of $\phi(3)=2,\phi(5)=4,\phi(7)=6$ is 12 and so
\begin{align*}a^{12}&\equiv 1\mod 3,\\ a^{12}&\equiv 1\mod 5,\\ a^{12}&\equiv 1 \mod 7.\end{align*} By Lemma 3, $$a^{12}\equiv 1\mod3\cdot 5\cdot 7=105.$$

Example. Compute $2^{1000000}\mod 77$.

Solution: $77=7\cdot 11$ and $\phi(7)=6,\ \phi(11)=10$. The least common multiple of $6$ and $10$ is $30$. So, $$2^{30}\equiv 1\mod 77.$$ Since $1000000=30\cdot 33333+10$, $$2^{1000000}\equiv 2^{10}\mod 77\equiv 23\mod 77.$$

There is an alternative way to calculate $2^{1000000}\mod 77$. First compute $2^{1000000}\mod 7$. $$2^{\phi(7)}=2^6\equiv 1\mod 7.$$ Since $1000000=6\cdot 166666+4$, $$2^{1000000}\equiv 2^4\equiv 2\mod 7.$$ On the other hand,
$$2^{10}\equiv 1\mod 11.$$ So, $$2^{1000000}\equiv 1\mod 11.$$ We now find $0\leq x\leq 76$ which satisfies \begin{align*}x&\equiv 2\mod 7\\ x&\equiv 1\mod 11\end{align*} by the Chinese Remainder Theorem (Theorem 7). Let $M=7\cdot 11=77$, $M_1=11$, and $M_2=7$. Since $(7,11)=1$, there exist $y,z\in\mathbb{Z}$ such that $7y+11z=1$. By Euclidean algorithm, one can find solution $y=-3$, $z=2$. Thus, \begin{align*}a_1&=2,\ m_1=7,\ M_1=11,\ N_1=2,\\ a_2&=1,\ m_2=11,\ M_2=7,\ N_2=-3.\end{align*} Hence, \begin{align}x&=\sum_{i=1}^2a_iM_iN_i\ &=23\mod 77.\end{align}

Theorem. \begin{equation}\sum_{d|n}\phi(d)=n.\end{equation}

Proof. Let $$f(n):=\sum_{d|n}\phi(d).$$ First we show that $f(n)$ is multiplicative. Suppose that $(m,n)=1$ and $d|mn$. Then $d$ can be written in the form $d=d_1d_2$ such that $d_1|m$ and $d_2|n$. Since $(d_1,d_2)=1$, by Corollary 8, $$\phi(d)=\phi(d_1d_2)=\phi(d_1)\phi(d_2).$$
Now, \begin{align*}f(mn)&=\sum_{d|mn}\phi(d)\\&=\sum_{d_1|m}\sum_{d_2|n}\phi(d_1)\phi(d_2)\\&=\sum_{d_1|m}\phi(d_1)\left(\sum_{d_2|n}\phi(d_2)\right)\\&=\sum_{d_1|m}\phi(d_1)f(n)\\&=f(n)\sum_{d_1|m}\phi(d_1)\\&=f(m)f(n).\end{align*} Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$ be the prime factorization of $n$. Then
$$f(n)=f(p_1^{\alpha_1})f(p_2^{\alpha_2})\cdots f(p_r^{\alpha_r})$$ and for each $i=1,\cdots, r$, \begin{align*}f(p_i^{\alpha_i})&=\sum_{d|p_i^{\alpha_i}}\phi(d)\\&=\sum_{j=0}^{\alpha_i}\phi(p_i^j)\\&=\sum_{j=1}^{\alpha_i}p_i^j\left(1-\frac{1}{p_i}\right)+1\\&=\sum_{j=1}^{\alpha_i}(p_i^j-p_i^{j-1})+1\\&=p_i^{\alpha_i}.\end{align*} Therefore, $$f(n)=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}=n.$$

Definition. Let $m>0$. We say that $a$ is congruent to $b$ modulo $m$ and write $a\equiv b\mod m$ if $m|b-a$.

Example. Since $6|7-1$, $1\equiv 7\mod 6$. Since $6|13-1$, $1\equiv 13\mod 6$. Since $6\not|7-2$, $7\not\equiv 2\mod 6$.

Theorem 1. Let $a,a’,b,b’,c,d$, and $m$ be integers with $d>0$ and $m>0$. Then

1. $a\equiv a\mod m$.
2. If $a\equiv b\mod m$ then $b\equiv a\mod m$.
3. If $a\equiv b\mod m$ and $b\equiv c\mod m$ then $a\equiv c\mod m$.
4. If $a\equiv b\mod m$ and $a’\equiv b’\mod m$ then $a+a’\equiv b+b’\mod m$.
5. If $a\equiv b\mod m$ and $a’\equiv b’\mod m$ then $aa’\equiv bb’\mod m$.
6. If $a\equiv b\mod m$ and $d|m$ then $a\equiv b\mod d$.

Proof.

1. Since $m|0=a-a$, $a\equiv a\mod m$.
2. Let $a\equiv b\mod m$. Then $m|b-a$ and so $b-a=mk$ for some $k\in\mathbb{Z}$. Since $a-b=m(-k)$ and $-k\in\mathbb{Z}$, then $m|a-b$, i.e., $b\equiv a\mod m$.
3. Suppose that $a\equiv b\mod m$ and $b\equiv c\mod m$. Then $m|b-a$ and $m|c-b$, so $$m|(b-a)+(c-b)=c-a.$$ Hence, $a\equiv c\mod m$.
4. Suppose that $a\equiv b\mod m$ and $a’\equiv b’\mod m$. Then $m|b-a$ and $m|b’-a’$, so $$m|(b-a)+(b’-a’)=(b+b’)-(a+a’),$$ that is, $a+a’\equiv b+b’\mod m$.
5. Suppose that $a\equiv b\mod m$ and $a’\equiv b’\mod m$. Then $m|b-a$ and $m|b’-a’$. Now, $$bb’-aa’=(b-a)a’+(b’-a’)b.$$ Since $m|b-a$ and $m|b’-a’$, $m|bb’-aa’$, i.e., $aa’\equiv bb’\mod m$.
6. If $a\equiv b\mod m$ then $m|b-a$. If $d|m$ then $d|b-a$ and so $a\equiv b\mod d$.

Remark 1. Properties 1-3 tell us that $\equiv\mod m$ is an equivalence relation on $\mathbb{Z}$. Properties 1-5 tell us that $\equiv\mod m$ is a congruence relation, an equivalence relation that preserves operations, on $\mathbb{Z}$. One could easily guess that $\equiv\mod m$ is where the name congruence relation is originated from. For more details about congruence relation, see the reference [1] below.

Definition. If $m>0$ and $r$ is the remainder when the division algorithm is used to divide $b$ by $m$, then $r$ is called the least residue of $b$ modulo $m$.

Example.

1. The least residue of $12\mod 7$ is $5$.
2. The least residue of $20\mod 4$ is $0$.
3. The least residue of $-12\mod 7$ is $2$.
4. The least residue of $-3\mod 7$ is $4$.

Theorem 2. Let $m>0$. Then

1. If $r$ and $b$ are integers such that $r\equiv b\mod m$ and $0\leq r<m$, then $r$ is the least residue $\mod m$.
2. Two integers are congruent $\mod m$ if and only if they have the same least residue $\mod m$.

Proof.

1. Suppose that $r\equiv b\mod m$. Then $m|b-r$ and so $b=mq+r$ for some $q\in\mathbb{Z}$. If $0\leq r<m$ then by the uniqueness of the quotient and the remainder, $r$ must be the least residue $\mod m$.
2. Suppose that $b$ and $b’$ have the same remainder when divided by $m$, say $$b=mq+r\ {\rm and}\ b’=mq’+r$$ for some $q,q’\in\mathbb{Z}$. Then $b-b’=m(q-q’)$ and so $b\equiv b’\mod m$. Conversely, suppose that $b\equiv b’\mod m$ and $b=mq+r$ with $0\leq r<m$. Then $b’\equiv b\mod m$ and $b\equiv r\mod m$, thus $b’\equiv r\mod m$. Therefore by part 1, $r$ is the least residue of $b’\mod m$.

Example. Find the least residue of $33\cdot 26^2\mod 31$.

Solution: $33\equiv 2\mod 31$ and $26\equiv -5\mod 31$. So, \begin{align*} 33\cdot 26^2&\equiv 2\cdot (-5)^2\mod 31\\ &\equiv 50\mod 31\\ &\equiv 19\mod 31.\end{align*} Since $0\leq 19<31$, the least residue is $19$.

Theorem 3 (The Cancellation Theorem). If $a,b>0$, $x$ and $x’$ are integers such that $(a,b)=1$, then $ax\equiv ax’\mod b$ implies $x\equiv x’\mod b$.

The following example shows that the Cancellation Theorem does not necessarily hold unless the condition $(a,b)=1$ is satisfied.

Example. $(2,4)=2\ne 1$. $2\cdot 1\equiv 2\cdot 3\mod 4$ but $1\not\equiv 3\mod4$.

The Cancellation Theorem is a special case of the following more general theorem.

Theorem 4. If $a,b>0$, $x$ and $x’$ are integers such that $(a,b)=d$, then
$ax\equiv ax’\mod b$ if and only if $x\equiv x’\mod b/d$.

Proof. \begin{align*} ax\equiv ax’\mod b&\Longrightarrow b|a(x-x’)\\ &\Longrightarrow a(x-x’)=bk\ \mbox{for some}\ k\in\mathbb{Z}\\ &\Longrightarrow \frac{a}{d}(x-x’)=\frac{b}{d}k\\ &\Longrightarrow \frac{b}{d}|\frac{a}{d}(x-x’)\\ &\Longrightarrow \frac{b}{d}|x-x’\ \mbox{since}\ \left(\frac{a}{d},\frac{b}{d}\right)=1\\ &\Longrightarrow x\equiv x’\mod\frac{b}{d}. \end{align*} Conversely, if $x\equiv x’\mod\frac{b}{d}$, then
\begin{align*} x’-x=\frac{b}{d}k\ \mbox{for some}\ k&\Longrightarrow ax’-ax=b\left(\frac{a}{d}\right)k\\ &\Longrightarrow ax\equiv ax’\mod b. \end{align*}

Theorem 5. If $a>0, b$, and $b’$ are integers such that
$b\equiv b’\mod a$, then $(a,b)=(a,b’)$.

Proof. \begin{align*} b\equiv b’\mod a&\Longrightarrow b’-b=aq\ \mbox{for some}\ q\in\mathbb{Z}\\ &\Longrightarrow b’=b+aq\\ &\Longrightarrow (a,b)=(a,b’) \end{align*} by Lemma 3 here.

As mentioned in Remark 1, $\equiv\mod m$ is an equivalence relation on $\mathbb{Z}$. For fixed $m$, each equivalence class with respect to $\equiv\mod m$ has one and only one representative between $0$ and $m-1$. Denote by $\mathbb{Z}/m\mathbb{Z}$ or $\mathbb{Z}_m$ the set of all equivalence classes, called the residue classes. Then
$$\mathbb{Z}/m\mathbb{Z}=\{[0],[1],\cdots,[m-1]\}.$$
Often $\mathbb{Z}/m\mathbb{Z}$ is written simply as
$$\mathbb{Z}/m\mathbb{Z}=\{0,1,\cdots,m-1\},$$
i.e, those residue classes are represented by their representatives (typically those least residues $\mod m$) unless there is a confusion.

Define the binary operations $+$ and $\cdot$ on $\mathbb{Z}/m\mathbb{Z}$: For any $[a],[b]\in\mathbb{Z}/m\mathbb{Z}$,
$$[a]+[b]:=[a+b],\ [a]\cdot[b]:=[a\cdot b].$$
Then $+$ and $\cdot$ are well-defined due to properties (4) and (5), respectively in Theorem 1.

Theorem 6. $(\mathbb{Z}/m\mathbb{Z},+,\cdot)$ is a commutative ring with unity.

Consider $\mathbb{Z}/9\mathbb{Z}$. Its multiplication table is given by
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|}\hline\cdot & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\hline 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\\hline 2 & 0 & 2 & 4 & 6 & 8 & 1 & 3 & 5 & 7\\\hline 3 & 0 & 3 & 6 & 0 & 3 & 6 & 0 & 3 & 6\\\hline 4 & 0 & 4 & 8 & 3 & 7 & 2 & 6 & 1 & 5\\\hline 5 & 0 & 5 & 1 & 6 & 2 & 7 & 3 & 8 & 4\\\hline
6 & 0 & 6 & 3 & 0 & 6 & 3 & 0 & 6 & 3\\\hline 7 & 0 & 7 & 5 & 3 & 1 & 8 & 6 & 4 & 2\\\hline 8 & 0 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1\\\hline\end{array}$$
As one can see clearly, not every nonzero element of $\mathbb{Z}/9\mathbb{Z}$ has a multiplicative inverse. So, $\mathbb{Z}/9\mathbb{Z}$ cannot be a field. However, there are elements of $\mathbb{Z}/9\mathbb{Z}$ that have multiplicative inverses. They are $1,2,4,5,7,8$. As representatives of residue classes, they are all relatively prime to $9$. In fact, the following theorem holds in general.

Theorem 7. The elements of $\mathbb{Z}/m\mathbb{Z}$ which have multiplicative inverses are those which are relatively prime to $m$, i.e., the numbers $a$ for which there exists $b$ with $ab\equiv 1\mod m$ are precisely those $a$ for which $(a,m)=1$.

Proof. Let $d=(a,m)$ and suppose that there exists $b\in\mathbb{Z}$ such that $ab\equiv 1\mod m$. Then by property 6 in Theorem 1 $ab\equiv 1\mod d$. Since $d|a$, $d$ must divide $1$, i.e., $d=1$. Conversely, if $(a,m)=1$ then by Bézout’s Lemma (Theorem 5 here), there exist $x,y\in\mathbb{Z}$ such that $ax+my=1$. Choose $b=x$. Then $ab\equiv 1\mod m$.

Definition. If $(a,m)=1$ then by negative power $a^{-n}\mod m$ we mean the $n$-th powers of the inverse residue class, i.e., it is represented by the $n$-th power of any integer $b$ for which $ab\equiv 1\mod m$.

Example. Find $160^{-1}\mod 841$, i.e., the inverse of $160\mod 841$.

Solution: First check if $(160,841)=1$ by the Euclidean algorithm.
\begin{align*} 841&=160\cdot 5+41,\\ 160&=41\cdot 3+37,\\ 41&=37\cdot 1+4,\\ 37&=4\cdot 9+1. \end{align*} So, $(160,841)=1$. Now by working backward, let us find $b$ such that $160\cdot b\equiv 1\mod 841$. \begin{align*} 1&=37-4\cdot 9\\ &=37-(41-37)9\\ &=10\cdot 37-9\cdot 41\\ &=10(160-3\cdot 41)-9\cdot 41\\ &=10\cdot 160-39\cdot 41\\ &=10\cdot 160-39(841-5\cdot 160)\\ &=205\cdot 160-39\cdot 841.\end{align*} Hence, $b=205=160^{-1}$.

Corollary 8. If $p$ is a prime number then every nonzero residue class has a multiplicative inverse, i.e, $\mathbb{Z}/p\mathbb{Z}$ is a field. We often denote this finite field of $p$ elements by $\mathbb{F}_p$.

Corollary 9. Suppose $0\leq a,b<m$. If $(a,m)=1$ then there exists $x_0\in\mathbb{Z}$ such that $ax_0\equiv b\mod m$ and all solutions of $ax\equiv b\mod m$ are of the form $x=x_0+mn$ for $n$ an integer. If $(a,m)=d$ then there exists $x\in\mathbb{Z}$ such that $ax\equiv b\mod m$ if and only if $d|b$ and in that case our congruence is equivalent to the congruence $a’x\equiv b’\mod m’$, where $a’=a/d,b’=b/d,m’=m/d$.

Proof. If $(a,m)=1$ then there exists $a^{-1}\in\mathbb{Z}$ such that $a\cdot a^{-1}\equiv 1\mod m$, so $a\cdot (a^{-1}b)\equiv b\mod m$. Choose $x_0=a^{-1}b$. Since $(a,m)=1$, by Theorem 7 here, all solutions of equation $ax\equiv b\mod m$ or equivalently $ax+mq=b$ for some $q\in\mathbb{Z}$ are given in the form $$x=x_0+mn$$ for some $n\in\mathbb{Z}$. Let $(a,m)=d$. If there exists $x\in\mathbb{Z}$ such that $ax\equiv b\mod m$, then clearly $d|b$. Conversely, suppose that $d|b$. Since $(a/d,m/d)=1$, there exists $x\in\mathbb{Z}$ such that $\frac{a}{d}x\equiv\frac{b}{d}\mod\frac{m}{d}$ and this is clearly equivalent to $ax\equiv b\mod m$.

References:

1. Stanley Burris and H. P. Sankappanavar, A Course in Universal Algebra, Springer-Verlag, 1981

Theorem 1. Given integers $a$, $b$, and $c$ with $a$ and $b$ not both $0$, there exist $x,y\in\mathbb{Z}$ such that $ax+by=c$ if and only if $(a,b)|c$.

Proof. Left as an exercise.

Corollary 2. Let $a$ and $b$ be integers. Then there exist $x,y\in\mathbb{Z}$ such that $ax+by=1$ if and only if $(a,b)=1$ i.e. $a$ and $b$ are relatively prime.

Corollary 3. Let $a,a’,b\in\mathbb{Z}$. If $(a,b)=1$ and $(a’,b)=1$, then $(aa’,b)=1$.

Proof. Since $(a,b)=1$ and $(a’,b)=1$, there exist $x,y,x’,y’\in\mathbb{Z}$ such that $ax+by=1$ and $a’x’+by’=1$. Now, \begin{align*}1&=(ax+by)(a’x’+by’)\\&=aa’xx’+b(axy’+a’x’y+byy’)\end{align*} Hence, $(aa’,b)=1$.

Theorem 4. If $a,b$ and $c$ are integers such that $(a,b)=1$ and $a|bc$, then $a|c$.

Proof. Since $(a,b)=1$, there exist $x,y\in\mathbb{Z}$ such that $ax+by=1$. So, we obtain $acx+bcy=c$. Since $a|ac$ and $a|bc$, $a|c$.

Remark. $a|bc$ does not necessarily imply that $a|b$ or $a|c$. For example, $6|36=4\cdot 9$ but $6\not|4$ and $6\not|9$. However, the following theorem holds.

Theorem 5. If $p$ is a prime number and $p|ab$, then $p|a$ or $p|b$.

Proof. Let $p$ be a prime number and $p|ab$. Suppose that $p\not|a$ and $p\not|b$. Since $p$ is prime and $p\not|a$, $(p,a)=1$ and so $px+ay=1$ for some $x,y\in\mathbb{Z}$. Now, $p|pbx+aby=b$ but this is a contradiction to the assumption that $p\not|b$. Therefore, $p|a$ or $p|b$.

Theorem 6. If $a$ and $b$ are integers and $(a,b)=d$, then $\frac{a}{d}$ and $\frac{b}{d}$ are relatively prime.

Proof. Since $(a,b)=d$, there exist $x,y\in\mathbb{Z}$ such that $ax+by=d$. Dividing the equation by $d$, we obtain

$\frac{a}{d}x+\frac{b}{d}y=1$. By theorem 1, this implies that $\left(\frac{a}{d},\frac{b}{d}\right)=1$.

Example 1. Consider the equation $9x+24y=15$. Since $(9,24)=3$ and $3|15$, from theorem 1, we know that a solution exist. First, we can find a solution to $9x+24y=3$ using the Euclidean algorithm as seen before. \begin{align*}24&=9\cdot 2+6\\9&=6\cdot 1+3\\6&=3\cdot 2+0\end{align*} Thus, \begin{align*}3&=9-6\cdot 1\\&=9-(24-9\cdot 2)\cdot 1\\&=9\cdot 3+24\cdot(-1)\end{align*} Hence, $x’=3$ and $y’=-1$ is a solution to $9x+24y=3$ and thereby $x=5x’=15$ and $y=5y’=-5$ is a solution to $9x+24y=15$. Finding a solution is not a big deal. But there are other solutions. For instance, $x=-1$ and $y=1$ is also a solution to $9x+24y=15$. How do we find other solutions? We now turn our attention to this question.

Suppose that $(x_0,y_0)$ is a solution to \begin{equation}\label{eq:lineqn}ax+by=c\end{equation} Then \begin{equation}\label{eq:lineqn2}ax_0+by_0=c\end{equation} Subtracting \eqref{eq:lineqn2} from \eqref{eq:lineqn}, we obtain \begin{equation}\label{eq:lineqn3}a(x-x_0)=b(y_0-y)\end{equation} Let $d=(a,b)$. Dividing \eqref{eq:lineqn3} by $d$, we obtain \begin{equation}\label{eq:lineqn4}\frac{a}{d}(x-x_0)=\frac{b}{d}(y_0-y)\end{equation} This means that $\frac{a}{d}|\frac{b}{d}(y_0-y)$. Since $\left(\frac{a}{d},\frac{b}{d}\right)=1$, by theorem 2, $\frac{a}{d}|y_0-y$ and so, $y_0-y=\frac{a}{d}t$ for some $t\in\mathbb{Z}$. From \eqref{eq:lineqn4} we also obtain $x-x_0=\frac{b}{d}t$. Therefore, $x$ and $y$ are written as \begin{equation}\label{eq:lineqnsol}x=x_0+\frac{b}{d}t,\ y=y_0-\frac{a}{d}t\end{equation} where $t\in\mathbb{Z}$. Conversely, any $(x,y)$ in the form \eqref{eq:lineqnsol} satisfies the equation \eqref{eq:lineqn}. $$a\left(x_0+\frac{b}{d}t\right)+b\left(y_0-\frac{a}{d}t\right)=ax_0+by_0=c$$

Theorem 7. Suppose that $a\ne 0$, $b\ne 0$, and $c$ are integers. Let $(x_0,y_0)$ be a particular solution to $ax+by=c$. Then all solutions to $ax+by=c$ are given by $$x=x_0+\frac{b}{d}t,\ y=y_0-\frac{a}{d}t$$ where $t\in\mathbb{Z}$ and $(a,b)=d$.

Example. In example 1, we found $(x_0,y_0)=(15,-5)$. So by theorem 6, all solutions to $9x+24y=15$ are given by $$x=15+8t,\ y=-5-3t$$ where $t\in\mathbb{Z}$.

Example. Find all positive integers $x,y$ such that $4x+6y=100$.

Solution. $(4,6)=2$ and $2|100$, so a solution exists.

$6=4\cdot 1+2$ i.e. $2=4\cdot (-1)+6\cdot 1$. $x_0=-50$ and $y_0=50$ is a particular solution to $4x+6y=100$. By theorem 3, all solutions are given by $$x=-50+3t,\ y=50-2t$$ where $t\in\mathbb{Z}$. Since $x$ and $y$ are required to be positive, we find that $17\leq t\leq 24$. The following table shows all those solutions. $$\begin{array}{|c||c|c|c|c|c|c|c|c|}\hline t & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24\\\hline x & 1 & 4 & 7 & 10 & 13 & 16 & 19 & 22\\\hline y & 16 & 14 & 12 & 10 & 8 & 6 & 4 & 2\\\hline\end{array}$$

Example. A man paid \$ 11.37 for some 39-cent pens and 69-cent pens. How many of each did he buy?

Solution. The problem is equivalent to solving the equation \begin{equation}\label{eq:pen}39x+69y=1137\end{equation} where $x$ and $y$ are nonnegative integers. $(39,69)=3$ and $3|1137$, so the equation has a solution. Solving the equation \eqref{eq:pen} is equivalent to solving \begin{equation}\label{eq:pen2}13x+23y=379\end{equation} where $x$ and $y$ are nonnegative integers. Since $(13,23)=1$, by the Euclidean algorithm, one can find a solution $x’=-7$ and $y’=4$ to $13x+23y=1$. $x_0=379x’=-2653$ and $y_0=379\cdot y’=1516$ is then a solution to \eqref{eq:pen2}. By theorem 3, all integer solutions to \eqref{eq:pen2} are given by $$x=-2653+23t,\ y=1516-13t,\ t\in\mathbb{Z}$$ From the conditions $x\geq 0, y\geq 0$, we obtain the inequality $115\frac{8}{23}\leq t\leq 116\frac{8}{23}$. There is only one integer $t=116$ that satisfies the inequality. $x=-2653+23\cdot 116=15$ and $y=1516-13\cdot 116=8$. So, the man bought 15 39-cent pens and 8 69-cent pens.

Theorem 1. Suppose that $a,b\in\mathbb{Z}$ with $0<a<b$. Then there exists uniquely $q,r\in\mathbb{Z}$, $0\leq r<a$, such that
$$b=aq+r$$

Theorem 2. If $a$ and $b$ are positive integers, then
$$(a,b)[a,b]=ab$$

Suppose that $0<a<b$. Then by the division algorithm, there exist uniquely $q,r\in\mathbb{Z}$ such that $b=aq+r$ where $0\leq r<a$. If $d=(a,b)$ then $d|r$. This means $d\leq(a,r)$ since $d$ is a common divisor of $a$ and $r$. Since $(a,r)|a$ and $(a,r)|b$, $(a,r)$ is a common divisor of $a$ and $b$. This implies $(a,r)\leq(a,b)=d$. Thus, $d=(a,r)=(a,b)$. More generally, we have the following lemma holds.

Lemma 3. For any integers $a>0$, $b$, $c$ and $k$, if $a=bk+c$ then $(a,b)=(b,c)$.

Example. Let $a=123$ and $b=504$. Then
$$504=123\cdot 4+12$$
By Lemma, we have
$$(123,504)=(12,123)$$
$$123=12\cdot 10+3$$
By Lemma again, we have
$$(12,123)=(3,12)=3$$
Hence, we obtain $(123,504)=3$.

Theorem 4. (The Euclidean Algorithm) Let $a$ and $b$ be integers, $0<a<b$. Apply the division algorithm repeatedly as follows. \begin{align*}b&=aq_1+r_1,\ 0<r_1<a\\a&=r_1q_2+r_2,\ 0<r_2<r_1\\r_1&=r_2q_3+r_3,\ 0<r_3<r_2\\&\vdots\\r_{n-2}&=r_{n-1}q_n+r_n,\ 0<r_n<r_{n-1}\\r_{n-1}&=r_nq_{n+1}\end{align*}Let $r_n$ be the last nonzero remainder. Then $(a,b)=r_n$

Example. Compute $(158,188)$ using the Euclidean algorithm.
\begin{align*}188&=158\cdot 1+30\\158&=30\cdot 5+8\\30&=8\cdot 3+6\\8&=6\cdot 1+2\\6&=2\cdot 3+0 \end{align*} Hence, $(158,188)=2$.

It is possible to use the Euclidean algorithm to write $(a,b)$ in the form $ax+by$. In the above example, \begin{align*}2&=8-6\cdot 1\\&=8-(30-8\cdot 3)\cdot 1\\&=-30+8\cdot 4\\&=-30+(158-30\cdot 5)\cdot 4\\&=158\cdot 4-30\cdot 21\\&=158\cdot 4-(188-158\cdot 1)\cdot 21\\&=158\cdot 25+188\cdot(-21) \end{align*}
In general, the following property holds.

Theorem 5. (Bézout’s Lemma) If $a$ and $b$ are integers such that $(a,b)$ is defined, then there exist $x,y\in\mathbb{Z}$ such that
\begin{equation}
\label{eq:bezout}
(a,b)=ax+by
\end{equation}

\eqref{eq:bezout} is called the Bézout’s identity.

Corollary 6. If $d$ is any common divisor of $a$ and $b$, not both of which are $0$, then $d|(a,b)$.

Definition. We say $k$ is a linear combination of $a$ and $b$ if there exist $x,y\in\mathbb{Z}$ such that $k=ax+by$.

Theorem 7. Given integers $a\ne 0$ and $b\ne 0$, and $m$, if $a|m$ and $b|m$ then $[a,b]|m$.

Proof. Assume that $\frac{m}{[a,b]}$ is not an integer. Then there exist $q,r\in\mathbb{Z}$ such that $m=[a,b]q+r$, $0<r<[a,b]$. The remainder $r$ is then written as $r=m-q[a,b]$. By assumption, $a|m$, and also $a|[a,b]$. So, $a|r$. By the same argument, we also obtain $b|r$. This means that $r$ is a common multiple of $a$ and $b$. But it is a contradiction to the fact that $0<r<[a,b]$. Hence, $r=0$.

Remark. This theorem and the preceding corollary are dual to each other.