cómo demostrar que $\frac{\gcd(a,m)\gcd(b,m)}{\gcd(ab,m)} \in \mathbb Z$

Question

Sé que esto se ha insinuado en una página anterior pero no consigo encontrar una respuesta completa.

sabemos que $\gcd(a,m) = ax_1+mx_2$ del algoritmo euclidiano. De forma similar, sabemos que $\gcd(b,m)=bx_2+mx_3$ y $\gcd(ab,m)=abx_5+mx_6$ y así

$$\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}$$

No entiendo cómo podemos decir que se divide sin un resto.

esto no es una tarea. Lo hago por deporte.

Answer 1

Una mejor manera de hacerlo es pensar en términos de la definición de GCD. Si $g = (x, y)$ entonces, por definición, $g\mid x$ , $g\mid y$ y si cualquier otro número $d$ también divide $x$ y $y$ entonces eso debe implicar $d\mid g$ .

Si puede establecer que $(ab, m)$ divide el numerador, entonces tienes $(ab, m) c = (a, m)(b, m)$ para algunos $c \in \mathbb{Z}$ y ahí tienes tu entero. Sigue el comentario de Darij para obtener más pistas.