Euclid’s Proof of the Infinitude of Primes

The oldest known proof that there are infinite number of primes is the one that is due to Euclid (around 300 BC). It is probably the most accessible. So I start the blog by stating this proof.

________________________________________________________

Theorem. There are infinitely many prime numbers.

The strategy is to show that given a finite list of prime numbers \left\{p_1, p_2, \cdots, p_n \right\}, we can always find another prime number not on the list.

Let n=p_1 \times p_2 \times \cdots \times p_n. Let p be a prime divisor of n+1. If p is on the list \left\{p_1, p_2, \cdots, p_n \right\}, then p would divide both n+1 and n. This means that p would divide 1 (the difference of n and n+1). This is impossible. So p must a prime number not on the original list. Hence there must be infinitely many prime numbers.

________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

\text{ }

Advertisements

One thought on “Euclid’s Proof of the Infinitude of Primes

  1. Pingback: Tweaking a proof of the infinitude of primes | Exploring Number Theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s