1.2: Divisibilidad y GCD en los números enteros
- Page ID
- 107535
En esta sección, buscaremos responder a las preguntas:
- ¿Qué significa para un entero dividir a otro?
- ¿Qué propiedades disfruta la divisibilidad en los enteros?
- ¿Cuál es el mayor divisor común de dos enteros?
- ¿Cómo podemos calcular el mayor divisor común de dos enteros?
1.2.1: La divisibilidad y el algoritmo de división
En esta sección, comenzamos a explorar algunas de las propiedades aritméticas y algebraicas de\(\mathbb{Z}\text{.}\) Nos enfocamos específicamente en las propiedades de divisibilidad y factorización de los enteros, ya que estas son el foco principal del texto en su conjunto. Uno de los objetivos principales de esta sección es formalizar definiciones con las que probablemente ya esté familiarizado y de las cuales tenga una comprensión intuitiva. Al principio, esto podría parecer complicar innecesariamente las cosas. Sin embargo, quedará claro a medida que avancemos que el lenguaje matemático formal y la notación son necesarios para extender estas propiedades a un entorno más abstracto. Comenzamos con una noción familiar.
Vamos\(a,b\in \mathbb{Z}\text{.}\) Decimos que\(a\) divide\(b\text{,}\) y escribimos\(a\mid b\text{,}\) si hay un entero\(c\) tal que\(ac = b\text{.}\) en este caso, digamos eso\(a\) y\(c\) son factores de\(b\text{.}\) Si no\(c\in \mathbb{Z}\) existe tal, escribimos\(a\nmid b\text{.}\)
Tenga en cuenta que el símbolo\(|\) es un verbo; por lo tanto, es correcto decir, por ejemplo,\(2|4\text{,}\) como 2 sí divide 4. No obstante, es un abuso de notación decir que\(2\mid 4 = 2\text{.}\) en cambio, probablemente nos referimos a\(4\div 2 = 2\) o\(\dfrac{4}{2} = 2\) (aunque todavía no trataremos en fracciones).
Determinar\(a\mid b\) si:
- \(a = 3\text{,}\)\(b = -15\)
- \(a = 4\text{,}\)\(b = 18\)
- \(a = -7\text{,}\)\(b = 0\)
- \(a = 0\text{,}\)\(b = 0\)
Comente brevemente los resultados de esta investigación. ¿Qué te diste cuenta? ¿Qué es lo que aún te preguntas?
A continuación se recogen varios resultados estándar sobre la divisibilidad en los\(\mathbb{Z}\) que se utilizará ampliamente en el resto de este texto.
Dejar\(a,b,c\in\mathbb{Z}\text{.}\) Si\(a\mid b\) y\(a\mid c\text{,}\) luego\(a\mid (b+c)\text{.}\)
Let\(a,b,c\in\mathbb{Z}\text{.}\) Si\(a\mid b\text{,}\) entonces\(a\mid bc\text{.}\)
Considera lo siguiente parcial converse al Teorema 1.2.1 : Si\(a,b,c\in\mathbb{Z}\) con\(a|bc\text{,}\) must\(a|b\) o\(a|c\text{?}\) Supply una prueba o dar un contraejemplo.
Vamos\(a,b,c,d\in \mathbb{Z}\text{.}\) Si\(a = b+c\) y\(d\) divide dos cualesquiera de\(a,b,c\text{,}\) entonces\(d\) divide el tercero.
Formular una conjetura similar a los teoremas anteriores sobre la divisibilidad en\(\mathbb{Z}\text{,}\) y luego probarla
Como vimos anteriormente, no todos los pares de enteros\(a,b\) satisfacen\(a\mid b\) o\(b\mid a\text{.}\) Sin embargo, nuestra experiencia en matemáticas elementales sí aplica: a menudo queda algo sobrante (un resto). El siguiente teorema formaliza esta idea para\(a,b\in \mathbb{N}\text{.}\)
El algoritmo de división para\(\mathbb{N}\).
Dejar\(a,b\in \mathbb{N}\text{.}\) Entonces existen enteros únicos\(q,r\) tales que\(a = bq + r\text{,}\) donde\(0 \le r \lt b\text{.}\)
- Pista 1
-
Hay dos partes en este teorema. Primero, debes establecer eso\(q\) y\(r\) existir. Esto se hace mejor a través de Axiom 1.2.1 . Si estás atascado en eso, revisa la segunda pista.
Una vez que haya establecido eso\(q\) y\(r\) exista, demuestre que son únicos pero asumiendo\(a = bq+r\) y\(a = bq' + r'\text{,}\) donde\(r,r'\) ambos satisfacen las condiciones del teorema. Argumentan eso\(q = q'\) y\(r = r'\text{.}\)
- Pista 2
-
Let\(S = \{ a-bs : s\in \mathbb{N}_0, a-bs\ge 0\}\text{.}\)
- ¡Advertencia!
-
Este teorema tiene dos partes: existencia y singularidad. No trates de probarlos a ambos al mismo tiempo.
1.2.2: Los divisores comunes más grandes
Pasamos a continuación a otra propiedad familiar de los enteros: la existencia de mayores divisores comunes.
Dejemos que\(a,b\in \mathbb{Z}\) tal que\(a\) y no\(b\) sean ambos 0. Un divisor más común de\(a\) y\(b\text{,}\) denotado\(\gcd(a,b)\text{,}\) es un número natural\(d\) satisfactorio
- \(d\mid a\)y\(d\mid b\)
- si\(e\in \mathbb{N}\)\(e\mid a\) y\(e\mid b\text{,}\) luego\(e\mid d\text{.}\)
Si\(\gcd(a,b) = 1\text{,}\) decimos eso\(a\) y\(b\) son relativamente primos o coprimos.
Esta definición puede ser diferente a la que está acostumbrado, que probablemente declaró que\(d \ge e\) rather than condition 2 in Definition: Greatest Common Divisor. It can be proved using the order relations of \(\mathbb{Z}\) that the definition given here is equivalent to that one. However, we will prefer this definition, as it generalizes naturally to other number systems which do not have an order relation like \(\mathbb{Z}\text{.}\)
Compute\(\gcd(a,b)\) si:
- \(a = 123\text{,}\)\(b = 141\)
- \(a = 0\text{,}\)\(b = 169\)
- \(a= 85\text{,}\)\(b = 48\)
Ahora que has tenido un poco de práctica computando gcds, describe tu método para encontrarlos en una oración o dos.
¿Cómo respondiste la última pregunta en Activity 1.2.1 ? Si eres como las clases de los autores, las respuestas probablemente variaron, aunque en algún momento te has referido a un “prime” (sean cuales sean esos), o posiblemente algún otro método ad hoc para encontrar el gcd. La mayoría de estos métodos se basan de alguna forma en nuestra capacidad para factorizar números enteros. Sin embargo, el problema de factorizar enteros arbitrarios es en realidad sorprendentemente intensivo desde el punto de vista computacional. Agradecidamente, hay otra forma de calcular\(\gcd(a,b)\text{,}\) a la que ahora recurrimos.
Que\(a,b,c\in\mathbb{Z}\) tal que\(a = b+c\) con\(a\) y\(b\) no ambos cero. Entonces\(\gcd(a,b) = \gcd(b,c)\text{.}\)
Supongamos\(a,b,c\in\mathbb{Z}\) tal que existe\(q\in\mathbb{Z}\) con\(a = bq + c\)\(a\) y\(b\) no ambos cero. Demostrar o desacreditar:\(\gcd(a,b)=\gcd(b,c)\text{.}\)
(Algoritmo Euclidiana).
Let\(a,b\in \mathbb{N}\text{.}\) Use Theorema 1.2.4 e Investigation 1.2.4 para determinar un algoritmo para la computación\(\gcd(a,b)\text{.}\) ¿Cómo podría modificarse su método para calcular\(\gcd(a,b)\) para\(a,b\in\mathbb{Z}\text{?}\)
Usar el algoritmo euclidiano para calcular\(\gcd(18489,17304)\text{.}\)
La siguiente identidad proporciona una caracterización útil del mayor divisor común de dos enteros, no ambos cero. Volveremos a esta idea varias veces, incluso después de haber dejado el reino familiar de los enteros.
Para cualquier número entero\(a\) y\(b\) no ambos 0, hay enteros\(x\) y\(y\) tales que
\ begin {ecuación*} hacha + por =\ gcd (a, b)\ texto {.} \ end {ecuación*}
- Pista 1
-
Aplica Axioma 1.2.1 a un conjunto bien elegido.
- Pista 2
-
Aplicar Axioma 1.2.1 a\(S = \{as+bt : s,t\in\mathbb{Z}, \ as+bt \gt 0\}\text{.}\)
Concluimos con una respuesta a las preguntas planteadas por Investigation 1.2.2 .
Dejar\(a, b\text{,}\) y\(c\) ser enteros. Si\(a|bc\) y\(\gcd(a,b) = 1\text{,}\) entonces\(a|c\text{.}\)
En esta sección, hemos recopilado algunos resultados iniciales sobre la divisibilidad en los números enteros. A continuación exploraremos los bloques de construcción multiplicativos de los enteros, los primos, en preparación para una exploración más profunda de la factorización.