Archivo de la etiqueta: divisibilidad

Álgebra Superior II: Algoritmo de la división en los enteros

Deja un comentario

Introducción

Gracias a todo lo trabajado con anterioridad y en particular a la entrada anterior de inmersión de los naturales en los enteros, ya podemos pensar al conjunto de enteros como el conjunto $\mathbb{Z}=\{\ldots,-2,-1,0,1,2,\ldots\}$. Además, dentro de esta estructura tenemos operaciones de suma, resta y producto. Sin embargo, aún no tenemos una operación de «división». Hay dos caminos que podemos seguir. Uno es algo parecido a lo que hicimos para tener una operación de resta: podemos construir ciertas clases de equivalencia sobre parejas de enteros, definir operaciones, orden, etcétera. Esto es lo que se hace para construir el conjunto $\mathbb{Q}$ de números racionales, del cual hablaremos más adelante. Otro camino es quedarnos en $\mathbb{Z}$ e intentar decir todo lo que podamos, aunque no tengamos una operación de división. Eso es lo que haremos ahora.

Por ejemplo, si tenemos los números $-20$ y $5$, entonces sí «podemos hacer la división» de manera exacta. Dicho de otra forma, sí existe un entero $k$ tal que $-20=5k$. Ese entero es $k=-4$. Sin embargo, si tenemos los números $20$ y $3$ no podemos hacer la división, en el sentido de que no existe un entero $k$ tal que $20=3k$. Sin embargo, sí podemos lograr que $3k$ quede muy cerca de $20$. Por ejemplo, podemos escribir $20=3\cdot 6 + 2$, es decir, el $20$ se queda únicamente a dos unidades de tres veces un entero.

En esta entrada hablaremos del algoritmo de la división. Lo que nos dice es que dados dos enteros $a$ y $b$, siempre sucederá que $a$ puede ser escrito como $b$ veces un entero, más un residuo «pequeño» en términos de $b$. También nos dice que esta forma de escribir a $a$ será única.

La intuición del algoritmo de la división

Lo que nos permite hacer el algoritmo de la división es saber «cuántas veces cabe un entero en otro». En general, vamos a poder escribir $a=qb+r$ y esto querrá decir que «$b$ cabe $q$ veces en $a$ y sobran $r$». Lo que nos gustaría es hacer esto de manera que sobre lo menos posible.

Un ejemplo sencillo sería el siguiente. Tomemos $a=7$ y $b=2$. Si nos preguntáramos: ¿cuántos equipos de $2$ personas se necesitan para repartir a $7$ personas?, una posible respuesta sería: podemos formar $2$ equipos de dos personas cada uno y dejar fuera a $3$ personas. Esto se escribiría como $7=2\cdot 2 + 3$. Sin embargo, una mejor respuesta (y la que deja a menos personas fuera) es la siguiente: podemos formar $3$ equipos de dos personas cada uno, y dejar a alguien fuera. Esto corresponde algebraicamente a la igualdad $7=3\cdot 2 + 1$. Esta forma de escribir al $7$ es mejor pues el residuo es más pequeño.

Hay algunos casos que suenan un poco raros. Por ejemplo, tomemos $a = 2$, $b = 3$. Podría parecer que la división de $2$ entre $3$ da cero pues «el $3$ el mayor que el $2$ y no hay modo de que $3$ quepa en $2$». Esto es cierto: $3$ cabe cero veces en $2$. Pero hay un residuo que no se ha mencionado, que en este caso es $2$. La forma de escribir esto algebraicamente será $2=3\cdot 0 + 2$. Aquí el $0$ quiere decir que «el $3$ cabe cero veces en el $2$» y el $2$ de la derecha quiere decir que «sobran $2$». Si lo pensamos como equipos, no nos alcanzaría para crear ni un sólo equipo de $3$ personas teniendo sólo $2$.

Otro caso extraño es cuando tenemos números negativos. Por ejemplo, si $a=-7$ y $b=3$ entonces la forma en la que queremos expresar a $a$ es como sigue: $-7=(-3)\cdot 3 + 2$. Lo hacemos de esta manera pues siempre querremos que el residuo que queda sea positivo. Y de entre los residuos que se pueden obtener, lo mejor es que sobren únicamente $2$.

Resulta que la cantidad que sobra siempre se puede garantizar que sea «chica». Si estamos repartiendo $a$ en cachos de tamaño $b$, siempre podremos garantizar que lo que sobra esté entre $0$ y $|b|-1$. En símbolos, el algoritmo de la división dice que dados $a, b \in \mathbb{Z}$, con $b\neq 0$, es posible encontrar $q$ y $r$ únicos, tales que $a = bq + r,$ con $0 \leq r < |b|$. A $q$ se le llama el cociente y a $r$ le llamamos el residuo.

Que no espante el valor absoluto que se le añade a la $b$. Aún no hemos definido qué es, pero lo explicaremos un poco más abajo. Sin embargo, antes de enunciar y demostrar el teorema daremos un ejemplo con números un poco más grandes y su intuición numérica.

