8.1: El mayor divisor común

Vista previa de la actividad\(\PageIndex{1}\): The Greatest Common Divisor

1. Explica lo que significa decir que un entero distinto de cero\(m\) divide un entero\(n\). Recordemos que usamos la notación\(m\ |\ n\) para indicar que el entero distinto de cero\(m\) divide el entero\(n\).
2. Dejar\(m\) y\(n\) ser enteros con\(m \ne 0\). Explique lo que significa decir que\(m\) no divide\(n\).

Definición

Dejar\(a\) y\(b\) ser enteros, no ambos 0. Un divisor común de\(a\) y\(b\) es cualquier entero distinto de cero que divide ambos\(a\) y\(b\). El mayor número natural que divide ambos\(a\) y\(b\) se llama el mayor divisor común de\(a\) y\(b\). El mayor divisor común de\(a\) y\(b\) se denota por gcd (\(a\),\(b\)).

1. Usa el método roster para listar los elementos del conjunto que contiene todos los números naturales que son divisores de 48.
2. Usa el método roster para listar los elementos del conjunto que contiene todos los números naturales que son divisores de 84.
3. Determinar la intersección de los dos conjuntos en Partes (3) y (4). Este conjunto contiene todos los números naturales que son divisores comunes de 48 y 84.
4. ¿Cuál es el mayor divisor común de 48 y 84?
5. Utilice el método sugerido en las Partes (3) a (6) para determinar cada uno de los siguientes: gcd (8, -12), gcd (0, 5), gcd (8, 27) y gcd (14, 28).
6. Si\(a\) y\(b\) son enteros, hacer una conjetura sobre cómo los divisores comunes de\(a\) y\(b\) están relacionados con el mayor divisor común de\(a\) y\(b\).

Vista previa de la actividad\(\PageIndex{2}\): The GCD and the Division Algorithm

Cuando hablamos del cociente y del resto cuando “dividimos un entero\(a\) por el entero positivo”\(b\), siempre nos referiremos al cociente\(q\) y al resto\(r\) garantizado por el Algoritmo de División. (Ver Sección 3.5, página 143.)

1. Cada fila de la siguiente tabla contiene valores para los enteros\(a\) y\(b\). En esta tabla, el valor de\(r\) es el resto (del Algoritmo de División) cuando\(a\) se divide por\(b\). Complete cada fila en esta tabla determinando gcd (\(a\),\(b\))\(r\), y gcd (\(b, r\)).
   

   \(a\)	\(b\)	gcd (\(a\),\(b\))	Resto\(r\)	gcd (\(b\),\(r\))
   \ (a\) ">44	\ (b\) ">12	\ (a\),\(b\)) ">	\ (r\) ">	\ (b\),\(r\)) ">
   \ (a\) ">75	\ (b\) ">21	\ (a\),\(b\)) ">	\ (r\) ">	\ (b\),\(r\)) ">
   \ (a\) ">50	\ (b\) ">33	\ (a\),\(b\)) ">	\ (r\) ">	\ (b\),\(r\)) ">

2. Formular una conjetura basada en los resultados de la tabla en la Parte (1).

El Sistema de Enteros

La teoría de números es un estudio del sistema de enteros, que consiste en el conjunto de enteros,\(\mathbb{Z} = \{..., -3, -2, -1, 0, 1, 2, 3, ...\}\) y las diversas propiedades de este conjunto bajo las operaciones habituales de suma y multiplicación y bajo la relación de ordenamiento habitual de “menos que”. Las propiedades de los enteros en la Tabla 8.1 se considerarán axiomas en este texto.

Cuadro 8.1: Axiomas para los números enteros

	Para todos los números enteros\(a\),\(b\), y\(c\);
