Archivo de la etiqueta: anillo

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

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.

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 y 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

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 en qué sucede si se tiene

    \[f\mathbb{R}[x]=g\mathbb{R}[x],\]

o, dicho de otra forma, pensemos en 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], osea, 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.\]

\square

Tarea moral

Los siguientes ejercicios no forman parte de la evaluación del curso, pero te servirán para entender mucho mejor los conceptos vistos en esta entrada, así como temas posteriores.

  • 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.
  • 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.
  • Muestra que la intersección de dos ideales de \mathbb{R}[x] es un ideal de \mathbb{R}[x].
  • 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.
  • 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?

Álgebra Superior II: Problemas de operaciones con polinomios

Introducción

En una entrada anterior ya construimos el anillo de polinomios con coeficientes reales. Para hacer esto, tomamos las sucesiones que consisten casi de puros ceros, y les pusimos operaciones de suma y producto. Ahora repasaremos esto resolviendo algunos problemas de operaciones con polinomios.

Problema de suma de polinomios

Comenzamos con un ejemplo de suma de polinomios del libro de Álgebra Superior de Bravo, Rincón y Rincón.

Ejercicio 399. Haz la suma de los siguientes polinomios:

    \begin{align*}p(x)&=(-85,0,-37,-35, 97, 50, \overline{0})\\q(x)&=(56,49,0,57,\overline{0}).\end{align*}

En el video se hace la suma de dos formas distintas. Primero, se hace la suma directamente de la definición, es decir, sumando los polinomios entrada a entrada como sucesiones. Después, se hace la suma en la notación de x y potencias, que tal vez conozcas mejor.

Es importante entender que la notación de sucesiones sirve para establecer los fundamentos de los polinomios, pero no es práctica para hacer operaciones con polinomios concretas. Dependiendo del tipo de problema que se quiere resolver, a veces hay que usar una notación u otra.

Suma de polinomios

Problemas de producto de polinomios

A continuación se resuelven dos ejercicios de producto de polinomios.

Ejercicio. Multiplicar los polinomios (2,0,3,\overline{0}) y (0,1,\overline{0}).

En el video se hace la multiplicación usando directamente la definición, paso a paso. Sin embargo, los pasos para realizar la multiplicación se pueden realizar en una tabla, como la que usamos en entradas anteriores. Después del video ponemos la tabla correspondiente a la multiplicación.

Para hacer la multiplicación con una tabla, ponemos a las entradas del primer polinomio en la primer fila de una tabla, y a las del segundo polinomio en la primer columna de la tabla. Luego, hacemos las multiplicaciones «en cada casilla» como sigue:

\bm{2}\bm{0}\bm{3}
\bm{0}000
\bm{1}203

De aquí, se puede leer el producto «por diagonales». La primer diagonal es 0, la segunda 2+0=2, la tercera 0+0=0 y la cuarta 3. Concluimos que el polinomio es

    \[(0,2,0,3,\overline{0}).\]

Veamos un ejemplo más, usando la notación de x y sus potencias.

Ejercicio. Encuentra el producto de polinomios (1+3x)(1-2x+3x^2).

Problema de división de polinomios

Finalmente, hacemos un ejemplo de división de polinomios. La técnica que se hace en el video es la de «dividir con casita», que es una forma visual de representar el algoritmo de la división para polinomios. Hablaremos un poco más adelante de este algoritmo, y de por qué siempre nos da un residuo cero o de grado menor.

Cuando se hace la «división con casita», hay que recordar dejar los espacios correspondientes a los términos que tengan coeficiente 0.

Ejercicio. Divide el polinomio x^5+x^3+3x entre el polinomio x^2-x+1.

División de polinomios

Álgebra Superior II: Inmersión de R en R[x], grado y evaluación de polinomios

Introducción

En esta entrada comenzaremos mostrando que podemos usar «la notación de siempre» para los polinomios, usando un símbolo x y potencias. Después de eso, hablaremos del grado de un polinomio y de cómo se comporta con las operaciones que hemos definido. Finalmente, haremos una distinción importante entre los polinomios, y las funciones que inducen.

Como recordatorio, en la entrada anterior definimos a los polinomios y sus operaciones de suma y multiplicación. Para ello, construimos a los polinomios como sucesiones en las que casi todos los términos son 0. Vimos que bajo estas operaciones se obtiene un dominio entero, es decir, un anillo conmutativo con unidad multiplicativa en donde se vale la regla de cancelación.

