## 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)} \}$$.

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.