Problema de divisibilidad (Teoría de números)

Question

Bueno, yo sólo quería que ustedes comprobar mi solución al siguiente problema:

Sea $S$ sea el conjunto de todos los enteros positivos de la forma $ax+by$ . Supongamos que $S$ es no vacío y $d=ax_o+by_o$ sea el menor elemento de $S$ . Demuestre que cada elemento de $S$ es divisible por $d$ .

Mi solución es la siguiente:

Sea n un elemento de $S$ tal que $n$ = $ax+by$ . Entonces existen enteros $q$ et $r$ con $0 \le r \lt d $ tal que $n=qd+r$ . Sustituyendo da, $ax+by=q(ax_0+by_0)+r$ $\Rightarrow$ $r=a(x-qx_0)+b(y-qy_0)$ .

Pero como $ax_0+by_0\leq q(ax+by)$ $\Rightarrow$ $a(x-qx_0)+b(y-qy_0) \leq 0$ $\Rightarrow$ $r \le 0$ .

Por lo tanto, $0 \leq r \leq 0$ $\Rightarrow$ $r = 0$ . De ahí el resultado.

Gracias por leer hasta aquí. Si tiene alguna sugerencia, puede dejarla a continuación.

$Correction:$ Gracias a fleablood , Llave ¡y a otros por la ayuda!

Supongamos que $r \ne 0.$

Tenga en cuenta que $r>0$ et $r = a(x-qx_o)+b(y-qy_0)$ $r \in S$ . Tenga en cuenta que $r < d$ esto contradice la minimalidad de d.

Answer 1

Sea $S$ sea el conjunto de todos los números enteros de la forma $ax+by$ y que $d$ sea el elemento menos positivo de $S$ . Demostraremos que $d=$ gcd(a,b) (para algunos $x$ et $y$ ).

Desde $d$ es un elemento de $S$ et $\gcd(a,b)$ divide todos los elementos de $S$ tenemos $\gcd(a,b)\mid d$ .

Por el algoritmo de la división, existen enteros $q$ et $r$ con $0\leq r<d$ tal que $a=qd+r$ . Entonces $r=a-qd=a-q(ax+by)=(1-qx)a-(qy)b$ Así que $r\in S$ . Pero $r<d$ Así que $r=0$ y así $d\mid a$ . Del mismo modo $d\mid b$ Así que $d\mid\gcd(a,b)$ .

Desde $d\mid\gcd(a,b)$ et $\gcd(a,b)\mid d$ entonces $d=\gcd(a,b)$ . Por lo tanto $x$ et $y$ variar, $ax+by$ alcanza sólo (y todos) los múltiplos de $\gcd(a,b)$ por lo que cada elemento de $S$ es divisible por $d$ .