La identidad de Bézout la prueba de que si $(a,b,c)=1$ $ax+bxy+cz=1$ ha entero soluciones

Question

Masiva editar para simplificar la cuestión. Algunos comentarios a continuación podría ser obsoleta - específicamente, el comentario de que de esta manera se sigue directamente de Dirichlet. Eso era verdad para la redacción original.

Estoy buscando una breve prueba, directamente de la identidad de Bézout, de la siguiente teorema:

Teorema 1: Si $(a,b,c)=1$ entonces existe un entero solución de $x,y,z$$ax+bxy+cz=1$.

El caso de $(a,b)=1$ resulta ser equivalente a la del teorema:

Teorema 2: La natural mapa: $$\mathbb Z_{nm}^\times\to\mathbb Z_{n}^\times$$ es en.

Eso es porque la "a" significa que si $(a,n)=1$ luego de algunos $y$, $a+ny\in\mathbb Z_{mn}^\times$, lo que significa que $(a+ny,m)=1$ e lo $1=(a+ny)x+mz=ax+nxy+mz$ tiene una solución. Lo contrario es igualmente obvio.

El caso general en el primer teorema de la siguiente manera, si conocemos el caso de al $(a,b)=1$ ya que, por general$(a,b)$,$\left(\frac{a}{(a,b)},\frac{b}{(a,b)}\right)=1$, por lo que desde el caso especial, obtenemos: $$\frac{a}{(a,b)}x_0 + \frac{b}{(a,b)} x_0y_0 + cz_0= 1$$ lo que implica:

$$ax_0 + bx_0y_0 + c((a,b)z_0)=(a,b)$$ Desde $1=(a,b,c)=((a,b),c)$ podemos encontrar $(u,v)$ por lo que: $$(a,b)u + cv = 1$$

A continuación, obtener:

$$a(x_0u) + b(x_0u)y_0 + c((a,b)z_0u + v) = 1$$

Por lo $(x,y,z)=(x_0u,y_0,(a,b)z_0u+v)$ es una solución de nuestra ecuación original. (Gracias Patrick Da Silva, para que la reducción de.)

Fácilmente se puede demostrar el Teorema 2 el uso de la estructura de $\mathbb Z_n^\times$ en términos del primer factorizations. De hecho, el Teorema 2, fue la motivación para esta pregunta, inicialmente - al principio pensé que era "obvio", pero inmediatamente se dio cuenta de que no era absolutamente trivial.

Ciertamente es posible traducir el "resumen" de la prueba del Teorema 2 en una prueba directa de que el caso especial del Teorema 1, utilizando el primer factorizations y teorema del resto Chino.

Pero algo acerca de este teorema sonó una campana para mí. Se ve como el tipo de teorema de que habría un corto Bezout la identidad de la prueba.

Ambos única factorización y teorema del resto Chino en realidad son resultados directos de Bézout, y a menudo teoremas que nos comprenden de manera intuitiva en términos de una única factorización y/o teorema del resto Chino tiene un corto, agudo prueba el uso de Bézout que evita tanto las palabras "prime" y "el resto."

Mi instinto es que debe haber una rápida prueba de lo anterior con la de Bézout, sin llamar a los números primos o restos, pero no he encontrado.

Es trivial si $(a,c)=1$, ya que el $ax+cz=1$ nos permite utilizar la $y=0$ para obtener una solución a $ax+bxy +cz=1$.

Es un poco más difícil, a ver si $(b,c)=1$, pero todavía no es difícil, ya que si $bu+cv=1$ $$a\cdot 1 + 1\cdot (1-a) = a\cdot 1 + b(u(1-a)) + c(v(1-a))$$ giving a solution $(x,y,z)=(1,u(1-a),v(1-a))$.

Que la asimetría (es fácil de resolver si $(a,n)=1$ y más difícil de resolver si $(b,n)=1$) sugiere que yo podría estar equivocado acerca de la existencia de dicha prueba, ya que de Bézout es simétrica declaración.

Si no era una prueba, parece que debería empezar con:

$$au+bv=1\\ax+ny=(a,n)\\bw+nz = (b,n)$$