Otro ejemplo para entender el algoritmo de la división en $\mathbb{Z}$

Comencemos planteando el problema para $a=3531$ y $b=8$. Es decir, queremos encontrar $q$ y $r$ enteros tales que $3531 = 8q + r$, donde además $0 \leq r < 8$. Ya que $r$ debe ser un número muy pequeño entre $0$ y $8$, podemos ir dando valores a $r$ hasta que $3531-r$ se pueda escribir como $8$ veces un entero.

Si $r = 0$, habríamos de verificar si $3531$ se puede escribir como $8$ veces un entero. Nuestra intuición nos dice que esto no debería poderse, pues $3531$ es un número impar, pero $8$ veces un entero siempre será un número par.

Si $r = 1$, entonces querríamos ver si $8q = 3530$. Pero esto tampoco se puede pues con $q=441$ tenemos $8q=3528<3530$ y con $q=442$ tenemos $8q=3536>3530$ y entonces ya se pasa. Si $r = 2$, buscaríamos si $8q = 3529$, pero de nuevo este es un número impar.

Finalmente, si $r = 3$, entonces queremos ver si se puede lograr $3528= 8q$. Esto sí se puede: se toma $q=441$. Así, hemos logrado determinar que con $q = 441$, $r = 3$ se cumple que $3531 = 8q + r$, con lo que terminamos el problema.

Geométricamente, esto significa que $3531$, en la recta de los números enteros, estará situado entre números que sean $8$ veces un entero, a saber, $8\cdot 441$ y $8\cdot 442$:

$$ \ldots < 8\cdot 441 < 3531 < 8\cdot 442 < \ldots \text{.}$$

Más precisamente, como $3531$ es un entero positivo, el problema consistió en encontrar el entero que sea $8$ veces un entero más cercano por la izquierda y añadir $3$ unidades. Esto también lo podemos enunciar como que «$3531$ está a $3$ unidades a la derecha de un número que es $8$ veces un entero»:

$$ 8\cdot 441 < 8\cdot 441 + 1 < 8\cdot 441 +2 < 3531 < 8\cdot 441 +4 < 8\cdot 441 +5 < 8\cdot 441 +6 < 8\cdot 441 +7 < 8\cdot 442 \text{.}$$

En realidad esto funciona sin importar los valores de $a$ y $b$. Dado un entero $b$, podemos poner los enteros de la forma $mb$ en la recta numérica y siempre podremos situar al entero $a$ entre dos de ellos:

$$qb \leq a < (q+1)b, \qquad q\in \mathbb{Z}.$$

Si $b>0$, los múltiplos de $b$ en la recta numérica se verían así:

$$\ldots -4b, -3b, -2b, -b, 0, b, 2b, 3b, 4b, \ldots $$

De este modo, $q$ sería el mayor múltiplo de $b$ más cercano a $a$, sin excederse de $a$.

Enunciado y demostración del algoritmo de la división en $\mathbb{Z}$

Para poder enunciar el algoritmo de la división sin importar el signo de $a$ y $b$, debemos introducir un símbolo adicional.

Definición. Si $b \in \mathbb{Z}$, definimos el valor absoluto de $b$, denotado por $|b|$, como sigue: $$|b| = \left\lbrace \begin{matrix} b & \text{si $b\geq 0$}\\ -b & \text{si $ b < 0$} \end{matrix}\right.$$

En el algoritmo de la división nos darán dos números enteros $a$ y $b$. Para la restricción $0 \leq r \leq |b|$, sucederá que, no importa si $b$ sea un número positivo o negativo, nosotros nos fijaremos en el número siempre positivo que resulta de aplicarle valor absoluto a $b$. El resultado dice lo siguiente.

Teorema. Sean $a$ y $b$ en $\mathbb{Z}$ con $b\neq 0$. Entonces existen únicos enteros $q$ y $r$ enteros únicos tales que $$ a = qb + r$$ y $0 \leq r < |b|$.

Para la demostración del algoritmo de la división, necesitaremos el principio del buen orden. Como recordatorio, dice que todo subconjunto no vacío de $\mathbb{N}$ tiene un elemento mínimo.

Demostración. Primero hay que demostrar que siempre existen $q$ y $r$ enteros que satisfacen las condiciones que queremos. Vamos a suponer que $b>0$. El caso $b<0$ es muy parecido y quedará como tarea moral.

Lo que haremos es considerar al conjunto $S$ de todos los elementos de la forma $a-tb$ en donde $t$ es un entero, y tales que sean mayores o iguales a cero. Primero veremos que $S$ en efecto es un conjunto no vacío.

  • Si $a\geq 0$, tomamos $t=0$ y obtenemos la expresión $a-tb=a\geq 0$.
  • Si $a<0$, tomamos $t=a$ y obtenemos $a-tb=a-ab=a(1-b)$. Como $b>0$, entonces $b\geq 1$ y por lo tanto $(1-b)\leq 0$. Como $a<0$, obtenemos $a(1-b)\geq 0$, como queríamos.