Propiedades de Cierre para Adición y Multiplicación	\ (a\)\(b\), y\(c\);” style="vertical-align:middle;” class="lt-math-7081">\(a + b \in \mathbb{Z}\) y\(ab \in \mathbb{Z}\)
Propiedades conmutativas para la suma y la multiplicación	\ (a\)\(b\), y\(c\);” style="vertical-align:middle;” class="lt-math-7081">\(a + b = b + a\), y\(ab = ba\)
Propiedades sociativas para la suma y la multiplicación	\ (a\)\(b\), y\(c\);” style="vertical-align:middle;” class="lt-math-7081">\((a + b) + c = a + (b + c)\) y\((ab)\ c = a\ (bc)\)
D istributivas Propiedades de la Multiplicación sobre la Adición	\ (a\)\(b\), y\(c\);” style="vertical-align:middle;” class="lt-math-7081">\(a\ (b + c) = (ab + ac)\), y\((b + c)\ a = ba + ca\)
Propiedades de Identidad Dditiva y Multiplicativa	\ (a\)\(b\), y\(c\);” style="vertical-align:middle;” class="lt-math-7081">\(a + 0 = 0 + a = a\), y\(a \cdot 1 = 1 \cdot a = a\)
Una propiedad inversa dditiva	\ (a\)\(b\), y\(c\);” style="vertical-align:middle;” class="lt-math-7081">\ (a + (-a) = (-a) + a = 0

También asumiremos las propiedades de los números enteros mostrados en la Tabla 8.2. Estas propiedades se pueden probar a partir de las propiedades del Cuadro 8.1. (Sin embargo, aquí no lo haremos.)

Tabla 8.2: Propiedades de los números enteros

Z ero Propiedad de Multiplicación	Si\(a \in \mathbb{Z}\), entonces\(a \cdot 0 = 0 \cdot a = 0\).
C ancellation Propiedades de Adición y Multiplicación	\ (a\ in\ mathbb {Z}\), entonces\(a \cdot 0 = 0 \cdot a = 0\).” style="vertical-align:middle;” class="LT-MATH-7081">Si\(a, b, c \in \mathbb{Z}\), y\(a + b = a + c\), entonces\(b = c\). Si\(a, b, c \in \mathbb{Z}\),\(a \ne 0\) y\(ac = bc\), entonces\(b = c\).

Ya hemos estudiado una buena parte de la teoría de números en este texto en nuestra discusión sobre los métodos de prueba. En particular, hemos estudiado los enteros pares e impares, la divisibilidad de los enteros, la congruencia y el Algoritmo de División. Consulte el resumen del Capítulo 3 para un resumen de los resultados relativos a los enteros pares e impares, así como los resultados relativos a las propiedades de los divisores. Revisamos algunas de estas propiedades y el Algoritmo de División en las Actividades de Vista Previa.

El mayor divisor común

Uno de los conceptos más importantes en la teoría de números elementales es el del mayor divisor común de dos enteros. La definición para el mayor divisor común de dos enteros (no ambos cero) se dio en Vista previa de Actividad\(\PageIndex{1}\).

1. Si\(a, b \in \mathbb{Z}\) y\(a\) y no\(b\) son ambos 0, y if\(d \in \mathbb{N}\), entonces\(d =\) gcd (\(a\),\(b\)) siempre que satisfaga todas las siguientes propiedades:
   • \(d\ |\ a\)y\(d\ |\ b\). Es decir,\(d\) es un divisor común de\(a\) y\(b\).
   • Si\(k\) es un número\(a\) natural tal que\(k\ |\ a\) y\(k\ |\ b\), entonces\(k \le d\) .Es decir, cualquier otro divisor común de\(a\) y\(b\) es menor o igual a\(d\).
2. En consecuencia, un número natural no\(d\) es el mayor divisor común de\(a\) y\(b\) siempre que no satisfaga al menos una de estas propiedades. Es decir, no\(d\) es igual a gcd (\(a\),\(b\)) siempre que
   • \(\bullet\)\(d\)no divide\(a\) o\(d\) no divide\(b\); o
   • \(\bullet\)Existe un número natural\(k\) tal que\(k\ |\ a\) y\(k\ |\ b\) y\(k > d\).
3. Esto significa que no\(d\) es el mayor divisor común de\(a\) y\(b\) siempre que no sea un divisor común de\(a\) y\(b\) o que exista un divisor común de\(a\) y\(b\) que sea mayor que\(d\).

En las actividades de vista previa, determinamos los mayores divisores comunes para varios pares de enteros. El proceso que utilizamos fue enumerar todos los divisores de ambos enteros, luego enumerar todos los divisores comunes de ambos enteros y, finalmente, de la lista de todos los divisores comunes, encontrar el divisor común más grande (más grande). Este método funciona razonablemente bien para enteros pequeños pero puede resultar bastante engorroso si los enteros son grandes. Antes de desarrollar un método eficiente para determinar el mayor divisor común de dos enteros, necesitamos establecer algunas propiedades de los divisores más comunes.

