Cómo mostrar $a,b$ coprima a $n\Rightarrow ab$ coprima a $n$ ?

Question

Dejemos que $a,b,n$ sean números enteros tales que $\gcd(a,n)=\gcd(b,n)=1$ . Cómo demostrar que $\gcd(ab,n)=1$ ?

En otras palabras, cómo demostrar que si dos enteros $a$ y $b$ no tienen ningún divisor común no trivial con y entero $n$ entonces su producto no tiene un divisor común no trivial con $n$ o bien.

Este es un problema que es un ejercicio en mi curso.

Intuitivamente parece plausible y es fácil de comprobar en casos concretos, pero cómo dar una prueba real no es obvio.

Answer 1

$\gcd(a,n)=1$ implica $ar+ns=1$ para algunos enteros $r,s$ . $\gcd(b,n)=1$ implica $bt+nu=1$ para algunos enteros $t,u$ . Así que $$1=(ar+ns)(bt+nu)=(ab)(rt)+(aru+sbt+snu)n$$ así que $\gcd(ab,n)=1$ .

Answer 2

Sugerencia $\rm\ \ (n,ab)\ =\ (n,nb,ab)\ =\ (n,\overbrace{(n,a)}^{\large 1}\:b)\ =\ (n,b)\ =\ 1\ $ utilizando las leyes anteriores de la DGC.

Estos ejercicios son fáciles de realizar aplicando las leyes básicas del GCD que mencioné en tus preguntas anteriores, es decir, el gcd asociativo conmutativo, distributiva y la ley modular $\rm\:(a,b+c\:a) = (a,b).\,$ De hecho, para que estas pruebas sean más intuitivas puede escribir $\rm\:gcd(a,b)\:$ como $\rm\:a\dot+ b\:$ y luego utilizar las leyes aritméticas conocidas, por ejemplo, ver esta prueba del sueño del novato de GCD $\rm\:(a\:\dot+\: b)^n =\: a^n\: \dot+\: b^n\:.$

Dijo conceptualmente : invertibles ("unidades") $\!\bmod n,\,$ son cerrado bajo la multiplicación , claro por

$$\begin{align}\rm a_k^{-1}\cdots a_1^{-1}&\rm\:\!\times\:\! (a_1\cdots a_k) =1\\[.2em] \rm\Rightarrow\ \ a_k^{-1}\cdots a_1^{-1} &\rm = (a_1\cdots a_k)^{-1}\end{align}\qquad$$

De manera más general: $ $ si $\rm\,(a,k)=(b,n)=1\,$ entonces $\rm\,(ab,kn)=(a,n)(b,k)$ .

Nota: $ $ También merece la pena destacar que las pruebas que utilizan las leyes GCD no sólo son más generales, sino que también son más eficientes notationally y, por tanto, más fácilmente comprensible. Como ejemplo, a continuación se muestra una demostración utilizando las leyes del GCD, seguida de una demostración utilizando la identidad de Bezout (de la respuesta de Gerry).

$\begin{eqnarray} \qquad 1&=& &\rm(a\:,\ \ n)\ &\rm (b\:,\ \ n)&=&\rm\:(ab,\ &\rm n\:(a\:,\ &\rm b\:,\ &\rm n))\ \ =\ \ (ab,n) \\[.2em] 1&=&\rm &\rm (a\color{#c00}r\!\!+\!\!n\color{#c00}s)\:&\rm(b\color{#c00}t\!\!+\!\!n\color{#c00}u)&=&\rm\ \ ab\:(\color{#c00}{rt})\!\!+\!\!&\rm n\:(a\color{#c00}{ru}\!\!+\!\!&\rm b\color{#c00}{st}\!\!+\!\!&\rm n\color{#c00}{su})\ \ so\ \ (ab,n)=1 \end{eqnarray}$

Obsérvese cómo la primera prueba que utiliza las leyes GCD evita todas las variables extrañas de Bezout $\rm\:\color{#c00}{r,s,t,u}\:,\:$ que no desempeñan ningún papel conceptual, sino que sólo sirven para ofuscar la verdadera esencia del asunto. Además, sin que ese ruido oscurezca nuestra visión, podemos ver inmediatamente una generalización natural de la prueba basada en la ley GCD, a saber

$$\rm\ (a,\ b,\ n)\ =\ 1\ \ \Rightarrow\ \ (ab,\:n)\ =\ (a,\ n)\:(b,\ n) $$

Esto lleva rápidamente a varias visiones basadas en el refinamiento de las factorizaciones únicas, por ejemplo, la de Euclides-Euler Teorema de los cuatro números (Vierzahlensatz) o, más generalmente, Perfeccionamiento de Schreier y Interpolación de Riesz. Véase también el excelente estudio mensual de Paul Cohn de 1973 Dominios de factorización únicos.

Answer 3

Dejemos que $P(x)$ sea el conjunto de primos que dividen a $x$ . Entonces $\gcd(a,n)=1$ si $P(a)$ y $P(n)$ son disjuntos. Como $P(ab)=P(a)\cup P(b)$ (*), $\gcd(a,n)=\gcd(b,n)=1$ implica que $P(ab)$ y $P(n)$ son disjuntos, lo que significa que $\gcd(ab,n)=1$ .

(*) Aquí utilizamos que si un primo divide a $ab$ entonces divide $a$ o $b$ .

Answer 4

Supongamos que $gcd(ab, n)=r$ debido a la propiedad de gcd, \begin{equation} r\geqslant 1\tag{1} \end{equation} Y allí $\exists s, t\in \mathbb{N}$ s.t. $$ab = rs$$ $$n = rt$$ y por lo tanto, $$a=\frac{rs}{b}, n =rt$$ En el caso de $b\mid s$ :

Allí $\exists x\in \mathbb{N}$ s.t. $$s=xb$$ Por lo tanto, $ab = rs = rxb\rightarrow a =rx$ $$a=rx$$ $$n=rt$$ Por lo tanto, $r$ es un divisor común de $a$ y $n$ y debe ser menor que el máximo común divisor. Por lo tanto, $$r\leqslant gcd(a,n)=1$$ Por (1), $$r=1$$ En el caso de $b\nmid s:$

Desde $a=\frac{rs}{b}\in\mathbb{N} \rightarrow b\mid r$ . Allí $\exists y\in \mathbb{N}$ s.t. $$r=yb$$ Por lo tanto, $$a=\frac{rs}{b}=sy$$ $$n=rt=tby$$ Por lo tanto, $y$ es un divisor común de $a$ y $n$ . De la misma manera, $y\leqslant gcd(a,n) = 1\implies y = 1$ y $r =b$ . \begin{align*} r &=gcd(r, rt)\\ &=gcd(b,n)\\ &=1 \end{align*} Por lo tanto, en ambos casos : $r=1$ $$gcd(ab, n) = r = 1$$