Archivo de la etiqueta: enteros

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

[latexpage]

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

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

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

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

[latexpage]

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

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

  • 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: Esbozo de construcción de los números racionales y reales

[latexpage]

Introducción

En la unidad pasada vimos la construcción de los números enteros a partir de los números naturales. Lo que hicimos fue considerar parejas de números naturales $(a,b)$ para las que dimos la relación $\sim$ definida por $(a,b)\sim (c,d)$ si y sólo si $a+d=b+c$, vimos que esta relación es de equivalencia. Dijimos que, aunque era incorrecto formalmente, convenía pensar a la pareja $(a,b)$ como $a-b$ (es incorrecto ya que no siempre se puede restar en $\mathbb{N}$).

La relación $\sim$, así definida, genera las clases de equivalencia $$\overline{(a, b)}=\lbrace (c, d)\in \mathbb{N}\times\mathbb{N} : a+d=b+c\rbrace$$ en $\mathbb{N}\times\mathbb{N}$. El conjunto $\mathbb{Z}$ lo construimos como el conjunto de todas estas clases de equivalencia. En él definimos las operaciones:

  • Suma: $\overline{(a,b)}+\overline{(c,d)}=\overline{(a+c,b+d)}$
  • Producto: $ \overline{(a,b)}\overline{(c,d)}=\overline{(ac+bd,ad+bc)}$

Vimos que estas operaciones están bien definidas. La suma es bastante natural. El producto parece algo artificial, pero se vuelve natural si pensamos en «multiplicar $a-b$ con $c-d$», pues $(a-b)(c-d)=(ac+bd)-(ad+bc)$. Recordemos que es una justificación informal, pero ayuda a entender la intuición.

Después, nos dedicamos a probar que con estas operaciones, suma y producto, el conjunto $\mathbb{Z}$ es un anillo conmutativo con $1$ en donde se vale cancelar. A partir de ahí empezamos a ver a $\mathbb{Z}$ desde el punto de vista de la teoría de números. Estudiamos el máximo común divisor, la relación de divisibilidad, el anillo de enteros módulo $n$, congruencias, ecuaciones en congruencias, teorema chino del residuo y mencionamos un poco de ecuaciones diofantinas.

Con eso terminamos la unidad de enteros, correspondiente al segundo segundo parcial del curso.

Las siguientes dos unidades contempladas por el temario oficial son:

  • Números complejos.
  • Anillo de polinomios.

Vale la pena hacer una observación. Típicamente tenemos la siguiente cadena de contenciones entre sistemas numéricos $$\mathbb{N}\subset \mathbb{Z}\subset \mathbb{Q} \subset \mathbb{R}\subset \mathbb{C}.$$

En las primeras dos unidades del curso hablamos de $\mathbb{N}$ y de $\mathbb{Z}$. De acuerdo a las contenciones anteriores, lo siguiente sería tratar a detalle los racionales $\mathbb{Q}$ y los reales $\mathbb{R}$. Sin embargo el temario oficial «se los salta». Esto es un poco raro, pero podría estar justificado en que estos sistemas numéricos se estudian en otros cursos del plan de estudios. Por ejemplo, $\mathbb{R}$ se estudia con algo de profundidad en los cursos de cálculo.

De cualquier forma nos va a ser muy útil mencionar, por lo menos por «encima», cómo hacer la construcción de $\mathbb{Q}$ y $\mathbb{R}$. La construcción de los números racionales ayuda a repasar la construcción de los enteros. En la construcción de los números reales nos encontraremos con propiedades útiles que usaremos, de manera continua, cuando hablemos de la construcción de los números complejos $\mathbb{C}$. Por estas razones, aunque no vayamos a evaluar, las construcciones de $\mathbb{Q}$ y $\mathbb{R}$, en el curso, las ponemos aquí para que las conozcas o las repases.

Motivación de construcción de los racionales

Los naturales no son suficientes para resolver todas las ecuaciones de la forma $$x+a=b,$$ pues si $a>b$ la ecuación no tiene solución en $\mathbb{N}$ y esta fue nuestra motivación para construir los números enteros. En $\mathbb{Z}$ todas estas ecuaciones tienen solución. Sin embargo, en $\mathbb{Z}$ la ecuación $$ax=b$$ tiene solución si y sólo si $a$ divide a $b$ (por definición se tiene que $a$ divide a $b$ si y sólo si $b$ es un múltiplo de $a$), pero no siempre sucede esto. Por ejemplo, $3x=7$ no tiene solución en $\mathbb{Z}$.

Construcción de los racionales

Para la construcción de los racionales consideremos el conjunto $\mathbb{Z}\times \mathbb{Z}\setminus\{0\}$ y sobre él la relación $\sim$ definida por $(a,b)\sim (c,d)$ si y sólo si $ad=bc$. Resulta que $\sim$ es relación de equivalencia, así que, para cada pareja $(a,b)\in \mathbb{Z}\times\mathbb{Z}$, denotaremos también como $\overline{(a,b)}$ a su clase de equivalencia, aunque en este caso $$\overline{(a, b)}=\lbrace (m, n)\in \mathbb{Z}\times\mathbb{Z}\setminus\{0\} : an=bm\rbrace.$$

