Álgebra abstracta
Capítulo 1 Números enteros
1.1 Divisibilidad
El estudio de la divisibilidad entre enteros parte del hecho fundamental siguiente.
-
Demostración: Consideremos el conjunto \(S = \{ x-ky \geq 0 \mid k\in \Z \} \). Se trata de un subconjunto no vacío de \(\N \), pues, por ejemplo, \(x - ky \geq 0 \) al tomar \(k = \Abs x \), luego el principio del buen ordenamiento de \(\N \) nos garantiza un elemento mínimo en \(S \), digamos, \(r = x - qy \). Entonces \(x = qy - r \) con \(0 \leq r < y \), pues de no ser así tendríamos \(0 \leq r - y = (x - qy) - y = x - (q + 1)y \), de donde se seguiría que \(r - y\in S \), en contradicción con la elección de \(r \) como el mínimo de \(S \).
Para demostrar que \(q \) y \(r \) obtenidos en el párrafo anterior son los únicos enteros que cumplen la condición, supongamos que \(q' \) y \(r' \) son otro par de enteros con la misma propiedad. Entonces \(q'y + r' = qy + r \) y por tanto \((q' - q)y = r - r' \). Puesto que \(y > 0 \), debemos tener \(\Abs {q' - q}y = \Abs {r' - r} \), de donde se sigue que \(\Abs {q' - q} = 0 \), pues de otro modo \(\Abs {r' - r} \) sería mayor que \(y \), en contradicción con la propiedad de que \(0 \leq r,r' < y \). Así pues, \(q' = q \), de donde se sigue que \(r' = r \) y por tanto que \(r \) y \(q \) son los únicos enteros que verifican las propiedades enunciadas en el teorema.
-
Ejemplo 1.3. El cociente y el residuo de dividir \(27 \) por \(7 \) son \(3 \) y \(5 \), respectivamente, pues
\[ 25 = 3\cdot 7 + 5 \]
con \(5 < 7 \). Por su parte, el cociente y el residuo de dividir \(7 \) entre \(27 \) son \(0 \) y \(7 \), pues
\[ 7 = 0\cdot 26 + 7 \]
con \(7 < 26 \). En general, está claro que si \(0 \leq x < y \), el cociente y el residuo de dividir \(x \) entre \(y \) serán \(0 \) y \(x \).
Observemos que si \(r \) es el residuo de dividir \(x \) entre \(y \), entonces el algoritmo de la división nos dice que
\[ r\in \{1,2,3\ldots , y- 1\}. \]
-
Ejemplo 1.4. Podemos usar el algoritmo de la división para establecer que todo cuadrado perfecto deja residuo de 0 o 1 al ser dividido entre 4: si \(n\in \Z \), podemos escribir \(n = q\cdot 2 + r \) con \(r\in \{0,1\} \), y por tanto
\[ n^2 = 4q^2 + 4qr + r = 4(q^2 + qr) + r^2, \]
donde \(r^2 = 0 \) o \(r^2 = 1 \), o sea que \(r^2 < 4 \) y por tanto es el residuo de dividir \(n^2 \) entre 4.
Procederemos ahora a extender el teorema 1.1 para incorporar los casos en que \(y \) es un entero negativo.
-
Demostración: Esto es lo que ya sabíamos para \(y > 0 \), pues en ese caso \(\Abs {y} = y \). Supongamos pues que \(y < 0 \). Entonces \(-y > 0 \), y por tanto existen enteros únicos \(q^* \) y \(r \) tales que \(x = q^*(-y) + r \) con \(0 \leq r < -y = \Abs {y} \), luego \(q = -q^* \) y \(r \) son los enteros que cumplen las condiciones deseadas.
Si \(\alpha \) es un número real cualquiera, existe el mayor de los enteros menores o iguales que \(\alpha \), y a dicho entero lo representaremos por \(\Floor \alpha \). Por ejemplo,
\[ \Floor {4.6} = 4,\qquad \Floor {\sqrt {2}} = 1,\qquad \Floor \pi = 3,\qquad \Floor {-2.3} = -3. \]
El último de los resultados anteriores nos muestra que \(\Floor \alpha \) nos da la parte entera de \(\alpha \) (el número que resulta de ignorar los decimales de \(\alpha \)) únicamente cuando \(\alpha \) es no negativo. Por otra parte, está claro que si \(\alpha \) es él mismo un entero, entonces \(\Floor \alpha = \alpha \).
Similarmente, existe la notación \(\Ceil \alpha \) para representar al menor de los enteros mayores o iguales que \(\alpha \). Para este caso, tenemos los ejemplos siguientes:
\[ \Ceil {4.6} = 5,\qquad \Ceil {\sqrt {2}} = 2,\qquad \Ceil \pi = 4,\qquad \Ceil {-2.3} = -2. \]
De nuevo, está claro que si \(\alpha \) es entero, será \(\Ceil \alpha = \alpha \). En general, se cumplen las identidades siguientes:
\(\seteqnumber{0}{1.}{0}\)\begin{equation} \label {eq:rel floor ceil} \Floor {-\alpha } = -\Ceil \alpha \qquad \text {y}\qquad \Ceil {-\alpha } = \Floor \alpha . \end{equation}
Podemos aprovechar las notaciones que acabamos de describir para dar un resultado práctico para determinar cocientes y residuos mediante una calculadora simple.
-
Demostración: Supongamos que \(y > 0 \) y sean \(q \) y \(r \) el cociente y el residuo de dividir \(x \) entre \(y \). Entonces
\[ \frac {x}{y} = q + \frac {r}{y}\qquad \text {con}\qquad 0 \leq \frac {r}{y} < 1, \]
lo que nos dice que sumar \(r/y \) a \(q \) no cambia su parte entera, y por lo tanto \(\Floor {q} = \Floor {q + r/y} = \Floor {x/y} \).
Ahora bien, si tenemos \(y < 0 \) y \(q \) es el cociente de dividir \(x \) entre \(y \), entonces \(-q \) es el cociente de dividir \(x \) entre \(-y > 0 \), y aplicando el argumento anterior y las fórmulas (1.1) obtenemos \(\Ceil {q}=-\Floor {-q}-\Floor {x/(-y)} = \Ceil {x/y} \).
-
-
• El cociente de dividir 26 por 7 es \(\Floor {\frac {26}{7}} = \Floor {3.\overline {714285}} = 3 \) y el residuo es \(26 - 3\cdot 7 = 5 \).
-
• El cociente de dividir 26 por \(-7\) es \(\Ceil {\frac {26}{-7}} = \Ceil {-3.\overline {714285}} = -3 \), y el residuo es de nuevo \(r = 26 - (-3)(-7) = 5 \).
-
• El cociente de dividir \(-26\) entre 7 es \(\Floor {-\frac {26}{7}} = -4 \), con residuo \(r = -26 - (-4)(7) = 2\).
-
• El cociente de dividir \(-26\) por \(-7\) es \(\Ceil {\frac {-26}{-7}} = 4 \), dejando residuo \(r = -26 - 4(-7) = 2 \).
-
-
Definición 1.8. Decimos que un entero no nulo \(x \) divide a otro entero \(y \), lo que en símbolos se expresa escribiendo
\[ x\mid y, \]
si existe un entero \(q \) tal que \(x = qy \). En otras palabras, \(x\mid y \) si el residuo de la división de \(x \) entre \(y \) es cero, lo que también se expresa diciendo que \(x \) es múltiplo de \(y \), que es un divisor de \(y \) o también que es un factor de \(y \).
Algunos hechos elementales sobre la división de enteros se enuncian en la proposición siguiente.
-
Proposición 1.9. Si \(x,x',y,y' \) son enteros, entonces
-
(a) si \(x\mid x' \) y \(y\mid y' \), también \(xx'\mid yy' \);
-
(b) si \(k\neq 0 \), entonces \(x\mid y \) si y sólo si \(kx\mid ky \);
-
(c) si \(x\mid y \) con \(y\neq 0 \), entonces \(\Abs x \leq \Abs y \);
-
(d) \(x\mid y \) y \(y\mid x \) si y sólo si \(x = \pm y \).
-
-
Demostración: Todos estos hechos se demuestran fácilmente. Aquí demostraremos únicamente el inciso (d) y dejaremos el resto como ejercicio al lector. Está claro que \(x = \pm y \) implica que \(x \) y \(y \) se dividen mutuamente. Recíprocamente, si \(x\mid y \) y \(y\mid x \), entonces \(x,y\neq 0 \) y el apartado (c) nos dice que \(\Abs x \leq \Abs y \) y \(\Abs y \leq \Abs x \), o sea que \(\Abs x = \Abs y \) y por tanto \(x = \pm y \).
-
Definición 1.10. Si \(x \) y \(y \) son dos enteros no nulos, el mayor de los enteros que los divide a ambos se llama máximo común divisor, al cual representaremos por \(\mcd {x,y} \). Cuando se da el caso de que \(\mcd {x,y} = 1 \), o sea, cuando \(x \) y \(y \) no tienen más divisor que la unidad, decimos que dichos números son primos relativos.
He aquí una forma bastante eficiente de calcular el máximo común divisor de dos enteros.
-
Teorema 1.11 (Algoritmo de Euclides). Sean \(x,y \) enteros no nulos y sean \((r_k)_k \) y \((q_k)_k \) las sucesiones de residuos y de cocientes, respectivamente, obtenidos mediante las relaciones recursivas siguientes:
\(\seteqnumber{0}{1.}{1}\)\begin{alignat*} {2} x & = q_1 y + r_1, & & 0\leq r_1 < y, \\ y & = q_2 r_1 + r_2,\qquad & & 0\leq r_2 < r_1, \\ r_{k-2} & = q_k r_{k-1} + r_k,\qquad & & 0\leq r_k < r_{k-1}\text { o } r_k = 0. \end{alignat*} Si \(r_1 = 0 \), entonces \(\mcd {x,y} = y \), y en caso contrario, \(\mcd {x,y} = r_{m-1}\), donde \(m\) es el menor entero positivo tal que \(r_m = 0\).
-
Demostración: Ante todo, debe quedar claro que la definición de las sucesiones \((q_k)_k\) y \((r_k)_k\) está justificada por el algoritmo de la división. Ahora bien, puesto que \(\mcd {x,y} = \mcd {\pm x,\pm y}\), basta dirigir nuestra atención al caso en que \(x \) y \(y \) son ambos positivos.
Está claro que si \(r_1 = 0 \) entonces \(\mcd {x,y} = y \). Supongamos pues que \(r_1 \neq 0 \). Las relaciones de arriba dejan claro que \((r_k)_k \) es una sucesión estrictamente decreciente hasta llegar al punto en que se vuelve constantemente cero (es decir, \(r_k = 0 \) para todo \(k \) mayor que cierto entero \(N\in \N \)). Así pues, existe un mínimo entero positivo \(m > 1 \) tal que \(r_m = 0 \), de manera que \(m-1 \) es el mayor de los enteros tales que \(r_{m-1}\neq 0 \). En otras palabras, para este entero \(m-1 \) se cumple el desarrollo siguiente:
\(\seteqnumber{0}{1.}{1}\)\begin{alignat*} {2} x & = q_1 y + r_1, & & 0\leq r_1 < y, \\ y & = q_2 r_1 + r_2,\qquad & & 0\leq r_2 < r_1, \\ r_1 & = q_3 r_2 + r_3,\qquad & & 0\leq r_3 < r_2, \\ & \vdots & & \ \ \vdots \\ r_{m-3} & = q_{m-1} r_{m-2} + r_{m-1},\qquad & & 0\leq r_{m-1} < r_{m-1}, \\ r_{m-2} & = q_m r_{m-1} + 0.\qquad & & \end{alignat*} Para demostrar que \(r_{m-1} = \mcd {x,y}\), observemos que la última igualdad de arriba nos dice que \(r_{m-1} \) divide a \(r_{m-2}\), luego también divide a \(r_{m-3}\), y en general se concluye por inducción que \(r_{m-1}\) es un divisor común de \(x\) y \(y\). Por otra parte, las ecuaciones de arriba también muestran muestran que \(d = \mcd {x,y}\) divide a \(r_1\), luego también a \(r_2\), y procediendo por inducción encontramos que divide a \(r_m\), por lo que debemos tener \(d\leq r_m\). Pero como \(d \) es el mayor de los divisores comunes de \(x \) y \(y \), necesariamente \(d = r_m \).
-
Ejemplo 1.12. Encontraremos \(\mcd {2352,350}\). Para dicho par de números, el algoritmos de Euclides se desarrolla así:
\(\seteqnumber{0}{1.}{1}\)\begin{align*} 2352 & =6(350)+252 \\ 350 & =1(252)+98 \\ 252 & =2(98)+56 \\ 98 & =1(56)+42 \\ 56 & =1(42)+14 \\ 42 & = 3(14). \end{align*} Por lo tanto, \(\mcd {2352,350} = 14\).