Prueba si $\gcd (a, b) = 1$ entonces existe $m$ y $n$ tal que $am+bn=1$

Question

Prueba si $\gcd (a, b) = 1$ .

¿Es correcto decir $\gcd (a, b) = 1$ ENTONCES existen coeficientes $m$ y $n\in\mathbb Z$ tal que $ma + nb = 1$ ?

Supongo que es correcto (relativamente primos) pero quería volver a comprobarlo...

Answer 1

Parece que otras respuestas abordan el " $\Leftarrow$ " en lugar de " $\Rightarrow$ " implicación, así que he aquí cómo $(a,b)=1$ implica $am+bn=1$ :

Si conoces el Algoritmo Euclidiano para hallar el máximo común divisor, puedes utilizarlo para demostrar la afirmación (y también es útil para hallar el $m$ y $n$ en la práctica). El algoritmo euclidiano le ofrece

\begin{align} a&=b x_1+r_1\\ b&=r_1 x_2+r_2\\ &\ \ \vdots\\ r_{n-2} &= r_{n-1} x_{n}+r_n\\ r_{n-1} &= r_{n} x_{n+1}+g \end{align} donde $g$ es el máximo común divisor, (en tu caso $g=1$ ). Se puede escribir al revés como \begin{align} g&=r_{n-1}-r_n x_{n+1}\\ r_n&=r_{n-2}-r_{n-1} x_{n}\\ &\ \ \vdots\\ r_2&=b-r_1 x_2\\ r_1&=a-b x_1 \end{align} Así podrá escribir $g$ como combinación lineal de $r_{n-1}$ y $r_n$ . Entonces también podrá escribir $r_n$ como combinación lineal de $r_{n-1}$ y $r_{n-2}$ . De esta forma se llega finalmente a $r_1$ que se puede escribir como una combinación lineal de $a$ y $b$ . Sustituyendo todo esto nos da $g$ como combinación lineal de $a$ y $b$ o $g=am+bn$ que es lo que querías.

Digamos, por ejemplo $a=10$ , $b=7$ . Por Algoritmo Euclidiano: \begin{align} 10&=7\cdot 1+3\\ 7&=3\cdot2+1 \end{align} y así $$1=7-3\cdot 2=7-(10-7\cdot 1)\cdot 2 = 3\cdot 7-2\cdot 10.$$

Answer 2

Supongamos que $au+bv=1$ para algunos números enteros $u,v$ . Sea $d:=\gcd(a,b)$ entonces tenemos $a=a'd$ y $b=b'd$ para algunos números enteros $a',b'$ . Por lo tanto, $$1=au+bv=a'du+b'dv=d(a'u+b'v)$$ y así $d\mid 1$ .

Answer 3

Sea $d=\gcd(a,b)$

Entonces $d|a$ y $d|b\Rightarrow$

$d|ma$ , $d|nb$ y $d|ma+nb=1\Rightarrow d|1\Rightarrow d=1$