proof of the infinitude of primes Archives

More examples of proof by contradiction

July 1, 2011 GB High School Geometry, High School Mathematics, Problem Solving and Proofs

We have had good discussions on mathematical proofs, so I am planning to create a mathematical proof series that will discuss the basics such as direct proof, indirect proof, and proof by mathematical induction. But before I do that, let me continue with more examples of proof by contradiction.

Proof by contradiction, as we have discussed, is a proof strategy where you assume the opposite of a statement, and then find a contradiction somewhere in your proof. Finding a contradiction means that your assumption is false and therefore the statement is true. Below are several more examples of this proof strategy.

Example 1: $\sqrt{2}$ irrational.

Example 2: $\sqrt{6}$ is irrational. The proof of this is basically the same as example 1, so it is left as an exercise.

Example 3: Proof that there are infinitely many primes.

Example 4: Knights and Liars

Example 5: $\sqrt{2} + \sqrt{3}$ is irrational. » Read more

3 comments irrationality of square root of 2, mathematical proofs, proof by contradiction, proof of the infinitude of primes, proof strategies

Formal Proof of the Infinitude of Primes

August 23, 2010 GB College Mathematics, Number Theory

In the Infinitude of Primes post, we have shown intuitively that there are infinitely many primes. In this post, we use our intuitive proof to create a more formal proof. The proof was supposedly constructed by Euclid and was shown in his book, The Elements.

Euclid (via Wikimedia)

We are going to use the proof strategy called proof by contradiction. Our proof is summarized as follows: » Read more

Leave a comment are primes finite, euclid's proof of the infinitude of primes, infinitude of primes, proof by contradiction, proof of the infinitude of primes

Prime Series 2: The Intuition Behind The Infinitude of Prime Numbers

June 21, 2010 GB College Mathematics, Number Theory

Note: This is the third part of the Prime Number Series

Part I: Introduction to Prime Numbers
Part III: Formal Proof of the Infinitude of Prime Numbers

In Introduction to Prime Numbers, we conjectured that the number of prime numbers is decreasing as the counting numbers increase. In this post, we discuss intuitively that there is no greatest prime, or that there are infinitely many prime numbers.

Before proceeding with our discussion, it is noteworthy to remember that a number can either be prime or composite. We also know that composite numbers are product of primes.

Fragment of the original "Elements" by Euclid (via Wikimedia).