Una propiedad fue sugerida en Vista previa de Actividad\(\PageIndex{1}\). Si miramos los resultados en la Parte (7) de esa actividad de previsualización, debemos observar que cualquier divisor común de\(a\) y\(b\) dividirá gcd (\(a\),\(b\)). De hecho, los objetivos principales del resto de esta sección son

1. Para encontrar un método eficiente para determinar gcd (\(a\),\(b\)), donde\(a\) y\(b\) son enteros.
2. Para probar que el número natural gcd (\(a\),\(b\)) es el único número natural\(d\) que satisface las siguientes propiedades:
   
   \(\bullet\)\(d\) divide\(a\) y\(d\) divide\(b\); y
   \(\bullet\) si \(k\)es un número natural tal que\(k\ |\ a\) y\(k\ |\ b\), entonces\(k\ |\ d\).

El segundo objetivo es sólo ligeramente diferente de la definición del mayor divisor común. La única diferencia está en la segunda condición donde\(k \le d\) se sustituye por\(k\ |\ d\).

Primero consideraremos el caso donde\(a\) y\(b\) son enteros con\(a \ne 0\) y\(b > 0\). La prueba del resultado establecido en la segunda meta contiene un método (llamado Algoritmo Euclidiana) para determinar los mayores divisores comunes de los dos enteros a y b. La idea principal del método es seguir reemplazando el par de enteros .a; b/ por otro par de enteros .b; r/, donde\(0 \le r < b\) y gcd.b; r/ D gcd.a; b/. Esta idea fue explorada en Preview Activity\(\PageIndex{2}\). Lema 8.1 es una conjetura que podría haber sido formulada en Preview Activity\(\PageIndex{2}\).

Lema 8.1.

Dejar\(c\) y\(d\) ser enteros, no ambos iguales a cero. Si\(q\) y\(r\) son enteros tales que\(c = d \cdot q + r\), entonces gcd (\(c\),\(d\)) = gcd (\(d\),\(r\)).

Prueba

Dejar\(c\) y\(d\) ser enteros, no ambos iguales a cero. Supongamos que\(q\) y\(r\) son enteros tales que\(c = d \cdot q + r\). Para facilitar la notación, vamos a dejar

\(m =\)gcd (\(c\),\(d\)) y\(n =\) gcd (\(d\),\(r\)).

Ahora,\(m\) divide\(c\) y\(m\) divide\(d\). En consecuencia, existen enteros\(x\) y\(y\) tal que\(c = mx\) y\(d = my\). Por lo tanto,

\[\begin{array} {rcl} {r} &= & {c - d \cdot q} \\ {r} &= & {mx - (my)q} \\ {r} &= & {m(x - yq).} \end{array}\]

Pero esto significa que\(m\) divide\(r\). Dado que m divide\(d\) y\(m\) divide\(r\),\(m\) es menor o igual a gcd (\(d\),\(r\)). Así,\(m \le n\).

Usando un argumento similar, vemos que\(n\) divide\(d\) y\(n\) divide\(r\). Ya que\(c = d \cdot q + r\), podemos probar que\(n\) divide\(c\). De ahí,\(n\) divide\(c\) y\(n\) divide\(d\). Así,\(n \le\) gcd (\(c\),\(d\)) o\(n \le m\). Ahora tenemos\(m \le n\) y\(n \le m\). De ahí,\(m = n\) y gcd (\(c\),\(d\)) = gcd (\(d\),\(r\)).

Comprobación de progreso 8.2: Ilustraciones de Lemma 8.1

Completamos varios ejemplos ilustrando Lemma 8.1 en Actividad previa\(\PageIndex{2}\). Para otro ejemplo, vamos\(c = 56\) y\(d = 12\). El divisor más común de 56 y 12 es 4.

1. Según el Algoritmo de División, ¿cuál es el resto\(r\) cuando 56 se divide por 12?
2. ¿Cuál es el mayor divisor común de 12 y el resto\(r\)?
   
   La clave para encontrar el mayor divisor común (en casos más complicados) es volver a utilizar el Algoritmo de División, esta vez con 12 y\(r\). Ahora encontramos enteros\(q_2\) y\(r_2\) tal que
   \[12 = r \cdot q_2 + r_2.\]