Observa que esta construcción se parece mucho a la que hicimos para $\mathbb{Z}$, aunque ahora nos basamos en el producto en $\mathbb{Z}$ (antes era la suma en $\mathbb{N}$). De nuevo, una forma de pensar bastante intuitiva (aunque formalmente incorrecta), es pensar a cada clase $\overline{(a,b)}$ «como $\frac{a}{b}$». Nota que estamos considerando sólo aquellas parejas $(a,b)$ tales que $b\neq 0$.

De esta forma $\mathbb{Q}$ es el conjunto de clases de equivalencia de las parejas $(a,b)$ tales que $b\neq 0$, en símbolos, $$\mathbb{Q}:=\{\overline{(a,b)}: a\in \mathbb{Z}, b\in \mathbb{Z}\setminus\{0\}\}.$$

Operaciones y orden en los racionales

Vamos a definir las operaciones en $\mathbb{Q}$. Ahora el producto es «intuitivo» y la suma no tanto.

  • Suma: $\overline{(a,b)} + \overline{(c,d)} = \overline{(ad+bc,bd)}$
  • Producto: $\overline{(a,b)}\overline{(c,d)}=\overline{(ac,bd)}$

La suma se vuelve mucho más intuitiva si primero pensamos en nuestra interpretación (informal) de $\overline{(a,b)}$ como $\frac{a}{b}$ y luego, por lo que aprendimos en educación primaria sobre la suma de fracciones, vemos que $$\frac{a}{b}+\frac{c}{d}=\frac{ad+bc}{bd}.$$

Ahora, para definir el orden en $\mathbb{Q}$, tomemos la pareja $(a,b)\in \mathbb{Z}\times\mathbb{Z}\setminus\{0\}$. Tenemos que la clase $\overline{(a,b)}$ es

  • Cero si $a=0$,
  • Positiva si ambos ($a$ y $b$) son negativos o ninguno es negativo con el orden definido en $\mathbb{Z}$ y
  • Negativa si exactamente alguno ($a$ o $b$) es negativo con el orden definido en $\mathbb{Z}$.

Diremos que $\overline{(a,b)}>\overline{(c,d)}$ si $\overline{(a,b)}-\overline{(c,d)}$ es positiva.

Se puede probar que estas operaciones suma y producto, así como el orden están bien definidas (es decir que no dependen del representante que se tome).

Antes, de continuar, consideremos lo siguiente: un campo se puede pensar como un conjunto en el que están definidas la «suma» y la «multiplicación» tales que:

  • La suma es asociativa, conmutativa, tiene un neutro (el $0$) e inversos aditivos.
  • La multiplicación es asociativa, conmutativa, tiene un neutro (el $1$) y todo elemento distinto de $0$ tiene un inverso multiplicativo.
  • Se tiene la distributividad del producto sobre la suma $a(b+c)=ab+bc$.

En vista de lo anterior queremos mencionar que se puede probar lo siguiente:

Teorema. El conjunto $\mathbb{Q}$ con sus operaciones de suma y producto es un campo ordenado.

Retomando lo que hablamos del neutro para la multiplicación, en un campo, veamos un ejemplo.

Ejemplo. La clase $\overline{(c,c)}$ es el neutro multiplicativo en $\mathbb{Q}$, veamos:

Se tiene que $$\overline{(a, b)(c, c)} = \overline{(ac,bc)}=\lbrace (m, n)\in\mathbb{Z}\times\mathbb{Z}\setminus\{0\}: acn=bcm\rbrace$$

y $\lbrace (m, n)\in\mathbb{Z}\times\mathbb{Z}\setminus\{0\}: acn=bcm\rbrace=\lbrace (m, n)\in \mathbb{Z}\times\mathbb{Z}\setminus\{0\}: anc=bmc\rbrace$, pero $\lbrace (m, n)\in\mathbb{Z}\times\mathbb{Z}\setminus\{0\}: anc=bmc\rbrace=\lbrace (m, n)\in\mathbb{Z}\times\mathbb{Z}\setminus\{0\}: an=bm\rbrace=\overline{(a, b)}$. Por lo tanto $\overline{(a, b)(c, c)}=\overline{(a, b)}$. Nota que aquí estamos usando que el producto en $\mathbb{Z}$ es asociativo, conmutativo y que se pueden cancelar factores distintos de cero.

En $\mathbb{Q}$, el inverso multiplicativo de la clase $\overline{(a,b)}$ es $\overline{(b,a)}$, veamos:

Su producto es $$\overline{(ab,ba)}=\lbrace (m, n)\in \mathbb{Z}\times\mathbb{Z}\setminus\{0\}: abn=bam\rbrace$$ y $\lbrace (m, n)\in \mathbb{Z}\times\mathbb{Z}\setminus\{0\}: abn=bam\rbrace=\lbrace (m, n)\in \mathbb{Z}\times\mathbb{Z}\setminus\{0\}: m=n\rbrace=\overline{(c, c)}$.

Notación simple de racionales y ecuaciones aún sin solución

Vamos a denotar la clase de equivalencia $\overline{(a,b)}$ por $\frac{a}{b}$, a partir de lo cual nuestra interpretación de pensarlo así ya se vuelve formal. Se puede mostrar que todo lo que aprendimos de esta notación en la primaria se deduce de las propiedades de $\mathbb{Q}$.

