Archivo de la etiqueta: aritmética

Álgebra Superior II: El algoritmo de Euclides

Por Leonardo Ignacio Martínez Sandoval

1 respuesta

Introducción

En entradas anteriores estudiamos los conceptos de máximo común divisor y de mínimo común múltiplo. Ahora nos enfocaremos en un aspecto un poco más práctico sobre el máximo común divisor que dejamos pendiente: ¿cómo lo calculamos? Para ello hablaremos de un procedimiento conocido como el algoritmo de Euclides, el cual afirma que afirma que podemos aplicar iteradas veces el algoritmo de la división en ciertos números específicos, comenzando con dos enteros $a$ y $b$ para encontrar su máximo común divisor de dos enteros positivos $a$ y $b$.

Lo primero que haremos es explicar el procedimiento mediante el cual podemos encontrar el máximo común divisor de dos números aplicando repetidamente el algoritmo de la división. En la siguiente sección daremos la demostración de por qué funciona este procedimiento. Hacia el final de la entrada también veremos que este mismo procedimiento nos permite también escribir al máximo común divisor de dos enteros $a$ y $b$ como combinación lineal de ellos, es decir, de la forma $ra+sb$ con $r$ y $s$ números enteros.

El procedimiento del algoritmo de Euclides

Sean $a, b$ cualesquiera enteros positivos, con $a \neq b$ y $a > b.$ Por el algoritmo de la división, sabemos que siempre existen $q, r \in \mathbb{Z}$ tales que podemos escribir $$a = bq + r, \enspace \text{con} \quad \quad 0 \leq r < b. $$

Luego, como $b$ y $r$ son enteros, también existen $q_1$ y $r_1$ tales que $$b = rq_1 + r_1,\enspace \text{con} \quad \quad 0 \leq r_1 < r.$$

Y como $r$ y $r_1$ son enteros, existen $q_2$ y $r_2 \in \mathbb{Z}^+$ tales que $$r = r_1q_2 + r_2,\enspace \text{con} \quad \quad 0 \leq r_2 < r_1.$$

Se puede continuar así sucesivamente. Pero este procedimiento debe de terminar, pues tenemos $b>r>r_1>r_2>\ldots \geq 0$, de modo que debe existir una $i$ tal que $r_i=0$. De esta forma, en el penúltimo paso tendremos que existen $q_{i-1}$ y $r_{i-1}$ enteros tales que $$r_{i-3} = r_{i-2}q_{i-1} + r_{i-1}, \enspace \text{con} \quad \quad 0 \leq r_{i-1} < r_{i-2}.$$

Y en el último paso tendríamos $q_i \in \mathbb{Z}^+$ y $r_i = 0$ tales que
$$r_{i-2} = r_{i-1}q_i + 0, \enspace \text{con} \quad \quad 0 = r_i < r_{i-1} .$$

Lo que nos dice el algoritmo de Euclides es que el último residuo no cero, en este caso $r_{i-1}$ es el máximo común divisor de $a$ y $b$.

Este procedimiento es particularmente útil cuando $a$ y $b$ son números tan grandes, tanto que determinar el máximo común divisor de ellos no sea inmediato. Aunque se comience con números muy grandes, el algoritmo de Euclides encuentra el MCD de manera rápida.

Ejemplo del algoritmo de Euclides

A continuación veremos el algoritmo de Euclides en acción.

Problema. Encuentra el máximo común divisor de $3456$ y $6524$.

Solución. Observamos que $6524 > 3456$. Así, $$6524 = 3456\cdot 1 + 3068, \quad \quad 0 \leq 3068 < 3456. $$
Aplicando nuevamente el algoritmo de la división, obtenemos
$$3456 = 3068 \cdot 1 + 388, \quad \quad 0 \leq 388 < 3068. $$
Aplicando una vez más el algoritmo de la división, se tiene
$$3068 = 388\cdot 7 + 352, \quad \quad 0 \leq 352 < 388. $$
Siguiendo este procedimiento,
$$388 = 352 \cdot 1 + 36, \quad \quad 0 \leq 36 < 352. $$
$$352 = 36 \cdot 9 + 28, \quad \quad 0 \leq 28 < 36. $$
$$36 = 28\cdot 1 + 8, \quad \quad 0 \leq 8 < 28.$$
$$28 = 8 \cdot 3 + 4, \quad \quad 0 \leq 4 < 8.$$
$$8 = 4\cdot 2 + 0.$$

Como el último residuo no cero es $4$, entonces $(6524, 3456)=4$.

$\triangle$

Observación. Aunque el algoritmo de Euclides requiere que los números $a$ y $b$ sean positivos, cuando ocurre el caso de que uno de ellos o los dos fueran negativos, no hay un gran obstáculo. Basta sacar el valor absoluto de ambos números al inicio, ya que los divisores de un número negativo son los mismos que los de su valor absoluto.

Veamos un ejemplo que usa esta observación.

Ejemplo. Obtén el máximo común divisor de $-100$ y $45$.

Solución. Como uno de los números es negativo, antes que nada sacamos valores absolutos: $|-100| = 100$ y $|45| = 45.$ Le aplicamos el algoritmo de Euclides a estos números:
$$ 100 = 45 \cdot 2 + 10, \quad \quad 0 \leq 10 < 45. $$
$$ 45 = 10 \cdot 4 + 5, \quad \quad 0 \leq 5 < 10. $$
$$10 = 5 \cdot 2 + 0.$$

Notemos que el último residuo no cero es $5$. Por lo tanto, $(-100, 45) = 5.$

$\triangle$

Demostración de la validez del algoritmo de Euclides

Ahora, veamos la demostración de que el algoritmo de Euclides funciona. El resultado clave para demostrarlo es la siguiente proposición.

Proposición. Sean $a,b \in \mathbb{Z}^+, $ tales que $a = bq + r.$ Entonces $(a,b) = (b,r).$

Demostración. Sean $a,b \in \mathbb{Z}^+$. Sea $d=(a,b)$ el máximo común divisor de $a$ y $b$, y sea $f=(b,r)$ el máximo común divisor de $b$ y $r$.

Tenemos que $d\mid a$. Además, $d \mid b,$ por lo que $d\mid bq$. Así, $d\mid a-bq=r$. De este modo, $d$ es un divisor común de $b$ y de $r$, de modo que $d\mid f$.

Por otro lado, $f\mid b$, de donde $f\mid bq$. Además, $f\mid r$. De este modo, $f\mid bq+r=a$. Concluimos entonces que $f$ es divisor común de $a$ y $b$. Pero entonces $f\mid d$.

Por propiedades de divisibilidad, tenemos entonces que $|f|=|d|$, pero como ambos son números no negativos concluimos entonces que $f=d$, como queríamos.

$\square$

Ya con este resultado demostrado, enunciemos formalmente el algoritmo de Euclides y demos su demostración.

Teorema. Empecemos tomando dos enteros positivos $a$ y $b$, con $a\geq b$. Usando el algoritmo de la división, definimos sucesivamente los números $r_0,r_1,\ldots,r_i$ y $q_0,q_1,\ldots,q_i$ de manera que se cumpla

\begin{align*}
b=aq_0+r_0\\
a=r_0q_1+r_1
\end{align*}

con $0\leq r_0<a$, y $0\leq r_1 < r_0$ y para $j=2,\ldots,i$ que se cumpla

\begin{align*}
r_{j-2}=r_{j-1}q_j+r_{j},
\end{align*}

con $0\leq r_j < r_{j-1}.$

Como $b\geq a > r_0 > r_1 > r_2 > \ldots > r_i$, entonces podemos suponer que $r_i=0$. Entonces $(a,b)=r_{i-1}$.

Demostración. Por la proposición anterior, tenemos que $(a,b)=(b,r_0)$. También por esa misma proposición, tenemos que $(b,r_0)=(r_0,r_1)$. Y, de hecho, aplicando repetidamente la proposición tenemos que:

$$(r_0,r_1)=(r_1,r_2)=\ldots=(r_{i-1},r_i)=(r_{i-1},0)=r_{i-1}.$$

La penúltima igualdad es porque $r_i=0$ y la última porque $(n,0)=n$ para cualquier entero positivo $n$.

$\square$

Máximo común divisor como combinación lineal entera

Una última consecuencia del algoritmo de Euclides es que nos ayuda a poner al máximo común divisor de dos números $a$ y $b$ como combinación lineal entera de ellos dos.

Una forma práctica de encontrar la combinación lineal correspondiente es mediante el siguiente procedimiento. Tomaremos como ejemplo el algoritmo de Euclides que ya habíamos hecho para encontrar $(6524,3456)$.

