Si $(a,b,c)=1$ ¿hay $n\in \mathbb Z$ tal que $(a,b+nc)=1$ ?

Question

En el libro Conferencias sobre formas modulares En la página 8 se encuentra la afirmación de que

Si $(a,b,c)=1$ entonces hay $n\in \mathbb Z$ tal que $(a,b+nc)=1$ .

Sé que, si $(a,b)=1$ , entonces podemos tomar $n=0$ . Pero, si $(a,b)\not=1$ Entonces, ¿qué podríamos hacer? Además, traté de ver las combinaciones lineales de $a, b, c$ que son $=1$ pero no he descubierto nada. La principal dificultad que he encontrado es que el coeficiente de $b$ podría no ser $1$ .
Cualquier pista es bien apreciada.
Gracias de antemano.

Answer 1

Dejemos que $\rm n$ sea el producto de todos los primos que dividen $\rm a$ pero no $\rm b$ . Supongamos que $\rm p\mid a,b+nc$ con $\rm p$ de primera.

• Supongamos que $\rm p\mid b$ . Entonces $\rm p$ no puede dividir $\rm c$ (ya que $\rm p\mid a,b,c\implies p\mid(a,b,c)$ ) ni divide $\rm n$ por definición, pero $\rm p\mid b\implies\rm p\mid (b+nc)-b=nc\implies p\mid n$ o $\rm p\mid c$ imposible.
• Supongamos que $\rm p\nmid b$ . Pero entonces $\rm p\mid a,p\nmid b\implies p\mid n\implies\rm p\mid (b+nc)-nc=b$ imposible.

Por lo tanto, el gcd $\rm(a,b+nc)$ es $1$ ya que no es divisible por ningún primo $\rm p$ .

Answer 2

(Prueba de exageración)

Sabemos que $\gcd(a,\gcd(b,c))=1$ . Sea $b+c=\gcd(b,c)P+\gcd(b,c)Q=\gcd(b,c)(P+Q)$ donde $b=\gcd(b,c)P$ y $c=\gcd(b,c)Q$ . Tenga en cuenta que $\gcd(P,Q)=1$ (ya que dividimos por el máximo común divisor). Por el Teorema de Dirichlet sobre los primos en la progresión aritmética hay infinitos primos de la forma $P \mod Q$ o en otras palabras hay infinitos primos $\pi=P+nQ$ . Obviamente hay un $\pi$ tal que $\gcd(a, \pi)=1$ y $\gcd(a,\gcd(b,c)\pi)=1$ . Bien $\gcd(b,c)\pi=\gcd(b,c)(P+nQ)=b+nc$ .

Answer 3

Merece la pena destacar que la idea clave de la prueba clásica en la respuesta de anon es bastante sencilla.

Teorema $\,\ \ b+c\ $ es coprima de $\ a\:$ si cada factor primo de $\,a\,$ divide $\,b\,$ o $\,c,\,$ pero no ambos.

Prueba $\ $ Si no, entonces $\,a\,$ y $\,b+c\,$ tienen un factor primo común $\,p.\,$ Por hipótesis $\,p\mid b\,$ o $\,p\mid c.\,$ Wlog, digamos $\,p\mid c.\,$ Entonces $\,p\mid (b+c)-c = b,\,$ así que $\,p\,$ divide ambos $\,b,c,\,$ contra hipótesis. $ $ QED

Ya que buscamos $\,b+nc\,$ coprima a $\,a,\,$ basta con elegir $\,n\,$ tal que cada factor primo $\,p\,$ de $\,a\,$ divide exactamente uno de $\,b\,$ o $\,nc.\,$ Nota $\,p\,$ no puede dividir ambos $\,b,c,\,$ si no $\,p\mid a,b,c,\,$ contra hipótesis. Por lo tanto, basta con elegir $\,n\,$ para ser el producto de los primos en $\,a\,$ que no se producen en $\,b\,$ o en $\,c.\,$

Este método de generación de (co)primos mediante la partición de los factores primos de $\,a\,$ en dos sumandos tiene una historia ilustre, por ejemplo, Stieltjes lo utilizó para generalizar la prueba clásica de Euclides de que hay infinitos primos: dividir el producto $\: a\,$ de los primos anteriores en dos productos $\,b,c.\,$ Su suma da un entero coprimo a los primos anteriores, por lo que sus factores primos son nuevos, es decir, no están entre los primos anteriores. La prueba clásica de Euclides es simplemente el caso especial en el que $\, c = 1.$

Answer 4

La respuesta de anon es elegante y corta, con la elección específica de $n$ . Por otro lado, la respuesta de Bageer es más "elemental" en el sentido de que podría revelar la esencia de la cuestión, al menos en mi opinión. Permítanme explicar por qué lo digo.
En primer lugar $(a,b+nc)=(a,g(P+nQ))=(a,P+nQ)$ , donde $g=(b,c)$ , $b=gP$ y $c=gQ$ . Así, la idea de Bageer es encontrar $n$ tal que $P+nQ$ es un primo mayor que $a$ . Y por el teorema de Dirichlet, esto es posible.

