PRMO 2014 Question 11

Preparation:
1.  If x + y = 130 and their gcd is 10 find all possible pairs of (x,y). Given that x,y are positive integers(natural numbers).
2. If xy = 7 + x + y and x,y are positive integers find the pairs (x,y) satisfying this equation.
3. Complete a rectangle method. How do you factorize axy + bx + cy = d?
Solution:
Multiply both sides by a
=> a^2xy + abx + acy = ad
=> ax(ay + b) + acy = ad
=> ax(ay + b) + ay(c) = ad
=> ax(ay + b) + (ay + b)(c) - bc = ad
=> (ax + c)(ay + b) = ad + bc

Now coming to the main question:

11. For natural numbers $x$ and $y$, let $(x,y)$ denote the greatest common divisor of $x$ and $y$. How many pairs of natural numbers $x$ and $y$ with $x\le y$ satisfy this equation:

xy = x + y + (x,y)

Solution:
Let gcd(x,y) = d
xy = x + y + d
xy - x - y = d
(x-1)(y-1) = d + 1

Let a,b co primes such that,
x = ad, y = bd
Since x <= y, it means that a <= b.
Also a,b are natural numbers, so a,b >= 1.

Now,
(ad - 1)(bd - 1) = d + 1
Since a,b >= 1
(ad - 1) >= d - 1
(bd - 1) >= d - 1

Hence
(ad - 1)(bd - 1) >= (d-1)^2
So (d+1) >= (d-1)^2.

Now RHS is growing exponentially while the LHS is growing lineraly.
So only small values of 'd' will satisfy this.
Start with d = 1
2 >= 0 ----- Ok
d = 2
3 >= 1 ----- Ok
d = 3
4 >= 4 ----- Ok this is the last 'd'.

So d = 1,2,3

Start with d = 1
(ad - 1)(bd - 1) = d + 1
(a-1)(b-1) = 2
a-1 = 2/(b-1)
a = 1 + 2/(b-1)
Remember a<=b and a is natural.
b = 1 not possible, divide by zero exception.
b = 2 => a = 3, not possible since a <= b
b = 3 => a = 2-----Ok
b > 3 => a can't be natural.
So one solution for (a,b) is (2,3), hence (x,y) = (2,3) since d = 1

Similarly, when you put d = 2 you will get only one valid (x,y) = (2,4).
And with d = 3, only valid (x,y) = (3,3).

So answer is 3 pairs.

$$$$