A Perplexing (Prime) Puzzle (Posted on 2007-06-05)

	Submitted by K Sengupta
Rating: 4.0000 (3 votes)
Solution:	(Hide)
If possible, let (pq+rs) be prime. Now, pq+rs = (p+s)r + (q-r)p = t*gcd(p+s, q-r), where t is a positive integer as each of p, q, r and s are positive......(#). Since, (pq+rs) is prime, it follows that: Either, t = 1; Or, gcd(p+s, q-r) = 1 Case (a): t=1 We observe that: gcd(p+s, q-r) = pq+rs > (pq+rs) -(p-q+ r+s) = (p+s)(r-1) +(q-r)(p+1) > = gcd(p+s, q-r) This is a contradiction. Case(b): gcd(p+s, q-r) = 1 We note that pr+qs = (p+ s)q -(q-r)p Then, by conditions of the problem: pr+rs=(q+s+p-r)(q+s-p+r) Or, (p+s)q - (q-r)p = (q+s+p-r)(q+s-p+r) Or, (p+s)(p-r-s) = (q-r)(q + r +s) Accordingly, there exists a positive integer n such that: p-r-s = n(q-r) and q+r-s = n(p+s) This gives, p+q = n(p + q - r + s, so that: n(r-s) = (n-1)(p+q) We now recall that p> q > r> s. if n =1, then r=s, which is a contradiction. If n> 2, then: 2> = n/(n-1) = (p+q)/(r-s) > (p+q)/r > (r+r)/r =2. This is a contradiction. Accordingly, our original assumption that (pq+rs) corresponds to a prime number is false. Consequently, it is NEVER the case that (pq+rs) is a prime number. .

	Subject	Author	Date
	Might be correct!	Praneeth Yalavarthi	2007-07-11 12:16:55
	Hint	K Sengupta	2007-06-29 12:52:26
	Helpful Observation?	Tommy	2007-06-28 14:23:15
	More number crunching	Brian Smith	2007-06-07 22:08:55
	Some number crunching	Brian Smith	2007-06-07 00:34:43