Como $S$ es un conjunto no vacío de naturales, debe tener un elemento mínimo, al que le llamaremos $r$. Como $r$ está en $S$, obtenemos que $r=a-qb$ para algún entero $q$. Esto es un buen primer paso, pues nos muestra que $a=qb+r$. Sin embargo, todavía nos falta demostrar la importante desigualdad $0\leq r < |b|$. Como $b>0$, debemos mostrar $0\leq r < b$. Como $r$ está en $S$, obtenemos de manera inmediata que $r\geq 0$.

Sólo nos falta mostrar que $r<b$. Supongamos, con el fin de encontrar una contradicción, que $r\geq b$. Si este fuera el caso, sucedería que $r-b\geq 0$ además tendríamos la siguiente cadena de igualdades: $$r-b=a-tb-b=a-(t+1)b.$$

Esto lo que nos diría es que $r-b$ también está en $S$. ¡Pero eso es una contradicción!. Por construcción, $r$ era el menor elemento de $S$ y $r-b$ es un número menor que $r$ y que también está en $S$. Esta contradicción salió de suponer que $r\geq b$, así que en realidad debe pasar $r<b$, como queríamos.

Con esto queda demostrada la existencia de los enteros $q$ y $r$, tales que $a = bq + r$, con $0 \leq r < b$. Falta ver la unicidad. Supongamos que existen $q’$ y $r’$ enteros que también cumplen $$a = bq’ + r’$$ con $0\leq r’ < b$.

Demostramos primero que $r = r’$. Al hacer la resta $r-r’$ por un lado notamos que como mucho, puede valer $(b-1)-0=b-1$, lo cual pasa cuando $r=b-1$ y $r’=0$. Así mismo, por lo menos debe valer $0-(b-1)=-b+1$, lo cual sucede cuando $r=0$ y $r’=b-1$. Pero esta resta también se puede escribir de la siguiente manera: $$r-r’=(a-qb)-(a-q’b)=(q’-q)b.$

El único número de la forma $bk$ en $\{-b+1,-b+2,\ldots,0,\ldots,b-2,b-2\}$ es el entero $0$, pues justo no alcanza para llegar a $b$ ni a $-b$. De esta forma, $r-r’=0$, es decir $r=r’$. Y de aquí, obtenemos que $(q’-q)b=r-r’=0$. Como $b\neq 0$, obtenemos $q’-q=0$ y por lo tanto $q’=q$. Esto termina la demostración de la unicidad.

$\square$

Quizás el uso del principio del buen orden de la impresión de que la demostración anterior es «muy sofisiticada». En realidad, esto no es así. Simplemente es la forma en la que se formaliza una idea muy intuitiva: si el residuo queda mayor a $b$, entonces todavía le podemos «transferir» un sumando $b$ de $r$ a $qb$. El principio del buen orden simplemente nos garantiza que en algún momento este proceso de «transferir» sumandos $b$ debe de concluir.

Tarea moral

  1. Encuentra $q$ y $r$ enteros tales que $-1873 = 31q + r$ y $0\leq r < 31$.
  2. Demuestra las siguientes propiedades de la función valor absoluto de $\mathbb{Z}$:
    • $|a|\geq 0$ para cualquier entero $a$.
    • $|ab|=|a||b|$ para cualesquiera enteros $a$ y $b$.
    • $|a+b|\leq |a|+|b|$ para cualesquiera enteros $a$ y $b$.
  3. En general, ¿cómo se calcula $q$, para $a<0$? ¿y para $b<0$? Completa los detalles de la demostración del algoritmo de la división para cuando $b<0$.
  4. Encuentra un número que al dividirse entre $2$ deje residuo $1$, que al dividirse entre $3$ deje residuo $2$ y que al dividirse entre $4$ deje residuo $3$.
  5. Demuestra que cualquier entero se puede escribir de la forma $3q+r$ en donde $r$ es $-1$, $0$ ó $1$.

Más adelante…

Cuando aplicamos el algoritmo de la división nos puede pasar un caso muy especial: que $r$ sea igual a cero. En otras palabras, en este caso podemos escribir $a=qb$ y por lo tanto $b$ cabe en $a$ «de manera exacta». Este caso es muy interesante y amerita un profundo estudio. Cuando esto sucede, decimos que $a$ es múltiplo de $b$, o bien que $b$ divide a $a$. En la siguiente entrada estudiaremos con más detalle la relación de divisibilidad en $\mathbb{Z}$. Un poco más adelante hablaremos de los ideales de $\mathbb{Z}$, que son un tipo de subconjuntos fuertemente relacionados con la noción de divisibilidad.

Entradas relacionadas

Álgebra Superior II: El criterio de la raíz racional para polinomios de coeficientes enteros

Deja un comentario

Introducción

En esta entrada veremos el criterio de la raíz racional. Este es un método que nos permite determinar las únicas raíces racionales que puede tener un polinomio con coeficientes enteros. Es una más de las herramientas que podemos usar cuando estamos estudiando polinomios en $\mathbb{R}[x]$.