3. ¿Cuál es el mayor divisor común de\(r\) y\(r_2\)?

Responder

Agrega textos aquí. No elimine primero este texto.

El Algoritmo Euclidiana

El ejemplo en Progress Check 8.2 ilustra la idea principal del Algoritmo Euclidiana para encontrar gcd (\(a\),\(b\)), lo cual se explica en la prueba del siguiente teorema.

Teorema 8.3: Algoritmo Euclideano

Dejar\(a\) y\(b\) ser enteros con\(a \ne 0\) y\(b > 0\). Entonces gcd (\(a\),\(b\)) es el único número natural\(d\) tal que

(a)\(d\) divide\(a\) y\(d\) divide\(b\), y
(b) si\(k\) es un entero que divide ambos\(a\) y\(b\), luego\(k\) divide\(d\).

Prueba

Dejar\(a\) y\(b\) ser enteros con\(a \ne 0\) y\(b > 0\), y let\(d =\) gcd (\(a\),\(b\)). Por el Algoritmo de División, existen enteros\(q_1\) y\(r_1\) tales que

\[a = b \cdot q_1 + r_1 \text{, and } 0 \le r_1 < b.\]

Si\(r_1 = 0\), entonces la ecuación (8.1.3) implica que\(b\) divide\(a\). De ahí que\(b = d =\) gcd (\(a\),\(b\)) y este número satisfaga las Condiciones (a) y (b).

Si\(r_1 > 0\), entonces por Lema 8.1, gcd (\(a\),\(b\)) = gcd (\(b\),\(r_1\)). Utilizamos nuevamente el Algoritmo de División para obtener enteros\(q_2\) y de\(r_2\) tal manera que

\[b = r_1 \cdot q_2 + r_2 \text{, and } 0 \le r_2 < r_1.\]

Si\(r_2 = 0\), entonces la ecuación (8.1.4) implica que\(r_1\) divide\(b\). Esto significa que\(r_1 =\) gcd (\(b\),\(r_1\)). Pero ya hemos visto que gcd (\(a\),\(b\)) = gcd (\(b\),\(r_1\)). De ahí,\(r_1 =\) gcd (\(a\),\(b\)). Además, si\(k\) es un entero que divide ambos\(a\) y\(b\), entonces, usando la ecuación (8.1.3), vemos que\(r_1 = a - b \cdot q_1\) y, por lo tanto,\(k\) divide\(r_1\). Esto demuestra que\(r_1 =\) gcd (\(a\),\(b\)) satisface las Condiciones (a) y (b).

Si\(r_2 > 0\), entonces por Lema 8.1, gcd (\(b\),\(r_1\)) = gcd (\(r_1\),\(r_2\)). Pero ya hemos visto que gcd (\(a\),\(b\)) = gcd (\(b\),\(r_1\)). De ahí que gcd (\(a\),\(b\)) = gcd (\(r_1\),\(r_2\)). Ahora continuamos aplicando el Algoritmo de División para producir una secuencia de pares de enteros (todos los cuales tienen el mismo mayor divisor común). Esto se resume en la siguiente tabla:

Par Original	Ecuación de División	Desigualdad del algoritmo de división	Nuevo par
(\(a, b\))	\(a = b \cdot q_1 + r_1\)	\(0 \le r_1 < b\)	(\(b, r_1\))
(\(b, r_1\))	\(b = r_1 \cdot q_2 + r_2\)	\(0 \le r_2 < r_1\)	(\(r_1, r_2\))
(\(r_1, r_2\))	\(r_1 = r_2 \cdot q_1 + r_3\)	\(0 \le r_3 < r_2\)	(\(r_2, r_3\))
(\(r_2, r_3\))	\(r_2 = r_3 \cdot q_1 + r_4\)	\(0 \le r_4 < r_3\)	(\(r_3, r_4\))
(\(r_3, r_4\))	\(r_3 = r_4 \cdot q_1 + r_5\)	\(0 \le r_5 < r_4\)	(\(r_4, r_5\))
...	...	...	...