$$6524 = 3456\cdot 1 + 3068, \quad \quad 0 \leq 3068 < 3456. $$
$$3456 = 3068 \cdot 1 + 388, \quad \quad 0 \leq 388 < 3068. $$
$$3068 = 388\cdot 7 + 352, \quad \quad 0 \leq 352 < 388. $$
$$388 = 352 \cdot 1 + 36, \quad \quad 0 \leq 36 < 352. $$
$$352 = 36 \cdot 9 + 28, \quad \quad 0 \leq 28 < 36. $$
$$36 = 28\cdot 1 + 8, \quad \quad 0 \leq 8 < 28.$$
$$28 = 8 \cdot 3 + 4, \quad \quad 0 \leq 4 < 8.$$
$$8 = 4\cdot 2 + 0.$$

Lo que haremos es la siguiente tabla, en donde en la columna izquierda ponemos todos los residuos que vamos encontrando. Además, completaremos la primera fila con $1,0$ y la segunda con $0,1$.

$6524$$1$$0$
$3456$$0$$1$
$3068$
$388$
$352$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Vamos a ir llenando la tabla con lo que ya sabemos del algoritmo de Euclides. Por el algoritmo de Euclides, sabemos que $3456$ cabe $1$ vez en $6524$. Por esta razón, restamos $1$ vez la segunda fila de la primera, para obtener $1-0=1$ y $0-1=-1$. Estos son los números que van en la fila $3$, columnas $2$ y $3$:

$6524$$1$$0$
$3456$$0$$1$
$3068$$\mathbf{1}$$\mathbf{-1}$
$388$
$352$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

De nuevo, $3068$ cabe una vez en $3456$, así que de nuevo restamos una vez el tercer renglón del segundo. Nos queda $0-1=-1$ y $1-(-1)=2$ para las nuevas entradas:

$6524$$1$$0$
$3456$$0$$1$
$3068$$1$$-1$
$388$$\mathbf{-1}$$\mathbf{2}$
$352$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Ahora cambia un poco, pues $388$ ya sabemos que cabe $7$ veces en $3068$ (por lo que hicimos del algoritmo de Euclides). Así, para la nueva fila restamos siete veces la cuarta fila de la tercera, para obtener como nuevos números $1-7\cdot (-1)=8$ y $-1-7\cdot (2)=-15$. La tabla queda así:

$6524$$1$$0$
$3456$$0$$1$
$3068$$1$$-1$
$388$$-1$$2$
$352$$\mathbf{8}$$\mathbf{-15}$
$36$
$28$
$8$
$4$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Siguiendo este procedimiento repetidamente, llegamos a la siguiente tabla:

$6524$$1$$0$
$3456$$0$$1$
$3068$$1$$-1$
$388$$-1$$2$
$352$$8$$-15$
$36$$-9$$17$
$28$$89$$-168$
$8$$-98$$185$
$4$$383$$-723$
Ejemplo de cómo poner al MCD como combinación lineal entera.

Los últimos dos números que pusimos en la tabla nos dan la respuesta de cómo poner a $4$ como combinación lineal entera de $6524$ y de $3456$:

$$4=383 \cdot 6524 – 723 \cdot 3456.$$

Verifica que en efecto las cuentas son correctas, y que esta expresión final es válida.

¿Cómo se demuestra que este procedimiento siempre funciona? Se puede mostrar inductivamente que, de hecho, para cada uno de los renglones con entradas $a,b,c$ se cumple que $a=6524b+3456c$. Esto queda como uno de los problemas de tarea moral.

Más adelante…

Esta entrada termina nuestra exploración introductoria al mundo de la aritmética de los números enteros. Sin embargo, todavía hay otros lugares a los que nos llevará el algoritmo de la división. Hasta ahora hemos discutido mucho el caso de la divisibilidad, es decir, cuando el residuo de la división de un número entre otro es igual a cero. Pero también podemos encontrar estructuras matemáticas muy ricas si estudiamos al resto de los posibles residuos. A partir de la siguiente entrada hablaremos del anillo de enteros módulo $n$, lo cual nos ayudará a formalizar estas ideas.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Usa el algoritmo de Euclides para encontrar el máximo común divisor de las siguientes parejas de números, y para escribirlo como combinación lineal entera de ellos.
    1. $15$ y $35$
    2. $18$ y $92$
    3. $201$ y $153$
    4. $328$ y $528$
  2. ¿Cómo usarías el algoritmo de Euclides para encontrar el máximo común divisor de los números $91$, $105$ y $119$? Es decir, debes encontrar el mayor entero $d$ que divida a estos tres números de manera simultánea.
  3. Hay otra forma de encontrar el máximo común divisor de dos números si conocemos su factorización en números primos. Imagina que tenemos dos números $n$ y $m$ y que, conjuntamente, usan los números primos distintos $p_1,p_2,\ldots, p_k$ en su factorización en primos (quizás con exponente cero). Esto nos permite escribirlos como:
    \begin{align*} m=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k} \\ n=p_1^{\beta_1}p_2^{\beta_2}\ldots p_k^{\beta_k}\ \end{align*}.
    1. Demuestra que la máxima potencia de $p_1$ que divide tanto a $m$ como a $n$ es $p_1^{\text{min}(\alpha_1,\beta_1)}$.
    2. Demuestra que el máximo común divisor de $m$ y $n$ es $$p_1^{\text{min}(\alpha_1,\beta_1)} p_2^{\text{min}(\alpha_2,\beta_2)}\cdots p_k^{\text{min}(\alpha_k,\beta_k)}.$$
  4. Demuestra un resultado análogo al del inciso anterior para el mínimo común múltiplo y usa ambos resultados para dar otra demostración de que $(m,n)[m,n]=mn$.
  5. Verifica que, en efecto, el método explicado en la entrada ayuda a escribir al máximo común divisor de dos enteros como combinación lineal de ellos.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

Álgebra Superior II: Teorema fundamental de la aritmética e infinidad de números primos

Por Ana Ofelia Negrete Fernández

2 respuestas

Introducción

En la entrada anterior comenzamos a hablar de los números primos. Lo que ahora veremos es que, en un sentido muy preciso, los números primos son los bloques con los cuales se construyen todos los demás enteros. El enunciado preciso estará dado por el teorema fundamental de la aritmética.

A grandes rasgos, el teorema fundamental de la aritmética afirma que todo entero se puede escribir como producto de primos, quizás algunos repetidos. Nos referimos a situaciones del tipo
\begin{align*}
8 &= 2 \cdot 2 \cdot 2 = 2^3,\\
13 &= 13^1,\\
152 &= 2^3\cdot 19, \enspace \text{etc.}
\end{align*}

Otro resultado que demostraremos en esta entrada es que hay una infinidad de primos. Euclides fue una de las primeras personas de quienes nos queda registro que lo notó. Veremos una demostración similar a la que él dió.

El teorema fundamental de la aritmética

El teorema fundamental de la aritmética dice que cualquier número entero es producto de números primos. Pero, más aún, nos dice que este producto es único, bajo ciertas condiciones que le ponemos a la representación. Para simplificar la presentación, estudiaremos primero lo que dice el enunciado para enteros positivos.

Teorema. Sea $n$ un entero positivo. Entonces, existe un único entero $k$ y únicos números primos $p_1\leq p_2 \leq p_3 \leq \ldots \leq p_k$ tales que $$n=p_1\cdot p_2\cdot \ldots \cdot p_k.$$

Por ejemplo, consideremos el número $1060$. Notemos que en efecto se puede escribir como producto de primos de la siguiente manera: $1060=2\cdot 2 \cdot 5 \cdot 53$. El teorema fundamental de la aritmética nos dice que esta es la única manera en la que podemos ponerlo como producto de primos. Si lo piensas un poco, no es totalmente obvio. ¿Qué impide que, por ejemplo, no pase que $1060$ tenga otra posible representación en donde el $5$ aparezca más veces, o el $2$ menos veces? Es lo que debemos estudiar.

Demostración de la existencia

Vamos a partir la demostración del teorema fundamental de la aritmética en dos partes. Primero veremos la existencia, y después la unicidad. Así, nos enfocaremos primero en ver que cualquier entero positivo tiene una factorización en números primos.

La demostración será por inducción fuerte. Si $n=1$, la factorización es la factorización vacía, en donde $k=0$, y como no estamos multiplicando nada obtenemos $1$. Si $n=2$, entonces la factorización es precisamente $2=2$, pues $2$ es un número primo. Supongamos que el resultado es cierto hasta antes de cierto número fijo $n$ y veamos qué pasa con $n$. Si $n$ es un número primo, entonces $n=n$ ya es una factorización como las que buscamos. Si $n$ no es un número primo, entonces lo podemos factorizar como $n=ab$, en donde $a$ y $b$ son enteros positivos distintos de $1$. Por ello, cada uno de $a$ y $b$ son menores que $n$ y por hipótesis inductiva tienen una factorización en primos, digamos
\begin{align*}
a&=q_1\cdot q_2 \cdot \ldots\cdot q_l\\
b&=r_1\cdot r_2 \cdot \ldots \cdot r_m.
\end{align*}