Si encontramos una raíz con este método, luego podemos encontrar su multiplicidad mediante el teorema de derivadas y multiplicidad. Esto puede ayudarnos a factorizar el polinomio. Otras herramientas que hemos visto que nos pueden ayudar son el algoritmo de Euclides, la fórmula cuadrática, el teorema del factor y propiedades de continuidad y diferenciabilidad de polinomios.

El criterio de la raíz racional

Si un polinomio $p(x)$ en $\mathbb{R}[x]$ cumple que todos sus coeficientes son números enteros, entonces decimos que es un polinomio sobre los enteros. Al conjunto de polinomios sobre los enteros se le denota $\mathbb{Z}[x]$.

Teorema (criterio de la raíz racional). Tomemos un polinomio $p(x)$ en $\mathbb{Z}[x]$ de la forma $$p(x)=a_0+a_1x+\ldots+a_nx^n.$$ Supongamos que el número $\frac{p}{q}$ es número racional simplificado, es decir con $p$ y $q\neq 0$ enteros primos relativos. Si $\frac{p}{q}$ es raíz de $p(x)$, entonces $p$ divide a $a_0$, y $q$ divide a $a_n$.

Demostración. Por definición, si $\frac{p}{q}$ es una raíz, tenemos que $$0=a_0+a_1\cdot \frac{p}{q} + \ldots + a_n \cdot \frac{p^n}{q^n}.$$

Multiplicando ambos lados de esta igualdad por $q^n$, tenemos que

$$0=a_0q^n+a_1pq^{n-1}+\ldots+a_{n-1}p^{n-1}q+a_np^n.$$

Despejando $a_0q^n$, tenemos que

\begin{align*}
a_0q^n&=-(a_1pq^{n-1}+\ldots+a_{n-1}p^{n-1}q+a_np^n)\\
&=-p(a_1q^{n-1}+\ldots+a_{n-1}p^{n-2}q+a_np^{n-1})
\end{align*}

Esto muestra que $a_0q^n$ es múltiplo de $p$. Pero como $\MCD{p,q}=1$, tenemos que $p$ debe dividir a $a_0$.

De manera similar, tenemos que

\begin{align*}
a_np^n&=-(a_0q^n+a_1pq^{n-1}+\ldots+a_{n-1}p^{n-1}q)\\
&=-q(a_0q^{n-1}+a_1pq^{n-2}+\ldots+a_{n-1}p^{n-1}).
\end{align*}

De aquí, $q$ divide a $a_np^n$, y como $\MCD{p,q}=1$, entonces $q$ divide a $a_n$.

$\square$

Como cualquier natural tiene una cantidad finita de divisores, el criterio de la raíz racional nos permite restringir la cantidad posible de raíces de un polinomio con coeficientes enteros a una cantidad finita de candidatos. Veamos un par de ejemplos.

Aplicación directa del criterio de la raíz racional

Ejercicio. Usa el criterio de la raíz racional para enlistar a todos los posibles números racionales que son candidatos a ser raíces del polinomio $$h(x)=2x^3-x^2+12x-6.$$ Después, encuentra las raíces racionales de $p(x)$.

Solución. El polinomio $h(x)$ tiene coeficientes enteros, así que podemos usar el criterio de la raíz racional. Las raíces racionales son de la forma $\frac{p}{q}$ con $p$ divisor de $-6$, con $q$ divisor de $2$ y además $\MCD{p,q}=1$. Los divisores enteros de $-6$ son $$-6,-3,-2,-1,1,2,3,6.$$ Los divisores enteros de $2$ son $$-2,-1,1,2.$$

Pareciera que hay muchas posibilidades por considerar. Sin embargo, nota que basta ponerle el signo menos a uno de $p$ o $q$ para considerar todos los casos. Así, sin pérdida de generalidad, $q>0$. Si $q=1$, obtenemos a los candidatos $$-6,-3,-2,-1,1,2,3,6.$$ Si $q=2$, por la condición de primos relativos basta usar los valores $-3,-1,1,3$ para $p$. De aquí, obtenemos al resto de los candidatos $$-\frac{3}{2},-\frac{1}{2},\frac{1}{2},\frac{3}{2}.$$

En el peor de los casos, ya solo bastaría evaluar el polinomio en estos $12$ candidatos para determinar si son o no son raíz. Sin embargo, a veces podemos hacer algunos trucos para disminuir todavía más la lista.

Observa que si evaluamos $$h(x)=2x^3-x^2+12x-6$$ en un número negativo, entonces la expresión quedará estrictamente negativa, así que ninguno de los candidatos negativos puede ser raíz. De este modo, sólo nos quedan los candidatos $$1,2,3,6,\frac{1}{2},\frac{3}{2}.$$