A partir de las desigualdades en la tercera columna de esta tabla, tenemos una secuencia estrictamente decreciente de enteros no negativos (\(b > r_1 > r_2 > r_3 > r_4 \cdot\cdot\cdot\)). En consecuencia, un término en esta secuencia debe ser eventualmente igual a cero. Dejar\(p\) ser el número natural más pequeño tal que\(r_{p + 1} = 0\). Esto significa que las dos últimas filas de la tabla anterior serán

Par Original	Ecuación del algoritmo de división	Desigualdad del algoritmo de división	Nuevo par
(\(r_{p - 2}, r_{p - 1}\))	\(r_{p - 2} = r_{p - 1} \cdot q_{p} + r_p\)	\(0 \le r_{p} < r_{p - 1}\)	(\(r_{p - 1}, r_{p}\))
(\(r_{p - 1}, r_{p}\))	\(r_{p - 1} = r_{p} \cdot q_{p + 1} + 0\)

Recuerde que esta tabla se construyó mediante el uso repetido de Lemma 8.1 y que el mayor divisor común de cada par de enteros produjo es igual a gcd (\(a\),\(b\)). Además, la última fila de la tabla indica que\(r_{p}\) divide\(r_{p - 1}\). Esto significa que gcd (\(r_{p - 1}, r_{p}\))\(= r_{p}\) y por lo tanto\(r_p =\) gcd (\(a\),\(b\)).

Esto demuestra que\(r_p =\) gcd (\(a\),\(b\)) satisface la Condición (a) de este teorema. Ahora supongamos que\(k\) es un entero tal que\(k\) divide\(a\) y\(k\) divide\(b\). Se procede a través de la tabla fila por fila. Primero, ya que\(r_1 = a - b \cdot q\), vemos que

\(k\)deben dividirse\(r_1\).

Eso nos dice la segunda fila\(r_2 = b - r_{1} \cdot q_{2}\). Dado que\(k\) divide\(b\) y\(k\) divide\(r_1\), concluimos que

\(k\)divide\(r_2\).

Continuando con cada fila, vemos que\(k\) divide cada uno de los restos\(r_1, r_2, r_3, ..., r_{p}\). Esto significa que\(r_p =\) gcd (\(a\),\(b\)) satisface la Condición (b) del teorema.

Comprobación de Progreso 8.4 (Usando el Algoritmo Euclidiana)

1. Utilice el Algoritmo Euclidiana para determinar gcd (180, 126). Observe que hemos eliminado la tercera columna (Desigualdad del algoritmo de división) de la siguiente tabla. No es necesario en los cómputos.

   Par Original	Ecuación del algoritmo de división	Nuevo par
   (180, 126)	\(180 = 126 \cdot 1 + 54\)	(126, 54)
   (126, 54)	126 =

   En consecuencia, gcd (180, 126) =.

2. Utilice el Algoritmo Euclidiana para determinar gcd (4208, 288).

   Par Original	Ecuación del algoritmo de división	Nuevo par
   (4208, 288)	\(4208 = 288 \cdot 14 + 176\)	(288,)

   En consecuencia, gcd (4208, 288) =.

Responder

Agrega textos aquí. No elimine primero este texto.

Algunas Observaciones sobre el Teorema 8.3

El teorema 8.3 se comprobó con los supuestos que\(a, b \in \mathbb{Z}\) con\(a \ne 0\) y\(b > 0\). Una versión más general de este teorema se puede probar con\(a, b \in \mathbb{Z}\) y\(b = 0\). Esto se puede probar usando el Teorema 8.3 y los resultados en el siguiente lema.

Lema 8.5.

Déjalo\(a, b \in \mathbb{Z}\) con\(b \ne 0\). Entonces

1. gcd (0,\(b\)) = |\(b\) |.
2. Si gcd (\(a\),\(b\)) =\(d\), entonces gcd (\(a\),\(-b\)) =\(d\).

Las pruebas de estos resultados están en Ejercicio (4). Una aplicación de este resultado se da en el siguiente ejemplo.

Ejemplo 8.6 (Usando el Algoritmo Euclidiana)

Dejar\(a = 234\) y\(b = -42\). Utilizaremos el Algoritmo Euclidiana para determinar gcd (234, 42).

