X and Y are positive integers, neither of which is divisible by 10. Their product is 100,000.

What is X + Y ?

(In reply to Answer by K Sengupta)

100,000 = 2^5 x 5^5, and so it follows that gcd(X, Y) = (2^a)*(5^b). for some nonnegative integers a and b. Since neither X nor Y is divisible by 10, it follows that at least one of a and b must be zero.

Without loss of generality, let us suppose that b=0, while a is non zero. Thus, gcd(X, Y) is 2 or a power of 2, and accordingly, 2 divides each of X and Y. However, for X*Y to be equal to 10^5, at least one of a and b must have additionally 5 as a factor, so that at least one of X and Y must be divisible by 10. This is a contradiction.

Accordingly, a=b=0, so that gcd(X, Y) = 1. Without loss of generality, we an set X>=Y. Then, gcd(X, Y)= 1 is satisfied only when (X, Y) = (1, 10^5), (2^5, 5^5).

In the former case, Y is divisible by 10, leading to a contradiction.

Thus, (X, Y) = (2^5, 5^5), so that: X+Y = 2^5 + 5^5 = 3157

Posted by K Sengupta on 2008-06-25 00:48:40