Si evaluamos en $x=2$ o $x=6$, entonces la parte de la expresión $2x^3-x^2+12x$ es múltiplo de $4$, pero $-6$ no. De esta forma, $h(x)$ no sería un múltiplo de $4$, y por lo tanto no puede ser $0$. Si evaluamos en $x=1$ o $x=3$, tendríamos que la parte de la expresión $2x^3+12x-6$ sería par, pero $-x^2$ sería impar, de modo que $h(x)$ sería impar, y no podría ser cero. Así, ya sólo nos quedan los candidatos $$\frac{1}{2},\frac{3}{2}.$$

Para ellos ya no hagamos trucos, y evaluemos directamente. Tenemos que
\begin{align*}
h\left(\frac{1}{2}\right) &= 2\cdot \frac{1}{8} – \frac{1}{4} + 12 \cdot \frac{1}{2}-6\\
&=\frac{1}{4}-\frac{1}{4}+6-6\\
&=0.
\end{align*}

y que
\begin{align*}
h\left(\frac{3}{2}\right) &= 2\cdot \frac{27}{8} – \frac{9}{4} + 12 \cdot \frac{3}{2}-6\\
&=\frac{27}{4}-\frac{9}{4}+18-6\\
&=\frac{9}{2}+12\\
&=\frac{33}{2}.
\end{align*}

Habiendo considerado todos los casos, llegamos a que la única raíz racional de $h(x)$ es $\frac{1}{2}$.

$\square$

Aplicación indirecta del criterio de la raíz racional

El criterio de la raíz racional lo podemos usar en algunos problemas, aunque en ellos no esté escrito un polinomio de manera explícita.

Problema. Muestra que $\sqrt[7]{13}$ no es un número racional.

Solución. Por definición, el número $\sqrt[7]{13}$ es el único real positivo $r$ que cumple que $r^7=13$. Se puede mostrar su existencia usando que la función $f:\mathbb{R}\to\mathbb{R}$ dada por $f(x)=x^7$ es continua, que $f(0)=0$, que $f(2)=128$, y aplicando el teorema del valor intermedio. Se puede mostrar su unicidad mostrando que la función $f$ es estrictamente creciente en los reales positivos. Lo que tenemos que mostrar es que este número real no es racional.

Si consideramos el polinomio $p(x)=x^7-13$, tenemos que $p(r)=r^7-13=0$, de modo que $r$ es raíz de $p(x)$. Así, para terminar el problema, basta mostrar que $p(x)$ no tiene raíces racionales.

El polinomio $p(x)$ tiene coeficientes enteros, así que podemos aplicarle el criterio de la raíz racional. Una raíz racional tiene que ser de la forma $\frac{p}{q}$ con $p$ divisor de $-13$ y $q$ divisor de $1$.

Sin perder generalidad, $q>0$, así que $q=1$. De esta forma, los únicos candidatos a ser raíces racionales de $p(x)$ son $-13,-1,1,13$. Sin embargo, una verificación de cada una de estas posibilidades muestra que ninguna de ellas es raíz de $p(x)$. Por lo tanto, $p(x)$ no tiene raíces racionales, lo cual termina la solución del problema.

$\square$

Aplicación en polinomio con coeficientes racionales

A veces un polinomio tiene coeficientes racionales, por ejemplo, $$r(x)=\frac{x^3}{2}+\frac{x^2}{3}-4x-1.$$

A un polinomio con todos sus coeficientes en $\mathbb{Q}$ se les conoce como polinomio sobre los racionales y al conjunto de todos ellos se le denota $\mathbb{Q}[x]$. Para fines de encontrar raíces racionales, los polinomios en $\mathbb{Q}[x]$ y los polinomios en $\mathbb{Z}[x]$ son muy parecidos.

Si tenemos un polinomio $q(x)$ en $\mathbb{Q}[x]$, basta con multiplicar por el mínimo común múltiplo de los denominadores de los coeficientes para obtener un polinomio $p(x)$ con coeficientes enteros. Como $q(x)$ y $p(x)$ varían sólo por un factor no cero, entonces tienen las mismas raíces. Por ejemplo, el polinomio $r(x)$ de arriba tiene las mismas raíces que el polinomio $$s(x)=6r(x)=3x^3+2x^2-24x-6.$$ A este nuevo polinomio se le puede aplicar el criterio de la raíz racional para encontrar todas sus raíces racionales.

Ejemplo. Consideremos el polinomio $$q(x)=x^3+\frac{x^2}{3}+5x+\frac{5}{3}.$$ Vamos a encontrar todos los candidatos a raíces racionales. Para ello, notamos que $q(x)$ y $p(x):=3q(x)$ varían sólo por un factor multiplicativo no nulo y por lo tanto tienen las mismas raíces. El polinomio $$p(x)=3x^3+x^2+15x+5$$ tiene coeficientes enteros, así que los candidatos a raíces racionales son de la forma $\frac{a}{b}$ con $a$ y $b$ primos relativos, $a\mid 5$ y $b\mid 3$. Sin pérdida de generalidad $b>0$.