Regresando a la notación con x y potencias

Ya dimos cimientos sólidos para construir al anillo de polinomios con coeficientes reales y sus operaciones. Es momento de regresar a la «notación usual» usando x y sus potencias, pues será más práctica en lo que viene.

Para empezar, notemos que a cada real r podemos asociarle el polinomio (r,\overline{0}). Esta es una asociación en la que las operaciones de suma y producto de \mathbb{R} se corresponden con con las de \mathbb{R}[x].

Observa además que tras esta asociación, el real 0 es el polinomio (\overline{0}) y el real 1 es el polinomio (1,\overline{0}), así que la asociación respeta los neutros de las operaciones. De manera similar se puede mostrar que la asociación respeta inversos aditivos y multiplicativos.

Por esta razón, para un real r podemos simplemente usar el símbolo r para el polinomio (r,\overline{0}), y todas las operaciones siguen siendo válidas. Para expresar a cualquier otro polinomio, nos bastará con introducir un símbolo más, y potencias.

Definición. Definimos x como el polinomio \{0,1,\overline{0}\}. Para cada natural n definimos x^n como el polinomio \{a_n\} tal que a_j=1 si j=n y a_j=0 para j\neq n.

Ejemplo. La definición de arriba implica x^0=1 y x^1=x. El polinomio x^3 es el polinomio

    \[(0,0,0,1,\overline{0}).\]

\square

Ejemplo. Hagamos la multiplicación de los polinomios x^2 y x^3. Estos son, por definición, (0,0,1,\overline{0}) y (0,0,0,1,\overline{0}). Hagamos esta multiplicación con el método de la tabla:

001
0000
0000
0000
1001
Multiplicación de x^2 y x^3.

El producto es el polinomio (0,0,0,0,0,1,\overline{0}), que por definición es el polinomio x^5.

\square

En general, para m y n enteros no negativos se tiene que x^mx^n = x^{m+n}, como puedes verificar de tarea moral.

Ya que tenemos al símbolo x y sus potencias, necesitaremos también agregar coeficientes para poder construir cualquier polinomio.

Definición. Dados un polinomio a:=\{a_n\} y un real r, definimos al polinomio ra como la sucesión

    \[ra:=\{ra_n\},\]

es decir, aquella obtenida de multiplicar cada elemento de a por r.

Ejemplo. Si tomamos al polinomio

    \[a=\left(0,\frac{1}{2},0,\frac{1}{3},\overline{0}\right)\]

y al real r=6, tenemos que

    \[6a=\left(0,3,0,2,\overline{0}\right).\]

Observa que 3x es el polinomio (0,3,\overline{0}), que 2x^3 es el polinomio (0,0,0,2,\overline{0}) y que la suma de los dos es precisamente el polinomio 6a, de modo que podemos escribir

    \[6a=3x+2x^3.\]

Si tomamos cualquier polinomio a y al real 0, tenemos que

    \[0a=\{0,0,0,0,\ldots\}=(\overline{0}),\]

es decir, 0a es el polinomio cero.

\square

La siguiente proposición es sencilla y su demostración queda como tarea moral.

Proposición. Para cualquier polinomio a=\{a_n\} en \mathbb{R}[x], los reales a_0,a_1,\ldots son los únicos reales tales que

    \[a=a_0+a_1x+a_2x^2+a_3x^3+\ldots.\]

Todo lo que hemos discutido en esta sección permite que ahora sí identifiquemos formalmente al polinomio

    \[(a_0, a_1, a_2, a_3, a_4, a_5, \ldots),\]

con la expresión

    \[a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+a_5x^5+\ldots\]

y que realicemos las operaciones en \mathbb{R}[x] «como siempre», es decir, sumando coeficientes de términos iguales y multiplicando mediante la distribución y reagrupamiento. Así, a partir de ahora ya no usaremos la notación de sucesiones y simplemente escribiremos a los polinomios con la notación de x y sus potencias. También, favoreceremos llamarles a los polinomios p(x),q(x),r(x),\ldots en vez de a,b,c,\ldots.

Ejercicio. Realiza la operación 6(\frac{1}{2}+x)(1+3x^2).

Solución. Por asociatividad, podemos hacer primero la primer multiplicación, que da 3+6x. Luego, multiplicamos este polinomio por el tercer término. Podemos usar las propiedades de anillo para distribuir y agrupar, o bien, podemos seguir usando el método de la tabla.

