Rango de $ax+by$ donde $\gcd(a,b)=1$

Question

Cómo mostrar ese rango de $ax+by$ $\mathbb{Z}$ si $\gcd(a,b) = 1$.

Fácilmente se puede demostrar que si podemos demostrar que existe una $x$ $y$ tal que $ax+by=1$. Esto puede ser demostrado por el uso de Euclides del mcd algotithm método.

Alguien puede demostrar mediante el uso de algún otro método?

Answer 1

Sospecho que cualquier prueba implicará necesariamente el algoritmo de la división en algún momento, aunque tal vez no todo el algoritmo de Euclides. Aquí es donde el algoritmo de la división se utiliza sólo una vez.

Deje $a,b\in\mathbb{Z}$. Definir $\mathcal{L}(a,b)$, el conjunto de combinaciones lineales de $a$$b$, para el conjunto $$\mathcal{L}(a,b) = \{ax+by\mid x,y\in\mathbb{Z}\}.$$

Lema 1. Deje $a,b\in\mathbb{Z}$. A continuación, $\mathcal{L}(a,b)$ es un ideal de a $\mathbb{Z}$; que es:

1. $\mathcal{L}(a,b)\neq\varnothing$;
2. Si $r,s\in\mathcal{L}(a,b)$,$r-s\in\mathcal{L}(a,b)$;
3. Si $r\in\mathcal{L}(a,b)$$t\in\mathbb{Z}$,$tr\in\mathcal{L}(a,b)$.

Prueba. Podemos expresar $0$$0a+0b$, lo $0\in\mathcal{L}(a,b)$.

Si $r,s\in\mathcal{L}(a,b)$, entonces no existe $x,y,v,w\in\mathbb{Z}$ tal que $r=ax+by$, $s=av+bw$. A continuación,$r-s = a(x-v) + b(y-w)\in\mathcal{L}(a,b)$.

Si $r\in\mathcal{L}(a,b)$, entonces no existe $x,y\in\mathbb{Z}$ tal que $r=ax+by$; por lo tanto, $tr = a(tx) + b(ty)$, por lo que $tr\in\mathcal{L}(a,b)$. $\Box$

Lema 2. Deje $a,b\in\mathbb{Z}$. A continuación, cualquiera de $\mathcal{L}(a,b)=\{0\}$, o de lo contrario no es un número entero positivo $d$ tal que $\mathcal{L}(a,b) = d\mathbb{Z}=\{dt\mid t\in\mathbb{Z}\}$. De hecho, $d$ es el menor entero positivo que se encuentra $\mathcal{L}(a,b)$, cuando este último no es igual a $\{0\}$.

Prueba. Supongamos que $\mathcal{L}(a,b)\neq\{0\}$. Entonces existe $r\neq 0$, $r\in\mathcal{L}(a,b)$; si $r\lt 0$,$-r=(-1)r\gt 0$, e $-r\in\mathcal{L}(a,b)$ por Lema 1.3. Por lo tanto, $\mathcal{L}(a,b)$ contiene números enteros positivos.

Deje $S = \{x\in\mathcal{L}(a,b)\mid x\gt 0\}$. A continuación, $S$ es un conjunto no vacío de enteros positivos, por lo que por el principio de ordenación de los números naturales llegamos a la conclusión de que $S$ tiene un menor elemento. Deje $d$ ser este elemento.