Los divisores de $5$ son $-5,-1,1,5$. Los divisores positivos de $3$ son $1$ y $3$. De esta forma, los candidatos a raíces racionales son $$-5,-1,1,5,-\frac{5}{3},-\frac{1}{3},\frac{1}{3},\frac{5}{3}.$$

Si ponemos un número positivo en $p(x)$, como sus coeficientes son todos positivos, tenemos que la evaluación sería positiva, así que podemos descartar estos casos. Sólo nos quedan los candidatos $$-5,-1,-\frac{5}{3},-\frac{1}{3}.$$

La evaluación en $-5$ da
\begin{align*}
-3\cdot 125 + 25 – 15\cdot 5 +5&=-375+25-75+5\\
&=-295,
\end{align*}

así que $-5$ no es raíz.

La evaluación en $-1$ da
\begin{align*}
-3+1-15+5=-12,
\end{align*}

así que $-1$ tampoco es raíz.

Como tarea moral, queda verificar que $-\frac{5}{3}$ tampoco es raíz, pero que $-\frac{1}{3}$ sí lo es.

$\square$

Tarea moral

  • Realiza las evaluaciones que faltan en el último ejemplo.
  • Determina las raíces racionales del polinomio $$x^7-6x^4+3x^3+18x-1.$$
  • Muestra que $\sqrt[3]{12}$ no es un número racional.
  • Encuentra todos los candidatos a ser raíces racionales de $$x^3+\frac{2x^2}{3}-7x-\frac{14}{3}.$$ Determina cuáles sí son raíces.
  • Puede que un polinomio en $\mathbb{Z}[x]$ no tenga raíces racionales, pero que sí se pueda factorizar en $\mathbb{Z}[x]$. Investiga acerca del criterio de irreducibilidad de Eisenstein.

Más adelante

Hemos visto como podemos encontrar algunas raíces de los polinomios con coeficientes en $\mathbb{Q}$, esta herramienta es extremadamente fuerte, porque aún encontrando solo una raíz para el polinomios, usando el teorema del factor, podemos cambiar nuestro polinomio por uno de al menos un grado menor.

La importancia de disminuir el grado de un polinomio, es que si logramos reducirlo a un polinomio de grado cuatro, entonces podremos encontrar todas las raíces, aunque estas pueden ser un poco complicadas.

El justificar la aseveración anterior, requiere esfuerzo, y será nuestra siguiente tarea, dar todas las soluciones a cualquier polinomio de grado menor o igual $4$.

Por lo mientras, para practicar los temas vistos, en la siguiente sección repasaremos algunos ejercicios para familiarizarnos con las técnicas que hemos visto.

Entradas Relacionadas

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

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.

$\square$

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. 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).$$

$\square$

Ejemplo. 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)$.

$\square$

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é.

$\square$

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).$$

$\square$

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$

Tarea moral

  • Muestra que el polinomio $x$ no tiene inverso multiplicativo.
  • Demuestra la parte de unicidad del algoritmo de la división.
  • 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$.
  • 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.
  • Encuentra el residuo de dividir el polinomio $x^5-x^4+x^3-x^2+x-1$ entre el polinomio $x-2$.

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.

Entradas Relacionadas

Álgebra Superior II: Problemas de sistemas de congruencias y teorema chino del residuo

Deja un comentario

Un ejercicio de dos ecuaciones lineales:

Resolver un sistema de dos ecuaciones lineales

Un ejercicio distinto de dos ecuaciones lineales:

Resolver un sistema de dos ecuaciones lineales

Un ejercicio de resolver un sistema de 3 ecuaciones lineales:

Resolviendo un sistema de tres ecuaciones lineales

Álgebra Superior II: Teoremas de Fermat y de Wilson

Deja un comentario

Introducción

En las entradas anteriores hablamos de congruencias, del anillo de enteros módulo $n$ y vimos algunos problemas. La gran ventaja de trabajar en $\mathbb{Z}_n$, o bien, de trabajar módulo $n$, es que para $n$ pequeña hay una cantidad pequeña de elementos y entonces las operaciones se vuelven muy sencillas.

Problema. Determina cuál es el residuo obtenido de dividir $705\cdot 702+714\cdot 711$ al dividirse entre $7$.

Solución. Tenemos que $705$, $702$, $714$ y $711$ los podemos poner como un múltiplo de $7$ más un residuo como sigue: $700+5$, $700+2$ y $714=714+0$, $711=707+4$. Así, $705\equiv 5\pmod 7$, $702\equiv 2 \pmod 7$, $714\equiv 0 \pmod 7$ y $711\equiv 4 \pmod 7$. Así, trabajando módulo $7$ tenemos que:

\begin{align*}
705\cdot 702+714\cdot 711 \equiv 5\cdot 2 + 0\cdot 4 \equiv 10 + 0 \equiv 10 \equiv 3 \pmod 7
\end{align*}
De esta forma, $705\cdot 702+714\cdot 711$ deja residuo $3$ al dividirse entre $7$.

$\square$

