Prueba por inducción de la identidad de Bézout para $n$ enteros sin factores comunes

Question

Pregunta: Deje $n\geq 2$. Para cualquier enteros $a_1,a_2,\ldots,a_n$ tienen ningún factor común, existe enteros $x_1,x_2,\ldots,x_n$ tal que $$a_1 x_1 + a_2 x_2 + \ldots + a_n x_n = 1.$$

Esto es lo que hicieron y lo que no entiendo $(\star)$$(\star \star)$:

$P(n)$ es el predicado anterior.

Base:
$P(2)$ es verdadero por la Identidad de Bezout.

Inducción paso:
Deje $k\in\mathbb{N}$ $k\geq 2.$
Supongamos ahora que $P(k)$ es verdad, y deje $a_1,a_2,\ldots,a_k,a_{k+1}$ ser enteros sin factores comunes.
Debemos deducir que
$$a_1 x_1 + \ldots + a_k x_k + a_{k+1}x_{k+1} = 1$$ para algunos enteros $x_1,x_2,\ldots,x_{k+1}$.
Deje $g$ ser el máximo común divisor de $a_1,\ldots,a_k$ $\qquad(\star)$
A continuación, $\frac{a_1}{g},\ldots,\frac{a_k}{g}$ no tienen ningún factor común.
Por la hipótesis de inducción, existe enteros $y_1,\ldots,y_k$ tal que
$$\left(\frac{a_1}{g}\right)y_1 + \ldots + \left(\frac{a_k}{g}\right)y_k = 1.$$

También, $g$ $a_{k+1}$ no tienen un factor común (otra cosa, $g$ sería un factor común de $a_1,\ldots,a_{k+1}$.)

Así que por la Base de caso, $\qquad (\star\star)$
$$gz+a_{k+1}z_{k+1} = 1$$ para algunos enteros $z,z_{k+1}$.

Así que mi consulta es:
$(\star)$: Pensé que a partir de la asunción en la inducción caso, se asume que todos los enteros no tienen ningún factor común?
$(\star\star)$ : ¿Por qué usamos la base de caso? Es esto permitido? Nunca he visto una prueba por inducción en la inducción de paso que utiliza el "caso"?

Answer 1

$1.$ $g = 1$ en este caso. Ningún factor común, por lo tanto $gcd = 1$ para los números $\quad$ $2.$ no Hay ningún problema en el uso de la base de casos como sabes que es verdad(en este caso la identidad de Bezout), una conclusión de que no puede ser falsa. También, usted debe saber que la identidad de Bézout puede extenderse a más de dos enteros: si $gcd(a_{1},a_{2},\ldots ,a_{n})=d$ entonces existen enteros $x_{1},x_{2},\ldots ,x_{n}$ tal que $d=a_{1}x_{1}+a_{2}x_{2}+... +a_{n}x_{n}$ donde $d$ $gcd$

Answer 2

(*) Lo que la pregunta está pidiendo que demostrar es que se puede hacer esto para cualquier conjunto de números que no tienen ningún factor común a todas ellas, excepto $1$.

Ahora el problema es que cuando se toma $k+1$ números con esta propiedad, y luego mirar a la primera $k$, puede que no tengan la propiedad requerida. Así, en el fin de utilizar la inducción de la hipótesis de que usted necesita para convertir el primer $k$ números de un conjunto con ningún factor común (aparte de $1$). Usted puede hacer esto mediante la división por el HCF.

Por ejemplo, ir de$k=2$$3$. Usted podría ser dados tres números de $6,10,15$. Estos no tienen ningún factor común, pero dos de ellos tienen un factor común. Aquí tienes $g=2$, $2\times 3-1\times 5=1$, y por lo $2\times 6-1\times 10=2$. Ahora se utiliza $8\times 2-1\times 15=1$ conseguir $8\times (2\times 6-1\times 10)-1\times 15=1$, es decir,$16\times 6-8\times 10-1\times 15=1$.

(**) Sí, es bastante común en la inducción de las pruebas que se utiliza más que el anterior valor de $k$, - por este punto, usted sabe que es verdadera para todos los valores anteriores de $k$, así que está bien. Esto es a veces llamado "el fuerte de inducción".