Máximo Común Divisor

DEF:

Sean $a, b \in \Z$ no ambos nulos. El MCD entre $a$ y $b$ es el mayor de los divisores comunes entre $a$ y $b$ y se nota $(a:b)$.

Observaciones:

• $(a:b) \in \N$ pues $(a:b) ≥ 1$.

• Siempre existe, pues $1 \in \mathscr{DivCom}_+(a, b)$.

  $$ \mathscr {DivCom}+(a, b) = \mathscr{Div}+(a) \cap \mathscr{Div}_+(b) ≠ \emptyset $$

  Y no puede ser tan grande pues si $d|a$ y $d|b$, entonces $|d|≤|a|$ y $|d|≤|b|$.

Propiedades:

Sean $a, b \in \Z$ no ambos nulos

1. $(a:b) = (\pm a:\pm b)$
2. $(a:b)=(b:a)$
3. $(a:1)=1$
4. $(a:0)=|a| \qquad \forall a \in \Z-\{0\}$
5. Si $b|a$, entonces $(a:b) = |b| \qquad \text{si } b \in \Z - \{0\}$

Algoritmo de Euclides

Proposición:

Sean $a, b \in \Z$ con $b≠0$

Entonces $\forall k \in \Z$ se tiene

$$ (a:b) = (b:a-kb) $$

En particular, como $r_b(a) = a-kb$, con $k$ el cociente (para $b≠0$), se tiene

$$ (a:b)=\big(b:r_b(a)\big) $$