The Euler’s theorem is very useful in the number theory:
Theorem 1. If $a$ and $m$ are relatively prime numbers, then
$$a^{\varphi(m)} \equiv 1 \pmod m.$$
Proof.
Let $m$ be a natural number and let
$$s_1, s_2, \ldots, s_r, \quad r = \varphi(m),$$
be a reduced residue system modulo $m$. Then
$$as_1, as_2, \ldots, as_r$$
is one complete residue system modulo $m$. This means that each of the numbers $s_1, s_2, \ldots, s_r$ is congruent with exactly one of the numbers $as_1, as_2, \ldots, as_r$, however, not necessarily in the same order. Therefore, there exist numbers $i_1, i_2, \ldots, i_r \in \{1, 2, \ldots, r \}$ such that
$$as_1 \equiv s_{i_1} \pmod m,$$
$$as_2 \equiv s_{i_2} \pmod m,$$
$$\vdots$$
$$as_r \equiv s_{i_r} \pmod m$$
is valid.
By multiplying the above congruences, we obtain:
$$a^rs_1s_2 \cdots s_r \equiv s_{i_1} s_{i_2} \cdots s_{i_r} \pmod m.$$
Since $r = \varphi (m)$ and $s_1s_2 \cdots s_m = s_{i_1}s_{i_2} \cdots s_{i_r}$ (this numbers are the same numbers as above, but multiplied in another order), that follows:
$$a^{\varphi(m)} \equiv 1 \pmod m,$$
and the statement of a theorem is proven.
From the Euler’s theorem follows the Fermat’s Little theorem:
Theorem 2. If $p$ is a prime number and the number $a$ is relatively prime with $p$, then
$$a^{p -1} \equiv 1 \pmod p.$$
The statement of a theorem directly follows from the fact that for every prime number $p$, $\varphi(p) = p-1$ is valid.
The converse of the Fermat’s Little theorem is not valid, that is, if $a$ and $p$ are relatively prime numbers and if $a^{p-1} \equiv 1 \pmod m$, then not follows that the number $p$ is a prime number.
We will show now how to use Euler’s and Fermat’s Little theorem.
Example 1. Find the remainder when the number $119^{120}$ is divided by $9$.
Solution.
Since $119 \equiv 2 \pmod{9}$, that $119^{221} \equiv 2^{221} \pmod 9$. By the Euler’s theorem now follows
$$2^{\varphi(9)} \equiv 1 \pmod 9.$$
Since $\varphi(9) = 6$, we have
$$2^{6} \equiv 1 \pmod 9.$$
By the remainder theorem, the number $221$ we write as $221 = 36 \cdot 6 + 5$, so $2^{221} = (2^6)^{36} \cdot 2^5$. Now it follows
$$2^{221} = (2^6)^{36} \cdot 2^5 \equiv \pmod 9.$$
Since $2^{6} \equiv 1 \pmod 9$, now it follows
$$2^{221} \equiv 1^{36} \cdot 2^5 \pmod 9,$$
that is,
$$2^{221} \equiv 32 \equiv 5 \pmod 9.$$
Therefore, the requested remainder is $5$.
Example 2. Find the remainder when the number $2^{30}$ is divided by $13$.
Solution.
By the Fermat’s Little theorem, we have:
$$2^{12} \equiv 1 \pmod{13}.$$
After squaring the above congruence, we obtain:
$$2^{24} \equiv 1 \pmod{13}.$$
Now this congruence we multiply with the congruence $2^6 \equiv -1 \pmod{13}$, and we obtain:
$$2^{30} \equiv -1 \pmod{13}.$$
Since $-1 \equiv 12 \pmod{13}$, that by substituting it in the previous congruence we obtain:
$$2^{30} \equiv 12 \pmod{13}.$$
Therefore, the requested remainder is $12$.
In the end, let’s just note how the Fermat’s Little theorem can be used to test weather a “large” natural number is a prime or composite number.
Let $m$ be some natural number. We choose some number $a$ (it is good to choose a prime number) that is not a divisor of $m$. Usually we choose $2, 3$ or $5$.
If
$$a^{m-1} \equiv 1 \pmod m$$
is valid, then the number $m$ is a prime number. Otherwise, $m$ is a composite number.