La ecuación $$ax=b$$ tiene solución casi siempre, el único problema es si $a=0$. Pero si $a\neq 0$, la solución es única y es $x=\frac{b}{a}$.

El conjunto $\mathbb{Q}$ es bastante bueno algebraicamente, pero le falta todavía más para ser bueno para análisis y cálculo. Todavía tiene «bastantes hoyos»: en él no podemos probar, por ejemplo, el teorema del valor intermedio para funciones continuas. Así mismo, hay varias ecuaciones que todavía no tienen solución en $\mathbb{Q}$.

Ejercicio. La ecuación $x^2=3$ no tiene una solución en $\mathbb{Q}$.

Una forma de enunciar el resultado anterior es decir «$\sqrt{3}$ es irracional». Pero nota que es incorrecto enunciarlo así, pues para ponerle un nombre a $\sqrt{3}$, es necesario saber quién es, y justo el punto del ejercicio es que, tan sólo con $\mathbb{Q}$, no podemos definirlo.

Solución. Vamos a proceder por contradicción. Supongamos que la ecuación $x^2=3$ tiene una solución $p/q$ en los racionales. De esta forma,$(p/q)^2=3$. Multiplicando por $q^2$ en ambos lados, $p^2=3q^2$.

La factorización en primos del lado izquierdo tiene una cantidad par de $3$’s. La factorización en primos del lado derecho tiene una cantidad impar de $3$’s. Esto es una contradicción al teorema fundamental de la aritmética, por lo tanto, no existe $p/q$ solución racional de $x^2=3$.

$\square$

Reales y hoyos en los racionales

Para la construcción de los reales, ya no podemos proceder como le hemos estado haciendo, considerando simplemente parejas de números del sistema anterior y construyendo una relación de equivalencia sobre ellas. Lo que buscamos cuando damos el paso entre $\mathbb{Q}$ y $\mathbb{R}$ ya no es sólo que los números tengan «inversos aditivos» o «inversos multiplicativos», sino que «todos los conjuntos acotados por abajo tengan un mejor mínimo». Esto es lo que garantiza que se «llenen los hoyos» que tienen los racionales.

Entendamos el concepto de «hoyo»:

Definición. Sea $X$ un orden total $\le$ y $S$ un subconjunto de $X$, un ínfimo de $S$, en $X$, es un $r\in X$ tal que

  • $r\leq s$ para todo $s\in S$ y
  • si $t\leq s$ para todo $t\in S$, entonces $t\leq s$.

Definición. Un conjunto $X$ con un orden total $\le$ es completo si todo subconjunto $S$ de $X$, acotado inferiormente, tiene un ínfimo.

Ejemplo. El conjunto $\mathbb{Q}$ no es completo, pues el subconjunto $$S=\{x\in \mathbb{Q}: x^2\geq 3\}$$ está acotado inferiormente, pero no tiene un ínfimo en $\mathbb{Q}$ (su ínfimo es $\sqrt{3}$ y $\sqrt{3}$ no pertenece a $\mathbb{Q}$).

Sucesiones de Cauchy y construcción de los reales

Hay varias formas de construir un sistema numérico que extienda a $\mathbb{Q}$ y que no tenga hoyos. Se puede hacer mediante cortaduras de Dedekind, mediante expansiones decimales o mediante sucesiones de Cauchy de números racionales. Todas estas construcciones son equivalentes. Daremos las ideas generales de la última.

Definición. Una sucesión $$\{x_n\}=\{x_1,x_2,x_3,\ldots\}$$ es de Cauchy si para todo $N$ existe un $M$ tal que si $m\geq M$ y $n\geq M$, entonces $|x_m-x_n|<\frac{1}{N}$. Denotaremos con $C(\mathbb{Q})$ al conjunto de todas las sucesiones de Cauchy de números racionales.

Construiremos una relación de equivalencia $\sim$ en $C(\mathbb{Q})$. Si tenemos dos de estas sucesiones:
\begin{align*}
\{x_n\}&=\{x_1,x_2,x_3,\ldots\} \quad \text{y}\\
\{y_n\}&=\{y_1,y_2,y_3,\ldots\},
\end{align*}

diremos que $\{x_n\}\sim \{y_n\}$ si para todo natural $N$ existe un natural $M$ tal que para $n\geq M$ tenemos que $$|x_n-y_n|<\frac{1}{N}.$$

Se puede probar que $\sim$ es una relación de equivalencia. Para cada sucesión $\{x_n\}$ de Cauchy usamos $\overline{\{x_n\}}$ para denotar a la clase de equivalencia de $\{x_n\}$. Por definición, el conjunto $\mathbb{R}$ es el conjunto de clases de equivalencia de $\sim$, en símbolos: $$\mathbb{R}:=\{\overline{\{x_n\}}: \{x_n\} \in C(\mathbb{Q})\}.$$

Operaciones y orden en los reales

En $\mathbb{R}$ podemos definir las siguientes operaciones:

  • Suma: $\overline{\{x_n\}} + \overline{\{y_n\}}= \overline{\{x_n + y_n\}}$ .
  • Producto: $\overline{\{x_n\}} \overline{\{y_n\}}= \overline{\{x_ny_n\}}$.

