Propiedades del MCD

Las propiedades del máximo común divisor (MCD) son esenciales en teoría de números, así que acá muestro algunas, y una que otra identidad (seguramente serán útiles en algunos razonamientos):

• Si ${d|a}$ y ${d|b}$, entonces
  $$d\,|\,\mathrm{mcd}(a,b)$$ Esto es evidente desde la definición del MCD. También se sigue de la definición de ${\alpha|\beta}$ (léase $\alpha$ divide a $\beta$) que siempre existe un k tal que ${\mathrm{mcd}(a,b)=dk}$.

• La identidad de Bézout: Si ${a,b}$ son dos enteros no nulos, entonces ${\mathrm{mcd}(a,b)=d}$ puede expresarse alternativamente como ${d=ax+by}$ para algún ${x,y}$ números enteros, i.e.
  $$\exists\,{x,y}\in\mathbb{Z}\;:\;\mathrm{mcd}(a,b)=ax+by$$ Una demostración común se hace empleando el algoritmo de Euclides. Antes también puedes emplear el hecho de que si ${d|a}$ y ${d|b}$, entonces ${d|ax+by,\;\forall\;x,y\in\mathbb{Z}}$ y de ahí sólo encontrar ${x,y}$ (Euclides) tales que d no sólo divida, sino que sea el MCD.

• Si ${\mathrm{mcd}(a,b)=d}$, entonces
  $$\mathrm{mcd}\left(\frac{a}{d},\frac{b}{d}\right)=1$$ Por identidad de Bézout, ${d=ax+by}$, es decir, ${1=\frac{a}{d}x+\frac{b}{d}y}$, que implica el enunciado.

• ${\forall\;n\in\mathbb{Z}^+}$,
  $$\mathrm{mcd}(na,nb)=n\cdot\mathrm{mcd}(a,b)$$ Por identidad de Bézout, ${\mathrm{mcd}(na,nb)=(na)x+(nb)y=n(ax+by)=n\cdot\mathrm{mcd}(a,b)}$.

• ${\forall\;n\in\mathbb{Z}}$,
  $$\mathrm{mcd}(a,b)=\mathrm{mcd}(a+nb,b)$$ Por identidad de Bézout, se tiene ${\mathrm{mcd}(a,b)=ax+by}$ y también ${\mathrm{mcd}(a+nb,b)=(a+nb)x+bY=ax+b(Y+nx)}$, entonces ${Y=y-nx}$ y la igualdad se satisface para todo n.
  

• Asociatividad y Conmutatividad:
  $$\mathrm{mcd}(a,b,c)=\mathrm{mcd}\left[a,\mathrm{mcd}(b,c)\right]=\mathrm{mcd}\left[\mathrm{mcd}(a,b),c\right]=\mathrm{mcd}\left[c,\mathrm{mcd}(a,b)\right]$$ Si ${d|a}$ y ${d|\mathrm{mcd}(b,c)}$, entonces ${d|\mathrm{mcd}\left(a,\mathrm{mcd}(b,c)\right)}$, pero ${d|\mathrm{mcd}(b,c)}$ implica que ${d|b}$ y ${d|c}$, por tanto también ${d|\mathrm{mcd}(a,b)}$, de donde se sigue la igualdad. Intenta construirla explícitamente a partir de la definición de ${\alpha|\beta}$.

• Si ${\mathrm{mcd}(a,b)=1}$, entonces
  $$\mathrm{mcd}(ab,c)=\mathrm{mcd}(a,c)\mathrm{mcd}(b,c)$$ Empleando las propiedades anteriores,
  \begin{align}\mathrm{mcd}(a,c)\mathrm{mcd}(b,c)&=\mathrm{mcd}\left[b\;\mathrm{mcd}(a,c),c\;\mathrm{mcd}(a,c)\right]\\[0.05in]&=\mathrm{mcd}\left[\mathrm{mcd}(ab,bc),\mathrm{mcd}(ac,c^2)\right]\\[0.05in]&=\mathrm{mcd}(ab,bc,ac,c^2)\\[0.05in]&=\mathrm{mcd}\left[ab,c^2,\mathrm{mcd}(bc,ac)\right]\\[0.05in]&=\mathrm{mcd}\left(ab,c,c^2\right)\\[0.05in]&=\mathrm{mcd}\left[ab,\mathrm{mcd}(c,c^2)\right]=\mathrm{mcd}\left(ab,c\right)\hspace{0.25in}\square\end{align}
  

• Si ${\mathrm{mcd}(a,b)=1}$, entonces
  $$\mathrm{mcd}(a,b)=\mathrm{mcd}\left(ab,a^2+b^2\right)$$ Empleando nuevamente las propiedades, para algún ${n,m\in\mathbb{Z}}$,
  \begin{align}\mathrm{mcd}(a,b)&=\mathrm{mcd}(a,b)\mathrm{mcd}(a+nb,b)=\mathrm{mcd}(a,b)\mathrm{mcd}(a,b+ma)\\[0.05in]&=\mathrm{mcd}\left[a(a+nb),b\right]=\mathrm{mcd}\left[a,b(b+ma)\right]\end{align} Sea $\displaystyle{n=\frac{b}{a}=\frac{1}{m}}$, entonces
  \begin{align}\mathrm{mcd}(a,b)&=\mathrm{mcd}\left(b,a^2+b^2\right)=\mathrm{mcd}\left(a,a^2+b^2\right)\\[0.05in]&\therefore\\[0.05in]\mathrm{mcd}(a,b)&=\mathrm{mcd}(a,a^2+b^2)\mathrm{mcd}(b,a^2+b^2)=\mathrm{mcd}(ab,a^2+b^2)\hspace{0.25in}\square\end{align}

Estas son sólo algunas propiedades, algunas básicas y otras más que nada interesantes y útiles. Probablemente un niño no se imagine aún que detrás de las matemáticas básicas de primaria hay un mundo riquísimo en teoría de números.