Yo no puedo romper este.
Demostrar: Si $\gcd(a,b,c)=1$ existe $z$ tal que $\gcd(az+b,c) = 1$ (la única restricción es que el $a,b,c,z \in \mathbb{Z}$).
Respuestas
¿Demasiados anuncios?
Esto se puede resolver de forma intuitiva mediante un ligero giro en Euclid la idea de generar nuevos números primos. Euclides empleadas $\,1 + p_1\cdots p_n$ es coprime a $\,c = p_1\cdots p_n.\,$ Stieltjes señaló la generalización de que, además, $\ \color{#c00}{p_1\cdots p_k} +\, \color{#0a0}{p_{k+1}\cdots p_n}\,$ es coprime a$\,c\,$, lo que motiva la siguiente
Idea clave $\, $ Coprimes a $\,c\,$ surgir por la división en $\rm\color{#c00}{two}\ \color{#0a0}{summands}$ todos los factores primos de a $\,c,\,$ es decir
Teorema $\,\ \ \color{#c00}a+\color{#0a0}b\ $ es coprime a $\ c\:$ si cada factor primo de $\,c\,$ divide $\,a\,$ o $\,b,\,$, pero no tanto.
Prueba de $\ $ Si no $\,a+b\,$ $\,c\,$ tienen en común un factor primordial $\,p.\,$ Por la hipótesis de $\,p\mid a\,$ o $\,p\mid b.\,$ Wlog, decir $\,p\mid b.\,$ $\,p\mid (a+b)-b = a,\,$ $\,p\,$ divide tanto a a $\,a,b,\,$ contra la hipótesis. $ $ QED
El OP busca $\,\color{#c00}{az}+\color{#0a0}b\,$ coprime a$\,c,\,$, por lo que es suficiente para elegir a $\,z\,$ de manera tal que cada primer factor de $\,p\,$ $\,c\,$ divide exactamente uno de $\,az\,$ o $\,b.\,$ $\,p\,$ no se puede dividir tanto $\,a,b,\,$ else $\,p\mid a,b,c,\,$ contra la hipótesis. Por lo tanto, es suficiente para dejar a $\,z\,$ ser el producto de números primos en $\,c\,$ que no se producen en $\,a\,$ o en $\,b.\ \ $ QED
Comentario $\ $ Nota cómo la solución se vuelve bastante obvio después de emplear Stieltjes idea, que asciende a nada más que un trivial cálculo de la diferencia de conjuntos (de los números primos)
Hagen von Eitzen
Puntos
171160
La afirmación no es necesariamente cierto: Considerar la posibilidad de $a=5$, $b=7$, $c=0$. A continuación,$\gcd(a,b,c)=\gcd(7,5)=1$, mientras que de $\gcd(az+b,c)=|az+b|\ne 1$, no importa lo $z$ elegimos.
Asume, por tanto, que $\gcd(a,b,c)=1$$c\ne0$. Deje $p$ ser un primer dividiendo $c$. A continuación, $0\cdot a+b=b$ $1\cdot a+b=a+b$ no pueden ser múltiplos de $p$ porque eso significaría $p\mid \gcd(a,b,c)$. Por tanto, para cada $p\mid c$ existe $z_p$$p\not\mid az_p+b$. Por el Teorema del Resto Chino, no existe $z$ $z\equiv z_p\pmod p$ para todos (un número finito) $p\mid c$. Desde $az+b\equiv az_p+b\pmod p$ llegamos a la conclusión de que $p\not \mid az+b$. En consecuencia, $\gcd(a+zb,c)=1$.
Onorio Catenacci
Puntos
6130
Deje $p_1,\ldots,p_k$ ser los primos que dividen a $c$ (asumiendo $c \ne 0$) y también se dividen $az+b$ algunos $z$. Tenga en cuenta que no $p_i$ puede dividir $a$, ya que entonces se dividía $b$.
De ello se sigue que dos valores distintos de $z$ para que algunos fijos $p_i$ divide $az+b$ debe difieren en un múltiplo de $p$. Por lo tanto, hay un único $z_i$$0 < z_i < p_i$$p_i|(az_i+b)$$p_i|(az+b) \Leftrightarrow z \equiv z_i \bmod p_i$.
Ahora seleccione los números de $y_i$$0 \le y_i < p_i$$y_i \ne z_i$. Por el Teorema del Resto Chino, hay un $z$ $z \equiv y_i \bmod p_i$ por cada $i$ y, por tanto, $az+b$ no es divisible por $p_i$${\rm gcd}(az+b,c)=1$.
barto
Puntos
6296
Esta cuestión está estrechamente relacionada con esto . Hay una pequeña diferencia, pero al parecer ambas soluciones, siempre que no cabe aquí también, después de una muy pequeña modificación:
Suponga $c\neq0$.
Deje $p_1,p_2,\ldots,p_i$ ser los primos comunes divisores de $c$$b$, con sus respectivas competencias, $e_1,\ldots,e_i$ en el primer factorización de $c$.
Si establecemos $d=p_1^{e_1}\cdots p_i^{e_i}$, $z=\frac cd$ va a satisfacer $\gcd(az+b,c)=1$.
Para ver por qué, supongamos $q$ es el primer y $q$ divide tanto a a$c$$az+b$. Si $q\mid b$, entonces debemos tener $q\mid az$ lo cual es imposible, ya que $\gcd(a,b,c)=1$$\gcd(z,b)=1$. Si $q\nmid b$, $q\mid z$ por la definición de $z$, y por lo tanto $q\nmid az+b$, una contradicción de nuevo.
Una alternativa con la inducción:
Claramente el deseado teorema es cierto para $a,c=\pm 1$.
Ahora supongamos que sabemos que es verdadero para todos los $a,c$ satisfacción $|a|+|c|\leq s$. (Vamos a hacer la inducción en $s$.)
Deje $|a|>1$. (El caso de $a=\pm1$ es trivial y no necesita de inducción, de hecho.)
Si $a\mid c$, vamos a $c=c'a$ y, a continuación, $(za+b,c)=(za+b,c'a)=(za+b,c')$ todos los $z$, porque se nos da $(a,b,c)=1$. Ahora $|a|+|c'|<|a|+|c|$ y llegamos a la conclusión, por la hipótesis de inducción, hay un $z$ satisfacción $(za+b,c)=1$.
Si $a\nmid c$, vamos a $g=(a,c)$.
Estamos buscando un entero $d$ $(d,c)=1$ tal que $az+kc=d-b$ tiene una solución para $z$$k$. (Esto es simplemente la reescritura $(az+b,c)=1$ donde $d\equiv az+b\pmod c$.)
Es bueno saber que una ecuación lineal tiene una solución si y sólo si $g\mid d-b$, o, equivalentemente, $d=z'g+b$ algunos $z'$. Debido a $|g|<|a|$ podemos utilizar de nuevo la hipótesis de inducción, y a la conclusión de que existe una $z'$, y por lo tanto no existe tal $z$.
