Find all possible pairs (p, q) of positive integers, with p ≤ q, such that (q² + 1)/(pq - 1) is an integer.

Let (q²+1)/(pq-1) = k

1) Max value that k can take in terms of q is when p = 1

we have to find maximum value of 

(q²+1)/(q-1) = (q+1) + 2/(q-1)

So, max value = q+3 (when q=2) --- (a)

2) q²+1 = k(pq-1)

=> k+1 = q(kp-q)

=> k+1 is a multiple of q

=> q+4 is a multiple of q (from (a))

So, maximum value that q can take is 4

Cases:

i) q = 1 p = 1 is not a solution

ii) q = 2

5/(2p-1) is integer => p = 1 

iii) q = 3

10/(3p-1) is integer => p = 1 and p = 2

iv) q = 4

17/(4p-1) is integer => no solution

The solutions are

(1,2) , (1,3) and (2,3)

Posted by Praneeth on 2010-01-08 08:35:43