Cuando hacemos lo primero, queda

    \begin{align*}(3+6x)(1+3x^2)&=3+9x^2+6x+18x^3\\&=3+6x+9x^2+18x^3.\end{align*}

Si hacemos lo segundo, tendríamos que hacer la siguiente tabla (¡cuidado con dejar el cero correspondiente al término x del segundo factor!)

36
136
000
3918
Multiplicación de dos polinomios

Leyendo por diagonales, el resultado es

    \[3+6x+9x^2+18x^3,\]

tal y como calculamos con el primer método.

\square

Grado de polinomios

Vamos a definir «grado» para todo polinomio que no sea el polinomio 0. Es muy importante recordar que el polinomio 0 no tiene grado.

Definición. Un polinomio p(x) en \mathbb{R}[x] es de grado n si es de la forma

    \[p(x)=a_0+a_1x+\ldots+a_nx^n,\]

para reales a_0,\ldots,a_n y a_n\neq 0. Al grado de p(x) lo denotamos por \deg(p(x)).

Por la discusión de la sección anterior, el grado está bien definido. En términos de la sucesión correspondiente al polinomio, su grado es el mayor entero que sea subíndice de una entrada no cero.

Ejemplo. El grado del polinomio p(x)=3 es 0. De hecho, todo polinomio que viene de un real tiene grado 0. Excepto el polinomio 0.

El grado del polinomio q(x)=1+2x^3+3x^7 es 7.

Sin embargo, el polinomio r(x)=0 no tiene grado, pues es el polinomio 0.

Notemos que el polinomio s(x)=2+4x se escribe como (2,4,\overline{0}) en notación de sucesión. La entrada 0 es 2, la entrada 1 es 4 y el resto de las entradas son 0. El grado de s(x) es 1, que es precisamente la posición de la última entrada distinta de 0 en su notación de sucesión.

\square

El siguiente resultado habla de cómo interactúa el grado con operaciones de polinomios.

Proposición. Si p(x) y q(x) son polinomios en \mathbb{R}[x] distintos de cero, entonces:

  • El grado del producto cumple

        \[\deg(p(x)q(x)) = \deg(p(x))+\deg(q(x)).\]

  • El grado de la suma cumple

        \[\deg(p(x)+q(x))\leq \max(\deg(p(x)),\deg(q(x))).\]

  • Si \deg(p(x))>\deg(q(x)), entonces

        \[\deg(p(x)+q(x))=\deg(p(x)).\]

Demostración. Supongamos que los grados de p(x) y q(x) son, respectivamente, m y n, y que p(x) y q(x) son

    \begin{align*}p(x)&=a_0+a_1x+\ldots+a_mx^m\\q(x)&=b_1+b_1x+\ldots+b_nx^n.\end{align*}


La demostración de la primera parte ya la hicimos en la entrada anterior. En la notación que estamos usando ahora, vimos que el coeficiente de x^{m+n} en p(x)q(x) es justo a_mb_n\neq 0, y que este es el término de mayor exponente.

Para la segunda y tercera partes, podemos asumir que m\geq n. Tenemos que p(x)+q(x) es

    \[\left(\sum_{i=0}^n (a_i+b_i)x^i\right) + a_{n+1}x^{n+1}+\ldots+a_mx^m.\]

De aquí, se ve que el máximo exponente que podría aparecer es m, lo cual prueba la segunda parte.

Para la tercer parte, cuando m>n tenemos que el coeficiente de x^m es a_m\neq 0, y que es el término con mayor exponente. Así, el grado de la suma es m.

\square

La hipótesis adicional del tercer punto es necesaria, pues en la suma de dos polinomios del mismo grado, es posible que «se cancele» el término de mayor grado.

Ejemplo. El producto de los polinomios 1+x+x^2+x^3 y 1-x es 1-x^4. Esto concuerda con lo que esperábamos de sus grados. El primero tiene grado 3, el segundo grado 1 y su producto grado 4=3+1.

La suma de los polinomios 1+\pi x^3 + \pi^2 x^5 y 1-\pi x^3 es 2+\pi^2x^5, que es un polinomio de grado 5, como esperaríamos por la tercer parte de la proposición.

La suma de los polinomios 4x^5+6x^7 y 6x^5+4x^7 es 10x^5+10x^7. Es de grado 7, como esperaríamos por la segunda parte de la proposición.

Sin embargo, en la suma de polinomios el grado puede disminuir. Por ejemplo, los polinomios 1+x^3-x^7 y 1+x^2+x^7 tienen grado 7, pero su suma es el polinomio 2+x^2+x^3, que tiene grado 3.

