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:
“There is no better proof of a man’s being truly good than his desiring to be constantly under the observation of good men.”
—François, Duc De La Rochefoucauld (1613–1680)
“The mother’s and father’s attitudes toward the child correspond to the child’s own needs.... Mother has the function of making him secure in life, father has the function of teaching him, guiding him to cope with those problems with which the particular society the child has been born into confronts him.”
—Erich Fromm (1900–1980)