# how to show that $\frac{\gcd(a,m)\gcd(b,m)}{\gcd(ab,m)} \in \mathbb Z$

I know this has been hinted at a previous page but I can't seem to find a complete answer.

we know that $\gcd(a,m) = ax_1+mx_2$ from the euclidean algorithm. In a similar way, we know that $\gcd(b,m)=bx_2+mx_3$ and $\gcd(ab,m)=abx_5+mx_6$, and so

$$\frac{\gcd(a,m)\gcd(b,m)}{\gcd(ab,m)}=\frac{(ax_1+mx_2)(bx_2+mx_3)}{abx_5+mx_6}=\frac{abx_1x_3+amx_1x_4+bmx_2x_3+m^2x_2x_4}{abx_5+mx_6}$$

I don't understand how we can say that it divides without a remainder.

this is not homework. I'm doing this for sports.

• Hint: Notice that $\gcd\left(ab,m\right)$ divides both $ab$ and $mb$. Hence, $\gcd\left(ab,m\right)$ divides $\gcd\left(ab,mb\right) = \gcd\left(a,m\right)b$. Now, $\gcd\left(ab,m\right)$ divides both $\gcd\left(a,m\right)b$ and $\gcd\left(a,m\right)m$. Hence, it divides $\gcd\left(\gcd\left(a,m\right)b,\gcd\left(a,m\right)m\right) = \gcd\left(a,m\right)\gcd\left(b,m\right)$. – darij grinberg Nov 11 '15 at 21:49
• Write the top as $ab(x_1x_3) + (ax_1x_4 + bx_2x_3 + mx_2x_4)m$. How can you relate the GCD of ab and m to expressions of this form? – user208649 Nov 11 '15 at 21:52

A better way of doing this is to think about it in terms of the definition of GCD. If $g = (x, y)$ then by definition, $g\mid x$, $g\mid y$, and if any other number $d$ also divides $x$ and $y$ then that must imply $d\mid g$.
If you can establish that $(ab, m)$ divides the numerator, then you have $(ab, m) c = (a, m)(b, m)$ for some $c \in \mathbb{Z}$, and there's your integer right there. Follow Darij's comment for further hints.