Today I was reading about HTTPS, then followed public/private keys to RSA, and then saw Euler’s theorem. Noticing Ruan Yifeng’s blog has no proof of Euler’s theorem, I wondered whether I could prove it, and spent a long while working out a proof scheme. I hope attentive readers will point out any problems.
Except for the proof part, the rest of this article is consistent with The RSA Algorithm Principle (Part 1). For any difficulties understanding Euler’s theorem, please go to Ruan Yifeng’s blog.
You can jump directly to the proof section
A Few Basic Concepts
Coprime Relationship
If two positive integers have no common divisor other than 1, we say the two numbers are coprime. For example, 15 and 32 have no common divisor, so they are coprime. This shows that non-prime numbers can also form a coprime relationship.
Applying the coprime relationship yields the following conclusions:
Any two primes form a coprime relationship, e.g. 13 and 61.
If one number is prime, then as long as the other is not a multiple of the former, the two form a coprime relationship, e.g. 3 and 10.
If the larger of two numbers is prime, then the two form a coprime relationship, e.g. 97 and 57.
1 and any natural number form a coprime relationship, e.g. 1 and 99.
If p is an integer greater than 1, then p and p-1 form a coprime relationship, e.g. 57 and 56.
If p is an odd number greater than 1, then p and p-2 form a coprime relationship, e.g. 17 and 15.
Euler’s Totient Function
Given any positive integer n, among the positive integers less than or equal to n, how many form a coprime relationship with n? (For example, among 1 to 8, how many numbers are coprime with 8?) The method of computing this value is called Euler’s totient function, denoted $\phi(n)$. Among 1 to 8, the numbers coprime with 8 are 1, 3, 5, 7, so $\phi(8) = 4$.
The computation of $\phi(n)$ is not complex, but to arrive at the final formula we need to discuss it step by step.
The First Case
If n=1, then $\phi(1) = 1$, because 1 is coprime with any number (including itself).
The Second Case
If n is prime, then $\phi(n)=n-1$, because a prime is coprime with every number smaller than it. For example, 5 is coprime with 1, 2, 3, 4.
The Third Case
If n is some power of a prime, i.e. $n = p^{k}$ (p prime, k an integer ≥ 1), then
$$\phi(p^k) = p^k - p^{k-1}$$
For example $\phi(8) = \phi(2^{3}) =2^{3} - 2^{2} = 8 -4 = 4$ .
This is because only numbers that do not contain the prime p can be coprime with n. Numbers containing the prime p total p^(k-1): namely 1×p, 2×p, 3×p, …, p^(k-1)×p. Remove them, and what remains are the numbers coprime with n.
The formula above can also be written in the following form:
$$\phi(p^k) = p^k - p^{k-1} = p^{k}(1 - \frac{1}{p}) $$
You can see the second case above is the special case of k=1.
The Fourth Case
If n can be decomposed into the product of two coprime integers,
$$n = p1 × p2$$
then
$$\phi(n) = \phi(p1p2) = \phi(p1)\phi(p2)$$
i.e. the totient of a product equals the product of the totients of its factors. For example, $\phi(56)=\phi(8×7)=\phi(8)×\phi(7)=4×6=24$.
The proof of this item uses the “Chinese Remainder Theorem”; I won’t expand on it here, just briefly state the idea: if a is coprime with p1 ($a<p1$), b is coprime with p2 $(b<p2)$, and c is coprime with p1p2 $(c<p1p2)$, then c corresponds one-to-one with the pair (a,b). Since a has $\phi(p1)$ possible values and b has $\phi(p2)$ possible values, the pair (a,b) has $\phi(p1)\phi(p2)$ possibilities, while c has $\phi(p1p2)$ possibilities — so $\phi(p1p2)$ equals $\phi(p1)\phi(p2)$.
The Fifth Case
Because any positive integer greater than 1 can be written as a product of a series of primes,
$$n = p_{1}^{k1}p_{2}^{k2} … p_{r}^{kr}$$
by the conclusion of item 4, we get
$$ \phi(n) = \phi(p_{1}^{k1})\phi(p_{2}^{k2}) … \phi(p_{r}^{kr}) $$
and then by the conclusion of item 3, we get
$$ \phi(n) = p_{1}^{k1}p_{2}^{k2} … p_{r}^{kr}(1-\frac{1}{p1})(1-\frac{1}{p2})…(1-\frac{1}{pr}) $$
which also equals
$$ \phi(n) = n(1-\frac{1}{p1})(1-\frac{1}{p2})…(1-\frac{1}{pr}) $$
This is the general computation formula for Euler’s totient function. For example, the totient of 1323 is computed as follows:
$$ \phi(1323) = \phi(3^3 \times 7^2) = 1323(1-\frac{1}{3})(1-\frac{1}{7}) = 756 $$
Euler’s Theorem
If two positive integers a and n are coprime, then n’s totient $\phi(n)$ makes the following equation hold: $$ a^{\phi(n)} \equiv 1(mod\ n) $$
The original blog has no proof section, so here I consider a proof method. Comments are welcome:
The Proof
According to Euler’s theorem we make the following assumption, where G is a constant; what we want to prove is G=1.
$$ a^{\phi(n)} = nX + G $$
where X is the quotient, unknown to us.
By the definition of coprimality, $a^{\phi(n)}$ is coprime with nX+G-1. We substitute nX+G-1 into the totient function in place of n, and substitute $a^{\phi(n)}$ in place of a.
$$ ({a^{\phi(n)}})^{\phi(nX+G-1)}=(nX+G-1)Y+G $$
Y is another quotient, unknown to us.
After transforming the powers we get:
$$ (a^{\phi(nX+G-1)})^{\phi(n)}=(nX+G-1)Y+G $$
Any power of a is definitely coprime with n, that is to say, the equation above can also be written in the following form
$$(a^{\phi(nX+G-1)})^{\phi(n)}=nZ+G$$
Z is another unknown quotient. Connecting the two equations:
$$ nZ+G=(nX+G-1)Y+G$$
After simplification:
$$nZ+G=nXY+(G-1)Y+G$$
So we have
$$ \begin{matrix} Z = XY \ (G-1)Y = 0 \end{matrix} $$
Although X, Y, Z are unknown, since $a^{\phi(n)} > n$, X, Y, Z definitely cannot be 0 — therefore G = 1 follows.
Euler’s theorem is proved.
Additional Discussion
The computation above can indeed yield the conclusion G=1, but it is still not entirely rigorous. I raise the following two questions;
if readers have any thoughts we can discuss.
- $a^{\phi(n)}$ is also coprime with nX+G+1 — why not substitute with nX+G+1?
- On what grounds do we assume $a^{\phi(n)} = nX + G$? Why is G a constant, and what if G were not constant?