Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
$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.
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