También podemos definir el orden en $\mathbb{R}$. Decimos que $\overline{\{x_n\}}$ es positivo si para $n$ suficientemente grande tenemos $x_n>0$. Decimos que $\overline{\{x_n\}}>\overline{\{y_n\}}$ si $\overline{\{x_n\}}- \overline{\{y_n\}}$ es positivo.

Se puede ver que las operaciones de suma y producto, así como el orden, están bien definidos. Más aún, se puede probar el siguiente resultado.

Teorema. El conjunto $\mathbb{R}$ con sus operaciones de suma y producto es un campo ordenado y completo.

Como antes, una vez que se prueba este teorema, se abandona la notación de sucesiones y de clases de equivalencia. En realidad se oculta, pues la construcción siempre está detrás, como un esqueleto que respalda las propiedades que encontramos.

El teorema nos dice que $\mathbb{R}$ ya no tiene hoyos, y esto es precisamente lo que necesitamos para resolver algunas ecuaciones como $x^2=3$. Un esbozo de por qué es el siguiente. Gracias a la existencia de ínfimos se puede probar el teorema del valor intermedio en $\mathbb{R}$. Se puede probar que la función $x^2$ es continua, que en $x=0$ vale $0$ y que en $x=2$ vale $4$, de modo que por el teorema del valor intermedio debe haber un real $x$ tal que $x^2=3$.

Reflexión final y motivación de números complejos

Las muchas otras importantes consecuencias de que $\mathbb{R}$ sea un campo ordenado y completo se discuten a detalle en cursos de cálculo. Si bien este es un logro enorme, aún tenemos un pequeño problema: ¡todavía no podemos resolver todas las ecuaciones polinomiales! Consideremos la ecuación $$x^2+1=0.$$ Podemos mostrar que para cualquier real $x$ tenemos que $x^2\geq 0$, de modo que $x^2+1\geq 1>0$. ¡Esta ecuación no tiene solución en los números reales!

Para encontrar una solución vamos a construir los números complejos. Con ellos podremos, finalmente, resolver todas las ecuaciones polinomiales, es decir, aquellas de la forma

$$a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0=0.$$

Hablaremos de esto en el transcurso de las siguientes dos unidades: números complejos y polinomios.

Tarea moral

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

  • ¿Cuál de las clases de equivalencia sería el neutro aditivo en $\mathbb{Q}$?
  • ¿Por qué la definición de orden en $\mathbb{Q}$ no depende del representante elegido?
  • ¿Cómo construirías el inverso multiplicativo de la sucesión de Cauchy $\{x_n\}$? Ten cuidado, pues algunos de sus racionales pueden ser $0$.
  • Aprovecha esta entrada de transición entre unidades para repasar las construcciones de $\mathbb{N}$ y de $\mathbb{Z}$.

Álgebra Superior II: Ecuaciones diofantinas

[latexpage]

Introducción

En entradas anteriores platicamos de congruencias y teoremas que nos sirven para trabajar con aritmética modular. Así mismo, aprendimos a resolver ecuaciones lineales y sistemas de ecuaciones lineales en congruencias en una variable.

Regresemos a $\mathbb{Z}$. Se usa el término ecuación diofantina para referirse a una ecuación en la cual las variables deben tomar soluciones enteras. Existe una gran variedad de formas que puede tomar una ecuación diofantina. «Resolver una ecuación diofantina» se refiere a encontrar, con demostración, una descripción del conjunto de todas sus soluciones en «términos sencillos».

Ejemplo 1. Encuentra todas las soluciones enteras $x$ a la ecuación $13x=91$.

Ejemplo 2. Encuentra todas las soluciones enteras $x,y$ a la ecuación $7x+5y=3$.

Los ejemplos $1$ y $2$ son ecuaciones diofantinas lineales en una y dos variables respectivamente. El objetivo de esta entrada es explicar cómo resolver estas ecuaciones. Continuamos la discusión de más ejemplos para abrir el panorama del tipo de problemas que aparecen en el área, y de las técnicas que se pueden usar.

Ejemplo 3. Encuentra todas las soluciones con enteros $x,y,z$ a la ecuación $x^2+y^2=z^2$.

Al Ejemplo 3 se le conoce como la ecuación pitagórica. Esa es posible resolverla con todo lo que hemos visto hasta ahora, pero no es tan sencillo. Requiere de un análisis cuidadoso de casos.

Ejemplo 4. Encuentra todas las soluciones enteras positivas $x,y$ a la igualdad $x^y=y^x$.

El Ejemplo $4$ es curioso. Si consideramos a la función real $f(x)=x^{\frac{1}{x}}$, el problema pide encontrar a aquellas parejas de enteros $x$ y $y$ tales que $f(x)=f(y)$. Una forma de resolver la ecuación es utilizando herramientas de cálculo diferencial en $f(x)$ para mostrar que para $x>5$ la función ya es estrictamente creciente. Esto reduce el análisis de casos de enteros que tenemos que intentar, y muestra que $(2,4)$, $(4,2)$ y $(n,n)$ son las únicas parejas de enteros válidas. La moraleja de este ejemplo es que a veces se tienen que usar herramientas de otras áreas de las matemáticas para resolver una ecuación, aunque esta sólo requiera de soluciones enteras.

