# Find two numbers given their product, GCD, and remainder of division of one by the other

$a$ and $b$ are two positive integers. If $ab=1260$, $gcd(a,b)=3$, and when $a$ is divided by $b$ the remainder is 18, what are $a$ and $b$?

How do you solve this? It looks like an application of Euclidean Algorithm but I'm not able to get the solution.

Factor $$1260 = 2^2 \cdot 3^2 \cdot 5 \cdot 7$$

Since the greatest common divisor of $a$ and $b$ is three, each is divisible by a single factor of $3$, and one of them is divisible by both factors of $2$; that is, we could write

$$a = 2^2 \cdot 3 \cdot 5^i \cdot 7^j$$

with $0 \le i, j \le 1$. Figuring out $i$ and $j$ is where you'll have to use the final assumption. If this doesn't lead to a solution, then write

$$b = 2^2 \cdot 3 \cdot ...$$

and proceed.

• It might be possible that $b$ contains the $2^2$ part. Dec 17, 2013 at 1:52
• @Berci Yes, you're right. I've fixed it now.
– user61527
Dec 17, 2013 at 1:53

Hint $\$ Let $\rm\ a,b = 3c,3d$. Then $\rm\, \gcd(c,d)=1,\,\ cd = 4\cdot 5\cdot 7,\ \ c\ {\rm mod}\ d = 18/3 = 6\$ so $\rm\,d>6.\,$ Thus $\rm\, d= 7\,$ or $\, 5\cdot 7.\,$ or $\ldots$ But only the first gives the sought $\rm\ c\ mod\ d = 6.\ \$ QED