Así, renombrando $q_1,\ldots,q_l,r_1,\ldots,r_m$ como $p_1\leq \ldots \leq p_k$ (donde $k=l+m$) para que queden en orden no decreciente obtenemos la factorización $$n=p_1\cdot p_2\cdot \ldots \cdot p_k $$ buscada. Esto termina la prueba de la primera parte.

Demostración de la unicidad

Veamos ahora que las factorizaciones en primos son únicas. Una vez más, procedemos por inducción fuerte. El resultado claramente es cierto para $n=1$ y $n=2$. Supongamos que el resultado es cierto hasta antes de cierto entero $n$ dado y supongamos que tenemos dos factorizaciones para $n$:

\begin{align*}
n&=p_1\cdot p_2 \cdot \ldots\cdot p_k\\
n&=q_1\cdot q_2 \cdot \ldots \cdot q_l.
\end{align*}

Notemos que $p_k$ es un divisor de $n$, así que debe dividir a $q_1\cdot\ldots\cdot q_l$. Por una propiedad de divisibilidad que vimos en la entrada pasada, debe suceder que o bien $p_k$ divide a $q_l$, o bien que divide a $q_1\cdot \ldots \cdot q_{l-1}$. Si pasa lo segundo, debe dividir o bien a $q_{l-1}$, o bien a $q_1\cdot \ldots \cdot q_{l-2}$. Y así sucesivamente, de modo que $p_k$ debe dividir a alguno de los $q_i$. Pero como $p_k$ y $q_i$ son primos, debe suceder entonces que $p_k=q_i$. Tras cancelar este término en ambas expresiones de $n$, llegamos a que:

$$p_1\cdot p_2 \cdot \ldots\cdot p_{k-1}=q_1\cdot \ldots \cdot q_{i-1} \cdot q_i \cdot \ldots \cdot q_l,$$

pero esto es una igualdad de factorizaciones en primos para un número menor estricto a $n$. Por hipótesis inductiva, ambas factorizaciones deben de ser la misma. Así, ambas factorizaciones de $n$ son la misma, pues se obtienen a partir de estas multiplicando por el número $p_k=q_i$.

$\square$

Otra forma de escribir el teorema fundamental de la aritmética

Hay otra manera de escribir el teorema fundamental de la aritmética, en donde los primos iguales se agrupan en un mismo término, y se coloca la potencia correspondiente.

Teorema. Sea $n$ un entero positivo. Existe un único entero no negativo $k$, únicos primos $p_1\leq \ldots \leq p_k$ y únicos exponentes $\alpha_1,\ldots,\alpha_k$ tales que:

$$n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot \ldots \cdot p_k^{\alpha_k}.$$

En realidad esta segunda versión del teorema se deduce de manera inmediata de la anterior.

Ejemplo. Consideremos el número $36$. El $2$ lo divide, así que $36=18\cdot 2$. Luego, el $3$ divide al $18$, de manera que $36=3\cdot 6\cdot 2$. Finalmente, notamos que $6=2\cdot 3$, de donde $36=3\cdot 2 \cdot 3 \cdot 2$. Para obtener la «forma estándar» de la factorización, agrupamos los primos iguales, les ponenmos el orden correspondiente y escribimos en orden creciente de primos. Así, la factorización de $36$ quedaría $36=2^2\cdot 3^2$.

$\triangle$

El conjunto de primos es infinito

En esta sección queremos demostrar otro resultado importante sobre el conjunto de los números primos.

Teorema. El conjunto de números primos es infinito.

Para dar la demostración, usaremos el método de demostración por contradicción, es decir, partiremos de que el conjunto de primos no es finito y, eventualmente se disparatará el asunto.

Este en efecto parece ser el método más conveniente. Sería difícil usar inducción dado que, si bien el conjunto de primos puede indexarse por $p_1, p_2, p_3, \ldots$, no es fácil determinar cuál es el primo que sigue en la lista. O bien, dado un entero $n$, no es fácil determinar si $n+1$ será o no un número primo. Resultaría igualmente difícil intentar la demostración por algún otro método directo.

La idea que usaremos es la siguiente. Si hay finitos primos, digamos $k$, significa que se puede crear una lista finita con ellos: $p_1, p_2, \ldots , p_k$. Veremos que siempre debe existir un primo distinto de los de la lista, lo que llevará a una contradicción con la hipótesis de que sólo existían $k$ primos.

Veamos primero unos casos particulares del argumento que usaremos. Supongamos que sólo existieran $2$ primos, el $2$ y el $3$. Consideremos el número $z = 2\cdot 3 + 1$. De acuerdo al teorema fundamental de la aritmética, este número o bien es primo, o bien debe tener un divisor primo $p$. No puede ser primo, pues dijimos que los únicos primos eran $2$ y $3$. No puede ser divisible entre $2$ pues deja residuo $1$ al hacer la división. Tampoco puede ser divisible entre $3$ pues también deja residuo $1$ al hacer la división. Así, debe haber otro primo que no sea $2$ y $3$ y que divida a este número. Esto contradice que sólo existieran $2$ primos.

Veamos otro ejemplo. Supongamos que hay únicamente 4 primos: $2,3,5,7$. Consideremos el número $2 \cdot 3 \cdot 5 \cdot 7 + 1 = 211.$ Si dividimos este número entre $2$, nos da $211=105\cdot 2 +1$, así que $2\nmid 211$. Si lo dividimos entre $3$, nos da $211=70\cdot 3 + 1$, así que $3\nmid 211$. De manera similar, se puede ver que las divisiones entre $5$ y $7$ también dejan residuo $1$, así que $5 \nmid 211$ y $7\nmid 211$.

Por el teorema fundamental de la aritmética, debe haber algún primo que divida a $211$. Pero estamos suponiendo que los únicos primos que existen son $2,3,5,7$ y acabamos de ver que ninguno de estos funciona. ¡Esto es una contradicción! Lo mismo ocurrirá sin importar la cantidad de primos $p_1, p_2, \ldots , p_k$ inicial. El problema no es cuántos son exactamente, sino la suposición de que son una cantidad finita.

Demostración. Supongamos, para buscar una contradicción, que el conjunto de números primos es finito y que consiste de exactamente los $k$ números primos $p_1, p_2, \ldots , p_k$. Consideremos el número $$p_1\cdot p_2 \cdot \ldots \cdot p_k +1.$$

El anterior número no es divisible por ninguno de los primos $$p_1, p_2, \ldots , p_k,$$ pues precisamente al hacer la división el residuo que queda es igual a $1$.

Por el teorema fundamental de la aritmética, $$p_1\cdot p_2 \cdot \ldots \cdot p_k + 1$$ debe tener entonces un divisor primo $p$ diferente de $$p_1, p_2, \ldots , p_k. $$ Esto es una contradicción, pues supusimos que sólo existían los primos $p_1,\ldots,p_k$.

$\square$

Más adelante…

Con los dos teoremas de esta entrada hemos profundizando un poco más en por qué los números primos son interesantes e importantes. La exploración de los números primos en este curso no irá mucho más lejos, pues pronto comenzaremos a tratar otros temas de aritmética modular. Sin embargo, te dejamos algunos pocos párrafos más sobre los números primos.

Los números primos siguen siendo interesantes para los matemáticos hoy en día; primero por la irregularidad con que van apareciendo en la recta numérica y porque hay muchas cosas que aún no se sabe acerca de su raro comportamiento. Por ejemplo, se conjetura que hay infinitos «primos gemelos», es decir, se cree que siempre es posible encontrar dos primos $a$ y $b$ que estén distanciados en dos unidades; no importa qué tan alejados estén del cero. El $3$ y el $5$ son primos gemelos. También los son el $17$ y el $19$. Nadie sabe si esta conjetura es cierta o falsa.

Los números primos aparecen en patrones muy irregulares, pero sí es posible decir algunas cosas al respecto. Por ejemplo, después del $2$ todo número primo $p$, es de la forma $4n +1$ o de la forma $4n -1$ para alguna $n \in \mathbb{N}$. Un resultado lindo en teoría de números es que para aquéllos primos que pertenecen a la primera categoría, que son los de la forma $4n+1$, siempre existe su expresión como una suma de cuadrados: $p = 4n + 1 = m^2 + n^2$, $n, m \in \mathbb{Z}.$ Pero a los primos de la segunda categoría es imposible expresarlos como suma de cuadrados. Estos son dos de los muchos resultados que demostró Euler para números primos, y puedes ahondar en ello en un curso de teoría de números.

