En la clase de hoy trataremos los números primos. Llamaremos número primo a todo número entero \(p\in\mathbb{Z}\), \(p>1\), que no tiene divisores más que el 1 y el mismo.
El siguiente resultado es muy importante:
Teorema: Si \(p\in\mathbb{Z}\) es primo y \(p|(a\,b)\), entonces, ó \(p|a\) ó \(p|b\)
Para determinar los primos podemos utilizar la criba de Eratóstenes.
Ejercicio: ¿Cuántos números primos hay menores de 50?
Como vemos al utilizar la criba de Eratóstenes, observamos que los números primos aparecen constantemente; en efecto, el teorema siguiente lo justifica.
Teorema: El conjunto de los números primos es infinito
Terminamos con el Teorema fundamental de la aritmética:
Teorema: Todo entero positivo se puede representar de forma única, salvo el orden, como producto de factores primos.
Este resultado es muy importante y nos ofrece consecuencias muy prácticas:
Teorema: Sean \(n,m\in \mathbb{Z}-\{-1,0,1\}\), con \(n=p_1p_2\cdots p_r\) y \(m=q_1q_2\cdots q_s\), sus descomposiciones en factores primos, y \(u_j\in\{-1,1\}\forall j\in\mathbb{N}\). Entonces, \[n|m\Leftrightarrow \forall i\in\{1,\ldots, r\}\exists j\in\{1,\ldots, r\}\,|\, p_i=q_ju_j\]
Como hemos visto, la criba de Eratóstenes nos proporciona un método para obtener los números primos menores de cierto valor. Así, si queremos conocer si un número, \(n\), es primo o compuesto, basta con dividirlo con los primos menores a \(n\), aunque no tenemos porque dividirlo por todos los \(p<n\):
Teorema: Si un entero positivo es compuesto, entonces existe un primo \(p<\sqrt{n}\) que lo divide.
Ejercicio: Determinar el siguiente número primo a 512.
Ejercicio: ¿Cuántos números primos hay entre 512 y 535?
Propiedades
Además,podemos obtener las siguientes propiedades:
Teorema: Sean \(n\in \mathbb{Z}^+\), con \(n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}\) la descomposición en factores primos con \(p_i\neq p_j\forall j\neq i,\alpha_i\in\mathbb{N}\forall i\in\{1,\ldots, r\}\). Entonces
- (Divisores de un número compuesto) los divisores de \(n\) son los términos del producto \[(1+p_1+p_1^2+\ldots+p_1^{\alpha_1})\cdots(1+p_r+p_r^2+\ldots+p_r^{\alpha_r})\]
- (Número de divisores de un número compuesto) \[(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_r+1)\]
- (Suma de los divisores de un número compuesto) \[\frac{p_1^{\alpha_1+1}-1}{p_1-1}\,\frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdots\frac{p_r^{\alpha_r+1}-1}{p_r-1}\]
- (Producto de los divisores de un número compuesto) el producto de los divisores de \(n\) es \(\sqrt{n^k}\) siendo \(k\) el número de divisores de \(n\).
Ejercicio: ¿Cuántos divisores que terminen en 7 tiene el número 2541?
Ejercicio: ¿Cuántos divisores que contengan el 7 tiene el número 9537?
Ejercicio: ¿Cuántos divisores tiene el número 11106?
Teorema: Sean \(m,n\in \mathbb{Z}^+\), con \(m=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}\cdot q_1\) y \(n=p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k}\cdot q_2\) la descomposición en factores primos comunes, siendo \(q_1\neq q_2\) y sin factores comunes. Entonces
\[{\displaystyle \textbf{mcd}(m,n)=p_{1}^{\operatorname {min} (\alpha _{1},\beta _{1})}\cdots p_{k}^{\operatorname {min} (\alpha _{k},\beta _{k})}}\]
Ejemplo: Calcular \(\textbf{mcd}(2800733^3,255255^3)\)
Ejemplo: Calcular \(\textbf{mcd}(86295023265, 20311518645)\)
Teorema: Dados dos números enteros \({\textstyle a=\prod _{p}p^{a_{p}}}\) y \({\textstyle b=\prod _{p}p^{b_{p}}}\), entonces \[\mathbf{mcm}(a,b)=\prod _{p}p^{\max(a_{p},b_{p})}.\]
Ejemplo: ¿Cuál es el valor de \(\mathbf{mcm}(356,248)\)?
Función \(\varphi\) de Euler
Recordemos que la función \(\varphi\) de Euler a una función, \(\varphi:\mathbb{Z}^+\to\mathbb{Z}^+\), dada por \[\varphi (n)=|\{m\in\mathbb{Z}^+|m<n, \mathbf{mcd}(n,m)=1\}|.\]
Esta función cumple propiedades muy interesantes, como
- Si \(p\) es primo, \(\varphi (p)=p-1\)
- Si \(p\) es primo, \(\varphi (p^\alpha)=p^{\alpha -1}(p-1)\)
- Si \(mcd(n,m)=1\) es \(\varphi (nm)=\varphi (n)\varphi (m)\)
Ejemplo: Calcular \(\varphi(939176)\)
Producto de Euler
La descomposición de un número entero en sus factores primos nos permite formular un resultado práctico para calcular la función \(\varphi\)
Si \(n\in\mathbb{Z}\) es \({\displaystyle n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}}\), entonces \[\varphi (n)=n\prod_{i=1}^r\left(1-\frac{1}{p_i}\right)\]
Ejemplo: Calcular \(\varphi(1433671404)\)
Factorización de Fermat
La factorización de un número se ha abordado extensamente; nosotros daremos una iniciación con un método sencillo, que servirá de introducción para los alumnos que deseen seguir explorando este campo.
El método de factorización de Fermat se basa en la representación de un número natural impar como la diferencia de dos cuadrados:
\[n=a^2-b^2.\]
Esa diferencia se puede factorizar algebraicamente como \((a+b)(a-b)\); si ninguno de esos factores es igual a 1, se trata de una factorización propia de \(n\).
El procedimiento consiste en buscar un número \(x\) mayor que \(\sqrt{n}\) y tal que \(x^2-n\) sea un cuadrado perfecto; entonces habremos encontrado la descomposición buscada.
Veamos un ejemplo. Tomemos el número \(n=10058886427\); la parte entera de su raíz cuadrada es \(\left \lfloor \sqrt{n} \right \rfloor=100293\).
- Sea \(x=100293+1\), calculamos \(\left \lfloor x^2-n \right \rfloor=9\)
- Como 9 es un cuadrado perfecto, la descomposición que buscamos es:
- \(n=x^2-9\); es decir, \(n=(x-3)(x+3)\)
- Por tanto, \(n=100291\cdot 100297\)
Este ejemplo tiene una sola iteración, pero puede complicarse más todavía:
- \(n=10233712469\)
- \(x=\left \lfloor \sqrt{n} \right \rfloor+1=101162\)
- Repetimos
- Es decimal \(\sqrt{x^2-n}\) entonces
- \(x=x+1\)
- en caso contrario
- \(n=(x-\sqrt{x^2-n})\cdot (x+\sqrt{x^2-n})\)
- Es decimal \(\sqrt{x^2-n}\) entonces
En este ejemplo:
- \(\sqrt{101162^2-n}=194.35\)
- \(x=101163 \to \sqrt{101163^2-n}=490\)
- \(n=(101163-490)\cdot (101163+490)=100673\cdot 101653\)
El algoritmo funciona más rápido cuando \(n\) es producto de dos factores cercanos; en otro caso puede alargarse. Veamos otros ejemplo:
- \(n=2615836543\)
- \(\sqrt{n}=51145.25\)
- \(x_1=51145+1 \to \sqrt{x_1^2-n}=277.0794\)
- \(x_2=51146+1 \to \sqrt{x_2^2-n}=423.1619\)
- \(x_3=51147+1 \to \sqrt{x_3^2-n}=530.4347\)
- \(x_4=51148+1 \to \sqrt{x_4^2-n}=619.4013\)
- \(x_5=51149+1 \to \sqrt{x_5^2-n}=697.1062\)
- \(x_6=51150+1 \to \sqrt{x_6^2-n}=766.9798\)
- \(x_7=51151+1 \to \sqrt{x_7^2-n}=831\)
- \(n=(51152-831)\cdot (51152+831)=50321\cdot 51983\)
En este caso 50321 es primo, pero 51983 no. Ahora habría que factorizar este número.
Ejercicio: Sea \(p\) el mayor factor primo de 10342962241, ¿cuánto es \(\mathbf{mod}(p,83)\)
Factorización con Casio
La calculadora Casio fx-991 permite factorizar números. Veamos un ejemplo:
Sin embargo, como nos dice, en el modo COMP, puede factorizar un entero positivo de no más de 10 dígitos en factores primos. Veamos el procedimiento para resolver algunos de los ejercicios cuando tenemos más de 10 dígitos
Sea \(N=(d_kd_{k-1}d_{k-2}\cdots d_{1}d_{0})_{10}\) expresado en base decimal. Así \(N\) se puede poner en formato \[N=(d_kd_{k-1}d_{k-2}\cdots d_{m+1})_{10}\, 10^{m+1}+ (d_{m}\cdots d_{0})_{10}\]
Por la propiedades de divisibilidad que conocemos, si \[a|(d_kd_{k-1}d_{k-2}\cdots d_{m+1})_{10}\] y \[a|(d_{m}d_{m-1}\cdots d_{0})_{10},\] entonces \(a|N\), y por tanto \(a\) es un factor de \(N\). De este modo podemos buscar factores que nos faciliten reducir los dígitos hasta que quepan en la calculadora.
Ejercicio: Encontrar la factorización de 930823188559.
Números primos en la web
Veamos algunas páginas sobre números primos interesantes:
Factorización con Casio ClassWiz
Congruencias
Utilicemos wiki para definir qué entendemos por congruencia:
un término usado en la teoría de números, para designar que dos números enteros \(a\) y \(b\) tienen el mismo resto al dividirlos por un número natural \(m\neq 0\), llamado el módulo; esto se expresa utilizando la notación \[a \equiv b \pmod{m}.\]
Esta definición nos permitía construir clases de equivalencia de números enteros, también llamadas clases de congruencia, que pueden ser dotadas de un sistema aritmético. Los conjuntos de estas clases son los conocidos \(\mathbb{Z}_n\), que poseen estructura de anillo.
Propiedades:
- Si \({\displaystyle a\equiv b{\pmod {m}}}\), entonces también \({\displaystyle b\equiv a{\pmod {m}}}\)
- Si \({\displaystyle a\equiv b{\pmod {m}}}\) y \({\displaystyle b\equiv c{\pmod {m}}}\), entonces también \({\displaystyle a\equiv c{\pmod {m}}}\).
- Si \(a\) es coprimo con \(m\) y \({\displaystyle a\equiv b{\pmod {m}}}\), entonces \(b\) también es coprimo con \(m\).
- Si \({\displaystyle a\equiv b{\pmod {m}}}\) y \(k\) es un entero, entonces también se cumple
- \({\displaystyle a(\pm)k\equiv b(\pm)k{\pmod {m}}}\),
- \({\displaystyle ka\equiv kb{\pmod {m}}}\),
- \({\displaystyle a^{k}\equiv b^{k}{\pmod {m}}\qquad k>0}\)
- Si además \(k\) es coprimo con \(m\) entonces podemos encontrar un entero \({\displaystyle k^{-1}\,}\), tal que \({\displaystyle kk^{-1}\equiv 1{\pmod {m}}}\)
- En este caso tiene perfecto sentido hablar de la división y podemos decir que \({\displaystyle {\frac {a}{k}}\equiv {\frac {b}{k}}{\pmod {m}}}\), entendiendo que \({\displaystyle a/k=ak^{-1}\,}\).
Como consecuencia de lo anterior, si tenemos dos congruencias con igual módulo:
\({\displaystyle a\equiv b{\pmod {m}}}\) y \({\displaystyle c\equiv d{\pmod {m}}}\),
podemos sumarlas, restarlas o multiplicarlas de forma que también se verifican las congruencias
- \({\displaystyle a+c\equiv b+d{\pmod {m}}}\)
- \({\displaystyle ac\equiv bd{\pmod {m}}}\)
Todas estas y más las tenéis en estos enlaces:
Observar que encontrar el resto del algoritmo de la división de \(a\) dividido entre \(b\) es equivalente a resolver la ecuación de congruencias \[a\equiv X{\pmod {b}}\]
Ejercicio: Encontrar el resto de la división de 93082318855943 entre 5.
Ejemplo: ¿En qué cifra termina \(123^{321}\)?
El inverso en \(\mathbb{Z}_n\)
Uno de nuestros cometidos será resolver la ecuación de congruencias \[aX\equiv b {\pmod {m}}\]
Recordemos que \(\mathbb{Z}_n\) es un anillo y solo si \(n\) es primo todos los elementos tiene inverso. Así un problema será saber si un elemento de \(\bar{b}\in\mathbb{Z}_n \) tiene inverso. Esto solo se nos cumplirá en el caso de que \(\mathbf{mcd}(b,n)=1\). Pero lo importante es saber cómo calcular el inverso.
Proposición: Si \(s,r\in\mathbb{Z}\) son tales que \(ns+ar=\mathbf{mcd}(n,a)=1\), entonces \[ar\equiv 1{\pmod {n}}.\]
Este resultado nos dice que la solución de Bezout nos ofrece el inverso en \(\mathbb{Z}_n\) para los elementos no divisibles por \(n\).
Ejemplo: Calcular el inverso de \(\bar{7}\) en \(\mathbb{Z}_{201} \)
Para encontrar este inverso necesitamos la solución de Bézout, que podemos hallar mediante el algoritmo extendido de euclides. Así pues, la ecuación \[aX\equiv b {\pmod {n}}\] donde \(\mathbf{mcd}(a,n)=1\) tendrá solución y esta vendrá dada por \[X\equiv a^{-1}b {\pmod {n}},\] donde \(a^{-1}\) es el inverso de \(a\) en \(\mathbb{Z}_{n}\).
Recordad, si \(n\) es primo entonces \(\mathbb{Z}_{n}\) es un cuerpo y siempre existirá el inverso. Si \(n\) no es primo entonces solo existira el inverso si \(\mathbf{mcd}(a,n)=1\).
Ejemplo: Resolver \(5X\equiv 52 {\pmod {53}}\)
| Ejercicio: ¿Para cuántos valores de \(0< c<10\) la ecuación diofántica \(54x+24y=c\) tiene solución entera? |