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

Question

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.

Answer 1

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.