Euler’s Theorem
If $$a$$ and $$n$$ are relatively prime, then $$!a^{\phi(n)} \equiv 1 \pmod{n}$$ where $$\phi(n)$$ is the number of integers in $$[1,n]$$ that are relatively prime to $$n$$.
The Euler’s Totient Function
Single Prime
First, we examine function $$\phi(p^k)$$, where $$p$$ is a prime:
In $$\{1,2,3,…,p^k\}$$, the only integers that are not relatively prime to $$p^k$$ are the multiples of $$p$$, and there are $$\frac{p^k}{p} $$ of them. Therefore $$!\begin{align}\phi(p^k) &= p^k – \frac{p^k}{p} \\ &= p^k (1- \frac{1}{p})\end{align}$$
Multiplicative Function
Lemma: if $$a$$ and $$b$$ are relatively prime, then $$\phi(ab) = \phi(a)\phi(b)$$
Proof:
We first arrange the numbers $$\{1,2,3,…,ab\}$$ by rows to a $$b \times a$$ matrix:
$$!\begin{bmatrix} 1 & 2 & \dots & a \\
a+1 & a+ 2& \dots & 2a\\
2a+ 1 & 2a+ 2 & \dots & 3a\\
\vdots & \vdots & \ddots & \vdots\\
(b-1)a + 1 & (b-1)a +2 &\dots & ab
\end{bmatrix}$$
This way, numbers in the same column are congruent to each other modulo $$a$$. Specifically, the element $$u_{ij}$$ at row i has the following property:
$$!\mathrm{rem}(u_{ij}, a) = j$$
We know (same as Euclid’s algorithm) that, $$!\gcd(u_{ij},a) = \gcd(\mathrm{rem}(u_{ij}, a), a) = \gcd(j,a)$$
This is to say that, if $$j \in \{1,2,3,…,a\}$$ satisfies $$\gcd(j,a) = 1$$, all the numbers in column $$j$$ are relatively prime to $$a$$, and there are $$\phi(a)$$ such columns in total.
Now let’s examine a column. The numbers in column $$j$$ can be written as: $$!\begin{bmatrix}
j\\
j+a\\
j+2a\\
\vdots\\
j+(b-1)a
\end{bmatrix}$$
Corollary: the remainders of the numbers in a column modulo b form a permutation of the sequence $$\{0,1,2,3,…,b-1\}$$.
This is equivalent to that each of the $$b$$ numbers in the row has a different remainder modulo b.We can prove it by contradiction:
Suppose $$!j+sa \equiv j+ta \pmod{b}$$ where $$b-1 \geq s > t \geq 0$$, we have $$!sa \equiv ta \pmod{b}$$ $$!(s-t)a \equiv 0 \pmod{b}$$
We know that $$\gcd(a,b) = 1$$, and (s-t) must be smaller than $$b$$, so there is contradiction.
Now, this corollary shows that every column has $$\phi(b)$$ numbers that are relatively prime to $$b$$.
Number $$u_ij$$ is relatively prime to $$ab$$ if and only if it is relatively to both $$a$$ and $$b$$. In other words, it must be on one of the $$\phi(a)$$ columns described above, and in one of the $$\phi(b)$$ positions on that column. Therefore, $$!\phi(ab) = \phi(a)\phi(b)$$
This can be applied to any positive integer $$n = p_1^{k_1}p_2^{k_2}p_3^{k_3}…p_r^{k_r} $$, where $$p$$ and $$k$$ are from the factored form under the fundamental theorem of arithmetic. We have $$!\phi(n) = n\prod_{p|n}(1 – \frac{1}{p})$$
Proof of the Theorem
We’ve finally come to prove that $$a^{\phi(n)} \equiv 1 \pmod{n}$$.
Lemma: Let $$m_1,m_2,m_3,…,m_{\phi(n)} $$ be the $$\phi(n)$$ integers that are relatively prime to n and in the range of $$[1, n]$$. Then there will no two of them, such that $$am_j \equiv am_i \pmod{n}$$, and all the remainders $$\mathrm{rem}(am_1, n), \mathrm{rem}(am_2, n), \mathrm{rem}(am_3, n), …, \mathrm{rem}(am_\phi(n), n)$$ form a permutation of the sequence $$\{m_1,m_2,m_3,…,m_{\phi(n)} \}$$.
Proof by contradiction:
Assume there is a pair of $$i$$ and $$j$$, such that $$am_j \equiv am_i \pmod{n}$$. Then $$a (m_j – m_i) \equiv 0 \pmod{n}$$. Since $$\gcd(a,n) = 0$$, $$m_j – m_i $$ must be divisible by $$n$$, which leads to contradiction. So we proved the difference between any $$am_i$$ and $$am_j$$. Also, $$\gcd(\mathrm{rem}(am, n), n) = gcd(am, n) = 1$$. Therefore, by definition, $$\mathrm{rem}(am, n) \in \{m_1,m_2,m_3,…,m_{\phi(n)} \}$$.
With this lemma, we can compute the congruence of the product of $$m_1,m_2,m_3,…,m_{\phi(n)}$$:
$$!\begin{align}
\prod_{i=1}^{\phi(n)}am_i & = a^{\phi(n)}\prod_{i=1}^{\phi(n)}\\
a^{\phi(n)}\prod_{i=1}^{\phi(n)}m_i & \equiv \prod_{i=1}^{\phi(n)}m_i \pmod{n}
\end{align}$$
For simplicity, we assign $$M = \prod_{i=1}^{\phi(n)}m_i$$, so we have $$!(a^{\phi(n)} – 1) M \equiv 0 \pmod{n}$$
Because $$M$$ is relatively prime to $$n$$, $$a^{\phi(n)} – 1$$ must be divisible by $$n$$.
Done.
