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:
“The source of Pyrrhonism comes from failing to distinguish between a demonstration, a proof and a probability. A demonstration supposes that the contradictory idea is impossible; a proof of fact is where all the reasons lead to belief, without there being any pretext for doubt; a probability is where the reasons for belief are stronger than those for doubting.”
—Andrew Michael Ramsay (1686–1743)
“Literature does not exist in a vacuum. Writers as such have a definite social function exactly proportional to their ability as writers. This is their main use.”
—Ezra Pound (1885–1972)