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

        riddles >> easy >> Prime number problem
        
(Message started by: BenVitale on Jun 3rd, 2009, 12:42pm)
Title: Prime number problem
Post by BenVitale on Jun 3rd, 2009, 12:42pm
I'm not sure if this forum is the right one for this problem.

I have 2 prime numbers p and q and a natural number n that satisfy the following relationship

1/p + 1/q + 1/pq = 1/n

So, I rearrange the fractions

1/n = (p + q + 1)/pq

which gives me

n = pq /(p + q + 1)

n is a natural number, hence (p + q + 1) must divide pq.

I found this is true for
p = 2 and q = 3, or
p = 3 and q = 2
hence pq = 6

1/2 + 1/3 + 1/6 = 1, so n = 1

What about primes larger than 3.
How to prove that (p + q + 1) does not divide pq?
Title: Re: Prime number problem
Post by SMQ on Jun 3rd, 2009, 1:19pm
Ah, but you already know [hide]the prime factorization of pq, which is, trivially, p * q; so the only numbers which divide pq are 1, p, q, and pq.  Clearly p + q + 1 is greater than any of 1, p, or q, so the only solution is p + q + 1 = pq.  This implies p + 1 = pq - q = (p - 1)q --> q = (p + 1)/(p - 1) and since q is a prime, the only solutions are p = 2 or p = 3.  Likewise p = (q + 1)/(q - 1) gives the same possibilities for q.  Q.E.D.[/hide]

--SMQ
Title: Re: Prime number problem
Post by BenVitale on Jun 4th, 2009, 10:28am

on 06/03/09 at 13:19:29, SMQ wrote:
Ah, but you already know [hide]the prime factorization of pq, which is, trivially, p * q; so the only numbers which divide pq are 1, p, q, and pq.  Clearly p + q + 1 is greater than any of 1, p, or q, so the only solution is p + q + 1 = pq.  This implies p + 1 = pq - q = (p - 1)q --> q = (p + 1)/(p - 1) and since q is a prime, the only solutions are p = 2 or p = 3.  Likewise p = (q + 1)/(q - 1) gives the same possibilities for q.  Q.E.D.[/hide]

--SMQ


Right. Thanks.


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