Paso	Par Original	Ecuación del algoritmo de división	Nuevo par
1	(234, 42)	\(234 = 42 \cdot 5 + 24\)	(42, 24)
2	(42, 24)	\(42 = 24 \cdot 1 + 18\)	(24, 18)
3	(24, 18)	\(24 = 18 \cdot 1 + 6\)	(18, 6)
4	(18, 6)	\(18 = 6 \cdot 3\)

Entonces gcd (234, 42) = 6 y por lo tanto gcd (234, -42) = 6.

Escribir gcd (\(a\),\(b\)) en términos de\(a\) y\(b\)

Utilizaremos el Ejemplo 8.6 para ilustrar otro uso del Algoritmo Euclidiana. Es posible utilizar los pasos del Algoritmo Euclidiana en orden inverso para escribir gcd (\(a\),\(b\)) en términos de\(a\) y\(b\). Utilizaremos estos pasos en orden inverso para encontrar enteros\(m\) y\(n\) tal que gcd (234, 42) = 234\(m\) + 42\(n\). La idea es comenzar con la fila con el último resto distinto de cero y trabajar hacia atrás como se muestra en la siguiente tabla:

Explicación	Resultado
Primero, usa la ecuación del Paso 3 para escribir 6 en términos de 24 y 18.	\(\begin{array} {rcl} {6} &= & {24 - 18 \cdot 1} \end{array}\)
Nosotros e la ecuación en el Paso 2 para escribir\(18 = 42 - 24 \cdot 1\). Substitute this into the preceding result and simplify.	\(\begin{array} {rcl} {6} &= & {24 - 18 \cdot 1} \\ {} &= & {24 - (42 - 24 \cdot 1)} \\ {} &= & {42 \cdot (-1) + 24 \cdot 2} \end{array}\)
W e ahora han escrito 6 en términos de 42 y 24. Usa la ecuación del Paso 1 para escribir\(24 = 234 - 42 \cdot 5\). Substitute this into the preceding result and simplify.	\(\begin{array} {rcl} {6} &= & {42 \cdot (-1) + 24 \cdot 2} \\ {} &= & {42 \cdot (-1) + (234 - 42 \cdot 5) \cdot 2} \\ {} &= & {234 \cdot 2 + 42 \cdot (-11)} \end{array}\)

De ahí que podamos escribir

\(\text{gcd}(234, 42) = 234 \cdot 2 + 42 \cdot (-11).\)

(Verifique esto con una calculadora.) En este caso, decimos que hemos escrito gcd (234, 42) como una combinación lineal de 234 y 42. De manera más general, tenemos la siguiente definición.

Definición

Dejar\(a\) y\(b\) ser enteros. Una combinación lineal de\(a\) y\(b\) es un número entero de la forma\(ax + by\), donde\(x\) y\(y\) son números enteros.

Comprobación de progreso 8.7 (Escribir el gcd como una combinación lineal)

Utilice los resultados de la comprobación de progreso 8.4 para

1. Escribe gcd (180, 126) como una combinación lineal de 180 y 126.
2. Escribe gcd (4208, 288) como una combinación lineal de 4208 y 288.

Responder

Agrega textos aquí. No elimine primero este texto.

El ejemplo anterior y la comprobación de progreso ilustran el siguiente resultado importante en la teoría de números, que se utilizará en la siguiente sección para ayudar a probar algunos otros resultados significativos.

Teorema 8.8

Dejar\(a\) y\(b\) ser enteros, no ambos 0. Entonces gcd (\(a\),\(b\)) se puede escribir como una combinación lineal de\(a\) y\(b\). Es decir, existen enteros\(u\) y\(v\) tal que\(\text{gcd}(a, b) = au + bv\).

No vamos a dar una prueba formal de este teorema. Ojalá que los ejemplos y actividades aporten evidencia de su validez. La idea es utilizar los pasos del Algoritmo Euclidiana en orden inverso para escribir gcd (\(a\),\(b\)) como una combinación lineal de\(a\) y\(b\). Por ejemplo, supongamos que la tabla completada para el Algoritmo Euclidiana es

