Interesting Question


by Aditya89
Tags: interesting
Aditya89
Aditya89 is offline
#1
Jan5-06, 05:14 AM
P: 23
Hey guys, u know how Euclid proved that primes r infinite. Now knowing that primes r infinite, if we take some primes p1, p2, p3,.....,pn then will p1*p2*.......*pn(+/-)1 always be prime?
Phys.Org News Partner Science news on Phys.org
Simplicity is key to co-operative robots
Chemical vapor deposition used to grow atomic layer materials on top of each other
Earliest ancestor of land herbivores discovered
Muzza
Muzza is offline
#2
Jan5-06, 05:48 AM
P: 696
No. 5 - 1 and 5 + 1 are not prime, for example.
HallsofIvy
HallsofIvy is offline
#3
Jan5-06, 08:38 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,879
Quote Quote by Muzza
No. 5 - 1 and 5 + 1 are not prime, for example.
Since 5 is not a product of primes, I don't see how that is relevant.

The point was that Euclid showed that, if there exist only a finite number of primes, p1, p2, ..., pn, then their product plus 1 is not divisible by any of p1,..., pn and so is either prime itself or is divisible by a prime not in the original list- in either case a contradiction.
Aditya89's question was whether that must, in fact, always be a prime. I don't believe so but I don't see a proof offhand.

Muzza
Muzza is offline
#4
Jan5-06, 09:42 AM
P: 696

Interesting Question


if we take some primes p1, p2, p3,.....,pn then will p1*p2*.......*pn(+/-)1 always be prime?
Since 5 is not a product of primes, I don't see how that is relevant.
It's perfectly relevant. Let n = 1 and p_1 = 5.

But if you for some odd reason believe that n = 1 is forbidden, consider 2*3*5*7 - 1 and 2*3*5*7*11*13 + 1.
mathwonk
mathwonk is offline
#5
Jan5-06, 10:11 AM
Sci Advisor
HW Helper
mathwonk's Avatar
P: 9,421
This brings up a point that comes up whenever you have to teach the prime factorization theorem. I have started saying something like " every integer greater than 1, is either prime or is a product of primes," because so many students fail to grok that a product of n factors can be prime if n = 1.


this somewhat clunky statement can also help them when they have to use it, as sometimes the first case is to assume their number is prime, and the second case is to assume it is not, but is a product of primes.
shmoe
shmoe is offline
#6
Jan5-06, 10:44 AM
Sci Advisor
HW Helper
P: 1,996
If you want infinitely many counter examples, take any two odd primes (or actually any number of odd primes), p1, p2, then p1*p2+/-1 will be even and greater than 2, hence composite.
vaishakh
vaishakh is offline
#7
Jan5-06, 12:51 PM
P: 343
No, the thing meant is you can refer to this set {2,3,5,7,11,13,17,....} and by now I think you can predict the rest of the set. The thing to be proved is that if we find the product of some first n consecutive terms in this set, and add or subtract, the number we get NEED NOT BE A PRIME.
vaishakh
vaishakh is offline
#8
Jan5-06, 12:54 PM
P: 343
Sorry, add or subtract "1", the number we get need not be a prime.
But anyway Aditya wants us to prove that they are always prime.
Muzza
Muzza is offline
#9
Jan5-06, 12:56 PM
P: 696
The thing to be proved is that if we find the product of some first n consecutive terms...
...if we take some primes p1, p2, p3,.....,pn then will p1*p2*.......*pn(+/-)1 always be prime?
In my world at least, "some primes" is not synonymous with "consecutive primes".

But anyway Aditya wants us to prove that they are always prime.
Even that can't be done. See the first reply in this thread.
shmoe
shmoe is offline
#10
Jan5-06, 01:46 PM
Sci Advisor
HW Helper
P: 1,996
It's maybe worth pointing out that the Euclid proof does not need to say anything about the n primes you start with. They don't need to be consecutive. They don't need to be ordered. They don't need to be the first n. They don't even need to be unique. Take *any* n primes, multiply them, add 1, this new number must be divisible by a prime that you didn't start with, though it need not be prime itself. This guarantees that for any finite list of primes, you can always add one more.

