0
$\begingroup$

$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.

$\endgroup$
0

2 Answers 2

3
$\begingroup$

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.

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

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.