Los números primos también han encontrado aplicaciones en criptografía, pues es bien sabido que si se eligen dos primos $p_1$ y $p_2$ tales que al multiplicarlos se obtenga un número compuesto $z$ de más de 100 dígitos, y si luego se establece que $p_1$ y $p_2$ sean la «clave» de mi mensaje cifrado pero yo únicamente doy a conocer el número compuesto $z$ a otra persona, entonces a una computadora le resultaría imposible factorizar $z$ en un corto lapso de tiempo. ¡Le tomaría años! De ahí que la contraseña secreta sería indescifrable.

Ahora, lo que se conoce como el «teorema fundamental de la aritmética» también tiene varias extensiones interesantes en otras áreas de las matemáticas. De hecho, en algunas estructuras la unicidad deja de ser cierta. Si combinamos a los números enteros con los números complejos (que veremos después), tenemos algunos ejemplos como $$12 = (1 + \sqrt{-11})(1 – \sqrt{-11})$$ pero también $$12 = (2 + \sqrt{-8})(2 – \sqrt{-8}).$$

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Encuentra la factorización en primos de cada uno de los siguientes números 100, 170, 2022, 5000 y 713.
  2. Encuentra el menor entero positivo $k$ que haga que $775k$ sea un número cuadrado perfecto, es decir, de la forma $n^2$ para algún entero $n$.
  3. Halla el número de divisores de $2360$ y calcula la suma de todos ellos.
  4. ¿Cuál es el número entero de $1$ a $100$ que tiene la mayor cantidad posible de divisores?
  5. Demuestra que un entero tiene una cantidad impar de divisores si y sólo si es un número cuadrado.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

Álgebra Superior II: Números primos y sus propiedades

Por Ana Ofelia Negrete Fernández

Deja un comentario

Introducción

En esta entrada hablaremos de los protagonistas de entre los números enteros: los números primos. Es difícil poder enunciar en palabras sencillas la importancia que tienen este tipo de números, así que haremos un recorrido que incluye lo siguiente. Comenzaremos dando la definición de qué es un número primo, y haremos algunas aclaraciones conceptuales. Luego, enunciaremos propiedades de divisibilidad que cumplen los números primos y que son muy únicas a ellos. Esto nos ayudará a entender un poco de las razones por las cuales son especiales.

Finalmente, dejaremos preparado el terreno para poder hablar de dos resultados fundamentales sobre los números primos en la próxima entrada: el teorema fundamental de la aritmética y la infinidad del conjunto de números primos. El primer resultado nos permitirá pensar a los números primos como los átomos de los números enteros, ya que a partir de multiplicarlos se obtendrá cualquier entero, sea éste primo o compuesto.

Definición de números primos

La definición con la que trabajaremos es la siguiente.

Definición. Un entero número entero $p$ es primo si y sólo si es positivo y tiene exactamente cuatro divisores: $1, \enspace -1, \enspace z \enspace \text{y } -z \text{.}$

De la definición hay algunos números que inmediatamente debemos descartar por no ser números primos. Por ejemplo, el $1$ no es un número primo pues tiene como divisores únicamente al $-1$ y al $1$, que son dos divisores, y no exactamente cuatro, como pide la definición. Del mismo modo, $-1$ tampoco es número primo pues tiene sólo dos divisores también y, para rematar, es negativo, lo cual no se vale.

Del mismo modo, concluimos que el $0$ no es número primo. Su problema es que tiene demasiados divisores. Cualquier número entero divide al $0$, así que tiene mucho más que cuatro divisores. Veamos nuestro primer ejemplo de un número que sí es primo.

Proposición. El entero $2$ es primo.

Demostración. Lo primero por notar es que $2$ es positivo. Supongamos que $x \in \mathbb{Z}$ divide a $2$. Por cómo se comparan en tamaños un número con un divisor, obtenemos que $|d|\leq 2$. Esto nos deja $5$ posibilidades para $d$: $-2,-1,0,1,2$. El $0$ nunca es divisor y se puede ver que cada uno de los otros cuatro números sí lo son. Así, el $2$ tiene exactamente cuatro divisores, que son $1$, $2$, $-1$ y $-2$. Concluimos entonces que $2$ es un número primo.

$\square$

Si bien el $-2$ también tiene exactamente esos mismos $4$ divisores, a $-2$ no le llamamos número primo porque es negativo. Recuerda que por definición sólo los números positivos pueden ser primos.

En la duda, si no sabemos si un número es primo, siempre podemos regresar a la definición.

Proposición. El entero $57$ no es primo.

Demostración. Notamos que $1$, $3$, $19$ y $57$ son todos ellos divisores de $57$, así como sus negativos. Por ello, el número $57$ tiene ocho divisores, y por lo tanto no es primo.

$\square$

Otras formas de pensar a los números primos

La definición de primos que dimos está en términos de la cantidad de divisores en total que se deben tener. Sin embargo, hay por lo menos otras dos formas de escribir esto mismo.

Proposición. Son equivalentes las siguientes tres afirmaciones para un número entero $p$:

  • El número $p$ es primo de acuerdo a nuestra definición de tener exactamente $4$ divisores.
  • El número $p$ es positivo y tiene exactamente $2$ divisores positivos.
  • El número $p$ es positivo y en cualquier forma de escribir $p=ab$ con $a$ y $b$ enteros positivos, sucede forzosamente que $a=1$ ó $b=1$.

Demostración. Los primeros dos puntos son equivalentes entre sí pues si $d$ es un divisor de $p$, entonces $-d$ también. Así, por cada divisor positivo hay uno negativo y viceversa. De hecho, los dos divisores positivos son, explícitamente, $1$ y $p$.

Si $p$ es primo con respecto a esta segunda definición, entonces el tercer inciso es claro, pues escribir $p=ab$ justo nos dice que $a|p$, de donde $a=1$ ó $a=p$, pues son sus únicos dos posibles divisores. Si $a=1$, tenemos lo que queremos. Y si $a=p$, entonces para que se de $p=ab$, debemos tener $b=1$, como queremos.

Finalmente, a partir del tercer inciso también se puede demostrar el segundo. Supongamos que $p$ cumple con el tercer inciso y supongamos que $d$ es divisor. ESto nos permite escribir $p=dr$ con $r$ algún entero. Por el tercer inciso, debemos tener $d=1$, o bien $r=1$, y entonces $d=p$, tal como nos pide el segundo inciso.

$\square$

Quizás no se ve tanto la ventaja entre distinguir entre las primeras dos versiones de la proposición anterior. De hecho, se parecen mucho. Sin embargo, sí vale la pena pensar en la tercera como algo diferente: nos dice que hay sólamente dos maneras de escribir a un primo como producto de números positivos. Esto nos ayuda, por ejemplo, a darnos cuenta rápidamente que un número no es primo aunque no tengamos todos sus divisores.

Ejemplo. El número $105$ no es primo pues se puede escribir como $5\cdot 21$. En esta expresión ninguno de los dos números es igual a $1$. Así, concluimos que $105$ no es primo.

$\square$

Propiedades de divisibilidad de los números primos

En el caso de los números primos, los máximos comunes divisores son asunto de todo o nada. Esto está escrito más formalmente en la siguiente definición.

Proposición. Sea $p$ un número primo y $a$ un entero. Si $p$ divide a $a$, tenemos $(a,p)=p$. Y si no, tenemos $(a,p)=1$.

Demostración. Sabemos que $(a,p)|p$ y que $(a,p)$ no es negativo. Así, $(a,p)$ debe ser uno de los dos divisores de $p$: $1$ ó $p$. Si $p$ divide a $a$, entonces $(a,p)=p$ pues $p$ es divisor común tanto de $p$ como de $a$. Pero si $p$ no divide a $a$, entonces a $(a,p)$ no le queda más que ser igual a $1$.

$\square$

La proposición anterior nos lleva a un lema de divisibilidad que nos resultará útil cuando enunciemos y probemos el teorema fundamental de la aritmética.

Proposición. Sea $p$ un número primo y $a,b$ números enteros. Si $p|ab$, entonces $p|a$ ó $p|b$.

Demostración. Si $p|a$, entonces ya terminamos. Si no, por la proposición anterior tenemos que $(p,a)=1$. Pero entonces por una propiedad anterior de divisibilidad con primos relativos obtenemos que $p|b$, como queríamos.

$\square$

Para la proposición anterior resultó crucial que $p$ fuera un número primo. Por ejemplo, tenemos que $9|180=15\cdot 12$, pero no es cierto ni que $9|15$, ni que $9|12$.

Más adelante…

