¿Cómo se utiliza la inducción para demostrar que $\gcd(an, bn) = |n|\gcd(a, b)$

Question

En el libro Teoría elemental de los números: Primas, Congruencias y Secretos escrito por William Stein, que puede encontrarse en http://wstein.org/ent/ Stein demuestra lo siguiente en la página 6/lemma 1.1.17:

Lema $\ $ Para cualquier número entero $a, b, n,$ tenemos $\, \gcd(an, bn) = |n|\gcd(a, b)$

Prueba $\ $ Recorremos el algoritmo de Euclides para $\gcd(an, bn)$ y anotar que en cada paso la ecuación es la ecuación del algoritmo de Euclides de Euclides para $\gcd(a, b)$ pero multiplicado por $n.$ Para simplificar, asumimos que ambos $a$ y $b$ son positivos. Demostraremos el lema por inducción en $a + b$ . La afirmación es verdadera en el caso base cuando $a + b \le 2$ desde entonces $a = b = 1$ . Supongamos ahora que $a, b$ son arbitrarios con $a \ge b$ . Sea $q$ y $r$ sea tal que $a = bq + r$ y $0 \le r < b$ . Entonces, por los lemas 1.1.9-1.1.10, tenemos $\gcd(a, b) = \gcd(b, r)$ . Multiplicando $a = bq + r$ por $n$ vemos que $an = bnq + rn$ Así que $\gcd(an, bn) = \gcd(bn, rn)$ . Entonces

$$b + r = b + (a - bq) = a - b(q - 1) \le a < a + b,$$

así que por inducción $\gcd(bn, rn) = |n|\gcd(b, r)$ . Desde $\gcd(b, r) = \gcd(a, b)$ Esto demuestra el lema.

Mi principal duda con respecto a esta prueba es que tengo problemas para seguir cómo $b + r < a + b$ conduce al hecho de que $\gcd(bn, rn) = |n| \gcd(b, r).$

Creo que mis problemas para comprender esta prueba están relacionados con mi comprensión básica de la inducción matemática, nunca supe lo que era antes de tropezar con esta prueba. Mi comprensión actual de la inducción es que demuestras tu afirmación para un caso base, $a + b = 2,$ entonces se demuestra que si la afirmación es verdadera para un número natural cualquiera, entonces es verdadera para el siguiente. Sin embargo, no entiendo cómo se utiliza ese principio en esta prueba, cualquier explicación es muy apreciada.

Answer 1

Es cierto que la inducción matemática consta de tres pasos:

1. Demostrar el caso base.
2. Supongamos que la afirmación es cierta para algunos $n\in\Bbb N$ (posiblemente incluyendo $0$ si es necesario).
3. Utilice el supuesto anterior para demostrar la afirmación de $n+1$ .

Veamos esto en la práctica con un ejemplo estándar:

$$1+2+3+\ldots+n = \frac{n(n+1)}{2}\tag{1}$$

Caso base: $$1=\frac{1(1+1)}{2}\quad\small\text{(obviously true)}$$

Supongamos que la fórmula $(1)$ es cierto para algunos $n$ . Ahora tenemos que demostrar que $$\underbrace{1+2+3+\ldots +n}_{\text{use the assumption on this}}+(n+1) = \frac{(n+1)(n+2)}{2}$$ y podemos usar la suposición para obtener $$1+2+3+\ldots +n+(n+1) = \frac{n(n+1)}{2} +(n+1) = \frac{(n+1)(n+2)}{2}$$ así que hemos terminado.

Ahora, en tu ejemplo, lo que se utiliza es una versión de la inducción llamada inducción fuerte. La diferencia es que en el paso 2, asumimos algo más fuerte, pero resulta que esto es equivalente a la inducción "débil" (sólo resulta ser más conveniente en algunos casos).

1. Demuestra el caso base.
2. Arreglar algunos $n\in\Bbb N$ y asumir que la afirmación es cierta para todo números naturales $k$ cuando $k< n$ .
3. Utilice el supuesto anterior para demostrar la afirmación de $n$ .

---

Ahora intentaré aclarar los pasos de su prueba. Definamos $m=a+b\in\Bbb N$ . Haremos la inducción en $m$ .

El caso base es $m = 2$ . Desde $a+b = 2$ y $a,b>0$ Debemos tener $a=b=1$ Así que $$\gcd(na,nb) = \gcd(n,n) = |n| = |n|\gcd(a,b).$$

Ahora dejemos que $m\in\Bbb N$ y asumir que $$\gcd(na',nb') = |n|\gcd(a',b'),\quad(\forall a',b'\in\Bbb N)\ a'+b' < m.\tag{2}$$ Queremos demostrar que la afirmación es cierta para $a,b$ (recuerda que $a+b=m$ ).

Utilizando la división de Euclides, tenemos $a = qb + r$ , $0\leq |r|<b$ y por lo tanto $$\gcd(a,b) = \gcd(b,r).$$ Pero si multiplicamos todo por $n$ obtenemos $na = qnb + nr$ , $0\leq |nr| < nb$ , por lo que tenemos que $$\gcd(na,nb) = \gcd(nb,nr).$$

Obsérvese que si podemos demostrar que $$\gcd(nb,nr) = |n|\gcd(b,r),\tag{3}$$ tendremos $$\gcd(na,nb) = |n|\gcd(a,b)$$ también. Así que veamos si podemos emplear nuestra suposición $(2)$ - para que funcione, debemos comprobar que $b+r<m$ y puedes comprobar con tu prueba cómo se hace. Por lo tanto, podemos aplicar el supuesto de inducción para concluir que $(3)$ es cierto.

Además, fíjate en que sí necesitamos una inducción fuerte, ya que no sabemos que $b + r + 1 = m$ que querríamos en la inducción ordinaria.