Editing Proof by contradiction (section)

===Infinitude of primes===

[[Euclid's theorem]] states that there are infinitely many primes. In [[Euclid's Elements]] the theorem is stated in Book IX, Proposition 20:<ref name="mathcs_clarku_edu">{{cite web | url=https://mathcs.clarku.edu/~djoyce/elements/bookIX/propIX20.html | title=Euclid's Elements, Book 9, Proposition 20 | access-date=2 October 2022}}</ref>

: Prime numbers are more than any assigned multitude of prime numbers.

Depending on how we formally write the above statement, the usual proof takes either the form of a proof by contradiction or a refutation by contradiction. We present here the former, see below how the proof is done as refutation by contradiction.

If we formally express Euclid's theorem as saying that for every natural number <math>n</math> there is a prime bigger than it, then we employ proof by contradiction, as follows.

Given any number <math>n</math>, we seek to prove that there is a prime larger than <math>n</math>. Suppose to the contrary that no such ''p'' exists (an application of proof by contradiction). Then all primes are smaller than or equal to <math>n</math>, and we may form the list <math>p_1, \ldots, p_k</math> of them all. Let <math>P = p_1 \cdot \ldots \cdot p_k</math> be the product of all primes and <math>Q = P + 1</math>. Because <math>Q</math> is larger than all prime numbers it is not prime, hence it must be divisible by one of them, say <math>p_i</math>. Now both <math>P</math> and <math>Q</math> are divisible by <math>p_i</math>, hence so is their difference <math>Q - P = 1</math>, but this cannot be because 1 is not divisible by any primes. Hence we have a contradiction and so there is a prime number bigger than <math>n</math>.