Ejemplo 5. Encuentra todas las soluciones con enteros $x,y,z$ a la ecuación $x^3+y^3=z^3$.

El Ejemplo $5$, o bien cualquier ecuación del estilo $x^n+y^n=z^n$ se le llama una ecuación de tipo Fermat, pues Pierre Fermat conjeturó que no existen soluciones para cuando $n\geq 3$ y $x,y,z$ son todos distintos de cero. Esta conjetura fue demostrada en $1995$ por Andrew Wiles. Una demostración de esta conjetura queda muy lejos de la teoría que hemos desarrollado hasta ahora, pero vale la pena decir que esta ecuación motivó fuertemente el desarrollo de varias herramientas de teoría de números, sobre unas llamadas curvas elípticas.

Ejemplo 6. Encuentra todas las soluciones enteras positivas $x,y$ a la igualdad $|2^x-3^y|=1$.

El Ejemplo $6$ se puede resolver también con herramientas que ya hemos visto en el curso, pero requiere de un análisis detallado. Este problema pide, en otras palabras, determinar cuándo «una potencia de $3$ está junto a una potencia de $2$». Un ejemplo de esto son $2^3=8$ y $3^2=9$. Otra pregunta clásica del área es la conjetura de Catalán, la cual afirma que estas son las únicas dos potencias no triviales que son consecutivas. Fue demostrada en $2002$ por Mihăilescu. Las técnicas también están muy lejos del alcance de este curso. Se usan técnicas en campos ciclotómicos y módulos de Galois.

En realidad, uno podría tomar cualquier ecuación en reales y hacerse la pregunta de si existirán soluciones en enteros y, de ser así, determinar cuántas o cuáles son. Ha existido (y existe) mucha investigación en el área. El interés de una ecuación diofantina en particular está relacionado con su aplicación a otros problemas y con la teoría que ayuda a desarrollar.

Ecuaciones diofantinas lineales

La ecuación diofantina del Ejemplo 1 se puede preguntar en general. Dados enteros $a$ y $b$, ¿cuáles son las soluciones enteras $x$ a la ecuación $ax=b$?

  • Si $a=0$, la ecuación tiene solución si y sólo si $b=0$, y en este caso, cualquier valor entero de $x$ es solución.
  • Si $a\neq 0$, esta ecuación tiene solución en enteros si y sólo si $a$ divide a $b$, y en este caso $x=b/a$ es la única solución entera.

Estudiemos ahora la generalización del Ejemplo 2.

Problema. Sean $a$ y $b$ enteros distintos de $0$ y $c$ un entero. Determina todas las soluciones enteras a la ecuación $$ax+by=c.$$

Primero, determinemos condiciones necesarias y suficientes en $a$, $b$ y $c$ para que la ecuación tenga soluciones enteras $x$ y $y$. Lo que nos está pidiendo la ecuación es que escribamos a $c$ como combinación lineal entera de $a$ y $b$. Recordemos que $$a\mathbb{Z}+b\mathbb{Z} = \text{MCD}(a,b) \mathbb{Z},$$ de modo que la ecuación tiene solución si y sólo si $\text{MCD}(a,b)$ divide a $c$. ¿Cuáles son todas las soluciones? Esto lo determinaremos mediante las siguientes proposiciones.

Proposición. Sean $a$ y $b$ enteros distintos de $0$ y $c$ un entero divisible entre $M:=\text{MCD}(a,b)$. Sean $a’=a/M$, $b’=b/M$, $c’=c/M$. Las soluciones enteras a la ecuación $ax+by=c$ son las mismas que para la ecuación $a’x+b’y=c’$

Demostración. Se sigue de manera directa usando que $M\neq 0$, ya que de la original podemos pasar a la nueva dividiendo entre $M$, y de la nueva a la anterior multiplicando por $M$.

$\square$

Ejemplo. $x=2$ y $y=7$ son soluciones a la ecuación $6x-4y=-16$, y también son soluciones a la ecuación $3x-2y=-8$.

$\square$

Al dividir ambos lados de la ecuación entre el máximo común divisor de $a$ y $b$ obtenemos una ecuación en la que los coeficientes de las variables ahora son primos relativos. Este fenómeno ya lo habíamos visto cuando hablamos de ecuaciones en congruencias. Estudiemos este tipo de ecuaciones en enteros. Comenzaremos con unas un poco más sencillas: aquellas en las que $c=0$. A estas les llamamos ecuaciones homogéneas.

Proposición. Sean $a$ y $b$ enteros distintos de $0$ y primos relativos. Las soluciones de la ecuación diofantina $ax+by=0$ son exactamente de la forma $x=-kb$, $y=ka$ para $k$ en los enteros.

Demostración. De la ecuación obtenemos $-ax=by$, por lo que $a$ divide a $by$. Como $a$ y $b$ son primos relativos, tenemos que $a$ divide a $y$. Así, existe un $k$ entero tal que $y=ka$. Entonces, $-ax=bka$. Como $a\neq 0$, podemos cancelar y despejar $x=-kb$.

En efecto, todas estas parejas son soluciones pues $a(-kb)+b(ka)=0$.

$\square$

