Euclid's Theorem - Proof Using Euler's Totient Function

Proof Using Euler's Totient Function

The theorem can be also proved by using Euler's totient function φ. In this proof, the following property will be used:

Assume that there is only a finite number of primes. Call them p₁, p₂, ..., p_r and consider the integer n = p₁p₂ ... p_r. Any natural number a ≤ n has a prime divisor q. Then, q must be one of p₁, p₂, ..., p_r, since that is the list of all prime numbers. Hence, for all a ≤ n, gcd(a, n) > 1 except if a = 1. This leads to φ(n) = 1, which contradicts the property above.