to the contrary that no such p exists (an application of proof by contradiction). Then all primes are smaller than or equal to , and we may form the list of them all. Let be the product of all primes and . Because is larger than all prime numbers it is not prime, hence it must be divisible by one of them, say . Now both and are divisible by , hence so is their difference , 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 Examples of refutations by contradiction The following examples are commonly referred to as proofs by contradiction, but formally employ refutation by contradiction (and therefore are intuitionistically valid). Infinitude of primes Let us take a second look at Euclid's theorem – Book IX, Proposition 20: Prime numbers are more than any assigned multitude of prime numbers. We may read the statement as saying that for every finite list of primes, there is another prime not on that list, which is arguably closer to and in the same spirit as Euclid's original formulation. In this case Euclid's proof applies refutation by contradiction at one step, as follows. Given any finite list of prime numbers , it will be shown that at least one additional prime number not in this list exists. Let be the product of all the listed primes and a prime factor of , possibly itself. We claim that is not in the given list of primes. Suppose to the contrary that it were (an application of refutation by contradiction). Then would divide both and , therefore also their difference, which is . This gives a contradiction, since no prime number divides 1. Irrationality of the square root of 2 The classic proof that the square root of 2 is irrational is a refutation by contradiction. Indeed, we set out to prove the negation ¬ ∃ a, b ∈ . a/b = by assuming that there exist natural numbers a and b whose ratio is the square root of two, and derive a contradiction. Proof by infinite descent Proof by infinite descent is a method of proof whereby a smallest object with desired property is shown not to exist as follows: Assume that there is a smallest object with the desired property. Demonstrate that an even smaller