En la siguiente entrada veremos dos teoremas importantes relacionados con los números primos: el teorema fundamental de la aritmética y el teorema de que existe una infinidad de primos.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Encuentra todos los números primos de $1$ a $20$.
  2. Sea $n$ un número entero que no sea un número primo, ni el negativo de un número primo. Demuestra $n$ que se puede expresar de la forma $ab$ con $a$ y $b$ enteros (positivos o negativos) de por lo menos ocho formas distintas.
  3. Sea $p>2$ un número tal que ninguno de los números $2,\ldots,\left\lfloor \sqrt{p}\right \rfloor$ lo divide. Muestra que $p$ es un número primo.
  4. Sea $n$ un número entero y $p$ un primo. Muestra que si $p|n^2$, entonces $p|n$. De hecho, muestra que en general, para un entero $k\geq 1$ se cumple que $p|n^k$ si y sólo si $p|n$.
  5. Sea $p$ un número primo. ¿Cuántos divisores tiene el número $p^{10}$? ¿Cuántos son positivos y cuántos negativos?

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

Álgebra Superior II: Máximo común divisor de polinomios y algoritmo de Euclides

Por Leonardo Ignacio Martínez Sandoval

2 respuestas

Introducción

En esta entrada continuamos estudiando propiedades aritméticas del anillo de polinomios con coeficientes reales. En la entrada anterior introdujimos el algoritmo de la división, la noción de divisibilidad y los polinomios irreducibles. Además, mostramos el teorema del factor y el teorema del residuo. Lo que haremos ahora es hablar del máximo común divisor de polinomios.

Mucha de la teoría que desarrollamos en los enteros también se vale para $\mathbb{R}[x]$. Como en $\mathbb{Z}$, lo más conveniente para desarrollar esta teoría es comenzar hablando de ideales. Con estos buenos cimientos, veremos que el máximo común divisor de dos polinomios se puede escribir como «combinación lineal de ellos». Para encontrar la combinación lineal de manera práctica, usaremos de nuevo el algoritmo de Euclides.

Antes de comenzar, haremos una aclaración. Hasta ahora hemos usado la notación $f(x), g(x),h(x)$, etc. para referirnos a polinomios. En esta entrada frecuentemente usaremos nada más $f,g,h$, etc. Por un lado, esto simplificará los enunciados y demostraciones de algunos resultados. Por otro lado, no corremos el riesgo de confusión pues no evaluaremos a los polinomios en ningún real.

Ideales de $\mathbb{R}[x]$

Comenzamos con la siguiente definición clave, que nos ayuda a hacer las demostraciones de máximo común divisor de polinomios de manera más sencilla.

Definición. Un subconjunto $I$ de $\mathbb{R}[x]$ es un ideal si pasa lo siguiente:

  1. El polinomio cero de $\mathbb{R}[x]$ está en $I$.
  2. Si $f$ y $g$ son elementos de $\mathbb{R}[x]$ en $I$, entonces $f+g$ está en $I$.
  3. Si $f$ y $g$ son elementos de $\mathbb{R}[x]$, y $f$ está en $I$, entonces $fg$ está en $I$.

Ejemplo 1. El conjunto $I_0=\{f\in \mathbb{R}[x]\mid f(0)=0 \}$.

Evidentemente el polinomio constante $0$, está en $I_0$, ya que evaluado en cualquier número es cero (en particular al evaluarlo en 0).

Si $f,g\in I_0$, entonces $(f+g)(0)=f(0)+g(0)=0+0=0$, por lo que $f+g\in I_0$.

Finalmente, si $g\in I_0$ y $f$ es cualquier polinomio, tenemos que $(fg)(0)=f(0)g(0)=f(0)\cdot 0=0$, por lo que $fg\in I_0$. Con esto concluimos que $I_0$ es un ideal.

$\triangle$

Al igual que en los enteros, los únicos ideales consisten de múltiplos de algún polinomio. El siguiente resultado formaliza esto.

Teorema (caracterización de ideales en $\mathbb{R}[x]$). Un subconjunto $I$ es un ideal de $\mathbb{R}[x]$ si y sólo si existe un polinomio $f$ tal que $$I=f\mathbb{R}[x]:=\{fg: g \in \mathbb{R}[x]\}.$$

Demostración de «la ida». Primero mostraremos que cualquier conjunto de múltiplos de un polinomio dado $f$ es un ideal. Tomemos $f$ en $\mathbb{R}[x]$ y $$I=f\mathbb{R}[x]=\{fg: g \in \mathbb{R}[x]\}.$$

La propiedad (1) de la definición de ideal se cumple pues tomando $g=0$ tenemos que $f\cdot 0 = 0$ está en $I$.

Para la propiedad (2), tomamos $fg_1$ en $I$ y $fg_2$ en $I$, es decir, con $g_1$ y $g_2$ en $\mathbb{R}[x]$. Su suma es, por la ley de distribución, el polinomio $f\cdot (g_1+g_2)$, que claramente está en $I$ pues es un múltiplo de $f$.

Para la propiedad (3), tomamos $fg$ en $I$ y $h$ en $\mathbb{R}[x]$. El producto $(fg)\cdot h$ es, por asociatividad, igual al producto $f\cdot(gh)$, que claramente está en $I$. De esta forma, $I$ cumple (1), (2) y (3) y por lo tanto es un ideal.

$\square$

Demostración de «la vuelta». Mostraremos ahora que cualquier ideal $I$ es el conjunto de múltiplos de un polinomio. Si $I=\{0\}$, que sólo tiene al polinomio cero, entonces $I$ es el conjunto de múltiplos del polinomio $0$. Así, podemos suponer que $I$ tiene algún elemento que no sea el polinomio $0$.

Consideremos el conjunto $A$ de naturales que son grado de algún polinomio en $I$. Como $I$ tiene un elemento no cero, $A$ es no vacío. Por el principio del buen orden, $A$ tiene un mínimo, digamos $n$. Tomemos en $I$ un polinomio $f$ de grado $n$. Afirmamos que $I$ es el conjunto de múltiplos de $f$, es decir, $$I=f\mathbb{R}[x].$$

Por un lado, como $f$ está en $I$ e $I$ es un ideal, por la propiedad (3) de la definición de ideal se tiene que $fg$ está en $I$ para todo $g$ en $\mathbb{R}[x]$. Esto muestra la contención $f\mathbb{R}[x]\subseteq I$.

Por otro lado, supongamos que hay un elemento $h$ que está en $I$, pero no es múltiplo de $f$. Por el algoritmo de la división, podemos encontrar polinomios $q$ y $r$ tales que $h-qf=r$ y $r$ es el polinomio cero o de grado menor a $f$. No es posible que $r$ sea el polinomio cero pues dijimos que $h$ no es múltiplo de $f$. Así, $r$ no es el polinomio cero y su grado es menor al de $f$.

Notemos que $-qf$ está en $I$ por ser un múltiplo de $f$ y que $h$ está en $I$ por cómo lo elegimos. Por la propiedad (2) de la definición de ideal se tiene entonces que $r=h+(-qf)$ también está en $I$. Esto es una contradicción, pues habíamos dicho que $f$ era un polinomio de grado mínimo en $I$, pero ahora $r$ tiene grado menor y también está en $I$. Por lo tanto, es imposible que exista un $h$ en $I$ que no sea múltiplo de $f$. Esto muestra la contención $I\subseteq f\mathbb{R}[x]$.

$\square$

Ejemplo 2. En el ejemplo anterior, $I_0$ denotaba el conjunto de polinomios que se anulan en $0$, podemos demostrar que $I_0=x\mathbb{R}[x]$, ya que si $f\in I_0$, por el teorema del factor, el polinomio $x-0$ divide a $f$, es decir que $f(x)=xg(x)$ para alguan $g\in \mathbb{R}[x]$. Esto prueba que $I_0\subseteq x\mathbb{R}$, dejamos el resto de los detalles como un ejercicio moral.

$\triangle$

El teorema anterior nos dice que cualquier ideal se puede escribir como los múltiplos de un polinomio $f$. ¿Es cierto que este polinomio $f$ es único? Para responder esto, pensemos qué sucede si se tiene $$f\mathbb{R}[x]=g\mathbb{R}[x],$$ o, dicho de otra forma, pensemos qué sucede si $f$ divide a $g$ y $g$ divide a $f$.

Si alguno de $f$ ó $g$ es igual a $0$, entonces el otro también debe de serlo. Así, podemos suponer que ninguno de ellos es igual a $0$. Como $g$ divide a $f$, podemos escribir a $f$ como $hg$ para $h$ un polinomio no cero. De manera similar, podemos escribir a $g$ como un polinomio $kf$ para $k$ un polinomio no cero. Pero entonces $$f=hg=hkf.$$

