Generalizing Euclid's ProofEuclid demonstrated that there are an infinite number of primes  or that no largest prime exists. His proof may be generalized to develop a method of searching for unknown primes. 
Section 1: Written 1999, Formatted 2010 Section 2: Written April 2011 

Euclid's Proof Start by assuming that you know all the primes that exist. For example, suppose that you know only six prime numbers: 2,3,5,7,11,13. To demonstrate the existence of another prime, just multiply all those numbers together and add one: P = 2*3*5*7*11*13 + 1 = 30031. This new number can not be a multiple of any of the primes in our list. That is, if we divide this number by any of the primes in our list the remainder will be 1. Thus, either this new number is prime or it is the product of two unknown primes. 


The Generalization By the same reasoning: We may take our list of primes break it into two groups and add the groups. The new number generated will not be in our list. As a result it will identify a new prime. To demonstrate lets assume the only known primes are: 2,3,5,7.
We may also use subtraction instead of addition:
All of the new numbers we have produced are primes, or the product of primes not in our list. A more rigorous demonstration of this could be used to create "family trees of primes". For example, all the numbers generated above would be called the offspring of 2,3,5&7. This method does a pretty good job of locating primes. However, like all other methods, it fails to find all primes, and it incorrectly finds some composites. Is there any significance to the primes that are missing from the family trees, or the composites that get included? Can this idea be extended further? Tell us. 
Related Pages at this site:
Readings: 

Method 2: Patterns with Holes We can factor a list of primes out of any arithmetic sequence, particularly the whole numbers. If we do so the factors will form a symmetric pattern where the length is the product of all the primes in the pattern: PL = p1*p2*p3*p4….. The number of elements in that sequence not a multiple of any of those
primes (which we will call "holes") can be determined with a
simple product by subtracting one from each prime: n(H) = (p11)(p21)(p31)(p41)…..
[Reasoning: One number out of p will be a multiple of p the rest will
not.] Each of these holes must be either a new prime, or a prime not already
in our list. The longer our list of primes gets, the more holes, and consequently
new primes, must appear in our pattern.