Ejemplo. Determina todas las soluciones a la ecuación diofantina $9x+5y=0$.

Solución. Tenemos que $9$ y $5$ son primos relativos y que la ecuación es homogénea. Por el resultado anterior, las soluciones son de la forma $x=-5k$ y $y=9k$.

$\square$

Ejemplo. Determina todas las soluciones a la ecuación diofrantina $9x-6y=0$.

Solución. Aquí hay que tener cuidado. Si bien la ecuación es homogénea, los coeficientes de las variables no son primos relativos. Si sólo consideramos las soluciones de la forma $x=6k$ y $y=9k$, en efecto todas estas son soluciones, pero nos faltará la solución $x=2$, $y=3$ que no es de esta forma.

Antes de poder usar la proposición, necesitamos dividir entre el máximo común divisor de $9$ y $6$, que es $3$, para obtener primero la ecuación diofantina equivalente $3x-2y=0$. Ahora sí, todas las soluciones enteras de esta ecuación (y por lo tanto de la original) son de la forma $x=2k$ y $y=3k$.

$\square$

Pasemos ahora al caso en el que los coeficientes de las variables son primos relativos, pero la ecuación ya no es homogénea.

Proposición. Sean $a$ y $b$ enteros distintos de $0$ y primos relativos. Sea $c$ un entero divisible entre $\text{MCD}(a,b)$. Se puede obtener una solución $x_0, y_0$ a la ecuación diofantina $ax+by=c$ usando el algoritmo de Euclides. El resto de las soluciones son exactamente de la forma $x=x_0-kb$, $y=y_0+ka$ en donde $k$ es cualquier entero positivo.

Demostración. Notemos que en efecto las soluciones propuestas satisfacen la ecuación diofantina pues
\begin{align*}
ax+by&=a(x_0-kb)+b(y_0+ka)\\
&=ax_0+by_0 + (-kab+kab)\\
&=ax_0+by_0\\
&=c.
\end{align*}

Aquí usamos que $x_0,y_0$ es una solución de $ax+by=c$. Veamos que estas soluciones son las únicas.

Si $x_1,y_1$ es una solución, entonces tenemos $$ax_1+by_1=c=ax_0+by_0,$$ y entonces $$a(x_1-x_0)+b(y_1-y_0)=c-c=0,$$ de modo que $(x_1-x_0)$, $(y_1-y_0)$ es una solución de la ecuación homogénea $ax+by=0$, y por la proposición anterior, debe suceder que $x_1-x_0=-ka$ y $y_1-y_0=kb$ con $k$ un entero. Así, $x_1=x_0-ka$ y $y_1=y_0+kb$, como queríamos.

$\square$

Ejemplo. Determina todas las soluciones a la ecuación diofantina $12x+13y=1$.

Solución. Por inspección, una solución es $x=-1$, $y=1$. Los coeficientes de las variables son primos relativos. Por la proposición anterior, todas las soluciones son de la forma $-13k-1$, $12k+1$ donde $k$ es un entero arbitrario.

$\square$

Resumimos todo lo obtenido en el siguiente resultado.

Teorema. Sean $a$ y $b$ enteros distintos de $0$ y $c$ un entero. Consideremos la ecuación diofantina $ax+by=c$. Si $M:=\text{MCD}(a,b)$ no divide a $c$, entonces la ecuación no tiene solución. Si sí, podemos usar el algoritmo de Euclides para encontrar una solución $x_0,y_0$. El resto de las soluciones son de la forma $x_0-ka’$, $y_0+kb’$, en donde $a’=a/M$, $b’=b/M$ y $k$ es cualquier entero.

Veamos un ejemplo en el que juntamos todo lo que ya sabemos.

Ejemplo. Determina todas las soluciones a la ecuación diofantina $21x-35y=14$.

Solución. Los coeficientes de las variables no son primos relativos, pues su máximo común divisor es $7$. Tenemos que $7$ divide a $14$, así que la ecuación sí tiene soluciones y son las mismas que las de la ecuación $3x-5y=2$. Por inspección, una solución es $x=-1, y=-1$. Así, todas las soluciones a esta ecuación (y por lo tanto a la original), son de la forma $x=5k-1, y=3k-1$.

$\square$

Tarea moral

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

  • Resuelve el Ejemplo 2
  • En todos los ejemplos, verifica que las soluciones obtenidas en efecto son soluciones del sistema original.
  • ¿Para cuántos enteros $c$ entre $1$ y $100$ se tiene que la ecuación lineal $21x+18y=c$ tiene solución $x,y$ en enteros?
  • Sólo hemos visto ecuaciones diofantinas lineales en dos variables. Sin embargo, con lo visto hasta ahora puedes argumentar por qué la ecuación diofantina $91x+14y-70z=100$ no tiene soluciones en enteros. ¿Por qué?
  • Investiga acerca de la ecuación pitagórica $x^2+y^2=z^2$.

Seminario de Resolución de Problemas: Primos y factorización única

[latexpage]

Introducción

En entradas anteriores hablamos de divisibilidad y de aritmética modular. Ahora platicaremos de las bloques que nos ayudan a construir a todos los enteros de manera multiplicativa: los números primos. Lo que dice el teorema fundamental de la aritmética es que todo número es producto de primos «de manera única». Tanto la teoría de números primos, como este teorema, son de gran ayuda en la resolución de problemas

