Generalizing Euclid's Proof

Euclid 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.

  • 2 + 3*5*7 = 107
  • 3 + 2*5*7 = 73
  • 5 + 2*3*7 = 47
  • 7 + 2*3*5 = 37
  • 2*3 + 5*7 = 41
  • 2*5 + 3*7 = 31
  • 2*7 + 3*5 = 29
  • etc

We may also use subtraction instead of addition:

  • 3*5*7 - 2 = 103
  • 2*5*7 - 3 = 67
  • 2*3*7 - 5 = 37
  • 2*3*5 - 7 = 23
  • etc

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) = (p1-1)(p2-1)(p3-1)(p4-1)….. [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.
Thus, every new prime we add to our list results in an even longer pattern which contains even more holes which are not multiples of any of the primes in our list.

Sequence Critical Factors    
0 2,3,5    
1 hole    
2 2    
3 3    
4 2    
5 5    
6 2,3    
7 hole    
8 2    
9 3    
10 2,5    
11 hole    
12 2,3    
13 hole \  
14 2 \  
15 3,5 Symmetry  
16 2 /  
17 hole /  
18 2,3    
19 hole    
20 2,5    
21 3    
22 2    
23 hole    
24 2,3    
25 5    
26 2    
27 3    
28 2    
29 hole    
30 2,3,5    

Example: Consider the primes 2,3,and 5. Together they define sequences with a pattern length of PL = 2*3*5 = 30. These patterns will have holes: n(H) = (2-1)(3-1)(5-1) = 9

Note: This method was developed by studying Goldbach's Conjecture and was expanded into a possible approach to Goldbach's Conjecture.

 
 

Return to: