Author |
Topic: p,q,pq-(p+q) prime numbers (need help) (Read 2350 times) |
|
cool_joh
Guest
|
 |
p,q,pq-(p+q) prime numbers (need help)
« on: Nov 23rd, 2007, 5:25pm » |
 Quote  Modify
 Remove
|
p is a prime number. Prove that there is a prime number, q such that pq - (p+q) is also prime.
|
|
 IP Logged |
|
|
|
mikedagr8
Uberpuzzler
A rich man is one who is content; not wealthy.
Gender: 
Posts: 1105
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #1 on: Nov 23rd, 2007, 6:49pm » |
Quote Modify
|
If p=5, q=3; then 15-8=7, also a prime. I don't know the general rule. I'm not sure if that is correct, either. 
|
|
IP Logged |
"It's not that I'm correct, it's that you're just not correct, and so; I am right." - M.P.E.
|
|
|
FiBsTeR
Senior Riddler
Gender:
Posts: 581
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #2 on: Nov 24th, 2007, 8:39am » |
Quote Modify
|
You've proved it for p=5, but it must be true for all primes p. 
|
|
IP Logged |
|
|
|
mikedagr8
Uberpuzzler
A rich man is one who is content; not wealthy.
Gender:
Posts: 1105
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #3 on: Nov 24th, 2007, 3:32pm » |
Quote Modify
|
It seems to always work for two consecutive primes (the numbers I tried at least) , but I'm not sure how to prove it mathematically if it is always true. 
Seems to also work for any two primes...
|
| « Last Edit: Nov 24th, 2007, 3:47pm by mikedagr8 » |
IP Logged |
"It's not that I'm correct, it's that you're just not correct, and so; I am right." - M.P.E.
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #4 on: Nov 24th, 2007, 3:55pm » |
Quote Modify
|
on Nov 24th, 2007, 3:32pm, mikedagr8 wrote:| It seems to always work for two consecutive primes (the numbers I tried at least) |
|
Your conjecture fails for p = 11, q = 13
pq - (p + q) = 143 - 24 = 119 = 7 *17
|
| « Last Edit: Nov 24th, 2007, 3:59pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
mikedagr8
Uberpuzzler
A rich man is one who is content; not wealthy.
Gender:
Posts: 1105
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #5 on: Nov 24th, 2007, 3:57pm » |
Quote Modify
|
on Nov 24th, 2007, 3:55pm, ThudanBlunder wrote:
Your conjecture fails for p = 11, q = 13
pq - (p + q) = 143 - 24 = 119 = 7 *17
|
|
I did say seems, for a reason. I'm not very good at this kind of mathematics, but I'm improving slowly.
|
|
IP Logged |
"It's not that I'm correct, it's that you're just not correct, and so; I am right." - M.P.E.
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #6 on: Nov 24th, 2007, 4:10pm » |
Quote Modify
|
on Nov 24th, 2007, 3:57pm, mikedagr8 wrote:
I did say seems, for a reason. |
|
Which was that three swallows do not a summer make? 
|
| « Last Edit: Jul 19th, 2008, 5:38pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #7 on: Nov 24th, 2007, 9:18pm » |
Quote Modify
|
This might be a tricky problem. If r is any prime, small relative to p and q, and p and q are both congruent to 2 modulo r, then pq-(p+q) is divisible by r, and so not a prime. In particular, 3 divides pq-(p+q) if p and q are each congruent to 2 modulo 3.
Regarding p=11, q=13, if p is congruent 4 modulo 7 and q is congruent to 6 modulo 7, then pq-(p+q) is divisible by 7. So, if the smaller of p and q is greater than 7, then pq-(p+q) is not a prime.
|
|
IP Logged |
|
|
|
mikedagr8
Uberpuzzler
A rich man is one who is content; not wealthy.
Gender:
Posts: 1105
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #8 on: Nov 25th, 2007, 9:13pm » |
Quote Modify
|
on Nov 24th, 2007, 4:10pm, ThudanBlunder wrote:
Which was that three swallows do not a summer make?
(In your sig you should lose the bracket.
And shouldn't it be 487'RU/16??
And \becauseUR16 surely ' should be ") 
|
|
No, my sig is meant to be 487'=RU... look up RU487 (it's a kind of durg, which had a lot of problems in Australia).
Also it's not my sig, its a tag by Jonah, I just modified it to my own touch.
|
| « Last Edit: Nov 26th, 2007, 2:31am by mikedagr8 » |
IP Logged |
"It's not that I'm correct, it's that you're just not correct, and so; I am right." - M.P.E.
|
|
|
thinktank
Newbie
Posts: 10
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #9 on: Nov 26th, 2007, 2:14am » |
Quote Modify
|
on Nov 24th, 2007, 3:55pm, ThudanBlunder wrote:
Your conjecture fails for p = 11, q = 13
pq - (p + q) = 143 - 24 = 119 = 7 *17
|
|
I think you misunderstood the problem, the problem states that for every prime p there should exist a set (q,r) both prime such that r=pq-(p+q).
So if p=11, a prime q=3, does exist for which r=19, is a prime. The problem stated is more complex than it seems, I think you would need more indepth knowledge of number theory to proove the conjecture...Though I dont have much knowledge of such areas the following might help
http://answers.yahoo.com/question/index?qid=20070710080620AAOHKM7
http://at.yorku.ca/cgi-bin/bbqa?forum=ask_an_algebraist_2003;task=show_m sg;msg=0265
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #10 on: Nov 26th, 2007, 2:41am » |
Quote Modify
|
on Nov 26th, 2007, 2:14am, thinktank wrote:
I think you misunderstood the problem, the problem states that for every prime p there should exist a set (q,r) both prime such that r=pq-(p+q).
So if p=11, a prime q=3, does exist for which r=19, is a prime. |
|
The conjecture I was referring to was that if pi,pi+1 are consecutive primes then pipi+1 - (pi + pi+1) is also prime for all i
3*5 - (3+5) = 7
5*7 - (5+7) = 23
7*11 - (7+11) = 59
But
11*13 - (11+13) = 119 = 7*17
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #11 on: Nov 27th, 2007, 9:34am » |
Quote Modify
|
I am stumped! I showed that, for every prime p, there is a bad choice for a prime q such that pq-(p+q) is not a prime. Then I observed that pq-(p+q)=(p-1)(q-1)-1. Hence, if S is any given finite set of primes, there is a prime q such that q-1 is divisible by every prime in S; thus pq-(p+q) is not divisible by any prime in S. But since such a q can be quite large, pq-(p+q) could still be not a prime.
In complete desperation, I even wondered if there could be a connection with this little fact: one can redefine addition and multiplication on Zp by a+'b=a+b-1 and ax'b=a+b-ab, obtaining a field Zp(+',x'), with additive identity 1 and multiplicative identity 0, necessarily isomorphic to the integers modulo p, Zp(+,x). Nothing came of this observation.
|
|
IP Logged |
|
|
|
tentflap
Newbie
Posts: 1
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #12 on: Nov 27th, 2007, 2:52pm » |
Quote Modify
|
this problem, can be taken far yes... but the answer to it was just and existence question. if asks if there exists a prime that you'd get a prime back. this was clearly answered and given back at the first or second reply i don't remember exactly at this point.
recently my teacher posted a similar question about pq-(p+q)+2 is a power of a prime. as far as i know this is true for all primes p and q however who would try every prime under the sun? also it is a similar issue trying to prove it.
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #13 on: Nov 27th, 2007, 6:38pm » |
Quote Modify
|
No, tentflap. This problem has not been solved yet.
That's an interesting fact about redefining addition and multiplication, ecoist. I hadn't heard of that before. I'm not sure if it might be useful here, though.
The links thinktank posted are not relevant to the problem.
This problem seems quite difficult.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #14 on: Nov 27th, 2007, 7:41pm » |
Quote Modify
|
Quote:| That's an interesting fact about redefining addition and multiplication, ecoist. I hadn't heard of that before. I'm not sure if it might be useful here, though. |
|
I don't think it is useful here either, but couldn't resist pointing out something I learned many years ago (applies to every field). What we learn in school changes over time.
Quote:| This problem seems quite difficult. |
|
Glad I'm not alone in this feeling. Given a prime p>3, there seems to always exist a prime q<p such that pq-(p+q) is a prime. But I can't get a handle on why this should be so.
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #15 on: Nov 27th, 2007, 11:24pm » |
Quote Modify
|
In fact, the statement about redefining addition and multiplication can be made much more general, ecoist.
Suppose we are given any ring R=(S,+,x), where S is the underlying set, and + and x are the binary operations. Given a bijection f:S->S, there is a unique ring R'=(S,+',x') with the same underlying set S as R such that f:R->R' is an isomorphism of rings. Indeed, the ring operations on R' can be defined by x +' y = f(f-1(x) + f-1(y)), and similarly for multiplication; furthermore, this is the only possible definition of the operations.
The special case you pointed out earlier follows from taking f(x)=1-x.
Unfortunately, after thinking about it more, it appears to me that this line of thought will not be fruitful for this problem. It also appears to be difficult to the point that I would not be surprised at all if there is not an elementary solution.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #16 on: Nov 28th, 2007, 3:16am » |
Quote Modify
|
on Nov 27th, 2007, 7:41pm, ecoist wrote:
Glad I'm not alone in this feeling. Given a prime p>3, there seems to always exist a prime q<p such that pq-(p+q) is a prime. |
|
This is much more interesting problem as at least negative answer is easily verifyable.
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #17 on: Nov 28th, 2007, 8:31am » |
Quote Modify
|
I would suspect though that, provided the answer is true, there are actually infinitely many "good" primes q.
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #18 on: Nov 28th, 2007, 10:13am » |
Quote Modify
|
on Nov 27th, 2007, 2:52pm, tentflap wrote:| recently my teacher posted a similar question about pq-(p+q)+2 is a power of a prime. as far as i know this is true for all primes p and q |
|
Try p = 3, q = 11 for a counterexample.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #19 on: Nov 28th, 2007, 10:37am » |
Quote Modify
|
on Nov 27th, 2007, 7:41pm, ecoist wrote:| Given a prime p>3, there seems to always exist a prime q<p such that pq-(p+q) is a prime. But I can't get a handle on why this should be so. |
|
on Nov 28th, 2007, 3:16am, Hippo wrote:| This is much more interesting problem as at least negative answer is easily verifyable. |
|
Well, there are no counterexamples in p < 2,500,000,000, and what's more, given a prime p, suitable primes q appear to be plentiful.
--SMQ
|
| « Last Edit: Nov 28th, 2007, 12:20pm by SMQ » |
IP Logged |
--SMQ
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #20 on: Nov 28th, 2007, 12:22pm » |
Quote Modify
|
...even more plentiful than I first thought...
If, for a given prime p > 3, we let q1 denote the least prime q such that pq - (p + q) is prime, the following are the p's with successively-larger q1's:
p = 5: q1 = 2
p = 11: q1 = 3
p = 29: q1 = 7
p = 47: q1 = 19
p = 257: q1 = 61
p = 1,601: q1 = 79
p = 3,671: q1 = 127
p = 5,897: q1 = 139
p = 6,833: q1 = 151
p = 10,079: q1 = 181
p = 11,897: q1 = 229
p = 20,789: q1 = 241
p = 29,879: q1 = 367
p = 92,867: q1 = 379
p = 128,273: q1 = 433
p = 289,937: q1 = 463
p = 403,889: q1 = 631
p = 569,423: q1 = 733
p = 677,543: q1 = 787
p = 803,717: q1 = 811
p = 3,592,319: q1 = 907
p = 3,772,883: q1 = 1033
p = 14,047,367: q1 = 1453
p = 65,678,807: q1 = 1579
p = 73,573,793: q1 = 1657
p = 429,708,029: q1 = 1741
...
While that's certainly not a proof, I'd consider it to be strong evidence that the conjecture is true.
--SMQ
|
| « Last Edit: Nov 28th, 2007, 12:22pm by SMQ » |
IP Logged |
--SMQ
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #21 on: Nov 28th, 2007, 12:46pm » |
Quote Modify
|
Here is a heuristic argument that would suggest the result is true as well. A sufficiently random integer n is prime with probability about 1/log n, and the nth prime is roughly of size n log n. Now with p fixed, we let q vary through all the primes q1, q2, ... . Assuming that an=pqn-p-qn is suitably random (which is impossible to make precise, and why this is only a heuristic argument), we see that the probability that an is prime is roughly 1/log(pqn-p-qn), which is about 1/log(pn log n - p - n log n)=bn. So the probability that an is not prime is about 1 - bn, and assuming that the events "an is prime" are all independent (again this is not provable), the probability that an is not prime for any n is the product of (1 - bn) as n ranges from 1 to infinity. It is not hard to see that this infinite product is zero for any p, which is to say that the probability that an is composite for every n is zero.
This method of thinking has no hope of actually solving the problem at hand, but at least gives another way of thinking about why the result should be true: the primes are somewhat random, but dense enough that two random sets of similar densities (namely the primes, and the set of all an) will probably intersect.
|
| « Last Edit: Nov 28th, 2007, 12:48pm by Obob » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #22 on: Jan 6th, 2008, 8:51pm » |
Quote Modify
|
This fact would follow from Schinzel's hypothesis H: the two polynomials f1(x)=x and f2(x) = px - x - p are conjectured to be simultaneously prime infinitely often.
Quantitatively, the Bateman-Horn conjecture implies that, for fixed p, if Q(x) is the number of q  x for which q and pq-p-q are both prime, then
Q(x) ~ 2C2  (q-1)/(q-2)  2x dt/(log t)2,
where the (finite) product is over the odd primes q dividing p(p-1), and C2 ~ 0.6602 is the twin prime constant. (The twin prime / Hardy Littlewood conjectures are special cases of the Schinzel's H / Bateman-Horn conjectures, respectively.)
For example, taking p=2, the claim that there are infinitely many prime q so that 2q-(2+q)=q-2 is also prime is equivalent to the twin prime conjecture, and the constant in front of the integral above is just 2C2, since the finite product is empty. Taking p=3, the product should be 2; for p=5, 4/3; p=7, 12/5.
I'd expect this problem to be quite hard. After all, how does one show such a q exists without showing there are infinitely many? And I don't know if any cases of Schinzel's Hypothesis are actually known, either with more than one polynomial or even one polynomial of degree > 1.
|
|
IP Logged |
|
|
|
cool_joh
Newbie
Gender:
Posts: 50
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #23 on: Jul 20th, 2008, 1:45am » |
Quote Modify
|
I don't think it is that hard, although I haven't solved this.
I got this problem from my friend. He's not that smart. So I guess we only need elementary number theory properties.
I'm pretty sure that this problem is correct, so it's more than just a conjecture. 
|
|
IP Logged |
MATH PRO
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: p,q,pq-(p+q) prime numbers (need help)
« Reply #24 on: Jul 20th, 2008, 2:43am » |
Quote Modify
|
on Jul 20th, 2008, 1:45am, cool_joh wrote:I don't think it is that hard, although I haven't solved this.
I got this problem from my friend. He's not that smart. So I guess we only need elementary number theory properties.
I'm pretty sure that this problem is correct, so it's more than just a conjecture. |
|
Being 'pretty sure' doesn't make it more than just a conjecture.
I posted this on sci.math and they couldn't prove or disprove it either.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print