\square

Evaluación de polinomios e introducción a raíces

Es importante entender que hay una diferencia entre un polinomio, y la función que induce. Por la manera en que definimos a los polinomios, «en el fondo» son sucesiones, incluso con la nueva notación de x y potencias. Sin embargo, cualquier polinomio define una función.

Definición. Si tenemos un polinomio

    \[p(x)=a_0+a_1x+\ldots+a_nx^n\]

en \mathbb{R}, éste define una función aplicar p que es una función f_p:\mathbb{R}\to \mathbb{R} dada por

    \[f_p(r)=a_0+a_1r+a_2r^2+\ldots+a_nr^n\]

para todo r\in \mathbb{R}.

Ejemplo. El polinomio p(x)=3x^2+4x^3 induce a la función f_p:\mathbb{R}\to \mathbb{R} tal que f_p(r)=3r^2+4r^3. Tenemos, por ejemplo, que

    \[f_p(1)=3\cdot 1^2 + 4\cdot 1^3 = 7\]

y que

    \[f_p(2)=3\cdot 2^2 + 4\cdot 2^3=44.\]

\square

Como las reglas de los exponentes y la multiplicación por reales funciona igual en \mathbb{R} que en \mathbb{R}[x], la evaluación en un real r obtiene exactamente lo mismo a que si simplemente reemplazamos x por r y hacemos las operaciones. Por ello, usualmente no distinguimos entre p(x) y f_p, su función evaluación, y para un real r usamos simplemente p(r) para referirnos a f_p(r).

De manera totalmente análoga, podemos pensar a p(x) como una función p:\mathbb{C}\to \mathbb{C}. También, como comentamos al inicio, podemos definir a los polinomios con coeficientes complejos, es decir a \mathbb{C}[x], y pensarlos como funciones.

Es momento de introducir una definición clave para lo que resta del curso.

Definición. Sea p(x) un polinomio en \mathbb{R}[x] o \mathbb{C}[x] y sea r un real o complejo. Decimos que r es una raíz de p(x) si p(r)=0.

Ejemplo. El polinomio p(x)=3 no tiene raíces, pues para cualquier real o complejo r se tiene p(r)=3\neq 0. Por otro lado, cualquier real o complejo es raíz del polinomio z(x)=0.

El polinomio q(x)=x^2+1 no tiene raíces en \mathbb{R} pues q(r)\geq 1 para cualquier real r. Pero sí tiene raíces en \mathbb{C}, pues

    \[q(i)=i^2+1=-1+1=0.\]

El polinomio s(x)=x(x-1)(x-1)=x^3-2x^2+x tiene como únicas raíces a 0 y 1, lo cual se puede verificar fácilmente antes de hacer la multiplicación. Esto debería darnos la intuición de que conocer a las raíces de un polinomio nos permite factorizarlo y viceversa. Esta intuición es correcta y la formalizaremos más adelante.

\square

Cuando hablamos de los números complejos, vimos cómo obtener las raíces de los polinomios de grado 2, y de los polinomios de la forma x^n-a en \mathbb{C}. La mayor parte de lo que haremos de aquí en adelante en el curso será entender a las raíces reales y complejas de más tipos de polinomios.

Tarea moral

Los siguientes ejercicios no forman parte de la evaluación del curso, pero te servirán para entender mucho mejor los conceptos vistos en esta entrada, así como temas posteriores.

  • Pasa el polinomio (0,0,0,0,4,0,3,\overline{0}) a notación con x y potencias. Luego, pasa el polinomio 1-x^3+x^6-x^9 a notación de sucesión. Suma ambos polinomios y exprésalos en notación con x. Multiplícalos usando distribución y agrupamiento. Multiplícalos usando una tabla.
  • Prueba usando la definición de multiplicación y de x^n que para m y n enteros no negativos se tiene que x^{m+n}= x^m x^n.
  • Toma P_1(x),\ldots,P_m(x) polinomios en \mathbb{R}[x] de grado n_1,\ldots,n_m respectivamente. ¿Cuál es el grado de P_1(x)+\ldots+P_m(x)? ¿Y el grado de P_1(x)\cdot \ldots \cdot P_m(x)?
  • Usando distribución y agrupamiento, muestra que para cada entero positivo n se cumple que

        \[(1-x)(1+x+x^2+\ldots+x^{n-1})=1-x^n.\]