Trabajando de esta forma, podemos encontrar el residuo al dividirse por $n$ de expresiones que involucran sumas y productos. El objetivo de esta entrada es entender qué sucede cuando queremos encontrar el residuo de expresiones que tienen potencias y factoriales.

Pequeño teorema de Fermat

Intentemos entender qué sucede con las potencias de un número $a$ en cierto módulo $n$.

Ejemplo. Imagina que tomamos al número $3$ y queremos elevarlo a distintas potencias y entender el residuo que deja al dividirse entre $7$. Tenemos, trabajando módulo $7$:
\begin{align*}
3^0\equiv 1\\
3^1\equiv 3\\
3^2\equiv 9 \equiv 2\\
3^3=27\equiv 21+6\equiv 6
\end{align*}

Nota que podríamos seguir, poniendo $3^4=81$. Pero podemos ahorrarnos trabajo pues $3^4\equiv 3\cdot 3^3 \equiv 3 \cdot 6 \equiv 18\equiv 4$, en donde usamos que ya sabíamos que $3^3\equiv 6$. Del mismo modo, podemos seguir substituyendo cada potencia en la siguiente para obtener
\begin{align*}
3^5\equiv 3\cdot 4\equiv 12\equiv 5\\
3^6\equiv 3\cdot 5 = 15\equiv 1\\
3^7\equiv 3\cdot 1 = 3\\
3^8\equiv 3\cdot 3 = 9 \equiv 2
\end{align*}

Podríamos seguir y seguir, pero ya no tiene mucho caso. A partir de aquí es fácil convencerse de que los residuos se ciclan: $1,3,2,6,4,5,1,3,2,6,4,5,1\ldots$. Notemos que si la potencia es múltiplo de $6$, entonces el residuo será $1$, es decir, $3^{6k}\equiv 1 \pmod 7$. Esto es fantástico, pues entonces si queremos determinar el residuo de dividir, digamos, $3^{605}$ entre $7$, basta ver que módulo $7$ tenemos $$3^{605}=3^{600}\cdot 3^5 \equiv 1\cdot 5 \equiv 5,$$

en donde estamos usando lo que mencionamos para $k=100$ y que ya hicimos $3^5$ módulo $7$.

A partir del ejemplo anterior, nos damos cuenta de que es importante saber cuándo $a^m\equiv 1\pmod n$, pues en ese momento las potencias «se empiezan a ciclar». El pequeño teorema de Fermat es un resultado que podemos aplicar cuando trabajamos módulo un número primo $p$. Dice que la potencia $p-1$ funciona para esto.

Teorema. Si $p$ es un número primo y $p$ no divide a $a$, entonces $p$ divide a $a^{p-1}-1$ o, dicho en otras palabras $a^{p-1}\equiv 1 \pmod p$.

Demostración. Afirmamos que los números $a$, $2a$, $3a$, $\ldots$, $(p-1)a$ dejan todos ellos residuos distintos al dividirse entre $p$ y, además, que ninguno de esos residuos es $0$. Probemos esto. Tomemos $0<i<j<p-1$. En una entrada anterior vimos que $[a]_p$ tiene inverso en $Z_p$. Sea $[b]_p$ su inverso. Si $[ia]_p=[ja]_p$, entonces multiplicando por $[b]_p$ de ambos lados tendríamos $$[i]_p=[i(ab)]_p=[j(ab)]_p=[j]_p.$$

Pero como $i$ y $j$ están entre $1$ y $p-1$, esto implica que $i=j$. Ninguno es cero pues si $[ia]_p=[0]_p$, entonces al multiplicar por $b$ tendríamos la contradicción $[i]_p=[i(ab)]_p=[0b]_p=[0]_p$. Esto muestra la afirmación.

Así, usando la afirmación en el segundo paso de la siguiente cadena módulo $p$, tenemos:
\begin{align*}
(p-1)! a^{p-1} &= (a)(2a)(3a)\cdots((p-1)a)\\
&\equiv 1\cdot 2 \cdot \ldots \cdot (p-1)\\
&= (p-1)!.
\end{align*}

El número $(p-1)!$ no es divisible entre $p$, pues es producto de puros números menores que $p$, de modo que $\text{MCD}(p, (p-1)!)=1$, así que tiene inverso módulo $p$, de modo que podemos cancelarlo de la congruencia anterior multiplicando en ambos lados por su inverso. De aquí obtenemos la igualdad que queremos: $$a^{p-1}\equiv 1 \pmod p.$$

$\square$

Ya que demostramos este teorema, podemos aprovecharlo para resolver problemas que parecen ser difíciles.

Problema. Demuestra que $13$ divide a $25^{181}-181^{25}$

Solución. Notemos primero que $13$ es primo y que no divide ni a $25$ ni a $181$. Por el pequeño teorema de Fermat, tenemos módulo $13$ que $25^{12}\equiv 1$ y que $181^{12}\equiv 1$. Así, módulo $13$ tenemos que $$25^{181}\equiv 25^{15\cdot 12}\cdot 25 \equiv 25 \equiv 12,$$ y que $$181^{25}\equiv 181^{2\cdot 12}\cdot 181\equiv 181 \equiv 12.$$

