Nerdy Math Question for Nerdy Math Nerds (Twin Prime Conjecture)

Exellus

Member
Oct 30, 2017
848
Euclid's theorem states:

Consider any finite list of prime numbers p1, p2, ..., pn. It will be shown that at least one additional prime number not in this list exists. Let P be the product of all the prime numbers in the list: P = p1p2...pn. Let q = P + 1. Then q is either prime or not:

  • If q is prime, then there is at least one more prime that is not in the list.
  • If q is not prime, then some prime factor p divides q. If this factor p were in our list, then it would divide P (since P is the product of every number in the list); but p divides P + 1 = q. If p divides P and q, then p would have to divide the difference[3] of the two numbers, which is (P + 1) − P or just 1. Since no prime number divides 1, p cannot be on the list. This means that at least one more prime number exists beyond those in the list.
This proves that for every finite list of prime numbers there is a prime number not in the list, and therefore there must be infinitely many prime numbers.

My question:

Does this theorem also hold if you let q = P - 1?

Wouldn't P-1 also be necessarily a new prime number? And if so, it and P+1 would be a set of twin primes.


So the proof would be:

Assume there are a finite number of twin primes such that P(n+1) - P(n) = 2

Then, from the final set of twin primes, choose the larger of these two primes P(n+1). Calculate S=p1p2...P(n+1). So you now have a product of all primes up to P(n+1). Call this S. S + 1 is a prime number and so is S - 1. This is a new set of twin primes not in our original list, thus there cannot be a finite list of twin primes.

Of course if S - 1 is not prime, then this falls apart.
 
Last edited:
OP
OP
Exellus

Exellus

Member
Oct 30, 2017
848
I'm hoping there's something clearly wrong with this, because it seems like an obvious proof to me.
 
Jan 26, 2019
2
You're ignoring the "If q is not prime " part here's a counter example to your proof:
2*3*5*7*11*13 = 30030
30031 = 59 * 509

Simply put there is no guarantee that given S=p1p2...P(n+1), S + 1 is prime.
 

Feep

Lead Designer, Iridium Studios
Verified
Oct 25, 2017
1,293
I could be wrong, but I don't think it works like that.

The purpose of the original Euclid's proof is to show that there being a finite set of primes is a *contradiction*. Which is to say, we know it's false, so in *reality*, we don't know if P+1 or P-1 is necessarily prime.

Therefore, you can't use the fact that P+1 and P-1 are primes to proof infinitely many twin primes. I think. However, I'm pretty sure there are infinite twin primes anyway. (EDIT: This is an unsolved problem, apparently, as there was a flaw with a proof published in 2004. So, I'm pretty sure that backs me up on this one, if no one has managed it. ^^)

As far as your original question, which is does the proof hold up with P-1, I believe it does.
 

Masoyama

Member
Oct 27, 2017
3,967
You have a fundamental misunderstanding. Euclids theorem states that there are an infinite number of prime numbers. You showed one proof of the theorem, but that does not mean its the only proof. You can prove a theorem through many different methods. You cannot just break a proof for one theorem in half, and then add more assumptions to prove something else.
 

low-G

Member
Oct 25, 2017
5,869
P, P+1, and P-1 can't all be prime, one of them would be divisible by 3 (P in this case).

maybe I'm missing what you're trying to say.
 

Feep

Lead Designer, Iridium Studios
Verified
Oct 25, 2017
1,293
P, P+1, and P-1 can't all be prime, one of them would be divisible by 3 (P in this case).

maybe I'm missing what you're trying to say.
P was never prime; it is the multiplicative result of every prime in a theoretical list of finite primes.
 

Feep

Lead Designer, Iridium Studios
Verified
Oct 25, 2017
1,293
Well, I'm not sure what OP is trying to say. I guess he's just trying to find another proof of infinite primes, but prime+1 isn't always prime.
He's attempting to use P+1 and P-1 as proof of infinitely many "twin" primes, which are primes that are 2 apart from each other. e.g. 3 and 5, 17 and 19. Buuuut it doesn't quite work that way.

As an example for when P+1 is not prime, look at 2*3*5*7*11*13 + 1 = 30,031. 30,031 is not prime. The conjecture is only used in a hypothetical scenario where there are finite primes, but in reality, there are infinitely many.
 

KarmaCow

Member
Oct 25, 2017
3,815
Maybe I'm missing something but isn't the issue that P+1 isn't necessarily prime? It could be, it could also be divisible by a prime number not in the set that formed P in the first place.
 
Oct 27, 2017
96
Incidentally, numbers like P+1 or P-1, where P is the product of the first n primes, are sometimes called "Euclid numbers", and as others have observed they don't have to be primes themselves. But just how many of them are primes? Infinitely many? Nobody knows! It's an open problem.
 

Xe4

Member
Oct 25, 2017
8,433
Yeah as you said, the reason the proof works is because of the fundamental theorem of arithmetic guaranteeing unique roots. As such multiplying all the primes {p1, p2, ..., pn} in a finite set to get P and adding 1 to be P+1 will produce a number that is either prime or not uniquely factorizable, hence a contraditiction. But it doesn't indicate anything about either P + 1 or P - 1 being prime themselves.

You already gave the counter example to P - 1, but one that is a counter example of both is 2*3*5*7*11*13*17 = 510510, of which both 510511 and 510509 are non prime, but neither of which are either uniquely factorizable by any of the primes in our finite set. There's nothing that says this cannot be true after some number N that is very large, though this is unlikely given the insanely huge numbers it has been tested to.

Cool thought though. Intresting to think about.
 

GravaGravity

Member
Oct 27, 2017
180
When are those cowards at Era HQ going to add scientific notation?

Serious tho that kind of formatting would make it a lot easier to follow and understand this sort of thing.