Paso	Par Original	Ecuación del algoritmo de división	Nuevo par
1	\((a, b)\)	\(a = b \cdot q_1 + r_1\)	\((b, r_1)\)
2	\((b, r_1)\)	\(b = r_1 \cdot q_2 + r_2\)	\((r_1, r_2)\)
3	\((r_1, r_2)\)	\(r_1 = r_2 \cdot q_3 + r_3\)	\((r_2, r_3)\)
4	\((r_2, r_3)\)	\(r_2 = r_3 \cdot q_4 + 0\)	\((r_3, r_4)\)

Podemos usar el Paso 3 para escribir\(r_3 = \text{gcd}(a, b)\) como una combinación lineal de\(r_1\) y\(r_2\). Entonces podemos resolver la ecuación en el Paso 2 para\(r_2\) y usar esto para escribir\(r_3 = \text{gcd}(a, b)\) como una combinación lineal de\(r_1\) y\(b\). Entonces podemos usar la ecuación en el Paso 1 para resolver\(r_1\) y usar esto para escribir\(r_3 = \text{gcd}(a, b)\) como una combinación lineal de\(a\) y\(b\).

En general, si podemos escribir\(r_p = \text{gcd}(a, b)\) como una combinación lineal de un par en una fila dada, entonces podemos usar la ecuación en el paso anterior para escribir\(r_p = \text{gcd}(a, b)\) como una combinación lineal del par en esta fila anterior.

Los detalles notacionales de este argumento de inducción se involucran bastante. Muchos matemáticos prefieren probar el Teorema 8.8 usando una propiedad de los números naturales llamada Principio de Ordenación del Bien. El principio de ordenación correcta para los números naturales establece que cualquier conjunto no vacío de números naturales debe contener un elemento mínimo. Se puede probar que el Principio de Ordenamiento del Bien es equivalente al Principio de Inducción Matemática.

Ejercicio 8.1

1. Encuentre cada uno de los siguientes divisores más comunes enumerando todos los divisores comunes de cada par de enteros.
   
   (a) gcd (21, 28)
   (b) gcd (-21, 28)
   (c) gcd (58, 63)
   (d) gcd (0, 12)
   (e) gcd (110, 215)
   (f) gcd (110, -215)
2. (a) Dejar\(a \in \mathbb{Z}\) y dejar\(k \in \mathbb{Z}\) con\(k \ne 0\). Demostrar que si\(k\ |\ a\) y\(k\ |\ (a + 1)\), entonces\(k\ |\ 1\), y por lo tanto\(k = \pm1\).
   b) Dejar\(a \in \mathbb{Z}\). Encuentra el mayor divisor común de los enteros consecutivos\(a\) y\(a + 1\). Es decir, determinar gcd (\(a\),\(a + 1\)).
3. (a) Dejar\(a \in \mathbb{Z}\) y dejar\(k \in \mathbb{Z}\) con\(k \ne 0\). Demostrar que si\(k\ |\ a\) y\(k\ |\ (a + 2)\), entonces\(k\ |\ 2\).
   b) Dejar\(a \in \mathbb{Z}\). Encuentra el mayor divisor común del divisor común\(a\) y\(a + 2\).
4. Déjalo\(a, b \in \mathbb{Z}\) con\(b \ne 0\). Demostrar cada uno de los siguientes:
   
   (a) gcd (0,\(b\)) =\(b\) | |
   (b) Si gcd (\(a\),\(b\)) =\(d\), entonces gcd (\(a\),\(-b\)) =\(d\). Es decir, gcd (\(a\),\(-b\)) = gcd (\(a\),\(b\)).
5. Para cada uno de los siguientes pares de enteros, utilice el Algoritmo Euclidiana para encontrar gcd (\(a\),\(b\)) y escribir gcd (\(a\),\(b\)) como una combinación lineal de\(a\) y\(b\). Es decir, encontrar enteros\(m\) y\(n\) tal que\(d = am + bn\).
   
   a)\(a = 36\),\(b = 60\)
   b)\(a = 901\),\(b = 935\)
   c)\(a = 72\),\(b = 714\)
   d)\(a = 12528\), e\(b = 21361\)
   )\(a = -36\), f\(b = -60\)
   )\(a = 901\), \(b = -935\)
