El principio de buen orden se puede utilizar para demostrar que hay un único gcd de dos enteros positivos...

Question

Pregunta
El principio de ordenación puede utilizarse para demostrar que existe un gcd único de dos enteros positivos. Sea $a$ y $b$ sean números enteros positivos, y que $S$ sea el conjunto de enteros positivos de la forma $as+bt$ , donde $s$ y $t$ son números enteros.

a) Demuestre que $S$ no está vacío.
b) Utilice la propiedad de buen orden para demostrar que $S$ tiene un elemento más pequeño $c$ .
c) Demuestre que si $d$ es un divisor común de $a$ y $b$ entonces $d$ es un divisor $c$ .
d) Demuestre que $c|a$ y $c|b$ .
e) Concluya a partir de (c) y (d) que el máximo común divisor de $a$ y $b$ existe. Termina la prueba demostrando que este gcd de dos enteros positivos es único.

Este es mi primer uso del principio de buen ordenamiento, así que necesito confirmación. Más sobre mi problema de esta pregunta en la sección Problema abajo.

Mi intento
a) $S$ es no vacía ya que $s$ y $t$ en $as+bt$ puede ser cualquier número entero no negativo.

b) A partir de (a), ya que $S$ es un conjunto no vacío de enteros positivos, por el principio de Well-Ordering existe un elemento mínimo $c$ .

c) Ya que $d|a$ y $d|b$ , $$a = dk_1, k_1 \in \mathbb{Z}$$ $$b = dk_2, k_2 \in \mathbb{Z}$$ Así, $$c = as + bt = (dk_1)s + (dk_2)t = d(k_1s) + d(k_2s) \equiv 0 (\bmod d)$$

d) Supongamos $c \nmid a$ entonces $a = qc + r, 0 < r < c$ . Supongamos ahora $r \in S$ Esto es una contradicción, ya que hemos establecido que $c$ es el menor elemento del conjunto $S$ .

e)

• Existencia: Hemos demostrado un mínimo elemento $c$ en un conjunto no vacío $S$ , de tal manera que $c\mid a$ y $c \mid b$ . Otros divisores como $d$ , divide $a, b, c$ Por lo tanto $d \leq c$ por lo que gcd $c$ existe.

• Unicidad: Supongamos que $\exists e \mid \gcd(a, b) = e$ entonces $$e \mid a, e \mid b \rightarrow e \mid c,$$ que es verdadera si y sólo si $e \leq c$ , teniendo en cuenta $\gcd(a, b) = e$ Por lo tanto $e = c$ .

El problema:
(a) y (b) fue mi primer uso del principio de ordenación de pozos (al menos conscientemente) por lo que necesito confirmación de que se está utilizando correctamente. (c) Estoy bastante seguro, así que es poco probable que esté equivocado. (d) Estoy un poco indeciso al respecto, ¿es también un uso correcto del principio de ordenación de pozos? (e) No puedo encontrar nada malo en ello, pero si es incorrecto, sólo señálalo.

Answer 1

Por un lado, no has utilizado el principio de buen orden. Demostraste que había al menos un elemento de $S$ exhibiendo una. Sería un poco mejor decir "tomar $s=1, t=0$ entonces $as+bt=a$ Así que $S$ no está vacío", pero ya tienes la idea. b es correcto tal y como está planteado -has utilizado el principio de ordenación de pozos correctamente-. c también está bien. Para d no justificas que $r \in S$ pero tú puedes. Este es el punto crítico. Usted tiene $r=a-qc$ Ahora sustituye en $c=as+bt$ y justificas lo que estabas suponiendo.