2
$\begingroup$

I've just been introduced to number theory and I had to admit it's a very cool math subfield. Solving problems is another matter entirely, however. Here is the problem:

For positive $a, b, c \in \mathbb{Z}$, prove that if $c = \gcd(a, b)$ then $c^2 \mid ab$.

I began by trying to list all the intuitions I had about the above:

If $c^2 \mid ab$, then $c^2 \mid a$ and $c^2 \mid b$ should also be valid statements, right?

I also feel that $c^2 \mid ab$ would also hold.

I've been introduced to the Euclidean algorithm as well, which means $c = \gcd(a, b)$ would also mean $c = \gcd(b, r)$ ($r$ being the remainder).

So I have a cluster of (what I think are correct) intuitions from the above, but pairing these into something that proves $c^2 \mid ab$ seems daunting. Could someone point me in the right direction so I can begin connecting these dots?

$\endgroup$
  • $\begingroup$ Have you looked at any examples for $a$ and $b$? $\endgroup$ – Carsten S Jun 29 '16 at 15:17
  • $\begingroup$ Hint $\ j\mid J,\, k\mid K\,\Rightarrow\, jk\mid JK\ $ $\endgroup$ – Bill Dubuque Jun 29 '16 at 15:17
  • $\begingroup$ the fact that it is a "gcd" is not necessary. It suffices that it is a common divisor. $\endgroup$ – Andres Mejia Jun 29 '16 at 15:20
3
$\begingroup$

If $c^2 \mid ab$, then $c^2 \mid a$ and $c^2 \mid b$ should also be valid statements, right?

Not at all. In fact for $c>1$, it's certain that at least one of these is false; otherwise the $\gcd$ of $a$ and $b$ would be $c^2$, not $c$.

What you do know from $c =\gcd(a,b)$ is that $c \mid a$ and $c \mid b $. And that's how you can deduce that $c^2 \mid ab$.

$\endgroup$
3
$\begingroup$

Hint: If $c$ divides both $a$ and $b$, then we can write $$a = cm$$ and $$b = cn$$ for some $m, n$.

If you multiply these two together a factor of $c^2$ appears on the RHS.

$\endgroup$
2
$\begingroup$

Write down the definitions:

$$\begin{cases}c\,\mid\,a\implies a=xc\\{}\\c\,\mid\,b\implies b=yc\end{cases}\implies ab=xyc^2\implies c^2\,\mid\,ab$$

and since the above is true for any common divisor, it is also true for the greatest common one.

$\endgroup$

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.