Advertencia: Lo que sigue no es la explicación, sino un largo análisis de las ecuaciones implicadas. Así que el lector no interesado puede terminar el post aquí. Gracias por la atención.

Además, nos encontramos con que nuestro objetivo es simplemente encontrar $k$ tal que $k\equiv P\pmod Q$ y $(k,a)=1$ . Así que estamos buscando $k$ tal que $xk+ya=1$ es solucionable, es decir $xP+xzQ+ya=1$ es solucionable. Restringimos $z$ para que $zQ\equiv b\pmod P$ es decir $zQ=z'P+b$ para algunos $z'$ , donde $b$ es otra variable. Ahora bien, ver $z', b$ como variables independientes con $x$ encontramos que nuestra ecuación se convierte en $x(1+z')P+xb+ya=1$ . Escriba además $xb=1-fg'$ , donde $g'=(P,a)$ . Finalmente llegamos a la ecuación $(1+z')(1-fg')P+yba=bfg'$ .
Además, escriba $P=g'P'$ y $a=g'a'$ . Entonces se convierte en $(1+z')(1-fg')P'+bya'=bf$ . Ahora, sólo tenemos que elegir $f$ , por lo que esto nos da una solución de hecho.
En primer lugar, estamos sujetos a tres condiciones: $$\begin{cases}z'P\equiv -b\pmod Q\\b\mid1-fg'\\(1+z')(1-fg')P'+bya'=bf\end{cases}.$$
A continuación, vamos hacia atrás, es decir, dado un $b$ existe una única clase de residuo módulo $Q$ tal que $z'P\equiv -b\pmod Q.$ Dejemos entonces que $b=1$ Así que $-z'$ es la inversa de $P$ en $\mathbb Z/Q\mathbb Z,$ lo que es posible ya que $\gcd(P,Q)=1.$
Y observamos que, en $hP+ya+mQ=1$ , $h$ se determina sólo en el módulo $g''=\gcd(a,Q),$ que es una combinación lineal de $a$ y $Q$ . Además, dado que $\gcd(g',g'')=1$ podemos encontrar $f$ tal que $1-fg'\equiv h\pmod {g''}.$ Esto implica que la ecuación $$(1-fg')P+ya\equiv1\pmod Q$$ es solucionable. Por lo tanto, nuestra ecuación original es resoluble módulo $Q$ . Ahora estoy tratando de "levantar" esta ecuación a enteros, así que por favor déjame continuar después, gracias.
Cualquier punto inadecuado debe ser localizado. Gracias de antemano.

Answer 5

Otros, más arriba, ya han reducido la cuestión al caso de que $(b,c)=1$ .

Tenga en cuenta que el caso $(b,c)=1$ se puede enunciar algebraicamente como el teorema:

El mapa natural: $$\mathbb Z_{ac}^\times\to \mathbb Z_{c}^\times$$ está en.

Esto se puede ver utilizando el teorema de la estructura: Si $c=p_1^{c_1}\dots p_k^{c_k}$ entonces $\mathbb Z_c^\times \cong \prod_i Z_{p_i^{c_i}}^\times$ , lo que se puede ver por el teorema chino del resto.

Ahora bien, si $a=p_1^{a_i}\cdots p_k^{a_k}$ (ahora permitimos el $a_k, c_k$ sea cero para utilizar un conjunto de primos) entonces el mapa $\mathbb Z_{ac}^\times\to \mathbb Z_{c}^\times$ está totalmente determinada por los mapas correspondientes $$\mathbb Z_{p_i^{a_i+c_i}}^\times\to \mathbb Z_{p_i^{c_i}}^\times$$ En particular, si ese mapa es onto para cada $i$ obtenemos que todo el mapa $\mathbb Z_{ac}^\times\to \mathbb Z_{c}^\times$ está en.

Así que podemos reducir a donde $a=p^i$ y $c=p^j$ . Ese caso es realmente fácil de probar.

---

Como alternativa, se factoriza $a=a_1a_2$ para que $(a_1,a_2)=(a_1,b)=(a_2,c)=1$ . (Que podemos hacerlo es una prueba de descenso relativamente directa.) Resuelve las dos ecuaciones $$a_2u+cv=1\\a_1p+a_2q=1$$ y entonces tienes las dos ecuaciones:

$$(b+c\cdot 0,a_1)=1$$ $$(b+c(1-b)v,a_2)=1$$

Así que puedes usar el Teorema Chino del Resto para resolver $$n\equiv 0\pmod {a_1}\\n\equiv (1-b)v\pmod{a_2}$$

Esto da:

$$n=(1-b)vpa_1$$

Que satisface $(b+cn,a_1)=(b+cn,a_2)=1$ y por lo tanto $(b+cn,a)=1$ .

Esencialmente, $b+cn\equiv b\pmod {a_1}$ y $b+cn\equiv 1\pmod {a_2}$ .

---

O puedes mirar mi prueba de descenso que si $(a,b,c)=1$ entonces puede encontrar $x,y,z$ para que $$ax+bxy+cz=1$$

Este resultado demuestra que $(a+by,c)=1$ para algunos $y$ . Tendrás que reordenar los nombres de las variables para obtener el resultado.