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 or totient function. As the name suggests, this function was introduced by Leonhard Euler but the name totient was coined by J. J. Sylvester.
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
$$
\phi(p)=p-1. \tag{1}
$$
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 larger, computing
$\phi(n)$ will become more difficult.
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
$$
\phi(ka)=k\phi(a). \tag{2}
$$
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
$$
\phi(pa)=(p-1)\phi(a). \tag{3}
$$
Example.
\begin{align*}
\phi(10^6)&=\phi(10^5\cdot 10)\\
&=10^5\phi(10)\ \mbox{by (2)}\\
&=10^5\phi(2\cdot 5)\\
&=10^5(2-1)\phi(5)\ \mbox{by (3)}\\
&=10^5\cdot 4 \ \mbox{by (1)}\\
&=400,000.\\\phi(60)&=\phi(2^2\cdot 3\cdot 5)\\
&=2\phi(2\cdot 3\cdot 5) \ \mbox{by (2)}\\
&=2\cdot(2-1)\phi(3\cdot 5) \ \mbox{by (3)}\\
&=2(3-1)\phi(5)\ \mbox{by (3)}\\
&=16 \ \mbox{by (1)}.\\
\phi(62)&=\phi(2\cdot 31)\\
&=(2-1)\phi(31)\ \mbox{by (3)}\\
&=30\ \mbox{by (1)}.
\end{align*}
Theorem 6. Let $p$ be a prime and $\alpha$ a positive integer. Then
$$
\phi(p^\alpha)=p^\alpha\left(1-\frac{1}{p}\right). \tag{4}
$$
Proof. It follows immediately from (2) and (1).
\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*}
Maxima. In Maxima, we have the command totient:
(%i1) totient(62);
(%o1) 30
Theorem 7 (Chinese Remainder Theorem) Suppose that we want to solve a system of congruences to different moduli:
\begin{align*}
x&\equiv a_1\mod m_1,\\
x&\equiv a_2\mod m_2,\\
&\cdots\ \ \ \ \ \cdots \tag{5}\\
x&\equiv a_r\mod m_r.
\end{align*}
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 (5). 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.
Maxima. Maxima has a built-in command for solving a system of congruences. It is chinese(a1,...,ar],[m1,...,mr]). For the Han Xing's problem:
(%i1) chinese([2,3,2],[3,5,7]);
(%o1) 23
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$,
$$
\phi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right). \tag{6}
$$
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 (4)}\\
&=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
$$
a^{\phi(m)}\equiv 1\mod m. \tag{7}
$$
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 (7) 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 11.
$$
\sum_{d|n}\phi(d)=n. \tag{8}
$$
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.$$