pi (really [tex]p_i[/tex]) is often used to denote the nth prime in number theory, but not always, so you can usually expect an explicit statement to this effect. If someone writes "some primes p1, p2, ..., pn" there's no reason to assume any other meaning than some collection of n numbers that are all prime.
vaishakh
vaishakh is offline
#11
Jan6-06, 12:27 PM
P: 343
You don't read Aditya's post. Read my post and prove or disprove it if you can. Interpret whatever you want to it, Just as Shmoe showed its very easy if you neglect two, by getting even numbers you are again reaching a composite number. But I think proving what I mean is quite difficult. I want to see if you can and moreover I am also interested the way to see how such proofs are framed in number theory because I have just now passed tenth grade and has no much knowldege on how to frame differant types proofs in number theory.
Muzza
Muzza is offline
#12
Jan6-06, 12:50 PM
P: 696
You don't read Aditya's post.
If anything, you haven't read MY post (if you had, you surely would have noticed that I even quoted from Aditya's post).

Read my post and prove or disprove it if you can.
I did disprove it, in the third reply to this thread. I gave the counterexamples 2*3*5*7 - 1 and 2*3*5*7*11*13 + 1.
shmoe
shmoe is offline
#13
Jan6-06, 02:11 PM
Sci Advisor
HW Helper
P: 1,996
Quote Quote by vaishakh
You don't read Aditya's post.
He did. I'm in complete agreement with Muzza and how he interpreted the OP, I was just adding some more info. You should look again at what I said about the [tex]p_i[/tex] notation. Even if you wanted to make the assumption that [tex]p_i[/tex] is the ith prime, a single value of n where p1*p2*...*pn+1 is not prime would disprove this interpretation of the OP's question (likewise for the - case), which asked if it was *always* prime (Muzza did this).
HallsofIvy
HallsofIvy is offline
#14
Jan8-06, 07:22 PM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,879
Sorry Muzza, I see your point now. Aditya89's first post referred to Euclid's proof of the fact that there are an infinite number of primes and I didn't notice his reference to "some primes". Your counterexample clearly shows that the answer is "no".

I'm still not clear if the product p1p2...pn+ 1 where the product is of all primes less than or equal to pn is necessarily prime. I suspect it isn't but don't see a proof.
shmoe
shmoe is offline
#15
Jan8-06, 09:35 PM
Sci Advisor
HW Helper
P: 1,996
Quote Quote by HallsofIvy
I'm still not clear if the product p1p2...pn+ 1 where the product is of all primes less than or equal to pn is necessarily prime. I suspect it isn't but don't see a proof.
He gave a counterexample to this as well, 2*3*5*7*11*13+1.
benorin
benorin is offline
#16
Jan15-06, 04:58 AM
HW Helper
P: 1,007
Here's how it goes:

Theorem There are infinitely many primes.

proof: Suppose there are only infinitely many primes. Let [itex]p_1,p_2,\ldots , p_n[/itex] be the list of all prime numbers. Put [itex]m=p_1p_2\ldots p_n+1[/itex]. Since m is clearly larger than 1, so m is either prime, or a product of primes. If m is prime, then this gives a contradiction as m is clearly larger than any prime on the above list. If m is not prime, then it is a product of primes. Let q denote such a prime (this would be on the list.) Then m is divisible by q, but m is not divisible by any [itex]p_i[/itex] for m divided by [itex]p_i[/itex] gives a quotient of [itex]\frac{p_1p_2\ldots p_n+1}{p_i}[/itex] and a remainder of 1.

I coppied this proof out of How to Prove It: A Structured Approach by Daniel J. Velleman.
mathwonk
mathwonk is offline
#17
Jan15-06, 09:44 PM
Sci Advisor
HW Helper
mathwonk's Avatar
P: 9,421
this is un productive, but maybe that does not matter since someone wonders abnout it?
Canute
Canute is offline
#18
Feb15-06, 01:01 PM
P: 1,499
For any series of consecutive primes p1xp2...pn the product N of this series +/-1 is not necessarily prime. This is because between pn and N there are primes which may be factors of N +/-1. Or is this not what was being asked?


Register to reply

Related Discussions
Very interesting article requires math I don't have, guru? If not, interesting NTL Introductory Physics Homework 12
Interesting question Special & General Relativity 8
Interesting question Introductory Physics Homework 2
Interesting question Set Theory, Logic, Probability, Statistics 13
an interesting question for you all General Physics 9