Infinitude of the primes
The Fundamental Theorem of Arithmetic states that every integer greater than 1 is either a prime number, or is the product of prime numbers, and that the product is unique up to changing the order of the factors. A version of this result appears in Book VII of Euclid's Elements, a 13 volume mathematical treatise which was written in about 300 BC.
In Book IX of Elements, Euclid used these ideas to construct the following famous argument, which proves that there are infinitely many primes. Suppose that p_1, p_2, ..., p_n is any finite list of distinct prime numbers and let P be the product of all of them. Since the number P+1 leaves remainder 1 when divided by any of the primes p_1, p_2, ..., p_n, it cannot have any of them as a factor. It follows that P+1 is either prime itself or has a prime factor not on the original list, which means that the original list must have been incomplete. The conclusion is that there must in fact be infinitely many prime numbers.
In his mathematical blog Cut The Knot, +Alexander Bogomolny describes a simple proof of the infinitude of the primes that was new to me. The argument constructs an explicit number, f(n), which has at least n+1 distinct prime factors. This shows that arbitrarily large finite sets of prime numbers exist, from which it follows that the set of primes is infinite.
The argument, which is summarized in the picture, relies on the polynomial factorization x^4 + x^2 + 1 = (x^2 – x + 1)(x^2 + x + 1). One key point about the factorization is that if x is a positive integer, the factors x^2 – x + 1 and x^2 + x + 1 are coprime (i.e., relatively prime) numbers. What this means is that they have no positive integer factors in common, other than 1.
The reason that the factors x^2 – x + 1 and x^2 + x + 1 are coprime is that any factor common to both of them, say c, would also have to divide the difference of x^2 + x + 1 and x^2 – x + 1, which is 2x. The numbers x^2 + x + 1 and x^2 – x + 1 are both odd, which forces c to divide x. However, x^2 + x + 1 and x^2 – x + 1 both leave a remainder of 1 when divided by x, which means that they also leave a remainder of 1 when divided by c, and this can only happen if c=1.
The proof can then be completed by the standard technique of mathematical induction. If n=0, the formula for f(n) shows that f(0)=2^2 + 2^1 + 1 = 7, which is the product of n+1 primes (a single prime in this case) as claimed. If we substitute the integer x=2^{2^{n-1}} into the identity x^4 + x^2 + 1 = (x^2 – x + 1)(x^2 + x + 1), we obtain the equation f(n)=(x^2 – x + 1)f(n–1). We may assume by induction that f(n–1) is a product of (n–1)+1=n distinct primes. Since x^2 – x + 1 is coprime to f(n–1), it follows that the prime factors of x^2 – x + 1 are all different from those of f(n–1), and thus that f(n) has at least n+1 distinct prime factors.
Relevant links
+Alexander Bogomolny's original blog post can be found here: http://www.cut-the-knot.org/proofs/InfinitudeOfPrimesViaPowersOfTwo.shtml
The values of f(n) appear in The On-Line Encyclopedia of Integer Sequences at http://oeis.org/A220161, although this application of the sequence is not (yet) mentioned there. The first four values of the sequence are 7, 21 (=3x7), 273 (=3x7x13), and 65793 (=3x7x13x241).
Euclid of Alexandria: http://en.wikipedia.org/wiki/Euclid
Euclid's Elements: http://en.wikipedia.org/wiki/Euclid's_Elements
Fundamental Theorem of Arithmetic: http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic
This would have made a good examination question for an undergraduate number theory course.
#mathematics #sciencesunday
The Fundamental Theorem of Arithmetic states that every integer greater than 1 is either a prime number, or is the product of prime numbers, and that the product is unique up to changing the order of the factors. A version of this result appears in Book VII of Euclid's Elements, a 13 volume mathematical treatise which was written in about 300 BC.
In Book IX of Elements, Euclid used these ideas to construct the following famous argument, which proves that there are infinitely many primes. Suppose that p_1, p_2, ..., p_n is any finite list of distinct prime numbers and let P be the product of all of them. Since the number P+1 leaves remainder 1 when divided by any of the primes p_1, p_2, ..., p_n, it cannot have any of them as a factor. It follows that P+1 is either prime itself or has a prime factor not on the original list, which means that the original list must have been incomplete. The conclusion is that there must in fact be infinitely many prime numbers.
In his mathematical blog Cut The Knot, +Alexander Bogomolny describes a simple proof of the infinitude of the primes that was new to me. The argument constructs an explicit number, f(n), which has at least n+1 distinct prime factors. This shows that arbitrarily large finite sets of prime numbers exist, from which it follows that the set of primes is infinite.
The argument, which is summarized in the picture, relies on the polynomial factorization x^4 + x^2 + 1 = (x^2 – x + 1)(x^2 + x + 1). One key point about the factorization is that if x is a positive integer, the factors x^2 – x + 1 and x^2 + x + 1 are coprime (i.e., relatively prime) numbers. What this means is that they have no positive integer factors in common, other than 1.
The reason that the factors x^2 – x + 1 and x^2 + x + 1 are coprime is that any factor common to both of them, say c, would also have to divide the difference of x^2 + x + 1 and x^2 – x + 1, which is 2x. The numbers x^2 + x + 1 and x^2 – x + 1 are both odd, which forces c to divide x. However, x^2 + x + 1 and x^2 – x + 1 both leave a remainder of 1 when divided by x, which means that they also leave a remainder of 1 when divided by c, and this can only happen if c=1.
The proof can then be completed by the standard technique of mathematical induction. If n=0, the formula for f(n) shows that f(0)=2^2 + 2^1 + 1 = 7, which is the product of n+1 primes (a single prime in this case) as claimed. If we substitute the integer x=2^{2^{n-1}} into the identity x^4 + x^2 + 1 = (x^2 – x + 1)(x^2 + x + 1), we obtain the equation f(n)=(x^2 – x + 1)f(n–1). We may assume by induction that f(n–1) is a product of (n–1)+1=n distinct primes. Since x^2 – x + 1 is coprime to f(n–1), it follows that the prime factors of x^2 – x + 1 are all different from those of f(n–1), and thus that f(n) has at least n+1 distinct prime factors.
Relevant links
+Alexander Bogomolny's original blog post can be found here: http://www.cut-the-knot.org/proofs/InfinitudeOfPrimesViaPowersOfTwo.shtml
The values of f(n) appear in The On-Line Encyclopedia of Integer Sequences at http://oeis.org/A220161, although this application of the sequence is not (yet) mentioned there. The first four values of the sequence are 7, 21 (=3x7), 273 (=3x7x13), and 65793 (=3x7x13x241).
Euclid of Alexandria: http://en.wikipedia.org/wiki/Euclid
Euclid's Elements: http://en.wikipedia.org/wiki/Euclid's_Elements
Fundamental Theorem of Arithmetic: http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic
This would have made a good examination question for an undergraduate number theory course.
#mathematics #sciencesunday