De esta forma, $25^{181}-181^{25}\equiv 12-12\equiv 0\pmod {13}$, es decir, $13$ divide a $25^{181}-181^{25}$

$\square$

Teorema de Wilson

En la demostración del teorema de Fermat aparece la expresión $(p-1)!$. ¿Qué residuo dejará al dividirse entre $p$? Hagamos una prueba.

Problema. Encuentra el residuo que se obtiene al dividir $10!$ entre $11$.

Solución. Para no trabajar con números tan grandes, notemos que en $$10!=1\cdot 2\cdot 3\cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10$$ podemos cambiar a $6,7,8,9,10$ por $-5, -4, -3, -2, -1$ al trabajar módulo $11$, así que basta encontrar $-(1\cdot 2\cdot 3 \cdot 4 \cdot 5)^2$ módulo $11$. Notemos que $3\cdot 4\equiv 12 \equiv 1 \pmod {11}$ y que $2\cdot 5 =10 \equiv -1 \pmod {11}$. Así, $$10!\equiv -(1\cdot 2\cdot 3 \cdot 4 \cdot 5)^2 \equiv -(1\cdot 1 \cdot -1)^2 \equiv -1 \equiv 10 \pmod {11},$$

es decir, el residuo que deja $10!$ al dividirse entre $11$ es $10$.

$\square$

El teorema de Wilson ayuda a cuando queremos encontrar el residuo de un factorial al dividirse entre un número primo. Una de las ideas del ejercicio anterior fue buena: nos conviene agrupar a números del factorial en productos sencillos. Lo más conveniente es que agrupemos a cada número con su inverso multiplicativo, pues así obtendremos un $1$. Eso lo podemos hacer si el inverso es diferente. La siguiente proposición nos ayuda a entender cuándo pasa esto.

Proposición. Sea $p$ un número primo. Los únicos elementos en $\mathbb{Z}_p$ que son inversos de sí mismos son $[1]_p$ y $[p-1]_p$.

Demostración. Claramente $[1]_p$ y $[p-1]_p=[-1]_p$ son inversos multiplicativos de sí mismos, pues $1\cdot 1=1=(-1)\cdot(-1)$. Ahora, si tenemos $a$ tal que $a$ es inverso multiplicativo de sí mismo, tenemos que $[a^2]_p\equiv [1]_p$, que por definición quiere decir que $p$ divide a $a^2-1=(a+1)(a-1)$. Cuando un primo divide a un producto, tiene que dividir a uno de los factores. Entonces $p$ divide a $a+1$ o a $a-1$, y obtenemos, respectivamente, que $[a]_p=[-1]_p=[p-1]_p$ o que $[a]_p=[1]_p$, como queríamos.

$\square$

Estamos listos para enunciar y demostrar el teorema de Wilson.

Teorema. Si $p$ es un número primo, entonces $p$ divide a $(p-1)!+1$ o, dicho en otras palabras, $(p-1)!\equiv -1 \pmod p$.

Demostración. Si $p=2$, el resultado es inmediato. Supongamos que $p\geq 3$. En $(p-1)!$ aparecen todos los números de $1$ a $p-1$. Todos ellos son primos relativos con $p$, así que tienen inverso módulo $p$. Ese inverso también aparece en $(p-1)!$. Así, podemos agrupar esos números en $(p-3)/2$ parejas de inversos multiplicativos, en donde por la proposición anterior sólo nos va a sobrar el $1$ y el $-1$. De esta forma, $$(p-1)!\equiv (1)(-1)(1\cdot 1\cdot \ldots\cdot 1) \equiv -1 \pmod p,$$

en donde en la expresión intermedia tenemos un $1$, un $-1$ y $(p-3)/2$ unos, uno por cada pareja de inversos que se multiplicaron. Esto termina la prueba.

$\square$

Veamos una posible aplicación.

Problema. Determina el residuo que se obtiene al dividir $15!+16!+17!$ entre $17$.

Solución. Notemos que $17$ divide a $17!$, así que $17!\equiv 0 \pmod {17}$. Por el teorema de Wilson, $16!\equiv -1 \pmod {17}$. Podemos multiplicar esa igualdad por $-1$ para obtener módulo $17$ que $$15! = 15! (-1)(-1) \equiv 15! \cdot 16 \cdot (-1) \equiv 16! (-1)\equiv (-1)(-1)\equiv 1.$$ Así, $15!+16!+17!\equiv 1 + (-1) + 0 \equiv 0 \pmod {17}$.

$\square$

Una solución alternativa es darse cuenta de que $$15!+16!+17!=15!(1+16)+17\cdot 16!=17\cdot (15!+16!)$$ y por lo tanto es múltiplo de $17$. Aunque tengamos herramientas fuertes, ¡siempre hay que recordar los básicos!