Para practicar la aritmética de polinomios, puedes ir a la sección correspondiente de Khan Academy.

Álgebra Superior II: El anillo de polinomios con coeficientes reales

Introducción

Estamos listos para la cuarta y última parte del curso, en donde construiremos el anillo de polinomios con coeficientes reales. Los elementos de este anillo son polinomios, los cuales se aparecen en numerosas áreas de las matemáticas. Tras su construcción, aprenderemos varias herramientas para trabajar con ellos.

En las tres primeras partes del curso ya trabajamos con otras estructuras algebraicas. Hasta ahora, hemos hablado de lo siguiente:

  • Naturales: Construimos a partir de teoría de conjuntos al conjunto \mathbb{N} de números naturales, sus operaciones y orden. De lo más relevante es que dentro de los naturales podemos hacer definiciones por recursión y pruebas por indución.
  • Enteros: Con \mathbb{N} construimos a los enteros \mathbb{Z}, sus operaciones y orden. Hablamos de divisibilidad y factorización. Esto dio pie a construir \mathbb{Z}_n, los enteros módulo n, junto con su aritmética. Aprendimos a resolver ecuaciones en \mathbb{Z} y sistemas de congruencias.
  • Racionales y reales: Mencionamos brevemente cómo se construye \mathbb{Q} a partir de \mathbb{Z} y cómo se construye \mathbb{R} a partir de \mathbb{Q}. Tanto \mathbb{R} como \mathbb{Q} son campos, así que ahí se pueden hacer sumas, restas, multiplicaciones y divisiones.
  • Complejos: A partir de \mathbb{R} construimos el campo \mathbb{C} de los números complejos. Definimos suma, multiplicación, inversos, norma y conjugados. Luego, desarrollamos herramientas para resolver varios tipos de ecuaciones en \mathbb{C}. Finalmente, construimos las funciones exponenciales, logarítmicas y trigonométricas.

Quizás a estas alturas del curso ya veas un patrón de cómo estamos trabajando. Aunque varias de estas estructuras ya las conocías desde antes, hay una primer parte importante que consiste en formalizar cómo se construyen. Luego, vimos cómo se definen las operaciones en cada estructura y qué propiedades tienen. Haremos algo muy parecido con los polinomios.

Intuición de los polinomios

La idea de esta entrada es llegar a los polinomios que ya conocemos, es decir, a expresiones como la siguiente:

    \[4+5x+\frac{7}{2}x^2-x^4+3x^5.\]

Lo que tenemos que formalizar es qué significa esa «x», y cómo le hacemos para sumar y multiplicar expresiones de este tipo.

Intuitivamente, lo que queremos ese que en la suma «se sumen términos del mismo grado» y que en el producto «se haga la distribución y se agrupen términos del mismo grado». Por ejemplo, queremos que la suma funcione así

    \begin{align*}(1+&x-x^2+3x^3)+(-7+3x+x^2+2x^3+x^4)\\&=(1-7)+(1+3)x+(-1+1)x^2+(3+2)x^3+(0+1)x^4\\&=-6+4x+0x^2+5x^4+x^4\\&=-6+4x+5x^3+x^4,\end{align*}

y que la multiplicación funcione así

    \begin{align*}(2&+3x)(5+x+x^2)\\&=2(5+x+x^2)+3x(5+x+x^2)\\&=(10+2x+2x^2)+(15x+3x^2+3x^3)\\&=10+(2+15)x+(2+3)x^2+3x^3\\&=10+17x+5x^2+3x^3.\end{align*}

El exponente más grande de una x puede ser tan grande como queramos, pero no se vale que los polinomios tengan una infinidad de términos. Así, queremos descartar cosas del estilo

    \[1+x+x^2+x^3+x^4+\ldots,\]

en donde sumamos indefinidamente.

Construcción de polinomios

Para construir polinomios formalmente, tenemos que elegir de dónde van a venir sus coeficientes. Puede ser \mathbb{Q}, \mathbb{R}, \mathbb{Z} o incluso \mathbb{Z}_7, digamos. Nosotros nos enfocaremos en construir los polinomios con coeficientes en \mathbb{R}, que tiene la ventaja de ser un campo. Algunas de las propiedades que probaremos se valen para cualquier elección de coeficientes, pero otras no. No profundizaremos en estas diferencias, pero es bueno que lo tengas en mente para tu formación matemática posterior.

Definición. Dado un conjunto X, una sucesión de elementos de X es una función a:\mathbb{N}\to X. Para n en \mathbb{N}, a a(n) usualmente lo denotamos simplemente por a_n, y a la sucesión a por \{a_n\}.