---

Como un ejemplo de un teorema que es "evidente" con la única factorización, pero tiene una simple prueba con la identidad de Bézout, considere la posibilidad de:

$(a,n)=(a,m)=1\implies (a,mn)=1$

Que tiene una única factorización de la prueba, pero se sigue directamente de Bézout multiplicando: $$1=(ax_1+ny_1)(ax_2+my_2) = a(ax_1x_2 + mx_1y_2+nx_2y_1) + mn(y_1y_2)$$

---

Así que, de nuevo, el objetivo es no tener nada acerca de los números primos o Teorema del Resto Chino en la prueba, y tener que ser "extraordinariamente breve" - tanto como sea posible, no debería ocultar las pruebas de CRT o de factorización única.

No sé que tal prueba existe, pero algunos instinto me dijo que lo hizo.

Answer 1

Esto puede no ser tan sencillo como se esperaba, pero es puro Bezout.

Vamos a usar un par de los resultados probados en esta respuesta: $$ (ac,bc)=c(a,b)\etiqueta{1} $$ y $$ (a,b)=1\quad\text{y}\quad(a,c)=1\implica(a,bc)=1\etiqueta{2} $$ Además, desde el $(a,b)\mid a$$(a,b)\mid bc$, tenemos $$ (a,b)\mid(a,bc)\etiqueta{3} $$

---

Lema 1: Si $(a,b)=1$, luego $$ \begin{align} 1.&(a,n)(b,n)\mid n\\ 2.&(a+b,a^mb^n)=1 \end{align} $$ Prueba: Supongamos que $(a,b)=1$. Luego de algunos $x,y$ hemos $$ ax+by=1\etiqueta{4} $$ Por lo tanto, hemos $$ \begin{align} n &=n(ax+by)\\ &=\left(\frac{n}{(b,n)}\frac{ax}{(a,n)}+\frac{n}{(a,n)}\frac{by}{(b,n)}\right)(a,n)(b,n)\tag{5} \end{align} $$ y por lo tanto, llegamos a la conclusión de que $$ (a,n)(b,n)\mediados n\etiqueta{6} $$ Además, a partir de $(4)$, también tenemos $$ \begin{align} 1&=a(x-y)+(a+b)y&&(4)-ay+ay\tag{7}\\ 1&=(a+b)x+b(y-x)&&(4)+bx-bx\tag{8}\\ \end{align} $$ $(7)$ $(8)$ $(a+b,a)=1$ $(a+b,b)=1$ . Aplicar repetidamente $(2)$ rendimientos $$ (a+b,a^mb^n)=1\etiqueta{9} $$ $\square$

---

Lema 2: $$ \left (\frac{n}{(a^n,n)}\right)=1 $$ Prueba: Desde $(a^k,n)\mid(a^{k+1},n)\mid n$, debemos tener, para algunos $k\le n$,$(a^{k+1},n)=(a^k,n)$.

Supongamos que $(a^{k+1},n)=(a^k,n)$. A continuación, $\left(a\frac{a^k}{(a^k,n)},\frac{n}{(a^k,n)}\right)=1$ y por lo tanto, $\left(a,\frac{n}{(a^k,n)}\right)=1$.

Desde $k\le n$,$(a^k,n)\mid(a^n,n)$, y, en consecuencia, $$ \left (\frac{n}{(a^n,n)}\right)=1\etiqueta{10} $$ $\square$

---

Teorema: Si $(a,b)=1$, luego $$ \left(a+\frac{nu}{(a^n,n), (b,n)}b,n\right)=1 $$ donde $u$ satisface $(b,n)=bu+nv$.