Como en entradas anteriores, el enfoque no es demostrar los resultados principales de la teoría. Esto se hace en un curso de Álgebra Superior II o en uno de Teoría de Números. La idea de la entrada es ver aplicaciones de estos resultados en situaciones concretas.

Números primos

Un entero es primo si tiene exactamente dos divisores positivos. El $1$ no es primo pues su único divisor es él mismo. Pero $2$, $17$ y $31$ sí son primos. De aquí y el algoritmo de la división, si $p$ es primo y $a$ es un entero, entonces $p\mid a$ o $\MCD{p,a}=1$.

Proposición 1. Si $p$ es un número primo que divide al producto de enteros $ab$, entonces $p\mid a$ ó $p\mid b$.

Demostración. Si $p$ no divide a $a$, entonces $\MDC(p,a)=1$, así que existe una combinación lineal entera $pn+am=1$. Multiplicando esta combinación por $b$, tenemos que $pbn+abm=b$. Como $p$ divide a $pbn$ y a $ab$, entonces divide a $b$.

$\square$

Problema. Muestra que si $p$ es un primo que divide a $123456^{654321}$, entonces $p$ divide a $123456$.

Sugerencia pre-solución. Aquí $123456$ y $654321$ no tienen nada de especial. Generaliza el problema y procede por inducción en el exponente.

Solución. Sea $a$ un entero, $n$ un entero positivo y $p$ un primo. Vamos a mostrar por inducción en $n$ que si $p\mid a^n$, entonces $p\mid a$. Para $n=1$ la conclusión es inmediata. Supongamos el resultado cierto para $n$. Si $p\mid a^{n+1}$, por la Proposición 1 tenemos que $p\mid a$ (en cuyo caso terminamos), o que $p\mid a^n$ (en cuyo caso terminamos por hipótesis inductiva). El problema se resuelve tomando $a=123456$ y $n=6543321$.

$\square$

Extendiendo la idea del problema anterior, se puede demostrar la siguiente proposición.

Proposición 2. Si $p$ es primo, $a$ un entero y $n$ un entero positivo tales que $p\mid a^n$, entonces $p^n\mid a^n$.

Teorema fundamental de la aritmética

Todo número es producto de primos de manera única. Más específicamente

Teorema (teorema fundamental de la aritmética). Sean $a$ un entero positivo. Entonces existe un único $n$, únicos primos $p_1<\ldots<p_n$ y exponentes $\alpha_1,\ldots,\alpha_n$ tales que $$a=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}.$$

La idea de la demostración es factorizar y factorizar. Si $n$ está expresado como producto de primos, ya está. Si no, hay uno de sus factores que no es primo y entonces se puede factorizar en dos números menores. Para probar la unicidad se usa la Proposición 1.

Veamos algunas aplicaciones del teorema fundamental de la aritmética.

Problema. Muestra que $\sqrt[3]{7}$ es un número irracional.

Sugerencia pre-solución. Procede por contradicción suponiendo que es racional para igualarlo a una fracción y eleva al cubo.

Solución. Si no fuera irracional, lo podríamos expresar como una fracción, digamos $\sqrt[3]{7}=\frac{a}{b}$ con $a$ y $b$ enteros. De aquí, $7b^3=a^3$. En la factorización en primos de $a^3$ y $b^3$ tenemos una cantidad múltiplo de $3$ de factores $7$. Así, en el lado derecho tenemos una cantidad mútiplo de $3$ de factores $7$ (por la Proposición 2), pero en el lado izquierdo no. Esto es una contradicción a la unicidad de la factorización en primos.

$\square$

Es posible que en un problema tengamos que usar el teorema fundamental de la aritmética repetidas veces.

Problema. Determina todos los enteros positivos $n$ para los cuales $2^8+2^{11}+2^n$ es un número entero al cuadrado.

Sugerencia pre-solución. Trabaja hacia atrás y usa notación adecuada. Intenta encontrar una diferencia de cuadrados.

Solución. Vamos a comenzar suponiendo $m^2=2^8+2^{11}+2^n$. De aquí, \begin{align*}
2^n&=m^2-2^8(1+2^3)\\
&=m^2-(3\cdot 2^4)^2\\
& =(m+48)(m-48).
\end{align*}

Por la unicidad del teorema fundamental de la aritmética, cada uno de los números $m+48$ y $m-48$ tienen que ser potencias de $2$, digamos $m+48=2^a$ y $m-48=2^b$ con $a>b$ y $a+b=n$. Además tenemos que $$2^b(2^{a-b}-1)=96=2^5\cdot 3.$$

Como $2^{a-b}-1$ es impar, de nuevo por la unicidad de la factorización en primos debemos tener que $2^{a-b}-1=3$, y por lo tanto que $2^b=2^5$. De aquí, $b=5$ y $a-b=2$, y así $a=7$. Por lo tanto, el único candidato es $n=5+7=12$.

Ya que trabajamos hacia atrás, hay que argumentar o bien que los pasos que hicimos son reversibles, o bien que $n$ en efecto es solución. Hacemos esto último notando que $2^8+2^{11}+2^{12}=2^8(1+2^3+2^4)=2^8\cdot 5^2$ que en efecto es un número cuadrado.