Definición. El soporte de una sucesión es el conjunto de naturales n tales que a_n\neq 0.

Podemos «visualizar» los primeros términos de una sucesión así:

    \[(a_0, a_1, a_2, a_3, a_4, a_5, \ldots),\]

en donde podemos poner tantos términos como queramos y los puntos suspensivos indican que «sigue y sigue». Por supuesto, usualmente esta visualización no puede guardar toda la información de la sucesión, pero puede ayudarnos a entenderla un poco mejor.

Ejemplo. Si tomamos la función identidad \text{id}:\mathbb{N}\to \mathbb{N}, obtenemos la sucesión

    \[(0,1,2,3,4,5,6,7,\ldots).\]

Al tomar la función a:\mathbb{N}\to \mathbb{Z} tal que a_n=(-1)^n, obtenemos la sucesión

    \[(1,-1,1,-1,1,-1,\ldots).\]

\square

Los polinomios son aquellas sucesiones de reales que «después de un punto tienen puros ceros».

Definición. Un polinomio con coeficientes reales es una sucesión \{a_n\} de reales tal que a_n\neq 0 sólo para una cantidad finita de naturales n.

En otras palabras, un polinomio es una sucesión con soporte finito. Si visualizamos a un polinomio como una sucesión, entonces es de la forma

    \[(a_0,a_1,a_2,a_3,a_4,a_5,\ldots),\]

en donde a partir de un punto ya tenemos puros ceros a la derecha. Por conveniencia, marcaremos ese punto con un \overline{0}.

Ejemplo. La sucesión

    \[\left(5,7,\frac{7}{2},0,-1,3,0,0,0,\ldots\right),\]

en la que después del 3 ya todos los términos son ceros, representa a un polinomio. Con la convención de arriba, podemos escribirlo como

    \[\left(5,7,\frac{7}{2},0,-1,3,\overline{0}\right).\]

Su soporte consiste de aquellas posiciones en las que la sucesión no es cero, que son 0,1,2,4,5.

La sucesión

    \[(1,-1,1,-1,1,-1,\ldots)\]

dada por a_n=(-1)^n no es un polinomio, pues podemos encontrar una infinidad de términos no cero.

\square

Para que las definiciones de la siguiente sección te hagan sentido, puedes pensar de manera informal que la sucesión

    \[(a_0, a_1, a_2, a_3, a_4, a_5, \ldots),\]

representa al polinomio

    \[a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+a_5x^5+\ldots.\]

La última condición en la definición de polinomio es la que garantiza que «tenemos un número finito de sumandos».

Definición. Definimos al conjunto de polinomios con coeficientes reales como

    \[\mathbb{R}[x]:=\{ p: p \text{ es polinomio con coeficientes reales}\}.\]

La igualdad se polinomios de define término a término.

Definición. Sean a=\{a_n\} y b=\{b_n\} en \mathbb{R}[x]. Decimos que a=b si para todo natural se tiene a_n=b_n.

En las siguientes secciones definiremos las operaciones de suma y producto en \mathbb{R}[x].

Suma y producto de polinomios

Los polinomios se suman «entrada a entrada».

Definición. Dados dos polinomios a=\{a_n\} y b=\{b_n\} en \mathbb{R}[x], definimos su suma como el polinomio

    \[a+b:=\{a_n+b_n\},\]

o bien, en términos de sucesiones, como la sucesión a+b:\mathbb{N}\to \mathbb{R} tal que (a+b)(n)=a(n)+b(n).

Observa que nos estamos apoyando en la suma en \mathbb{R} para esta definición.

Ejemplo. Los polinomios

    \[\left(0,2,0,4,-1,\frac{2}{3},\overline{0}\right)\]

y

    \[\left(1,-2,-1,-4,-2,\overline{0}\right)\]

tienen como suma al polinomio

    \[\left(0+1,2-2,0-1,4-4,-1-2,\frac{2}{3}+0,0+0,\ldots\right),\]

que es

    \[\left(1,0,-1,0,-3,\frac{2}{3},\overline{0}\right).\]

\square

La suma de dos polinomios sí es un polinomio pues claramente es una sucesión, y su soporte se queda contenido en la union de los soportes de los sumandos.

La siguiente definición guarda la idea de que para multiplicar queremos distribuir sumandos y agrupar términos del mismo grado. Tiene sentido si piensas en la asociación intuitiva informal que discutimos al final de la sección anterior.

