[skip-to-content]
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\gcd}{\operatorname{mcd}} \renewcommand{\lcm}{\operatorname{mcm}} \renewcommand{\deg}{\operatorname{gr}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Sección2.2El Algoritmo de División

Una aplicación del Principio del Buen-Orden que usaremos frecuentemente es el algoritmo de división.

Este es un ejemplo perfecto de una demostración de existencia y unicidad. Debemos primero demostrar que los números \(q\) y \(r\) realmente existen. Después debemos mostrar que si \(q'\) y \(r'\) también son tales números, entonces \(q = q'\) y \(r = r'\text{.}\)

Existencia de \(q\) y \(r\text{.}\) Sea

\begin{equation*} S = \{ a - bk : k \in {\mathbb Z} \text{ y } a - bk \geq 0 \}. \end{equation*}

Si \(0 \in S\text{,}\) entonces \(b\) divide a \(a\text{,}\) y podemos tomar \(q = a/b\) y \(r = 0\text{.}\) Si \(0 \notin S\text{,}\) podemos usar el Principio del Buen-Orden. Debemos primero mostrar que \(S\) es no vacío. Si \(a \gt 0\text{,}\) entonces \(a - b \cdot 0 \in S\text{.}\) Si \(a \lt 0\text{,}\) entonces \(a - b(2a) = a(1 - 2b) \in S\text{.}\) En cualquier caso \(S \neq \emptyset\text{.}\) Po el Principio del Buen-Orden, \(S\) tiene un elemento mínimo, digamos \(r = a - bq\text{.}\) Por lo tanto, \(a = bq + r\text{,}\) \(r \geq 0\text{.}\) Mostremos ahora que \(r \lt b\text{.}\) Supongamos que \(r \gt b\text{.}\) Entonces

\begin{equation*} a - b(q + 1)= a - bq - b = r - b \gt 0. \end{equation*}

En este caso tendríamos \(a - b(q + 1)\) en el conjunto \(S\text{.}\) Pero entonces \(a - b(q + 1) \lt a - bq\text{,}\) lo que llevaría a una contradicción del hecho que \(r = a - bq\) es el menor elemento de \(S\text{.}\) Así \(r \leq b\text{.}\) Como \(0 \notin S\text{,}\) \(r \neq b\) y así \(r \lt b\text{.}\)

Unicidad de \(q\) y \(r\text{.}\) Supongamos que existen enteros \(r\text{,}\) \(r'\text{,}\) \(q\text{,}\) y \(q'\) tales que

\begin{equation*} a = bq + r, 0 \leq r \lt b \quad \text{and}\quad a = bq' + r', 0 \leq r' \lt b. \end{equation*}

Entonces \(bq + r = bq' + r'\text{.}\) Supongamos que \(r' \geq r\text{.}\) De la última ecuación tenemos \(b(q - q') = r' - r\text{;}\) por lo tanto, \(b\) debe dividir a \(r' - r\) y \(0 \leq r'- r \leq r' \lt b\text{.}\) Estos es posible solo si \(r' - r = 0\text{.}\) Luego, \(r = r'\) y \(q = q'\text{.}\)

Sean \(a\) y \(b\) enteros. Si \(b = ak\) para algún entero \(k\text{,}\) escribiremos \(a \mid b\text{.}\) Un entero \(d\) se llama divisor común de \(a\) y \(b\) si \(d \mid a\) y \(d \mid b\text{.}\) El máximo común divisor de los enteros \(a\) y \(b\) es un entero positivo \(d\) tal que \(d\) es un divisor común de \(a\) y \(b\) y si \(d'\) es cualquier otro divisor común de \(a\) y \(b\text{,}\) entonces \(d' \mid d\text{.}\) Escribiremos \(d = \gcd(a, b)\text{;}\) por ejemplo, \(\gcd( 24, 36) = 12\) y \(\gcd(120, 102) = 6\text{.}\) Decimos que dos enteros \(a\) y \(b\) son relativamente primos si \(\gcd( a, b ) = 1\text{.}\)

Sea

\begin{equation*} S = \{ am + bn : m, n \in {\mathbb Z} \text{ and } am + bn \gt 0 \}. \end{equation*}

Claramente, el conjunto \(S\) es no-vacío; luego, por el Principio del Buen-Orden \(S\) tiene un elemento mínimo, digamos \(d = ar + bs\text{.}\) Afirmamos que \(d = \gcd( a, b)\text{.}\) Escriba \(a = dq + r'\) con \(0 \leq r' \lt d\text{.}\) Si \(r' \gt 0\text{,}\) entonces

\begin{align*} r'& = a - dq\\ & = a - (ar + bs)q\\ & = a - arq - bsq\\ & = a( 1 - rq ) + b( -sq ), \end{align*}

que está en \(S\text{.}\) Pero esto estaría en contradicción con el hecho de que \(d\) es el menor miembro de \(S\text{.}\) Luego, \(r' = 0\) y \(d\) divide a \(a\text{.}\) Un argumento similar muestra que \(d\) divide a \(b\text{.}\) Por lo tanto, \(d\) es un divisor común de \(a\) y \(b\text{.}\)

Supongamos que \(d'\) es otro divisor común de \(a\) y \(b\text{,}\) y queremos mostrar que \(d' \mid d\text{.}\) Si \(a = d'h\) y \(b = d'k\text{,}\) entonces

\begin{equation*} d = ar + bs = d'hr + d'ks = d'(hr + ks). \end{equation*}

Es decir \(d'\) divide a \(d\text{.}\) Luego, \(d\) es el único máximo común divisor de \(a\) y \(b\text{.}\)

SubsecciónEl Algoritmo de Euclides

Entre otras cosas, el Teorema 2.10 nos permite calcular el máximo común divisor de dos enteros.

Ejemplo2.12

Calculemos el máximo común divisor de \(945\) y \(2415\text{.}\) Primero observemos que

\begin{align*} 2415 & = 945 \cdot 2 + 525\\ 945 & = 525 \cdot 1 + 420\\ 525 & = 420 \cdot 1 + 105\\ 420 & = 105 \cdot 4 + 0. \end{align*}

Usando los pasos de atrás para adelante, 105 divide a 420, 105 divide a 525, 105 divide a 945, y 105 divide a 2415. Luego, 105 divide tanto a 945 como a 2415. Si \(d\) fuese otro divisor común de 945 y 2415, entonces \(d\) también dividiría a 105. Por lo tanto, \(\gcd( 945, 2415 ) = 105\text{.}\)

Volviendo a recorrer las ecuaciones anteriores de abajo para arriba, podemos obtener números enteros \(r\) y \(s\) tales que \(945 r + 2415 s = 105\text{.}\) Note que

\begin{align*} 105 & = 525 + (-1) \cdot 420\\ & = 525 + (-1) \cdot [945 + (-1) \cdot 525]\\ & = 2 \cdot 525 + (-1) \cdot 945\\ & = 2 \cdot [2415 + (-2) \cdot 945] + (-1) \cdot 945\\ & = 2 \cdot 2415 + (-5) \cdot 945. \end{align*}

Así \(r = -5\) y \(s= 2\text{.}\) Note que \(r\) y \(s\) no son únicos, pues por ejemplo \(r = 41\) y \(s = -16\) también funcionarían.

Para calcular \(\gcd(a,b) = d\text{,}\) estamos usando sucesivas divisiones para obtener una sucesión decreciente de enteros positivos \(r_1 \gt r_2 \gt \cdots \gt r_n = d\text{;}\) es decir,

\begin{align*} b & = a q_1 + r_1\\ a & = r_1 q_2 + r_2\\ r_1 & = r_2 q_3 + r_3\\ & \vdots \\ r_{n - 2} & = r_{n - 1} q_{n} + r_{n}\\ r_{n - 1} & = r_n q_{n + 1}. \end{align*}

Para encontrar \(r\) y \(s\) tales que \(ar + bs = d\text{,}\) empezamos con la última ecuación y sustituímos los resultados obtenidos de las ecuaciones anteriores:

\begin{align*} d & = r_n\\ & = r_{n - 2} - r_{n - 1} q_n\\ & = r_{n - 2} - q_n( r_{n - 3} - q_{n - 1} r_{n - 2} )\\ & = -q_n r_{n - 3} + ( 1+ q_n q_{n-1} ) r_{n - 2} \\ & \vdots \\ & = ra + sb. \end{align*}

El algoritmo que acabamos de usar para encontrar el máximo común divisor \(d\) de dos enteros \(a\) y \(b\) y escribir \(d\) como combinación lineal de \(a\) y \(b\) se conoce como el algoritmo de Euclides.

SubsecciónNúmeros Primos

Sea \(p\) un entero tal que \(p \gt 1\text{.}\) Decimos que \(p\) es un número primo, o simplemente \(p\) es primo, si y solo si los únicos números enteros positivos que dividen a \(p\) son 1 y el mismo \(p\text{.}\) Un entero \(n \gt 1\) que no es primo se llama compuesto.

Supongamos que \(p\) no divide a \(a\text{.}\) Debemos mostrar que \(p \mid b\text{.}\) Como \(\gcd( a, p ) = 1\text{,}\) existen enteros \(r\) y \(s\) tales que \(ar + ps = 1\text{.}\) Así

\begin{equation*} b = b(ar + ps) = (ab)r + p(bs). \end{equation*}

Como \(p\) divide tanto a \(ab\) como a sí mismo, \(p\) divide a \(b = (ab)r + p(bs)\text{.}\)

Demostraremos este teorema por contradicción. Supongamos que existe solo una cantidad finita de primos, digamos \(p_1, p_2, \ldots, p_n\text{.}\) Sea \(P = p_1 p_2 \cdots p_n + 1\text{.}\) Entonces \(P\) debe ser divisible por algún \(p_i\) con \(1 \leq i \leq n\text{.}\) En este caso, \(p_i\) debe dividir a \(P - p_1 p_2 \cdots p_n = 1\text{,}\) lo que es una contradicción. Luego, ya sea \(P\) es primo o existe un primo adicional \(p \neq p_i\) que divide a \(P\text{.}\)

Unicidad. Para demostrar la unicidad procederemos por inducción en \(n\text{.}\) El teorema es claramente verdadero para \(n = 2\) pues en este caso \(n\) es primo. Ahora supongamos que el resultado se cumple para todos los enteros \(m\) tales que \(1 \leq m \lt n\text{,}\) y

\begin{equation*} n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l, \end{equation*}

con \(p_1 \leq p_2 \leq \cdots \leq p_k\) y \(q_1 \leq q_2 \leq \cdots \leq q_l\text{.}\) Por el Lema 2.13, \(p_1 \mid q_i\) para ciertos \(i = 1, \ldots, l\) y \(q_1 \mid p_j\) para ciertos \(j = 1, \ldots, k\text{.}\) Como todos los \(p_i\) y los \(q_i\) son primos, \(p_1 = q_i\) y \(q_1 = p_j\text{.}\) Luego, \(p_1 = q_1\) pues \(p_1 \leq p_j = q_1 \leq q_i = p_1\text{.}\) Por la hipótesis de inducción,

\begin{equation*} n' = p_2 \cdots p_k = q_2 \cdots q_l \end{equation*}

tiene una factorización única. Luego, \(k = l\) y \(q_i = p_i\) para \(i = 1, \ldots, k\text{.}\)

Existencia. Para demostrar la existencia, supongamos que existe algún entero que no puede ser escrito como producto de primos. Sea \(S\) el conjunto de tales números. Por el Principio del Buen-Orden, \(S\) contiene un elemento mínimo, digamos \(a\text{.}\) Si los únicos factores positivos de \(a\) son \(a\) y 1, entonces \(a\) es primo, lo que es una contradicción. Luego, \(a = a_1 a_2\) con \(1 \lt a_1 \lt a\) y \(1 \lt a_2 \lt a\text{.}\) Ni \(a_1\in S\) ni \(a_2 \in S\text{,}\) pues \(a\) es el menor elemento de \(S\text{.}\) Así

\begin{align*} a_1 & = p_1 \cdots p_r\\ a_2 & = q_1 \cdots q_s. \end{align*}

Por lo tanto,

\begin{equation*} a = a_1 a_2 = p_1 \cdots p_r q_1 \cdots q_s. \end{equation*}

Así \(a \notin S\text{,}\) lo que es una contradicción.

SubsecciónNota Histórica

Los números primos ya fueron estudiados por los antiguos Griegos. Dos resultados importantes de la Antigüedad son la demostración de Euclides de que existe una infinidad de primos y la criba de Ertóstenes, un método para calcular todos los números primos menores a un entero positivo dado. Un problema en teoría de números es encontrar una función \(f\) tal que \(f(n)\) es primo para cada entero \(n\text{.}\) Pierre Fermat (1601?–1665) conjeturó que \(2^{2^n} + 1\) era primo para todo \(n\text{,}\) pero posteriormente Leonhard Euler (1707–1783) demostró que

\begin{equation*} 2^{2^5} + 1 = \text{4,294,967,297} \end{equation*}

es un número compuesto. Una de las muchas conjeturas no demostradas sobre números primos es la conjetura de Goldbach. En una carta a Euler en 1742, Christian Goldbach enunció la conjetura que todo entero positivo con la excepción de 2 parecía ser suma de dos primos: \(4 = 2 + 2\text{,}\) \(6 = 3 + 3\text{,}\) \(8 =3 + 5\text{,}\) \(\ldots\text{.}\) Si bien la conjetura ha sido verificada para todos los números hasta \(4 \times 10^{18}\text{,}\) aún no ha sido demostrada en general. Como los números primos tienen un rol importante en la criptografía de clave pública, hay actualmente gran interés en determinar si un número grande es primo o no.