2
$\begingroup$

If $ab=600$ how large can the greatest common divisor of $a$ and $b$ be?

I am not sure if I should check for all factor multiples of $a$ and $b$ for this question. Please advise.

$\endgroup$
4
$\begingroup$

We have $600=2^3\cdot 5^2\cdot 3$. To make the gcd large, we give a $2$ to each of $a$ and $b$, also a $5$. So the largest possible gcd is $10$.

Remark: The idea generalizes. Let $n$ have prime power factorization $$n=p_1^{d_1}p_2^{d_2}\cdots p_k^{d_k}.$$ Let $e_i=\lfloor d_i/2\rfloor$, where $\lfloor x\rfloor$ is the greatest integer that is $\le x$. Then the greatest possible gcd of $a$ and $b$, where $ab=n$, is $$p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}.$$

$\endgroup$
  • $\begingroup$ You are welcome. For the maximum, we distribute the power of any prime $p$ as evenly as possible between $a$ and $b$. $\endgroup$ – André Nicolas Jun 10 '13 at 2:00
1
$\begingroup$

$$ab=600=2^3\cdot 3\cdot 5^2$$ The greatest common divisor of $a,b$ will have the greatest number of common prime factors that you can arrange.

$\endgroup$
  • $\begingroup$ Thanks for the explanation $\endgroup$ – user81494 Jun 10 '13 at 1:47

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.