El grado del lado izquierdo es $\deg(f)$ y el del derecho es $\deg(h)+\deg(k)+\deg(f)$, de donde obtenemos que $\deg(h)=\deg(k)=0$. En otras palabras, concluimos que $h$ y $k$ son polinomios constantes y distintos de cero. Resumimos esta discusión a continuación.

Proposición. Tomemos $f(x)$ y $g(x)$ polinomios en $\mathbb{R}[x]$ distintos del polinomio $0$. Si $f(x)$ divide a $g(x)$ y $g(x)$ divide a $f(x)$, entonces $f(x)=hg(x)$ para un real $h\neq 0$. Del mismo modo, si $f(x)=hg(x)$ con $h$ un real, entonces $f(x)$ divide a $g(x)$ y $g(x)$ divide a $f(x)$.

Cuando sucede cualquiera de las cosas de la proposición anterior, decimos que $f(x)$ y $g(x)$ son asociados.

Ya que no hay un único polinomio que genere a un ideal, nos conviene elegir a uno de ellos que cumpla una condición especial. El coeficiente principal de un polinomio es el que acompaña al término de mayor grado. En otras palabras, si $p(x)$ es un polinomio de grado $n$ dado por $$p(x)=a_0+\ldots+a_nx^n,$$ con $a_n\neq 0$, entonces $a_n$ es coeficiente principal.

Definición. Un polinomio es mónico si su coeficiente principal es $1$.

Por la proposición anterior, existe un único polinomio mónico asociado a $p(x)$, y es $\frac{1}{a_n}p(x)$. Podemos resumir las ideas de esta sección mediante el siguiente teorema.

Teorema. Para todo ideal $I$ de $\mathbb{R}[x]$ distinto del ideal $\{0\}$, existe un único polinomio mónico $f$ tal que $I$ es el conjunto de múltiplos de $f$, en símbolos, $$I=f\mathbb{R}[x].$$

Máximo común divisor de polinomios

Tomemos $f$ y $g$ polinomios en $\mathbb{R}[x]$. Es sencillo ver, y queda como tarea moral, que el conjunto $$f\mathbb{R}[x]+g\mathbb{R}[x]=\{rf+sg: r,s \in \mathbb{R}[x]\}$$ satisface las propiedades (1), (2) y (3) de la definición de ideal. Por el teorema de caracterización de ideales, la siguiente definición tiene sentido.

Definición. El máximo común divisor de $f$ y $g$ es el único polinomio mónico $d$ en $\mathbb{R}[x]$ tal que $$f\mathbb{R}[x]+g\mathbb{R}[x] = d\mathbb{R}[x].$$ A este polinomio lo denotamos por $\MCD{f,g}$.

De manera inmediata, de la definición de $\MCD{f,g}$, obtenemos que es un elemento de $f\mathbb{R}[x]+g\mathbb{R}[x]$, o sea, una combinación lineal polinomial de $f$ y $g$. Este es un resultado fundamental, que enunciamos como teorema.

Teorema (identidad de Bézout). Para $f$ y $g$ en $\mathbb{R}[x]$ existen polinomios $r$ y $s$ en $\mathbb{R}[x]$ tales que $$\MCD{f,g}=rf+sg.$$

El nombre que le dimos a $\MCD{f,g}$ tiene sentido, en vista del siguiente resultado.

Teorema. Para $f$ y $g$ en $\mathbb{R}[x]$ distintos del polinomio cero se tiene que:

  • $\MCD{f,g}$ divide a $f$ y a $g$.
  • Si $h$ es otro polinomio que divide a $f$ y a $g$, entonces $h$ divide a $\MCD{f,g}$.

Demostración. Por definición, $$f\mathbb{R}[x]+g\mathbb{R}[x] = \MCD{f,g}\mathbb{R}[x].$$ El polinomio $f$ pertenece al conjunto del lado izquierdo, pues lo podemos escribir como $$1\cdot f + 0 \cdot g,$$ así que también está en el lado derecho. Por ello, $f$ es un múltiplo de $\MCD{f,g}$. De manera similar se prueba que $g$ es un múltiplo de $\MCD{f,g}$.

Para la segunda parte, escribimos a $\MCD{f,g}$ como combinación lineal polinomial de $f$ y $g$, $$\MCD{f,g}=rf+sg.$$ De aquí es claro que si $h$ divide a $f$ y a $g$, entonces $h$ divide a $\MCD{f,g}$.

$\square$

Todo esto va muy bien. El máximo común divisor de dos polinomios en efecto es un divisor, y es «el mayor», en un sentido de divisibilidad. Además, como en el caso de $\mathbb{Z}$, lo podemos expresar como una combinación lineal de sus polinomios. En la tarea moral puedes ver algunos ejemplos que hablan del concepto dual: el mínimo común múltiplo.

El algoritmo de Euclides

Al igual que como sucede en los enteros, podemos usar el algoritmo de la división iteradamente para encontrar el máximo común divisor de polinomios, y luego revertir los pasos para encontrar de manera explícita al máximo común divisor como una combinación lineal polinomial de ellos. Es un buen ejercicio enunciar y demostrar que esto es cierto. No lo haremos aquí, pero veremos un ejemplo de cómo aplicar el algoritmo.

Problema: Encuentra el máximo común divisor de los polinomios
\begin{align*}
a(x)&=x^7+x^6+x^5+x^4+x^3+x^2+x+1\\
b(x)&=x^4+x^3+x^2+x+1,
\end{align*} y exprésalo como combinación lineal de $a(x)$ y $b(x)$.

Solución. Aplicando el algoritmo de la división repetidamente, tenemos lo siguiente:

\begin{align*}
a(x)&=x^3b(x)+(x^2+x+1)\\
b(x)&=x^2(x^2+x+1)+(x+1)\\
x^2+x+1&=x(x+1)+1.
\end{align*}

Esto muestra que $a(x)$ y $b(x)$ tienen como máximo común divisor al polinomio $1$. Por lo que discutimos antes, debe haber una combinación lineal polinomial de $a(x)$ y $b(x)$ igual a $1$ Para encontrarla de manera explícita, invertimos los pasos:

