Proof of Euler’s Theorem without Advanced Techniques

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) = 0$, 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)} \}$.

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.

Author: Chaoping Guo

Learning is a privilege that I am grateful for.