Definición. Dados dos polinomios a=\{a_n\} y b=\{b_n\} en \mathbb{R}[x], definimos su producto como el polinomio

    \[ab:=\{c_n\},\]

en donde c_n está dado por

    \[c_n:=\sum_{i+j=n} a_ib_j,\]

en otras palabras,

    \[c_n=a_0b_n+a_1b_{n-1}+\ldots+a_{n-1}b_1+a_nb_0.\]

Aquí nos estamos apoyando en la suma y producto en \mathbb{R} para definir la multiplicación de polinomios.

Una forma práctica de hacer el producto es mediante una tabla. En la primer fila ponemos al primer polinomio y en la primer columna al segundo. Las entradas interiores son el producto de la fila y columna correspondiente. Una vez que hacemos esto, la entrada c_j del producto es la suma de los elementos en la j-ésima «diagonal».

Ejemplo. Multipliquemos a los polinomios

    \[a=(3,-2,0,1,\overline{0})\]

y

    \[b=(0,2,7,\overline{0}).\]

Ponemos a a y b en la primer fila y columna respectivamente de la siguiente tabla:

3-201
0
2
7

Luego, en cada entrada interior de la tabla ponemos el producto de los coeficientes correspondientes:

3-201
03 \cdot 0-2 \cdot 00\cdot 01\cdot 0
23 \cdot 2-2 \cdot 20\cdot 21\cdot 2
73 \cdot 7-2 \cdot 70\cdot 71\cdot 7

Después, hacemos las operaciones:

3-201
00000
26-402
321-1407

Finalmente, para encontrar el coeficiente c_j del producto, hacemos la suma de las entradas en la j-ésima diagonal dentro de la tabla, es decir:

    \begin{align*}c_0&=0\\c_1&=6+0=6\\c_2&=21-4+0=17\\c_3&=-14+0+0=-14\\c_4&=0+2=2\\c_5&=7.\end{align*}

De esta forma, el polinomio producto es

    \[(0,6,17,-14,2,7,\overline{0}).\]

Es muy recomendable que notes que esto coincide con el producto (por ahora informal)

    \begin{align*}(3-&2x+x^3)(2x+7x^2)\\&=6x+17x^2-14x^3+2x^4+7x^5.\end{align*}

\square

El anillo de polinomios con coeficientes reales

Los polinomios y los enteros se parecen, en el sentido de que como estructura algebraica comparten muchas propiedades. La idea de esta sección es formalizar esta afirmación.

Teorema. El conjunto \mathbb{R}[x] con las operaciones de suma y producto arriba definidos forman un anillo.

Demostración. Por una parte, tenemos que mostrar que la suma es asociativa, conmutativa, que tiene neutro e inversos aditivos. Por otra parte, tenemos que mostrar que el producto es asociativo. Finalmente, tenemos que mostrar que se vale la ley distributiva.

Tomemos dos polinomios a=\{a_n\}, b=\{b_n\} y un natural n. El término n de a+b es a_n+b_n y el de b+a es b_n+a_n, que son iguales por la conmutatividad de la suma en \mathbb{R}. De manera similar, se muestra que la suma es asociativa.

El polinomio (\overline{0}) es la identidad de la suma. Esto es sencillo de mostrar y se queda como tarea moral. Además, si a=\{a_n\} es un polinomio, entonces \{-a_n\} es una sucesión con el mismo soporte (y por lo tanto finito), que cumple que

    \[\{a_n\}+\{-a_n\}=(0,0,0,\ldots)=(\overline{0}),\]

así que la suma tiene inversos aditivos.

Ahora probemos la asociatividad del producto. Tomemos tres polinomios a=\{a_n\}, b=\{b_n\}, c=\{c_n\} y un natural n. Hagamos el producto (ab)c. Para cada i, el i-ésimo término de ab es un cierto d_i dado por

    \[d_i = \sum_{k+l=i} a_k b_l.\]

El n-ésimo término de (ab)c es entonces

    \begin{align*}\sum_{i+j=n}d_ic_j &= \sum_{i+j=n}\sum_{k+l=i} a_kb_lc_j\\&=\sum_{k+l+j=n}a_kb_lc_j.\end{align*}

Un argumento análogo muestra que el n-esimo término de a(bc) es también

    \begin{align*}\sum{k+l+j=n}a_kb_lc_j,\end{align*}

lo cual muestra que la multiplicación es asociativa.