\begin{equation*}
\begin{split}
1 & =(x^2+x+1)-x(x+1)\\
& =(x^2+x+1)-x(b(x)-x^2(x^2+x+1))\\
& =(x^2+x+1)(x^3+1)-xb(x)\\
& =(x^3+1)(a(x)-x^3(b(x))-xb(x)\\
& =(x^3+1)a(x)-x^3(x^3+1)b(x)-xb(x)\\
& =(x^3+1)a(x)+(-x^6-x^3-x)b(x)
\end{split}
\end{equation*}

Así, concluimos que una combinación lineal que sirve es: $$(x^3+1)a(x)+(-x^6-x^3-x)b(x) = 1.$$

$\triangle$

Más adelante…

Como mencionamos, los conceptos que desarrollamos en esta sección son muy similares a los que desarrollamos para $\mathbb{Z}$, sin embargo, para que puedas acostumbrarte a la notación, en la siguiente entrada practicaremos como calcular el Máximo Común Divisor para dos polinomios.

Después de eso, el siguiente paso será extrapolar el concepto de elementos primos en el conjunto de los polinomios y con esa nueva herramienta ver la posibilidad de poder dar un resultado análogo al teorema fundamental de la aritmética que dimos en $\mathbb{Z}$.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Verifica que el conjunto $$f\mathbb{R}[x]+g\mathbb{R}[x]=\{rf+sg: r,s \in \mathbb{R}[x]\}$$ satisface las propiedades (1), (2) y (3) de la definición de ideal.
  2. Encuentra el máximo común divisor de los polinomios $x^8-1$ y $x^6-1$. Exprésalo como combinación lineal de ellos.
  3. Muestra que la intersección de dos ideales de $\mathbb{R}[x]$ es un ideal de $\mathbb{R}[x]$.
  4. Al único polinomio mónico $m$ tal que $$f\mathbb{R}[x]\cap g\mathbb{R}[x]=m\mathbb{R}[x]$$ le llamamos el mínimo común múltiplo de $f$ y $g$, y lo denotamos $\mcm{f,g}$. Muestra que es un múltiplo de $f$ y de $g$ y que es «mínimo» en el sentido de divisibilidad.
  5. Muestra que si $f$ y $g$ son polinomios mónicos en $\mathbb{R}[x]$ distintos del polinomio cero, entonces $fg = \MCD{f,g} \mcm{f,g}$. ¿Es necesaria la hipótesis de que sean mónicos? ¿La puedes cambiar por una hipótesis más débil?

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»

Álgebra Superior II: Algoritmo de la división, teorema del factor y teorema del residuo

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

Introducción

Tal vez te hayas dado cuenta de que ya hablamos de suma, producto y resta de polinomios, pero aún no hemos hablado de la división. Una razón es que no todos los polinomios tienen inverso multiplicativo. Sin embargo, los polinomios sí tienen un algoritmo de la división parecido al que estudiamos para el conjunto $\mathbb{Z}$ de enteros. A partir de él podemos extender varios de los conceptos aritméticos de $\mathbb{Z}$ a $\mathbb{R}[x]$: divisibilidad, máximo común divisor, factorización, etc. Luego, estos aspectos se pueden conectar a evaluación de polinomios mediante el un teorema clave: el teorema del factor.

Como recordatorio, hasta ahora, ya construimos el anillo $\mathbb{R}[x]$ de polinomios con coeficientes reales y vimos que era un dominio entero. También, vimos que una copia de $\mathbb{R}$ vive en $\mathbb{R}[x]$, con lo justificamos pasar de la notación de sucesiones, a la notación usual de polinomios usando el símbolo $x$ y sus potencias. En la entrada anterior también hablamos del grado de un polinomio (cuando no es el polinomio cero), de la evaluación de polinomios y de raíces.

Algoritmo de la división

Recordemos que en $\mathbb{Z}$ tenemos un algoritmo de la división que dice que para enteros $a$ y $b\neq 0$ existen únicos enteros $q$ y $r$ tales que $a=qb+r$ y $0\leq r < |b|$.

En $\mathbb{R}[x]$ hay un resultado similar. Pero hay que tener cuidado al generalizar. En $\mathbb{R}[x]$ no tenemos una función valor absoluto que nos permita decir que encontramos un «residuo más chiquito». Para la versión polinomial del algoritmo de la división tenemos que usar una función que diga «qué tan grande es un polinomio»: el grado.

Teorema (algoritmo de la división en $\mathbb{R}[x]$). Sean $f(x)$ y $g(x)$ polinomios en $\mathbb{R}[x]$, donde $g(x)$ no es el polinomio cero. Entonces, existen únicos polinomios $q(x)$ y $r(x)$ en $\mathbb{R}[x]$ tales que $$f(x)=q(x)g(x)+r(x),$$ en donde $r(x)$ es el polinomio cero, o $\deg(r(x))<\deg(g(x))$.

Demostración. Probaremos la parte de existencia. La parte de unicidad queda como tarea moral. Para probar la existencia, haremos inducción fuerte sobre el grado de $f(x)$. Sin embargo, antes de poder hacer esto, necesitamos hacer el caso en el que $f(x)$ no tiene grado, es decir, cuando es el polinomio cero.

Si $f(x)$ es el polinomio cero, entonces $q(x)=0$ y $r(x)=0$ son polinomios que funcionan, pues $0=0\cdot g(x)+0$, para cualquier polinomio $g(x)$.

Asumamos entonces a partir de ahora que $f(x)$ no es el polinomio cero. Hagamos inducción sobre el grado de $f(x)$. Si $f(x)$ es de grado $0$, entonces es un polinomio de la forma $f(x)=a$ para $a$ en $\mathbb{R}$. Hay dos casos de acuerdo al grado de $g(x)$:

  • Si $g(x)$ es de grado $0$, es de la forma $g(x)=b$ para un real no cero y podemos tomar $q(x)=a/b$ y $r(x)=0$.
  • Si $g(x)$ es de grado mayor a $0$, entonces tomamos $q(x)=0$ y $r(x)=f(x)$. Esta es una elección válida pues se cumple \begin{align*}\deg(r(x))&=\deg(f(x))\\& =0\\& <\deg(g(x)).\end{align*}.

Esto termina la demostración de la base inductiva.

Supongamos que el resultado es cierto para cuando $f(x)$ tiene grado menor a $n$ y tomemos un caso en el que $f(x)$ tiene grado $n$. Hagamos de nuevo casos con respecto al grado de $g(x)$, al que llamaremos $m$. Si $m>n$, entonces tomamos $q(x)=0$ y $r(x)=f(x)$, que es una elección válida pues $$\deg(r(x))=n<m.$$

En el caso de que $m\leq n$, escribamos explícitamente a $f(x)$ y a $g(x)$ en términos de sus coeficientes como sigue: \begin{align*}f(x)&=a_0+\ldots+a_nx^n\\g(x)&=b_0+\ldots+b_mx^m.\end{align*}

Consideremos el polinomio $$h(x):=f(x)-\frac{a_n}{b_m}x^{n-m}g(x).$$ Notemos que en $h(x)$ el coeficiente que acompaña a $x^n$ es $a_n-\frac{a_nb_m}{b_m}=0$, así que el grado de $h(x)$ es menor al de $f(x)$ y por lo tanto podemos usar la hipótesis inductiva para escribir $$h(x)=t(x)g(x)+u(x)$$ con $u(x)$ el polinomio $0$ o $\deg(u(x))<\deg(g(x))$. De esta forma,
\begin{align*}
f(x)&=t(x)g(x)+u(x)+\frac{a_n}{b_m}x^{n-m}g(x)\\
&=\left(t(x)+\frac{a_n}{b_m}x^{n-m}\right)g(x)+u(x).
\end{align*}

Así, eligiendo $q(x)=t(x)+\frac{a_n}{b_m}x^{n-m}$ y $r(x)=u(x)$, terminamos la hipótesis inductiva.

$\square$

Aplicando el algoritmo de la división de forma práctica

Veamos ahora un ejemplo de cómo se puede aplicar este teorema anterior de forma práctica. A grandes rasgos, lo que podemos hacer es «ir acumulando» en $q(x)$ a los términos $\frac{a_n}{b_m}x^{n-m}$ que van apareciendo en la inducción, y cuando $h(x)$ se vuelve de grado menor a $q(x)$, lo usamos como residuo. Hagamos un ejemplo concreto.

Ejemplo. Tomemos $f(x)=x^5+x^4+x^3+x^2+2x+3$ y $g(x)=x^2+x+1$. Vamos a aplicar iteradamente las ideas de la demostración del teorema anterior para encontrar los polinomios $q(x)$ y $r(x)$ tales que $$f(x)=q(x)g(x)+r(x),$$ con $r(x)$ el polinomio $0$ o de grado menor a $g(x)$.

Como el grado de $f(x)$ es $5$, el de $g(x)$ es $2$ y $5>2$, lo primero que hacemos es restar $x^{5-2}g(x)=x^3g(x)$ a $f(x)$ y obtenemos:

$$h_1(x)=f(x)-x^3g(x)=x^2+2x+3.$$

Hasta ahora, sabemos que $q(x)=x^3+\ldots$, donde en los puntos suspensivos va el cociente que le toca a $h_1(x)=x^2+2x+3$. Como el grado de $h_1(x)$ es $2$, el de $g(x)$ es $2$ y $2\geq 2$, restamos $x^{2-2}g(x)=1\cdot g(x)$ a $h_1(x)$ y obtenemos.

$$h_2(x)=h_1(x)-g(x)=x+2.$$

Hasta ahora, sabemos que $q(x)=x^3+1+\ldots$, donde en los puntos suspensivos va el cociente que le toca a $h_2(x)=x+2$. Como el grado de $h_2(x)$ es $1$, el de $g(x)$ es $2$ y $2>1$, entonces el cociente es $0$ y el residuo es $h_2(x)=x+2$.

De esta forma, concluimos que $$q(x)=x^3+1$$ y $$r(x)=x+2.$$

En conclusión,
\begin{align*}
x^5+ & x^4+x^3+x^2+2x+3\\
&= (x^3+1)(x^2+x+1) + x+2.
\end{align*}

Esto se puede verificar fácilmente haciendo la operación polinomial.

$\triangle$

Hay una forma más visual de hacer divisiones de polinomios «haciendo una casita». Puedes ver cómo se hace esto en el siguiente video en Khan Academy, y los videos que le siguen en la lista.

Divisibilidad en polinomios

Cuando trabajamos en $\mathbb{Z}$, estudiamos la noción de divisibilidad. Si en el algoritmo de la división obtenemos que $r(x)$ es el polinomio $0$, entonces obtenemos una noción similar para $\mathbb{R}[x]$.

Definición. Sean $f(x)$ y $g(x)$ polinomios en $\mathbb{R}[x]$. Decimos que $g(x)$ divide a $f(x)$ si existe un polinomio $q(x)$ tal que $f(x)=q(x)g(x)$.

Ejemplo 1. El polinomio $x^3-1$ divide al polinomio $x^4+x^3-x-1$, pues $$x^4+x^3-x-1 = (x^3-1)(x+1).$$

$\triangle$

Ejemplo 2. Si $g(x)$ es un polinomio no cero y constante, es decir, de la forma $g(x)=a$ para $a\neq 0$ un real, entonces divide a cualquier otro polinomio en $\mathbb{R}[x]$. En efecto, si $$f(x)=a_0+a_1x+\ldots + a_nx^n$$ es cualquier polinomio y tomamos el polinomio $$q(x)=\frac{a_0}{a}+\frac{a_1}{a}x+\ldots + \frac{a_n}{a}x^n,$$ entonces $f(x)=g(x)q(x)$.

$\triangle$

El último ejemplo nos dice que los polinomios constantes y no cero se comportan «como el $1$ se comporta en los enteros». También nos dice que cualquier polinomio tiene una infinidad de divisores. Eso nos pone en aprietos para definir algo así como los «polinomios primos» en términos del número de divisores. En la siguiente sección hablaremos de cómo hacer esta definición de manera adecuada.

Polinomios irreducibles

Cuando trabajamos con enteros, vimos que es muy útil poder encontrar la factorización en términos de números primos. En polinomios no tenemos «polinomios primos», pero tenemos un concepto parecido.

Definición. Un polinomio $p(x)$ en $\mathbb{R}[x]$ es irreducible en $\mathbb{R}[x]$ si no es un polinomio constante, y no es posible escribirlo como producto de dos polinomios no constantes en $\mathbb{R}[x]$.

Ejemplo. El polinomio $$x^4+x^2+1$$ no es irreducible en $\mathbb{R}[x]$ pues $$x^4+x^2+1=(x^2+x+1)(x^2-x+1).$$

Los polinomios $x^2+x+1$ y $x^2-x+1$ sí son irreducibles en $\mathbb{R}[x]$. Más adelante veremos por qué.

$\triangle$

La razón por la cual quitamos a los polinomios constantes es parecida a la cual en $\mathbb{Z}$ no consideramos que $1$ sea primo: ayuda a enunciar algunos teoremas más cómodamente.

Hay unos polinomios que fácilmente se puede ver que son irreducibles: los de grado $1$.

Proposición. Los polinomios de grado $1$ en $\mathbb{R}[x]$ son irreducibles.

Demostración. Si $f(x)$ es un polinomio de grado $1$, entonces no es constante. Además, no se puede escribir a $f(x)$ como el producto de dos polinomios no constantes pues dicho producto tiene grado al menos $2$.

$\square$

Hay otros polinomios en $\mathbb{R}[x]$ que no son de grado $1$ y que son irreducibles. Por ejemplo, con la teoría que tenemos ahora te debe ser fácil mostrar de tarea moral que $x^2+1$ es irreducible en $\mathbb{R}[x]$.

La razón por la que siempre insistimos en que la irreducibilidad sea en $\mathbb{R}[x]$ es por que a veces un polinomio no se puede factorizar en polinomios con coeficientes reales, pero sí con coeficientes complejos. Aunque $x^2+1$ sea irreducible en $\mathbb{R}[x]$, si permitimos coeficientes complejos se puede factorizar como $$x^2+1=(x+i)(x-i).$$

Más adelante seguiremos hablando de irreducibilidad. Por ahora, nos enfocaremos en los polinomios de grado $1$.

Teorema del factor

Una propiedad clave de los polinomios de grado $1$ es que, es lo mismo que $x-a$ divida a un polinomio $p(x)$, a que $a$ sea una raíz de $p(x)$.

Teorema (del factor). Sea $a$ un real y $p(x)$ un polinomio en $\mathbb{R}[x]$. El polinomio $x-a$ divide a $p(x)$ si y sólo si $p(a)=0$.

Demostración. De acuerdo al algoritmo de la división, podemos escribir $$p(x)=(x-a)q(x)+r(x),$$ en donde $r(x)$ es $0$ o un polinomio de grado menor estricto al de $x-a$. Como el grado de $x-a$ es $1$, la única posibilidad es que $r(x)$ sea un polinomio constante $r(x)=r$. Así, $p(x)=(x-a)q(x)+r$, con $r$ un real.

Si $p(a)=0$, tenemos que $$0=p(a)=(a-a)q(a)+r=r,$$ de donde $r=0$ y entonces $p(x)=(x-a)q(x)$, lo que muestra que $x-a$ divide a $p(x)$.

Si $x-a$ divide a $p(x)$, entonces $p(x)=(x-a)q(x)$, de donde $p(a)=(a-a)q(a)=0$, por lo que $a$ es raíz de $p(x)$.

$\square$

Ejemplo. Consideremos el polinomio $p(x)=x^3-6x^2+11x-6$. ¿Podremos encontrar algunos polinomios lineales que lo dividan? A simple vista, notamos que la suma de sus coeficientes es $1-6+11-6=0$. Esto nos dice que $p(1)=0$. Por el teorema del factor, tenemos que $x-1$ divide a $p(x)$. Tras hacer la división, notamos que $$p(x)=(x-1)(x^2-5x+6).$$

Veamos si podemos seguir factorizando polinomios lineales que no sean $x-1$. Si un polinomio $x-a$ divide a $p(x)$, por el teorema del factor debemos tener $$0=p(a)=(a-1)(a^2-5a+6).$$ Como $a\neq 1$, entonces $a-1\neq 0$, de modo que tiene que pasar $$a^2-5a+6=0,$$ en otras palabras, hay que encontrar las raíces de $x^2-5x+6$.

Usando la fórmula general cuadrática, tenemos que las raíces de $x^2-5x+6$ son
\begin{align*}
x_1&=\frac{5+\sqrt{25-24}}{2}=3\\
x_2&=\frac{5-\sqrt{25-24}}{2}=2.
\end{align*}

Usando el teorema del factor, concluimos que tanto $x-2$ como $x-3$ dividen a $p(x)$. Hasta ahora, sabemos entonces que $$p(x)=(x-1)(x-2)(x-3)h(x),$$ donde $h(x)$ es otro polinomio. Pero $(x-1)(x-2)(x-3)$ ya es un polinomio de grado $3$, como $p(x)$ y su coeficiente de $x^3$ es $1$, como el de $p(x)$. Concluimos que $h(x)=1$ y entonces $$p(x)=(x-1)(x-2)(x-3).$$

$\triangle$

Teorema del residuo

En realidad, la técnica que usamos para el teorema del factor nos dice algo un poco más general. Cuando escribimos $$p(x)=(x-a)q(x)+r$$ y evaluamos en $a$, obtenemos que $p(a)=r$. Reescribimos esta observación como un teorema.

Teorema (del residuo). Sea $a$ un real y $p(x)$ un polinomio en $\mathbb{R}[x]$. El residuo de dividir $p(x)$ entre $x-a$ es $p(a)$.

Problema. Encuentra el residuo de dividir el polinomio $p(x)=x^8-x^5+2x^3+2x$ entre el polinomio $x+1$.

Solución. Se podría hacer la división polinomial, pero esto es largo y no nos piden el polinomio cociente, sólo el residuo. Así, podemos resolver este problema más fácilmente usando el teorema del residuo.

Como $x+1=x-(-1)$, el residuo de la división de $p(x)$ entre $x+1$ es $p(-1)$. Este número es
\begin{align*}
p(-1)&=(-1)^8-(-1)^5+2(-1)^3+2(-1)\\
&=1+1-2-2\\
&=-2.
\end{align*}

$\square$

Más adelante…

Los teoremas que hemos visto en esta entrada serán las principales herramientas algebraicas que tendremos en el estudio de los polinomios así como en la búsqueda de las raíces de los polinomios y en resolver la pregunta sobre su irreductibilidad.

El algoritmo de la división nos servirá (como nos sirvió en $\mathbb{Z}$ para poder precisar el algoritmo de Euclides y definir el máximo común divisor de dos polinomios.

Por ahora, en la siguiente entrada, nos encargaremos de practicar lo aprendido y resolver ejercicios sobre raíces y residuos de polinomios.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Muestra que el polinomio $x$ no tiene inverso multiplicativo.
  2. Demuestra la parte de unicidad del algoritmo de la división.
  3. Muestra que el polinomio $x^2+1$ es irreducible en $\mathbb{R}[x]$. Sugerencia. Procede por contradicción. Una factorización tiene que ser de la forma $x^2+1=p(x)q(x)$ con $p$ y $q$ de grado $1$.
  4. Factoriza en términos lineales al polinomio $p(x)=x^3-12x^2+44x-48$. Sugerencia. Intenta enteros pequeños (digamos de $-3$ a $3$) para ver si son raíces. Uno de ellos funciona. Luego, usa el teorema del factor para expresar a $p(x)$ como un polinomio lineal por uno cuadrático. Para encontrar el resto de factores lineales, encuentra las raíces del cuadrático.
  5. Encuentra el residuo de dividir el polinomio $x^5-x^4+x^3-x^2+x-1$ entre el polinomio $x-2$.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»