$\square$

Fórmulas que usan el teorema fundamental de la aritmética

Sean $a$ y $b$ números enteros positivos y $P={p_1,\ldots,p_n}$ el conjunto de números primos que dividen a alguno de $a$ o $b$. Por el teorema fundamental de la aritmética, existen exponentes $\alpha_1,\ldots,\alpha_n$ y $\beta_1,\ldots,\beta_n$, tal vez algunos de ellos cero, tales que \begin{align*}
a&=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots\cdot p_n^{\alpha_n}\\ b&=p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_n^{\beta_n}. \end{align*}

Por ejemplo, si $a=21, b=28$, entonces $P={2,3,7}$, $a=2^0 3^1 7^1$ y $b=2^2 3^0 7^1$.

Proposición 3. Se tiene que $a$ divide a $b$ si y sólo si para todo primo $p_i$ se tiene que $\alpha_i\leq \beta_i$.

Problema. ¿Cuántos múltiplos de $108$ hay que sean divisores de $648$?

Sugerencia pre-solución. Factoriza en primos a $108$ y a $648$ y usa la Proposición 3.

Solución. Tenemos que $108=2^23^3$ y que $648=2^3\cdot 3^4$. Por la Proposición 3, un número que funcione debe ser de la forma $2^a3^b$ con $2\leq a \leq 3$ y con $3\leq b \leq 4$. Así, $a$ tiene $2$ posibilidades y $b$ también, de modo que hay $2\cdot 2=4$ números que cumplen.

$\square$

Una consecuencia inmediata de la Proposición 3 anterior es la fórmula para el número de divisores de un entero en términos de los exponentes de su factorización en primos.

Proposición 4. El entero $a$ tiene $(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_n+1)$ divisores positivos.

Problema. Determina cuántos enteros hay entre $1$ y $10000$ que tienen $49$ divisores positivos.

Sugerencia pre-solución. Usa la fórmula de la Proposición 4 para trabajar hacia atrás y ver qué forma debe tener un entero que cumple lo que se quiere. Divide en casos para que el producto se $49$.

Solución. Tomemos $a$ un entero y $p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}$ su factorización en primos. Por la Proposición 4, necesitamos que $(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_n+1)=49$.

A la izquierda tenemos puros números mayores o iguales que $2$. El número $49$ tiene como únicos divisores a $1$, $7$ y $49$. De esta forma, sólo hay dos casos posibles:

  • El número $a$ tiene sólo un divisor primo y $a=p_1^{48}$
  • El número $a$ tiene dos divisores primos y $a=p_1^6p_2^6$

El primer caso es imposible, pues $p_1$ sería por lo menos $2$ y $2^{48}>2^{20}=(1024)^2>(1000)^2>10000$. Para el segundo caso, recordemos que $p_2>p_1$ en la factorización en primos. Si $p_2\geq 5$, entonces como $p_1\geq 2$, tendríamos $a\geq (2\cdot 5)^6 = 1000000>10000$, así que esto no es posible.

La única otra posibilidad es $p_2=3$ y por lo tanto $p_1=2$. En este caso obtenemos al número $a=(2\cdot 3)^6=6^6=46656$, que sí cae en el intervalo deseado. Así, sólo hay un número como el que se pide.

$\square$

La factorización en primos también sirve para encontrar máximos comunes divisores y mínimos comunes múltiplos.

Proposición 4.  Se pueden calcular $\MCD{a,b}$ y $\mcm{a,b}$ como sigue:
\begin{align*}
\text{MCD}(a,b)&=p_1^{\min(\alpha_1,\beta_1)}\cdot p_2^{\min(\alpha_2,\beta_2)}\cdot\ldots\cdot p_n^{\min(\alpha_n,\beta_n)}\\
\text{mcm}(a,b)&=p_1^{\max(\alpha_1,\beta_1)}\cdot p_2^{\max(\alpha_2,\beta_2)}\cdot\ldots\cdot p_n^{\max(\alpha_n,\beta_n)}.
\end{align*}

Volvamos a ver un problema que ya habíamos resuelto con anterioridad.

Problema. Demuestra que $\MCD{a,b}\mcm{a,b}=ab$.

Sugerencia pre-solución. Usa la Proposición 4. Puedes argumentar algunos pasos por simetría.

Solución. Expresemos a $a$ y $b$ en su factorización en primos como lo discutimos arriba. Al multiplicar $\MCD{a,b}$ y $\mcm{a,b}$, el exponente de $p_i$ es $\min(\alpha_i,\beta_i)+\max(\alpha_i,\beta_i)=\alpha_i\beta_i$. Este es el mismo exponente de $p_i$ en $ab$. Así, ambos números tienen la misma factorización en primos y por lo tanto son iguales.

$\square$

Más ejemplos

Puedes ver más ejemplos del uso de esta teoría en la Sección 3.3 del libro Problem Solving through Problems de Loren Larson.

Si $p$ es primo, entonces todo entero $n$ que no sea múltiplo de $p$ tiene inverso módulo $n$. Esto se usa en los teoremas de Fermat y Wilson. También hay una entrada con ejercicios de estos teoremas resueltos en video.