Prime Number

ooellis

I was discussing something with my friends today. If you take the product of the first n primes and add 1 will this give you a prime number?

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?

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.

ooellis

Yes but what about the primes that are larger than the primes that went into it but still smaller than number in question. I know 2311 is prime, but there are still many primes larger than 7 but less than 2311. Maybe eventually there is somewhere that it breaks down, then again maybe it won't...

IamNameless

I don't think it breaks down either, that is used in the theorem in finding that there are infinite amount of primes. So they must have proved that at some time too (though I couldn't find it). I've been interested in this also, since I noticed it.

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. ;)

lurflurf

from
http://ansuz.sooke.bc.ca/creative/te...gest-prime.php
"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."

ooellis

Good call Lurflurf.

Thanks

ktm

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. It's not necessarily a prime itself (though it could be), but it is an interesting number in its own right.

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.

Aeneas

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.

IamNameless

If it can produce either a prime or a composite, how do you know which one you found? And if you found a composite number wouldn't that make the proof meaningless? I don't get it :(

morphism

Euclid's proof assumes that you're taking the product of ALL the primes then adding one. Since clearly any number of the form p_1 * p_2 * ... * p_n + 1 isn't going to be divisible by any of the primes p_1, ..., p_n, we must conclude that its prime factors are different from those n ones (and being an integer greater than 1, it does have prime factors), hence there must be a prime not in the set {p_1, ..., p_n}.

IamNameless

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

ktm

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"?

Aeneas

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.

CRGreathouse

Yep. It only works for 2, 3, 5, 7, 11, 31, 379, 1019, ... = A005234.

lurflurf

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