Prueba: Supongamos que $(a,b)=1$$(b,n)=bu+nv$. El uso de $(2)$ repetidamente, obtenemos $$ (a^n,b)=1\etiqueta{11} $$ La combinación de $(6)$ $(11)$ de rendimiento $$ (a^n,n), (b,n)\mediados n\etiqueta{12} $$ Por lo tanto, $\dfrac{n}{(a^n,n)(b,n)}\in\mathbb{Z}$ $(10)$ dice que $$ \left (\frac{n}{(a^n,n), (b,n)}(b,n)\right)=1\etiqueta{13} $$ $(9)$ $(13)$ implica que $$ \left(a+\frac{n}{(a^n,n), (b,n)}(b,n),a^n\frac{n}{(a^n,n), (b,n)}(b,n)\right)=1\etiqueta{14} $$ Desde $(a^n,n)\mid a^n$,$\left.n\,\middle|\,a^n\dfrac{n}{(a^n,n)(b,n)}(b,n)\right.$, por lo que el uso de $(3)$ $(14)$ rendimientos $$ \left(a+\frac{n}{(a^n,n), (b,n)}(b,n),n\right)=1\etiqueta{15} $$ El resto es Bezout. $(15)$ dice que no se $x,y$, de modo que $$ \left(a+\frac{n}{(a^n,n), (b,n)}(b,n)\right)x+ny=1\etiqueta{16} $$ Además, desde el $(b,n)=bu+nv$, obtenemos $$ \left(a+\frac{nu}{(a^n,n), (b,n)}b\right)x+n\left(y+\frac{nv}{(a^n,n), (b,n)}\right)=1\etiqueta{17} $$ el que dice que $$ \left(a+\frac{nu}{(a^n,n), (b,n)}b,n\right)=1\etiqueta{18} $$ $\square$

---

Una nota sobre la aplicación

En primer lugar, $(18)$ puede parecer una respuesta teórica en el sentido de que es muestra de que podemos encontrar una $k$, de modo que $(a+bk,n)=1$, pero computacionalmente, lo que podría parecer un poco complicado debido a la aparición de $(a^n,n)$ en el denominador. Sin embargo, $n/(a^n,n)$ es simplemente $n$ con todos los factores comunes a $a$ eliminado. Para calcular los $n/(a^n,n)$, se puede empezar con $n_0=n$, y generar la secuencia $$ n_{k+1}=\frac{n_k}{(a,n_k)}\etiqueta{19} $$ en algún punto de $(a,n_k)=1$. Para ese $k$, tenemos $$ \frac{n}{(a^n,n)}=n_k\etiqueta{20} $$

Answer 2

Aplicación del Teorema del Resto Chino:

$$x\equiv a \textrm{ (mod $b$)}$$ $$x\equiv 1\textrm{ (mod $p$)}, \textrm{ for primes $p$ that divides $n$, but does not divide $b$}$$

Answer 3

Utilizamos una forma constructiva de Stieltjes método de construcción de coprimes.

