Vamos a terminar la Teoría de números con dos problemas muy relacionados: la factorización de números y el estudio de la primalidad.
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 rápido que \(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)\)
Podéis ver más de este método en:
- Método de factorización de Fermat
- LA FACTORIZACIÓN DE FERMAT
- El método de Fermat y el número 100 895 598 169
Ejercicio: ¿Cuántas interaciones son necesarias para factorizar los siguientes números? a) 10536179707, b) 10961461409, c) 10953920297, d) 10930461001
Test de Primalidad
El segundo problema de los que añadimos como apéndice a la Teoría de números es el de los test de primalidad.
Con anterioridad, vimos el teorema de Euler que nos determina el inverso, cuando existe, de un elemento en \(\mathbb{Z}_n\). Este teorema tenía un antecedente, que se conoce como el Teorema pequeño de Fermat:
Si \(a,p\in\mathbb{Z}\) con \(p\) primo y \(p\) no divide a \(a\), entonces \[a^{p-1}\equiv 1\pmod{p}\]
Consecuentemente si dado un número \(n\) que no divida a \(a\) se cumple \[a^{n-1}\not\equiv 1\pmod{n}\]
implicaría que \(n\) no es primo, pues de lo contrario incumpliría el Teorema pequeño de Fermat.
Pues bien, este resultado lo podemos utilizar para chequear si un número es primo. Este test se denomina test de primalidad de Fermat.
Disponemos de un resultado que nos garantiza si un número es primo, el Teorema de Wilson:
El número \(n\in\mathbb{Z},\, n>1\) es primo si, y sólo, si \[(n-1)!\equiv -1\pmod{n}\]
El problema es el cómputo del factorial que es treméndamente costoso para número muy grandes. Por ese motivo utilizamos los test de primalidad.
Un test de primalidad (o chequeo de primalidad) es un algoritmo que, dado un número de entrada \(n\), no consigue verificar la hipótesis de un teorema cuya conclusión es que \(n\) es compuesto.
El test de Fermat nos propone buscar si un número es compuesto probando las igualdades
\[\begin{align*}2^{n-1}&\equiv 1\pmod{n},\\ 3^{n-1}&\equiv 1\pmod{n},\\ 5^{n-1}&\equiv 1\pmod{n},\\ &\ldots\\ a^{n-1}&\equiv 1\pmod{n},\end{align*}\] hasta encontrar un valor de \(1<a<n\) para el que no se cumpla.
Lo que ocurre es que podemos encontrar valores que verifican la igualdad siempre y no por ello son primos: son los conocidos números de Carmichael, o pseudoprimos.
Hay más test de este tipo, son conocidos como test probabilísticos de primalidad, pues no nos garantizan que es primo; más bien ofrecen una probabilidad de que sea primo.
El test de Fermat puede mejorarse utilizando el criterio de Euler:
Si \(p\in\mathbb{Z}\) es primo y \(p\) no divide a \(a\), entonces \[a^\frac{p-1}{2}\equiv 1\pmod{p}\, \mbox{ ó, } a^\frac{p-1}{2}\equiv -1\pmod{p}\]
El test probabilístico de primalidad más utilizado es el de Rabin-Miller, basado en el resultado:
Sea \(p\in\mathbb{Z},\, p>1\) primo impar y \(k,m\in\mathbb{Z}\), tales que \(p-1=2^km\), com \(m\) impar. Entonces, para todo entero positivo \(a\), menor que \(p\), se cumple al menos una de los siguientes resultados:
- Algún número de la serie \(a^{2^km},a^{2^{k-1}m},\ldots,a^{m}\) es congruente con -1 módulo \(p\).
- \(a^m\equiv 1\pmod{p}\)
Ejercicio:Sean \(4x-11y+z=43\), \(7x+3y+5z=8\) y \((x_s,y_{s},z_s)\) la solución talque \(\text{min}\{0<z_{s}\}\). ¿Cuánto suma \(x_{s}+z_{s}\)? |