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


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

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

  • $\begingroup$ 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)$. $\endgroup$ – darij grinberg Nov 11 '15 at 21:49
  • $\begingroup$ 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? $\endgroup$ – 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.

  • $\begingroup$ Thank you, I managed to solve it thanks to Darij Grinberg's comment :) $\endgroup$ – Oria Gruber Nov 11 '15 at 23:02

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.