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 p1, p2, ..., pr and consider the integer n = p1p2 ... pr. Any natural number a ≤ n has a prime divisor q. Then, q must be one of p1, p2, ..., pr, 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.
Read more about this topic: Euclid's Theorem
Famous quotes containing the words proof and/or function:
“Ah! I have penetrated to those meadows on the morning of many a first spring day, jumping from hummock to hummock, from willow root to willow root, when the wild river valley and the woods were bathed in so pure and bright a light as would have waked the dead, if they had been slumbering in their graves, as some suppose. There needs no stronger proof of immortality. All things must live in such a light. O Death, where was thy sting? O Grave, where was thy victory, then?”
—Henry David Thoreau (18171862)
“It is not the function of our Government to keep the citizen from falling into error; it is the function of the citizen to keep the Government from falling into error.”
—Robert H. [Houghwout] Jackson (18921954)