Yo reclamo que $\mathcal{L}(a,b)=d\mathbb{Z}$. Desde $d\in\mathcal{L}(a,b)$), luego por el Lema 1.3 sabemos que $dt\in\mathcal{L}(a,b)$ todos los $t\in\mathbb{Z}$, lo $d\mathbb{Z}\subseteq\mathcal{L}(a,b)$. Por el contrario, vamos a $x\in\mathcal{L}(a,b)$. Utilizando el algoritmo de la división, existen únicas $q,r\in\mathbb{Z}$ tal que $$x = qd + r,\quad 0\leq r\lt d.$$ Desde $x,qd\in\mathcal{L}(a,b)$), luego por el Lema 1.2 sabemos que $x-qd=r\in \mathcal{L}(a,b)$. Desde $r\lt d$, no podemos tener a $r\gt 0$ (que estaría en contradicción con el hecho de que $d$ es el menor entero positivo en $\mathcal{L}(a,b)$), por lo que debemos concluir que $r=0$. Por lo tanto, $x=qd$, lo $x\in d\mathbb{Z}$. Esto demuestra $\mathcal{L}(a,b)\subseteq d\mathbb{Z}$, y así lo demuestra la igualdad. $\Box$

Lema 3. Deje $a,b\in\mathbb{Z}$. Si $s|a$$s|b$, $s|t$ todos los $t\in\mathcal{L}(a,b)$.

Prueba. Deje $s$ ser un divisor común de a$a$$b$, y deje $t\in\mathcal{L}(a,b)$; entonces no existe $x,y\in\mathbb{Z}$ tal que $t=ax+by$. Desde $s|a$,$s|ax$. Desde $s|b$,$s|by$. Desde $s|ax$$s|by$,$s|ax+by=t$. Por lo tanto, $s|t$, como se reivindica. $\Box$

Lema 4. Deje $a,b\in\mathbb{Z}$. Si $\mathcal{L}(a,b) = d\mathbb{Z}$, $d$ es un divisor común de a$a$$b$.

Prueba. Cada elemento de a $\mathcal{L}(a,b)$ es un múltiplo de a $d$; y $a=a\times 1 + b\times 0$, $b=a\times 0 + b\times 1$, por lo $a,b\in\mathcal{L}(a,b)$. Por lo tanto, $a$ $b$ ambos son múltiplos de $d$, lo $d$ es un divisor común de a $a$ y $b$. $\Box$

Teorema. Deje $a$ $b$ ser números enteros. Si $\mathcal{L}(a,b) = d\mathbb{Z}$, $d$ es un máximo común divisor de a$a$$b$. Que es:

1. $d|a$ $d|b$.
2. Si $c|a$$c|b$,$c|d$.

Por el contrario, si $d$ es un máximo común divisor de a$a$$b$,$\mathcal{L}(a,b)=d\mathbb{Z}$.

Prueba. Parte 1 de la siguiente manera por el Lema 4, y la Parte 2 por el Lema 3, probando que si $\mathcal{L}(a,b)=d\mathbb{Z}$, $d$ es un mcd de a$a$$b$.

Por el contrario, supongamos que $d$ es un mcd de a$a$$b$. Deje $\mathcal{L}(a,b) = c\mathbb{Z}$. Entonces a partir de la $d$ es un divisor común de a$a$$b$$c\in\mathcal{L}(a,b)$, $d|c$ por el Lema 3. Y por Lema $4$, $c|a$ y $c|b$, lo $c|d$ (ya que estamos asumiendo $d$ es un mcd de a$a$$b$). Por lo tanto, $d=\pm c$, por lo que $d\mathbb{Z}=c\mathbb{Z} = \mathcal{L}(a,b)$. $\Box$

Corolario. Deje $a$ $b$ ser números enteros. A continuación, $\mathcal{L}(a,b)=\mathbb{Z}$ si y sólo si $\gcd(a,b)=1$.

Prueba. $$\begin{align*} \mathcal{L}(a,b)=\mathbb{Z} &\iff \mathcal{L}(a,b) = 1\mathbb{Z}\\ &\iff \gcd(a,b) = 1.\quad\Box \end{align*}$$

Answer 2

Sugerencia $\:\!$ Subconjuntos de a $\mathbb Z$ cerrado bajo la resta tiene forma $\rm m\:\mathbb Z$ $(= \mathbb Z$ si tiene dos coprime elementos)