${\bf Theorem}\quad\ \ \ \color{#c0f}{(a,b,c)=1}\, \Rightarrow\, (a\!+\!bn,c) = 1\,\ $ algunos $\,n\,$ que satisface $\ \color{#c00}{(n,a)=1}$

$\requieren{cancel}{\bf Prueba}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \fantasma{1^{1^{1^{1^{1^{1^1}}}}}} \phantom{\dfrac{1}{1^{1^1}}} (a,c) = 1\,\Rightarrow\, \smash[t]{\overbrace {(\!+\!bc,c)}^{\large (a,\,c)}=1.}\ $ Else induct on $c\!:\ $ $(un\!+\!bn,\color{#c70}{\large \frac{c}{(a,c)}})=1,\,$ $\, \color{#c00}{(n,a)\!=\!1},\,$ $(a\!+\!bn,\color{#0a0}{(a,c)}) = (bn,(a,c))=1\,$ $\,\color{#c0f}{(b,a,c)}=1=(\color{#c00}{n,a},c)\ $ $\ (a\!+\!bn,\color{#C70}{\large \frac{c}{\cancel{(a,c)}}}\!\color{#0a0}{\cancel{\small (a,c)}}\!)=1$

Answer 4

Correcto, pero imperfecto respuesta, vagamente basada en las ideas en robjohn la respuesta.

Lema 1: Si $(a,b)=1$, entonces para cualquier $n$, podemos encontrar $n=n_1n_2$$(n_1,n_2)=(a,n_1)=(b,n_2)=1$.

Prueba: Esto requiere de la inducción. Si $(n,a)=1$$n_1=n$$n_2=1$. De lo contrario, deje $m=\frac{n}{(a,n)}$. Luego, por inducción,$m=m_1m_2$$(m_1,m_2)=(m_1,a)=(m_2,b)$. Pero, a continuación, deje $n_1=m_1$$n_2=m_2(a,n)$. Desde $(a,b)=1$, $((a,n),b)=1$, por lo $(n_2,b)=1$. Así que hemos terminado.

[Que se supone $(x,z)=(y,z)=1\Rightarrow (xy,z)=1$, que es fácil de demostrar con Bézout.]

---

Teorema 1: Si $(a,b)=1$ $\exists x,y.z: ax+bxy + cz=1$

Prueba: Por el Lema 1, podemos escribir $c=c_1c_2$$(c_1,c_2)=(a,c_1)=(b,c_2)=1$. Resolver las siguientes ecuaciones:

$$ c_1p + c_2q = 1\tag{1}$$ $$au_1+c_1v_1=1\tag{2}$$ $$bu_2+c_2v_2=1\tag{3}$$

Reescribir (3) como: $$a\cdot 1 + bu_2(1-a) + c_2v_2(1-a)=1\tag{4}$$ Multiplicando (2) por $c_2q$ y (4) por $c_1p=1-c_2q$ y sumando, obtenemos:

$$a(c_2qu_1 + 1-c_2q) + b(u_2(1-a)c_1p) + c_1c_2(v_1q+v_2p(1-a))=1\tag{5}$$

Dejando $y=u_2(1-a)c_1p, x=c_2q(u_1-1)+1, z_0=v_1q+v_2p(1-a)$ vemos que:

$$ax + by+ cz_0=1\tag{6}$$

Y aquí está la magia: $$xy = c_2q(u_1-1)y + y = c_1c_2q(u_1-1)p(1-a)u_2 + y=cD+y\tag{7}$$

donde $D=q(u_1-1)p(1-a)u_2$.

Por lo $$ax + bxy + c(z_0-bD)=1$$Esto demuestra nuestro teorema.

No del todo satisfactoria, excepto por el hecho de que tenemos una forma sistemática para encontrar $x,y,z$ cualquier $(a,b,c)$.

---

¿Qué está pasando aquí? Como se señaló en la pregunta, si $(a,c)=1$ $ax+cz=1$ tiene una solución, y $y=0$ nos da nuestra solución.

Si $(b,c)=1$, entonces la solución de $bu+cv=1$ lo que nos da una solución:

$$a\cdot 1 + b(u(1-a)) + c(v(1-a))=1$$ Por lo anterior, tenemos esencialmente soluciones fáciles:

$$ax+bxy \equiv 1 \pmod {c_1,c_2}$$

y somos la combinación de estas soluciones fáciles a estas dos ecuaciones en la forma en que la identidad de Bézout nos permite demostrar el Teorema del Resto Chino.

La (no-realmente-para-la magia) el hecho de que $xy\equiv y\pmod {c}$ proviene del hecho de que $x\equiv 1\pmod {c_2}$$y\equiv 0\pmod {c_1}$.

Lema 1 es esencialmente robjohns trabajo acerca de la $(a^n,n)$, pero en sentido inverso. Creo Lema 1 es una medida más directa de la inducción - exponenciación es artificial en este problema.

Esta prueba es también bastante exactamente la misma respuesta que i707107, que dieran la respuesta en términos de la descomposición en factores primos y el Teorema del Resto Chino.

---

Pero Posiblemente Menos Misterioso Prueba

Hay un poco el enfoque más directo donde podemos probar de forma más concreta el teorema:

Teorema 3: Si $(a,b)=1$, entonces para cualquier $c$ podemos encontrar $x,y,z$ por lo que:

$$ax+by+cz = 1\\ c\mid xy-y$$

Nota: Teorema 3 implica claramente Teorema 1. No es transparente, que el Teorema 1 implica Teorema 3.

La prueba del Teorema 3:

Como se señaló antes, cuando $(a,c)=1$ podemos encontrar una solución a la ecuación lineal con $y=0$. Si $(b,c)=1$, podemos encontrar una solución con la con $x=1$. En ambos casos, $xy-y=0$, por lo que la segunda condición es verdadera.

Así que todo lo que tenemos que mostrar es que si $(c_1,c_2)=1$ y tenemos soluciones:

$$ ax_i+by_i+c_iz_i=1\\c_i\mid x_iy_i-y_i$$

para $i=1,2$, entonces podemos encontrar una solución:

$$ax+by+c_1c_2z = 1\\ c_1c_2\mid xy-y$$

El camino directo para combinar las ecuaciones lineales simplemente funciona. Solucionar $c_1u+c_2v=1$ y elige:

$$x = c_2vx_1 + c_1ux_2\\y=c_2vy_1 + c_1uy_2\\z=z_1v+z_2u$$

Para obtener $c_1c_2$ multiplicamos la primera ecuación lineal por $c_2v$ y el segundo por $c_1u$ y añadir para obtener una ecuación lineal para $a,b,c_1c_2$.

Ahora sólo tiene que comprobar que $xy-y$ es divisible por $c_1c_2$. Esto se puede hacer por dolorosos de cálculo. El gran truco es usar ese $(c_1u)^2 = c_1u(1-c_2v) = c_1u - c_1c_2(uv)$ y de la misma manera que $(c_2v)^2 = c_2v - c_1c_2(uv)$. Esto le permite conseguir que $xy = c_2vx_1y_1 + c_1ux_2y_2 + c_1c_2D$ algunos $D$. Pero, a continuación, $x_iy_i-y_i$ divisible por $c_i$ significa que podemos escribir esto como: $xy = c_2vy_1 + c_1uy_2 + c_1c_2D_2 = y + c_1c_2D_2$, para algunas de las $D_2$.

Básicamente, la razón por la que $c_1c_2\mid xy-y$ es que el $x$ $y$ son las fórmulas para el teorema del resto Chino, por lo $x\equiv x_i\pmod {c_i}$ y, por tanto, $c_i\mid xy-y$ por cada $i$. Pero usted puede evitar los llamamientos para el teorema del resto trabajando y demostrando que $c_1c_2|xy-y$.

Una vez que se tiene este resultado, puedes usar el Lema 1 anterior para demostrar el resultado general para todos los $c$.

Un último comentario. Lema 1 en realidad es fácil de generalizar a:

Lema 2: Si $(a,b,c)=1$ entonces existe una factorización $c=c_1c_2$$(c_1,a)=(c_2,b)=(c_1,c_2)=1$.

Prueba: Dejando $a'=\frac{a}{(a,b)}$ $b'=\frac{b}{(a,b)}$ aplicamos el Lema de 1 a $a',b',c$ obtenemos $c=c_1c_2$$(c_1,c_2)=(a',c_1)=(b',c_2)=1$. Pero entonces, dado que la $((a,b),c_1)=1$$(a',c_1)=1$, nos hve que $(a,c_1)=1$. Asimismo, para $b$. Esto requiere que los Lemas:

Lema 3: Si $(a_1,c)=(a_2,c)=1$$(a_1a_2,c)=1$.

Prueba: Esto es demostrado fácilmente de Bézout por la multiplicación de las dos ecuaciones $a_ix_i+cy_i=1$$i=1,2$.

Lema 4: Si $(a,b)=1$$c\mid b$$(a,c)=1$.

Prueba: Nuevo, fácil de probar de Bézout - si $c=bd$$1=ax+by=ax+c(dy)$.

Lema 2 significa que podemos eliminar la condición de que $(a,b)=1$ en nuestros teoremas - solo que de la condición de factor de $c$ a través de Lema 1.

---

Robjohn prueba, simplificado

Robjohn la respuesta se puede resumir de la siguiente manera:

Lema 5: Si $(a,b,n)=1$ entonces existe un $n_1$ tales que las siguientes condiciones: $$(a+n_1,n)=1\\(b,n)\mid n_1\mid n$$

Prueba: Inducción en $n$.

Si $(a,n)=1$ podemos optar $n_1=n$ desde $(a,n)=1\Rightarrow (a+n,n)=1$$(b,n)\mid n$.

Si $(a,n)>1$ escritura $n=(a,n)m$, y encontrar$m_1$, de modo que $(a+m_1,m)=1$$(b,m)\mid m_1\mid m$. . Escrito $$1=(a+m_1)x + my = ax + m_1\left(x+\frac{m}{m_1}y\right)$$, we see that $(una,m_1)=1$.

Deje $n_1=m_1$. A continuación, $(a,n_1)=(a,m_1)=1$, y podemos concluir que $(a+n_1,a)=1$$(a+n_1,(a,n))=1$. Por lo $$(a+n_1,n)\mid (a+n_1,(a,n))\cdot(a+n_1,m)=1$$

Por último, podemos ver fácilmente que, desde $(a,n)=1$,$(b,n)=(b,m)$. Por lo $(b,n)=(b,m)\mid n_1=m_1\mid m\mid n$.

---

Teorema: Si $(a,b,n)=1$ entonces existe un $x,y,z$, de modo que $ax+bxy+cz=1$.

Prueba: Vamos a $n_1$ ser como en el Lema 5. A continuación, podemos encontrar soluciones para: $$bu+nv=n_1\\(a+n_1)x+nz=1$$

La sustitución de $n_1$ en la segunda, obtenemos: $$(a+bu)x + n(z+xv)=1$$

---

Este es el corazón de robjohn la solución, sino que evita que la exponenciación en el argumento, y menos de todas las fracciones. Esencialmente, $n_1=\frac{n}{(a^n,n)}$, pero esos detalles son ruidosas por el resto de la prueba, mientras que estas son las únicas propiedades que realmente necesitamos para$n_1$, y podemos probar que por inducción directamente.

Answer 5

Creo que he encontrado un excelente corto de la prueba.

Teorema 1: Si $(a,b,c)=1$ existe $x,y,z$, de modo que $$ax+bxy+cz=1$$.

Prueba: Inducción en $c$$b$.

Podemos resolver si $b=1$ mediante el establecimiento $(x,y,z)=(1,(1-a),0)$.

Ahora, supongamos que, para algunos, $c$ podemos resolver para $(a,b,c')$ si $c'<c$ $(a,b',c)$ si $b'<b$.

Luego descanso, esta en dos casos.

Caso 1 Si $b\not\mid c$, $(b,c)<b$ y, por la hipótesis de inducción, podemos resolver:

$$ax+(b,c)xy+cz =1$$ y $$bu+cv=(b,c)$$

A continuación, $$ax +bx(uy) + c(z+vxy)=1$$

Caso 2 Si $1<b\mid c$,$1=(a,b,c)=(a,b)$. Deje $c=bd$.

Desde $d<c$$(a,b,d)|(a,b,c)=1$, podemos resolver:

$$ax+bxy + dz=1$$

Que puede ser visto como diciendo que $(a+by,d)=1$. Pero de $(a,b)=1$, podemos ver que $(a+by,b)=1$. Así que esto significa que $(a+by,c)=(a+by,db)=1$. Y entonces podemos encontrar una solución a $$(a+by)X+cZ=1$$

(Que podría ser más explícito en el último paso: Si $au+bv=1$$(a+by)u + b(v-yu)=1$. Multiplicando eso por $(a+by)x+ dz=1$ nos da una solución explícita a $(a+by)X + bdZ=1$.)

---

El truco aquí en caso de que (1) fue en robjohn la prueba de que él resuelto por el triple $(a,(b,c),c)$ primero, y luego mostrar que había una solución para el triple $(a,b,c)$. Acabo de empujó ese truco en el descenso de la parte de la prueba.

Esto oculta el "factoring" parte de la prueba. Ciertamente, estamos esencialmente de factoring las partes de $c$ que son comunes con $b$ en el descenso, pero se siente más orgánico.

Un hecho interesante acerca de esta prueba es que el nuevo $y$ obtenemos a través de la inducción es siempre el mismo $y$ o $yu$. Desde $a$ no cambia en la inducción, y $y=1-a$ al $b=1$, esto significa que el $y$ obtenemos de esta prueba es siempre divisible por $a-1$.