6. (a) Encontrar enteros\(u\) y\(v\) tal que\(9u + 14v = 1\) o explicar por qué no es posible hacerlo. Entonces encontrar enteros\(x\) y\(y\) tal que\(9x + 14y = 10\) o explicar por qué no es posible hacerlo.
   (b) Encontrar enteros\(x\) y\(y\) tales que\(9x + 15y = 10\) o explicar por qué no es posible hacerlo.
   (c) Encontrar enteros\(x\) y\(y\) tal que\(9x + 15y = 3162\) o explicar por qué no es posible hacerlo.
7. (a) Observe que gcd (11, 17) = 1. Encuentra enteros\(x\) y\(y\) tal que\(11x + 17y = 1\).
   b) Dejar\(m, n \in \mathbb{Z}\). Wrtie la suma\(\dfrac{m}{11} + \dfrac{n}{17}\) como una sola fracción.
   (c) Encontrar dos números racionales con denominadores de 11 y 17, respectivamente, cuya suma sea igual a\(\dfrac{10}{187}\). Pista: Escribe los números racionales en la forma\(\dfrac{m}{11} + \dfrac{n}{17}\), donde\(m, n \in \mathbb{Z}\). Después escribe
   \[\dfrac{m}{11} + \dfrac{n}{17} = \dfrac{10}{187}.\]
   Usar Ejercicios (7a) y (7b) para determinar\(m\) y\(n\).
   d) Encontrar dos números racionales con denominadores 17 y 21, respectivamente, cuya suma sea igual\(\dfrac{326}{357}\) o explique por qué no es posible hacerlo.

   e) Encontrar dos números racionales con denominadores 9 y 15, respectivamente, cuya suma sea igual\(\dfrac{10}{225}\) o explique por qué no es posible hacerlo.
   
   Exploración y Actividades

8. Combinaciones lineales y el mayor divisor común
   
   (a) Determinar el divisor más común de 20 y 12?
   b) Dejar\(d = \text{gcd}(20, 12)\). Escribe d como una combinación lineal de 20 y 12.
   (c) Generar al menos seis combinaciones lineales diferentes de 20 y 12. ¿Son estas combinaciones lineales de 20 y 12 múltiplos de gcd (20, 12)?
   d) Determinar el mayor divisor común de 21 y -6 y luego generar al menos seis combinaciones lineales diferentes de 21 y -6. ¿Son estas combinaciones lineales de 21 y -6 múltiplos de gcd (21, -6)?
   e) La siguiente proposición se introdujo por primera vez en el Ejercicio (18) de la página 243 de la Sección 5.2. Completa la prueba de esta proposición si aún no lo has hecho.

   Proposición 5.16

   Dejar\(a\),\(b\), y\(t\) ser enteros con\(t \ne 0\). Si\(t\) divide\(a\) y\(t\) divide\(b\), entonces para todos los enteros\(x\) y\(y\),\(t\) divide\(ax + by\)

   Prueba: Dejar\(a\),\(b\) y\(t\) ser enteros con\(t \ne 0\), y asumir que\(t\) divide\(a\) y\(t\) divide\(b\). Vamos a probar eso para todos los enteros\(x\) y\(y\),\(t\) divide\((ax + by)\).
   Así que vamos\(x \in \mathbb{Z}\) y vamos\(y \in \mathbb{Z}\). Desde\(t\) divide\(a\), existe un entero mtal que...
   (f) Ahora vamos\(a\) y\(b\) ser enteros, no tanto cero como let\(d =\) gcd (\(a\),\(b\)). Teorema 8.8 afirma que\(d\) es una combinación lineal de\(a\) y\(b\). Además, let\(S\) and\(T\) be los siguientes conjuntos: Es
   \[S = \{ax + by\ |\ x, y \in \mathbb{Z}\} \ \ \ \text{and}\ \ \ \ \ T = \{kd\ |\ k \in \mathbb{Z}\}.\]
   decir,\(S\) es el conjunto de todas las combinaciones lineales de\(a\) y\(b\), y\(T\) es el conjunto de todos los múltiplos del mayor divisor común de\(a\) y \(b\). ¿El conjunto\(S\) es igual al conjunto\(T\)? Si no, ¿uno de estos conjuntos es un subconjunto del otro conjunto? Justifica tus conclusiones.

   Nota: En las Partes (c) y (d), estábamos explorando casos especiales para estos dos conjuntos.

Responder

Agrega textos aquí. No elimine primero este texto.