Lo último que nos queda por probar es la ley distributiva. Tomemos tres polinomios a=\{a_n\}, b=\{b_n\}, c=\{c_n\} y un natural n. Usamos las propiedades de las operaciones en \mathbb{R} para ver que el n-ésimo término de a(b+c) es

    \begin{align*}\sum_{i+j=n} a_i(b_j+c_j)&=\sum_{i+j=n} (a_ib_j+ a_i c_j)\\&=\sum_{i+j=n} a_ib_j + \sum_{i+j=n} a_ic_j.\end{align*}

A la derecha tenemos el n-ésimo término de ab sumado con el n-ésimo término de ac, así que coincide con el n-ésimo término de la suma ab+ac. Esto muestra que a(b+c) y ab+ac son iguales término a término y por lo tanto son iguales como polinomios.

\square

Como de costumbre, al inverso aditivo de un polinomio a le llamamos -a, y definimos a-b:=a+(-b).

Proposición. La multiplicación en \mathbb{R}[x] es conmutativa.

Demostración. Tomemos dos polinomios a=\{a_n\} y b=\{b_n\}. Tenemos que ver que ab y ba son iguales término a término. Tomemos entonces un natural n. El término c_n de ab es

    \[c_n=\sum_{i+j=n} a_ib_j,\]

y el término d_n de ba es

    \[d_n=\sum_{i+j=n} b_ia_j.\]

Por la conmutatividad de la suma y el producto en \mathbb{R}, tenemos que c_n=d_n.

\square

Proposición. La multiplicación en \mathbb{R}[x] tiene identidad.

Demostración. El polinomio (1,\overline{0}) es la identidad multiplicativa. Esto es sencillo de mostrar y se queda como tarea moral.

\square

Proposición. Si a y b son polinomios en \mathbb{R}[x] distintos del polinomio (\overline{0}), entonces su producto también.

Demostración. Para ello, tomemos el mayor natural m tal que a_m\neq 0 y el mayor natural n tal que b_n\neq 0. Estos existen pues a y b no son el polinomio (\overline{0}), y su soporte es finito.

Cualquier pareja de naturales k y l tales que k+l=m+n con k\leq m-1 cumple l\geq n+1. Así, si k+l=m+n tenemos que:

  • Si k\leq m-1, entonces b_l=0 y por lo tanto a_kb_l=0
  • Si k\geq m+1, entonces a_k=0 y por lo tanto a_kb_l=0
  • Finalmente, si k=m, entonces l=n y

        \[a_kb_l=a_mb_n\neq 0.\]

De esta forma, el (m+n)-ésimo término de ab es

    \[\sum_{k+l=m+n} a_k b_l=a_mb_n\neq 0,\]

de modo que ab no es el polinomio (\overline{0}).

\square

Corolario. En \mathbb{R}[x] se vale la regla de cancelación, es decir, si a,b,c son polinomios, a\neq 0 y ab=ac, entonces b=c.

Demostración. De la igualdad ab=ac obtenemos la igualdad a(b-c)=0. Como a\neq 0, por la proposición anterior debemos tener b-c=0, es decir, b=c.

\square

A un anillo conmutativo cuya multiplicación tiene identidad y en donde se vale la regla de cancelación se le conoce como un dominio entero.

Teorema. El anillo \mathbb{R}[x] es un dominio entero.

Con esto terminamos la construcción de \mathbb{R}[x] y de sus operaciones. Cuando trabajamos con los polinomios de manera práctica resulta engorroso mantener esta notación de sucesiones. En la siguiente entrada justificaremos el uso de la notación «usual» de los polinomios, en la que usamos la letra «x» y exponentes.

Tarea moral

Los siguientes ejercicios no forman parte de la evaluación del curso, pero te servirán para entender mucho mejor los conceptos vistos en esta entrada, así como temas posteriores.

  • Justifica por qué el soporte del producto de dos polinomios es finito.
  • Muestra que la suma en \mathbb{R}[x] es asociativa.
  • Verifica que el polinomio (\overline{0}) es la identidad aditiva en \mathbb{R}[x].
  • Verifica que el polinomio (1,\overline{0}) es la identidad multiplicativa en \mathbb{R}[x].
  • Considera los polinomios a=\left(\frac{1}{3},4,\frac{5}{7},8,\overline{0}\right) y b=\left(0,0,\frac{2}{5},\frac{3}{4},\overline{0}). Determina

Álgebra Superior II: Teoremas de Fermat y de Wilson

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!