Yet another proof that primes are infinite

March 10, 2020 · by · in bu-cs131-discrete-mathematics, Uncategorized · Leave a comment

In CS131, we see the “Proof from the Book” due to Euclide that the number of prime numbers is infinite. Here is another favorite proof that is based on elementary facts. Suppose that 2,3,5,\ldots,p is a list of all the primes. From what we have learnt about the  sum of geometric progressions we know that for any n:

1+\frac{1}{2}+\frac{1}{2^2}+\ldots+\frac{1}{2^n} < \frac{1}{1-\frac{1}{2}},

1+\frac{1}{3}+\frac{1}{3^2}+\ldots+\frac{1}{3^n} < \frac{1}{1-\frac{1}{3}},

\vdots

1+\frac{1}{p}+\frac{1}{p^2}+\ldots+\frac{1}{p^n} < \frac{1}{1-\frac{1}{p}}.

Multiplying these inequalities term by term, we obtain:

(1+\frac{1}{2}+\ldots+\frac{1}{2^n} )\times \ldots \times (1+\frac{1}{p}+\ldots +\frac{1}{p^n} )  < \frac{1}{ (1-\frac{1}{2})\cdot(1-\frac{1}{3})\cdot \ldots \cdot (1-\frac{1}{p})}

Observe the following.

  • The LHS of the inequality is  strictly greater than S_n = 1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\ldots+\frac{1}{2^n}>1+\frac{1}{2}+2\frac{1}{4}+4\frac{1}{8}+\ldots+2^{n-1} \frac{1}{2^n} =1+\frac{n}{2}.

By combining the above, we derive the conclusion that for any n,  the RHS is greater than \frac{n}{2}+1. Contradiction, since assuming that we have a finite number of primes, the RHS should be finite. Therefore, the set of prime numbers is infinite.

Leave a Reply

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

Gravatar
WordPress.com Logo

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

Facebook photo

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

Cancel

Connecting to %s

%d bloggers like this: