$\gcd(a,b) = \gcd(a + b, \mathrm{lcm}[a,b])$

Question

Mostrar que si $a$ $b$ son enteros positivos, entonces tenemos: $\gcd(a,b) = \gcd(a + b, \mathrm{lcm}[a,b])$.

Answer 1

A continuación se presentan algunas de las pruebas. En primer lugar, he aquí un par de mi lesión.matemáticas post en 2001/11/10
Para la variedad aquí es otro el uso de $\rm\ (a,b)\ \ [a,b]\ =\ ab\ \ $ básica y mcd leyes:

$\rm\quad (a,b)\ (a+b, [a,b])\ =\ (aa+ab,\ ab+bb,\ ab)\ =\ (aa,\:bb,\:ab)\ =\ (a,b)^2\quad $ QED

Por cierto, recordar que la clave de la identidad en la segunda prueba surgió el otro día en nuestra discusión de Stieltjes $\rm\ 4\:n+3\ $ generalización de Euclides prueba de una infinidad de números primos. He aquí un impermeable de la prueba:

LEMA $\rm\ \ (a+b,\:ab) = 1\ \iff\ (a,\:b) = 1$

Prueba de $\rm\ \ \ (a,\:b)^2 \subset (a+b,\:ab) \subset (a,\:b)\ \ $ desde, por ejemplo, $\rm\ \ a^2 = a\:(a+b)-ab\in (a+b,\:ab)$

Por lo tanto $\rm\ 1\in (a+b,\ ab)\ \Rightarrow\ 1\in (a,\:b)\:.\:$ por el Contrario $\rm\ 1 \in (a,\:b)\ \Rightarrow\ 1 \in (a,\:b)^2 \subset (a+b,\:ab)\quad$ QED

Answer 2

Otro intento de Dubuquesque; para garantizar su legibilidad, escriba $d=\gcd(a,b)$:\begin{align*} \gcd\Bigl(d(a+b), ab\Bigr) &= \gcd\Bigl(d(a+b), ab, ab\Bigr)\\ &=\gcd\Bigl(d(a+b),\ ab-a(a+b),\ ab-b(a+b)\Bigr)\\ &=\gcd\Bigl(d(a+b),\ a^2,\ b^2\Bigr)\\ &=\gcd\Bigl(d(a+b),\ \gcd(a^2,b^2)\Bigr)\\ &=\gcd\Bigl(d(a+b),\ \gcd(a,b)^2\Bigr)\\ &=\gcd\Bigl(d(a+b),\ d^2\Bigr)\\ &= d\gcd\Bigl(a+b,d\Bigr)\\ &= d\gcd\Bigl(a+b,\gcd(a,b)\Bigr)\\ &= d\gcd(a,b)\\ &= \gcd(a,b)\gcd(a,b). \end{align*}

(Segunda línea utiliza el hecho de que $a(a+b)$ y $b(a+b)$ son ambos múltiplos de $d(a+b)$).

Ahora divida por $\gcd(a,b)$ para obtener el resultado deseado.

Answer 3

Tal vez overkill, pero si aceptar la 'ley de distribución' $(x,[y,z])=[(x,y),(x,z)]$ en Wikipedia, entonces es fácil:

$(a+b,[a,b])=[(a+b,a),(a+b,b)]=[(b,a),(a,b)]=(a,b)$

donde en la segunda igualdad utilicé el hecho fácil $(x,y)=(x,y \mod x)$.

Answer 4

Comienzo por escribir $a=d a'$, $b=d b'$, donde $d=(a,b)$.

Answer 5

$\newcommand{\lcm}{\:\text{lcm}}$Aquí es un divisor de nivel de prueba que refleja básicamente Ido's de la primera prueba. Podemos utilizar las siguientes definiciones: $\;\gcd(a,b)\;$ $\;\lcm(a,b)\;$ son no-negativos números tales que, para todos los $\;d\;$, \begin{array} \\ d|\gcd(a,b) & \equiv & d|a \land d|b \\ d|\lcm(a,b) & \equiv & d|a \lor d|b \\ \end{array} junto con 'divisor extentionality', es decir, $\;s = t \;\equiv\; \langle \forall d :: d|a \equiv d|b \rangle\;$ para los números negativos $\;s,t\;$.

Empezamos con el más complejo lado de esta ecuación, ampliar las definiciones anteriores, y tratar de simplificar: para todos los $\;d\;$, \begin{align} & d|\gcd(a+b, \lcm(a,b)) \\ = & \;\;\;\;\;\text{"expand the definitions of %#%#% and %#%#%"} \\ & d|(a+b) \;\land\; (d|a \lor d|b)) \\ = & \;\;\;\;\;\text{"distribute %#%#% over %#%#%"} \\ & (d|(a+b) \land d|a) \;\lor\; (d|(a+b) \land d|b) \\ = & \;\;\;\;\;\text{"on left hand side, use %#%#% to simplify %#%#%; similar for right hand side"} \\ & (d|b \land d|a) \;\lor\; (d|a \land d|b) \\ = & \;\;\;\;\;\text{"logic: simplify; reintroduce definition of %#%#%"} \\ & d|\gcd(a,b) \\ \end{align} que por divisor extensionality demuestra $\;\gcd\;$.