Euclid's theorem
Euclid's theorem states that there are infinitely many primes.
Theorem: There are infinitely many primes.
Proof by cases: Consider any finite set of primes. It will be shown that at least one more prime exists outside of this set: $$\set{p_1, p_2, p_3, ... p_n}$$ Now, let \(P\) be the product of all these primes: $$P = p_1 \times p_2 \times p_3 \times ... \times p_n$$ Add \(1\) to \(P\), and call this integer \(q\): $$q = P + 1 = p_1 \times p_2 \times p_3 \times ... \times p_n + 1$$ Like all integers, \(q\) is either prime or not. This brings us to two possible cases.
1. \(q\) is prime
If \(q\) is prime, then there is a prime that exists outside the finite set, \(q.\) It cannot already exist in the finite set because \(q\) is the product of all the primes in the set plus \(1.\)
2. \(q\) is not prime (composite)
If \(q\) is composite, then some prime factor \(p\) divides \(q.\) \(p\) could exist inside or outside the finite set. If \(p\) is outside the finite set, then we're done, and we've shown that a prime, \(p\), exists outside the finite set. However, suppose \(p\) is inside the finite set. In that case, \(p\) divides \(P\), since \(P\) was defined as the product of all the primes in that finite set: $$p \mid P$$ And as previously mentioned, \(p\) also divides \(q\): $$p \mid q$$ If \(p\) divides \(P\) and \(q\), it must also divide their difference (since that is a linear combination of \(P\) and \(q\)): $$p \mid (q - P)$$ Remember that \(q = P + 1\): $$p \mid ((P + 1) - P)$$ $$p \mid 1$$ It is impossible for a prime to divide \(1.\) The only positive integer that can divide \(1\) is itself. So, there's no way for the prime factor \(p\) to be in the finite set of primes. Therefore, a prime exists outside the finite set and it is \(p.\) \(■\)
Proof by cases: Consider any finite set of primes. It will be shown that at least one more prime exists outside of this set: $$\set{p_1, p_2, p_3, ... p_n}$$ Now, let \(P\) be the product of all these primes: $$P = p_1 \times p_2 \times p_3 \times ... \times p_n$$ Add \(1\) to \(P\), and call this integer \(q\): $$q = P + 1 = p_1 \times p_2 \times p_3 \times ... \times p_n + 1$$ Like all integers, \(q\) is either prime or not. This brings us to two possible cases.
1. \(q\) is prime
If \(q\) is prime, then there is a prime that exists outside the finite set, \(q.\) It cannot already exist in the finite set because \(q\) is the product of all the primes in the set plus \(1.\)
2. \(q\) is not prime (composite)
If \(q\) is composite, then some prime factor \(p\) divides \(q.\) \(p\) could exist inside or outside the finite set. If \(p\) is outside the finite set, then we're done, and we've shown that a prime, \(p\), exists outside the finite set. However, suppose \(p\) is inside the finite set. In that case, \(p\) divides \(P\), since \(P\) was defined as the product of all the primes in that finite set: $$p \mid P$$ And as previously mentioned, \(p\) also divides \(q\): $$p \mid q$$ If \(p\) divides \(P\) and \(q\), it must also divide their difference (since that is a linear combination of \(P\) and \(q\)): $$p \mid (q - P)$$ Remember that \(q = P + 1\): $$p \mid ((P + 1) - P)$$ $$p \mid 1$$ It is impossible for a prime to divide \(1.\) The only positive integer that can divide \(1\) is itself. So, there's no way for the prime factor \(p\) to be in the finite set of primes. Therefore, a prime exists outside the finite set and it is \(p.\) \(■\)
⚠ Often, this proof is needlessly formulated as a proof by
contradiction. Make no mistake. Thousands of years ago, Euclid proved this theorem directly, as
shown above. The assumption that the finite set consists of all primes is totally unnecessary, and
honestly, making the proof indirect weakens it.
Well, it looks like we'll never run out of primes! So, if in an application, you need a larger prime, keep looking, and you will find one given enough time. Although, as the prime number theorem states, this could be a really long time.