wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> p,q,pq-(p+q) prime numbers (need help)
        
(Message started by: cool_joh on Nov 23rd, 2007, 5:25pm)
Title: p,q,pq-(p+q) prime numbers (need help)
Post by cool_joh on Nov 23rd, 2007, 5:25pm
p is a prime number. Prove that there is a prime number, q such that pq - (p+q) is also prime.
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by mikedagr8 on Nov 23rd, 2007, 6:49pm
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. :-X
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by FiBsTeR on Nov 24th, 2007, 8:39am
You've proved it for p=5, but it must be true for all primes p.  ;)
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by mikedagr8 on Nov 24th, 2007, 3:32pm
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...
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by ThudanBlunder on Nov 24th, 2007, 3:55pm

on 11/24/07 at 15:32:23, 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
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by mikedagr8 on Nov 24th, 2007, 3:57pm

on 11/24/07 at 15:55:36, 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.
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by ThudanBlunder on Nov 24th, 2007, 4:10pm

on 11/24/07 at 15:57:14, mikedagr8 wrote:
I did say seems, for a reason.

Which was that three swallows do not a summer make?   :P
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by ecoist on Nov 24th, 2007, 9:18pm
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.
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by mikedagr8 on Nov 25th, 2007, 9:13pm

on 11/24/07 at 16:10:27, ThudanBlunder wrote:
Which was that three swallows do not a summer make?   :P

(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 (http://en.wikipedia.org/wiki/Jonah_Takalua), I just modified it to my own touch.
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by thinktank on Nov 26th, 2007, 2:14am

on 11/24/07 at 15:55:36, 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_msg;msg=0265
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by ThudanBlunder on Nov 26th, 2007, 2:41am

on 11/26/07 at 02:14:53, 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
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by ecoist on Nov 27th, 2007, 9:34am
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.
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by tentflap on Nov 27th, 2007, 2:52pm
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.
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by Obob on Nov 27th, 2007, 6:38pm
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.
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by ecoist on Nov 27th, 2007, 7:41pm


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.
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by Obob on Nov 27th, 2007, 11:24pm
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.
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by Hippo on Nov 28th, 2007, 3:16am

on 11/27/07 at 19:41:44, 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. ;)
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by Obob on Nov 28th, 2007, 8:31am
I would suspect though that, provided the answer is true, there are actually infinitely many "good" primes q.
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by pex on Nov 28th, 2007, 10:13am

on 11/27/07 at 14:52:39, 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.
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by SMQ on Nov 28th, 2007, 10:37am

on 11/27/07 at 19:41:44, 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 11/28/07 at 03:16:47, 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
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by SMQ on Nov 28th, 2007, 12:22pm
...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
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by Obob on Nov 28th, 2007, 12:46pm
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.
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by Eigenray on Jan 6th, 2008, 8:51pm
This fact would follow from [link=http://en.wikipedia.org/wiki/Schinzel's_hypothesis_H]Schinzel's hypothesis H[/link]: the two polynomials f1(x)=x and f2(x) = px - x - p are conjectured to be simultaneously prime infinitely often.

Quantitatively, the [link=http://en.wikipedia.org/wiki/Bateman-Horn_conjecture]Bateman-Horn conjecture[/link] implies that, for fixed p, if Q(x) is the number of q http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif x for which q and pq-p-q are both prime, then

Q(x) ~ 2C2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif(q-1)/(q-2) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/int.gif2x dt/(log t)2,

where the (finite) product is over the odd primes q dividing p(p-1), and C2 ~ 0.6602 is the [link=http://en.wikipedia.org/wiki/Twin_prime_conjecture#Hardy.E2.80.93Littlewood_conjecture]twin prime constant[/link].  (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.
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by cool_joh on Jul 20th, 2008, 1:45am
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. ;D
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by ThudanBlunder on Jul 20th, 2008, 2:43am

on 07/20/08 at 01:45:24, 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. ;D

Being 'pretty sure' doesn't make it more than just a conjecture.

I posted this on sci.math (http://groups.google.com/group/sci.math/browse_thread/thread/60bb3d812630084a/adbfba2166278204?lnk=gst&q=pq+-+(p%2Bq)+prime#adbfba2166278204) and they couldn't prove or disprove it either.
Title: Re: p,q,pq-(p+q) prime numbers (need help)
Post by towr on Jul 20th, 2008, 7:07am

on 07/20/08 at 01:45:24, cool_joh wrote:
I got this problem from my friend. He's not that smart. So I guess we only need elementary number theory properties.
It's a very real possibility that he thinks he has proved it, but in fact hasn't.
Of course we'd be happy to have a look at his proof and heap praise upon him if he's right, or gently point out errors if he isn't.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board