- #1

- 4

- 0

For instance:

2*3 +1 = 7 ------> prime

2*3*5 +1 = 31 -------> prime

2*3*5*7 + 1 = 2311 ------> prime

Can anybody find if/where this breaks down and why?

- Thread starter ooellis
- Start date

- #1

- 4

- 0

For instance:

2*3 +1 = 7 ------> prime

2*3*5 +1 = 31 -------> prime

2*3*5*7 + 1 = 2311 ------> prime

Can anybody find if/where this breaks down and why?

- #2

Daniel Y.

I don't believe this pattern will break down. When you multiply the prime number by the next prime number, it is obvious the product is divisible by the (prime) number you just multiplied it by. However, when you add 1 to the product, this removes any possibility of dividing the sum by the factors that went into it.

For instance:

2*3 +1 = 7 ------> prime

2*3*5 +1 = 31 -------> prime

2*3*5*7 + 1 = 2311 ------> prime

Can anybody find if/where this breaks down and why?

- #3

- 4

- 0

- #4

- 22

- 0

- #5

Daniel Y.

That is very true, and we obviously do not know whether or not it will 'break down' somewhere.

There are two types of proofs, a mathematical induction, and an empirical induction. An empirical induction is usually just going through many cases of the theory and testing it to see if it is true. The more times the theory holds up, the greater its chance of being a correct theory, but can never be proven, since you cannot go through an infinite set of numbers. However, mathematical induction is a process by which a theory is proven to be true for all values, without having to go through an impossible set of data to prove the theory. Such an induction may be possible for your prime number theory, but I am too tired tonight to attempt it. ;)

- #6

lurflurf

Homework Helper

- 2,432

- 132

from

http://ansuz.sooke.bc.ca/creative/teebee/no-largest-prime.php [Broken]

"2, 3, 5, 7, 11, 13.

2 x 3 x 5 x 7 x 11 x 13 = 30030.

Add 1, you get 30031.

But 30031 = 59 x 509, so it's not prime.

The procedure doesn't always generate primes."

http://ansuz.sooke.bc.ca/creative/teebee/no-largest-prime.php [Broken]

"2, 3, 5, 7, 11, 13.

2 x 3 x 5 x 7 x 11 x 13 = 30030.

Add 1, you get 30031.

But 30031 = 59 x 509, so it's not prime.

The procedure doesn't always generate primes."

Last edited by a moderator:

- #7

- 4

- 0

Good call Lurflurf.

Thanks

Thanks

- #8

- 14

- 0

This is concisely explained by modular arithmetic, i.e. [tex]p_{1}p_{2}p_{3}...p_{n} + 1 \equiv 1 \pmod{p_{k}}[/tex] with k a natural less than or equal to n.

Now here's an exercise for you: prove that there's an infinite number of primes.

- #9

- 27

- 0

Euclid did it in Book 9, Proposition 20 - but it is often stated slightly wrongly as in the original post. Multiplying the first n primes and adding 1 gives EITHER a new prime OR a composite number having a prime factor not in the original list. This proves that the number of primes is infinite.If you take the product of the first n primes and add 1, then it gives you a number that's not divisible by any of the first n primes.

Now here's an exercise for you: prove that there's an infinite number of primes.

Last edited:

- #10

- 22

- 0

- #11

morphism

Science Advisor

Homework Helper

- 2,015

- 4

- #12

- 22

- 0

Oh I see, I suppose I should have thought about that a little more. Thanks.

- #13

- 14

- 0

1. I did not state it incorrectly. What I said has many implications, which I did not mention, so that he could figure it out for himself.Euclid did it in Book 9, Proposition 20 - but it is often stated slightly wrongly as in the original post. Multiplying the first n primes and adding 1 gives EITHER a new prime OR a composite number having a prime factor not in the original list. This proves that the number of primes is infinite.

2. If I suggested that he figure out the proof of infinite primes for himself, why would you post a proof of it?

3. "slightly wrongly"?

- #14

- 27

- 0

Sorry KTM. By 'original posts' (I missed off the 's') I meant the ones at the start of the thread, not yours. The point I was trying to make is that it is a common misconception that Euclid's proof rests on multiplying together any 'assigned multitude of prime numbers' (Heath) and adding one to necessarily get a new prime. It is 'slighly wrong' in that you only have to add '..or number with a new prime factor' to make it right. Euclid actually starts by imagining three known primes and showing that there are more than that, so it is in effect a proof of the infinity of primes by induction.1. I did not state it incorrectly. What I said has many implications, which I did not mention, so that he could figure it out for himself.

2. If I suggested that he figure out the proof of infinite primes for himself, why would you post a proof of it?

3. "slightly wrongly"?

- #15

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

Yep. It only works for 2, 3, 5, 7, 11, 31, 379, 1019, ... = http://www.research.att.com/~njas/sequences/A005234 [Broken].from

http://ansuz.sooke.bc.ca/creative/teebee/no-largest-prime.php [Broken]

"2, 3, 5, 7, 11, 13.

2 x 3 x 5 x 7 x 11 x 13 = 30030.

Add 1, you get 30031.

But 30031 = 59 x 509, so it's not prime.

The procedure doesn't always generate primes."

Last edited by a moderator:

- #16

lurflurf

Homework Helper

- 2,432

- 132

This is very simple

We wish to show there are an infinite number of primes

it is sufficent to show that given any finite collection of primes we may find one new one

say we know p1,p2,...,pn-1,pn

consider x=1+p1*p2*...*pn-1*pn

x may be prime or composite we do not care

what is important is that x has at least one prime factor that is not one of

p1,p2,...,pn-1,pn