Take any finite list of prime numbers p1, p2, ..., pn. It will be shown that some additional prime numbers not in this list exist. Let P be the product of all the prime numbers in the list:

P = p1p2...pn. Let q = P + 1: 1 more than this product. Then, q is either prime or not:

- If q is prime then there is at least one more prime than is listed.

- If q is not prime then some prime factor p divides q.

This factor p is not on our list: if it were, then it would divide P (since P is the product of every number on the list); but as we know, p divides P + 1 = q. Then p would have to divide the difference of the two numbers* which is (P + 1) − P or just 1. But no prime number divides 1 so there would be a contradiction, and therefore p cannot be on the list. This means at least one more prime number exists beyond those in the list. (Wikipedia)

* If some integer

*k*divides two integers

*a*,

*b*then

*k*divides

*a-b*.

This will be immediate to some, but I'll provide a small proof of that fact for clarity's sake.

Proof:

*k*divides

*a*-->

*a = kx*, where x is an integer, by def. of "divides"

*k*divides

*b*-->

*b = ky*, where y is an integer, by def. of "divides"

*a-b = kx - ky = k(x-y)*

but

*x-y*is an integer

Hence

*k*divides

*a-b*, by definition of "divides".

## No comments:

Post a Comment