Si $n,m \in \mathbb{N}$ entonces hay $c,d$ tal que $cd = (m,n)$ , $(c,d) = 1$ y $(m/c,n/d) = 1$ .

Question

Supongamos que $m,n \in \mathbb{N}$ . Utilizando el teorema fundamental de la aritmética es fácil demostrar que existe $c,d \in \mathbb{N}$ tal que $(c,d) = 1$ , $cd = (m,n)$ y $(\frac{m}{c},\frac{n}{d}) = 1$ .

¿Hay alguna forma rápida de demostrar esto sin usar las factorizaciones primos de $m$ y $n$ ¿es decir, sólo las propiedades básicas del gcd, lcm, etc.?

Answer 1

$c$ consiste en todas las potencias primarias de $(m,n)$ que tienen el mismo exponente que en $m$ ...

Sí, la factorización costosa no es necesaria. Podemos calcular $\,c\,$ de forma eficiente mediante gcds iterados que se cancelan de $\,m\,$ todos los primos que se producen a mayor potencia que en $\,(m,n).\,$ Estos son exactamente los primos en $\,m' = m/(m,n)\,$ y podemos cancelarlas desde $m$ cancelando repetidamente cualquier gcd que tenga con $\,m',\,$ dando lugar a la solución $\ c = {\rm gdc}(m, m'),\ \ d = (m,n)/c,\ $ donde

$\begin{align}&{\rm gdc}(x,y)\ :=\qquad \text{// greatest divisor of $\,x\,$ that is coprime to $\,y$}\\ &\quad {\rm if}\ \, \gcd(x,y) = 1\ \ {\rm then}\ \ x\\ &\quad {\rm else}\ \, {\rm gdc}(x/{\rm gcd}(x,y),\,y) \end{align}$

Answer 2

Dejemos que $d=(m,n)$ y $c=1$ por lo que la afirmación se demuestra trivialmente