\( \newcommand{\Implies}{\Rightarrow} \newcommand{\Iff}{\Leftrightarrow} \renewcommand{\emptyset}{\varnothing} \newcommand{\powersetsym}{\mathcal{P}} \newcommand{\fto}{\rightarrow} \newcommand{\mto}{\mapsto} \newcommand{\Cx}{\mathbb{C}} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\Ns}{\mathbb{N}^*} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\K}{\mathbb{K}} \newcommand{\vv}[1]{\boldsymbol{#1}} \newcommand{\Abs}[1]{\left\lvert#1\right\rvert} \newcommand{\norm}[1]{ \left\|#1\right\| } \newcommand{\pnorm}[1]{\left\|#1\right\|_p} \newcommand{\supnorm}[1]{\left\|#1\right\|_\infty} \newcommand{\innerprod}[1]{\left\langle #1\right\rangle} \newcommand{\Ceil}[1]{\left\lceil #1\right\rceil} \newcommand{\Floor}[1]{\left\lfloor #1\right\rfloor} \newcommand{\Conj}[1]{\overline{#1}} \newcommand{\arccot}{\mathop{\text{arc\,cot}}\nolimits} \newcommand{\arcsec}{\mathop{\text{arc\,sec}}\nolimits} \newcommand{\arccsc}{\mathop{\text{arc\,csc}}\nolimits} \renewcommand{\arg}{\mathop{\text{arg}}\nolimits} \newcommand{\mcd}[1]{\mathop{\text{mcd}}\left(#1\right)} \newcommand{\mcm}[1]{\mathop{\text{mcm}}\left(#1\right)} \renewcommand{\ker}{\mathop{\text{ker}}\nolimits} \newcommand{\grad}{\mathop{\text{grad}}\nolimits} \newcommand{\dom}{\mathop{\text{dom}}\nolimits} \newcommand{\rng}{\mathop{\text{ran}}\nolimits} \newcommand{\diam}{\mathop{\text{diam}}\nolimits} \newcommand{\Obj}{\mathop{\text{obj}}\nolimits} \newcommand{\Hom}{\mathop{\text{hom}}\nolimits} \newcommand{\End}{\mathop{\text{end}}\nolimits} \newcommand{\Aut}[1]{\mathop{\mathrm{aut}}\nolimits(#1)} \newcommand{\Inn}[1]{\mathop{\mathrm{int}}\nolimits(#1)} \newcommand{\Deg}{\mathop{\mathrm{grad}}\nolimits} \newcommand{\Img}{\mathop{\text{im}}\nolimits} \newcommand{\Id}{\mathop{\mathrm{id}}\nolimits} \newcommand{\sgn}{\mathop{\mathrm{sgn}}\nolimits} \renewcommand{\Re}{\mathop{\mathrm{Re}}\nolimits} \renewcommand{\Im}{\mathop{\mathrm{Im}}\nolimits} \newcommand{\Char}{\mathop{\mathrm{car}}\nolimits} \renewcommand{\mod}[1]{\mathop{(\mathop{\text{mód}}\nolimits #1)}} \newcommand{\res}{\mathop{\text{mód}}} \newcommand{\categof}[1]{\mathsf{#1}} \newcommand{\CC}{\categof{C}} \newcommand{\CONJ}{\categof{Conj}} \newcommand{\SET}{\categof{Set}} \newcommand{\GRP}{\categof{Grp}} \newcommand{\AGRP}{\categof{Ab}} \newcommand{\morph}[1]{\mathrel{\mathop{\longrightarrow}\limits^{#1}}} \newcommand{\subgr}{\leq} \newcommand{\nsubgr}{\mathrel{\unlhd}} \newcommand{\iso}{\cong} \newcommand{\genby}[1]{\left\langle #1\right\rangle} \newcommand{\symgr}[1][n]{S_{#1}} \newcommand{\GenOf}[1]{\mathop{\text{gen}}\left(#1\right)} \newcommand{\normalizer}[2][G]{{\mathbf N}_{#1}(#2)} \newcommand{\centralizer}[2][G]{{\mathbf C}_{#1}(#2)} \newcommand{\orbit}[2][G]{\mathcal{O}_{#1}(#2)} \newcommand{\stab}[2][G]{#1(#2)} \newcommand{\GL}[2][n]{\mathrm{GL}(#1,#2)} \newcommand{\SL}[2][n]{\mathrm{SL}(#1,#2)} \newcommand{\Ort}[2][n]{\mathrm{O}(#1,#2)} \newcommand{\SO}[2][n]{\mathrm{SO}(#1,#2)} \newcommand{\KleinV}{\mathbf{V}}\)

[siguiente][arriba]

1.1 Divisibilidad

Teorema 1.1 (Algoritmo de la división). Para cualesquiera enteros \( x, y \), con \( y > 0 \), existen enteros únicos \( q \) y \( r \) tales que \[ x = qy + r\qquad \text {con}\qquad 0\leq r < y. \]
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 de buen ordenamiento de \( \N \) nos garantiza un elemento mínimo en \( S \), digamos \( r = x - qy \). Entonces \( x = qy + r \), pero además \( r \) cumple con \( 0\leq r < y \), pues si no fuese así tendríamos \( 0 \leq r - y = (x - qy) - y = x - (q+1)y \), pero entonces sería \( r - y\in S \), contradiciendo nuestra elección de \( r \) como el mínimo de \( S \).

Pasemos ahora a demostrar la unicidad de \( q \) y \( r \). Para esto, supongamos que \( q' \) y \( r' \) son otro par de enteros que cumplen lo señalado por el teorema, de manera que, en particular, \( x = q'y + r' = qy + r \), y por tanto \( (q' - q)y = r - r' \). Puesto que \( y > 0 \), la igualdad anterior implica que \( \Abs {q' - q}y = \Abs {r - r'} \), luego \( \Abs {r' - r} \) es un múltiplo de \( y \), pero como \( r' \) y \( r \) son no negativos y son menores que \( y \), sólo puede ser que \( \Abs {q' - q} = 0 \), o sea que \( q' = q \) y de ahí que \( r' = r \). Esto establece la unicidad de los enteros \( q \) y \( r \) y con ello concluye la prueba del teorema.

Definición 1.2. A los elementos \( q \) y \( r \) del teorema anterior los llamamos cociente y residuo de la división de \( r \) por \( y \), respectivamente.
Ejemplo 1.3. Consideremos los enteros 26 y 7. El primer múltiplo de 7 que deja un residuo menor que 7 al ser restado de 26 es \( 3\cdot 7 \), y \[ 26 = 3\cdot 7 + 5. \] Así, \( 3 \) y \( 5 \) son, respectivamente, el cociente y el residuo de dividir 26 entre 7. Por otra parte, el cociente y el residuo de dividir 7 entre 26 son 0 y 7, respectivamente, pues \[ 7 = 0\cdot 26 + 7, \] con \( 7 \leq 26 \).

En general, está claro que si \( 0\leq x < y \), entonces el cociente y el residuo de dividir \( x \) entre \( y \) serán \( q=0 \) y \( r = x \), respectivamente.

Observemos que si \( r \) es el residuo de dividir \( x \) entre \( y \), entonces el algoritmo de la división dicta 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.

Corolario 1.5. Para cualesquiera enteros \( x,y \) con \( y\neq 0 \), existen enteros únicos \( q \) y \( r \) tales que \[ x = qy + r\qquad \text {con}\qquad 0\leq r < \Abs {y}. \]
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: \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.

Corolario 1.6. Si \( x,y \) son enteros con \( y > 0 \), entonces el cociente de dividir \( x \) entre \( y \) es \[ \Floor {\frac {x}{y}}\ \text {si}\ y > 0 \qquad \text {y}\qquad \Ceil {\frac {x}{y}}\ \text {si}\ y < 0. \]
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} \).

Ejemplo 1.7.
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
  1. si \( x\mid x' \) y \( y\mid y' \), también \( xx'\mid yy' \);
  2. si \( k\neq 0 \), entonces \( x\mid y \) si y sólo si \( kx\mid ky \);
  3. si \( x\mid y \) con \( y\neq 0 \), entonces \( \Abs x \leq \Abs y \);
  4. \( 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: \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: \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í: \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\).

[siguiente][arriba]