El Método de Factorización de Fermat
El método de factorización de Fermat se basa en la observación de que la búsqueda de factores de un número entero impar (notemos que los números pares son fácilmente reconocibles y por lo tanto se les puede dividir entre dos fácilmente encontrando factores) es equivalente a obtener soluciones enteras para $x,y$ de la ecuación
(1)En efecto, si $n$ es una diferencia de cuadrados, este se puede expresar como el producto de la suma por la diferencia de tales números. Si $n=ab$ con $a\ge b\ge 1$ entonces podemos escribir:
(2)y como $n$ es impar cada uno de los números $a,b$ son impares y por lo tanto $\left( \frac{a-b}{2} \right)$ y $\left( \frac{a+b}{2}\right)$ son enteros no negativos.
Iniciamos la búsqueda para la factorización con posibles valores de $x,y$ que satisfagan la ecuación anterior Eq.(1) o equivalentemente la ecuación
(3)determinando al menor entero $k$ que cumpla con que $k^2\ge n$ y entonces buscar ahora en los enteros:
(4)hasta que llegemos a un valor $m\ge \sqrt n$ tal que $m^2-n$ sea un cuadrado perfecto.
El proceso tiene que terminar pues de hecho en algún punto llegareíamos a:
(5)que es la representación de $n$ que nos da la factorización trivial $n=n\cdot 1$. Si se llega a este punto sin que hayamos encontrado una diferencia que sea un cuadrado, entonces $n$ es un numero primo.
Ejemplo: Fermat uso su método para factorizar
(6)con tan solo 11 pazos. Comparemos esto con el tedioso proceso de hacer 4850 divisiones por los primos impares que hay hasta 44021. Con este métdo vemos que en realidad NO necistamos conocer todos los primos menores que $\sqrt n$ para factorizar a $n$.
Ejercicio: Factorizar al número n=119143.
por lo que tenemos la factorización:
(7)El método de Fermat es más efectivo cuando los dos factores de $n$ estan cercanos, pues en este caso un cuadardo aprecera pronto. Por ejemplo, supongamos que $n = 23449$ entonces el menor cuadrado que es mayor que $n$ es $154^2$, por lo que la sucesión de números de la forma $k^2-n$ inicia con:
$154^2- 23449 = 23716-23449 = 267$ y luego
por lo que los factores de $23449$ son $(155+24)(155-24) = 179\cdot 131$.
Notemos que cuando estamos en búsqueda de cuadrados en a sucesión $k^2-n$ podemos rápidamente descartar algunos números pues sabemos que todo cuadrado termina en 0,1,4,5,6,9 (basta trabajar los cuadrados módulo 10). Esto nos permite descartar ya varios valores en el ejemplo anterior, conservando a 1266, 1961 y 4761. Si ahora calculamos los dos últimos dígitos de todos los cuadrados vemos que esto nos da como posibilidades:
por lo que el entero 1266 puede ser eliminado. Como 61 sí aparece como posibilidad para dos últimos dígitos de un cuadrado, es tan solo necesario determinar si 1961 o 4761 son cuadrados, el último no lo es, pero $4761 = 69^2$.
Algoritmo en Python:
# -*- coding: utf-8 -*-
#!/usr/bin/env python
# Este programa factoriza a un número impar n usando el método de Fermat de diferencia de cuadrados.
import math as m
rescuad=[0,1,4,5,6,9]
def factoriza(n,p=1):
if n%2 == 0:
print '%d no es impar' % n
exit()
else:
k=int(m.sqrt(n))+1
# print k
while True:
if int(m.sqrt(k**2-n))%10 in rescuad:
if int(m.sqrt(k**2-n)) != m.sqrt(k**2-n):
k+=1
else:
x = int(k)
y = int(m.sqrt(k**2-n))
# print x,y
return p,x+y,x-y
else: k+=1
while True:
n=raw_input('Escribe el numero impar a factorizar o q para salir: ')
if n=='q': exit()
n=int(n)
a,b,c = factoriza(n)
print n,'= %d * %d * %d' % (a,b,c)
if b==1 or c==1:
print '%d es primo' % n
El Pequeño Teorema de Fermat
Teorema (Fermat). Si $p$ es un primo y $p\nmid a$, entonces $a^{p-1}\equiv 1\pmod p$.
Demostración: Consideremos a los enteros positivos múltiplos de $a$ módulo $p$:
(9)Todos estos números son no congruentes por pares módulo $p$ por lo que forman un juego completo de residuos módulo $p$ y por lo tanto son congruentes módulo $p$ al juego reducido $0,1,2, \ldots, p-1$ en otro posible orden. Si multiplicamos todos estos neumeros entonces tenemos que:
(10)de donde
(11)como $p\nmid (p-1)!$ lo podemos cancelar en la ecuación anterior y por lo tanto $a^{p-1}\equiv 1 \pmod p$.
Corolario: Si $p$ es primo, entonces $a^p\equiv a \pmod p$ para todo entero $a$.
Hay varias demostraciones del pequeño teorema de Fermat y me gustaría presentar otra prueba pues también tiene su importancia en el método usado.
Lema: El coeficiente binomial $\binom pk \equiv 0 \pmod p$ para $1\le k\le p-1$.
Demostración: como $\binom pk=\frac{p!}{k!(p-k)!}$ tenemos que $p! = k! \binom pk$ y entonces $p\mid k!\binom pk$ pero $p\nmid k!$ por lo que $p\mid \binom pk$.
Ahora para dar una segunda demostración tenemos que por el binomio de Newton:
(12)ahora el resultado puede probarse fácilmente por inducción en $a$.
Ejemplo: Calcular $5^{32}$ módulo $11$.
Otro uso del teorema de Fermat es para probar si un número es primo o no. En efecto si la congruencia $a^b\equiv a \pmod b$ no es verdadera para alguna elección de $a$, entonces $b$ no es primo. Por ejemplo si $n=117$ tenemos que $2^{117} = (2^7)^{16}2^5 \equiv 44 \not\equiv 2 \pmod 117$ por lo que $117$ no es primo (de hecho 117=13\cdot 9).
El converso del teorema de Fermat es falso, es decir no es verdad que si $a^n\equiv a\pmod n$ para todo $a$ implica que $n$ es primo:
Lema Si $p,q$ son primos distintos tale que $a^p\equiv a \pmod q$ y $a^q \equiv a \pmod p$, entonces $a^{pq}\equiv a \pmod{ pq}$.
Ahora notemos que $2^{340} \equiv 1 \pmod 341$ pues tenemos que $341 = 11\cdot 31$. Ahora notemos que
(13)por lo que
(14)y entonces cancelando un factor de 2 obtenemos $2^{340}\equiv 1 \pmod 341$ y por lo tanto el coverso del teorema de Fermat es falso.
El teorema de Wilson
Teoream (Wilson): Si $p$ es un número primo, entonces $(p-1)!\equiv -1 \pmod p$.
Demostración: El caso $p=2,3$ es trivial. Supongamos entonces que $p> 3$. Sopongamos que $a$ es cualquiera de los enteros $1,2,3,\ldots, p-1$ y consideremos la congruencia $ax\equiv 1 \pmod p$. Como $(a,p)=1$ esta congruencia tiene una única solución, es decir existe un entero $a'$ con $1\le a' \le p-1$ tal que $aa'\equiv 1 \pmod p$. Como $p$ es primo tenemos que $a\equiv a' \pmod p$ si y sólo si $a=1 \lor a=-1$.
Si excluimos a los enteros 1 y $p-1$ y agrupamos al resto de los enteros $2,3, \ldots, p-2$ en parejas de la forma $a,a'$ con $a\ne a'$ y multiplicamos obtenemos:
y por lo tanto si multiplicamos por $(p-1)$ obtenemos:
(16)Podemos ilustrar esta demostración por ejemplo tomando a $p=13$ y reproduciendo los cálculos anteriores.
El converso del teorema de Wilson es también verdad:
Proposición: Si $(n-1)!\equiv -1 \pmod p$ entonces $n$ es primo.
En efecto, si $n$ no es primo entonces $n=dd'$ $d,d'$ divisores no triviales. Estos divisorees aprarecen como factores de $(n-1)!$ por lo que $n\mid (n-1)!$. pero por hipótesis $(n-1)!\equiv -1 \pmod n$ por lo que $0\equiv -1 \pmod n$ que es una contradicción.
Teorema: La congruencia cuadrática $x^2+1 \equiv 0 \pmod p$, con $p$ primo impar, tiene solución si y sólo si $p\equiv 1 \pmod 4$.
Si $a$ es una solución, entnces por el teorema de Fermat:
(17)Tomando las distintes posibilidades para p obtenemos que $p\equiv 1 \pmod 4$. Conversamente en el producto $(p-1)!$ se tiene que:
(18)por lo que al hacer el producto obtenemos que
(19)y si $p=4k+1$ entonces $a=\left( \frac{p-1}2 \right)!$ es una solución de la congruencia cuadrática.
Ejemplo: Reproducir la prueba para $p=13$.
Corolario: Existe una infinidad de números compuestos de la forma $n! + 1$.
Sin embago en converso de este corolario es una pregunta avierta. Es decir, no se sabe si hay una infinidad de primos de la forma $n! + 1$. Para $1\le n \le 100$ se sabe que sólo $n=1,2,3,11,27,37,41,73$ y $33$ generan a un primo de la forma $n!+1$.
El Teorema de Euler
Lema: Si $n>1$ y $(a,n)=1$ entonces
(20)Teorema: Si $n$ es un entero positivo y $(a,n)=1$ entonces $a^{\phi(n)}\equiv 1 \pmod n$.
La demostración sigue la misma idea que la demostración para $p$.
Ejemplo: Ilustrar este resulatdo para $n=9$.
Como corolario se tiene el teorema de Fermat.
Ejemplo: Usar el teorema de Euler para reducir $3^{256} \pmod 100$. Es decir para encontrar los dos últimos deigitos.
Segunda prueba del teorema de Euler:
La prueba es por inducción sobre $k$ en la siguiente afirmación:
Afirmación: $a^{\phi(p^k)}\equiv 1 \pmod{p^k}$. Suponiendo el teorema de Fermat. Para el paso inductivo notar que $\phi(p^{k+1}) = p\phi(p^k)$ entonces:
Ahora usar el hecho de que $\phi$ es multiplicativa para concluir con toda generalidad.
Ejercicio: Demuestra que un número $n$ que es primo relativo con $10$ divide a un número formado por puros unos.
Como $(9n,10)=1$ entonces $10^{\phi(9n)}\equiv 1\pmod{9n}$ y entonces existe $k$ entero tal que $kn=(10^{\phi(9n)}-1)/9$.
Propiedades de la funcíon $\phi$ de Euler.
Teorema: Para $n\ge 1$ se tiene que
(22)Los números entereos entre $1 \land n$ pueden ser dividos enclases de la manera siguiente: Si $d$ es un divisor positivo de $n$, podemos al entero $m$ en la clase $S_d$ si $(m,n)=d$. Es decir:
(23)Como $(m,n)=d if and only if(m/d,n/d)=1$, tenemos que el número de elementos en la clase $S_d$ es igual al número de enteros que no exceden a $n/d$ y que son primos relativos con $n/d$, es deicr, es igual a $\phi(n/d)$. Como cada uno de los enteros entre $1,\ldots, n$ está en una y sólo una clase $S_d$ obtenemos la fómrula:
(24)Ejercicio: Da una prueba distinta usando el hecho de que $\phi$ es multiplicativa.
Ejercicio: Da una prueba distinta usando el hecho de que $\sum_{d\mid n}\mu(d)/d = \prod(1-1/p_i)$ donde el producto es sobre todos los distintos primos que divide a $n$.
Teorema: Para $n>1$ la suma de los entermos menores que $n$ que son primos relativos con $n$ es $\frac 12 n \phi(n)$, es decir:
(25)Demostración: Si $a_1, a_2, \ldots, a_{\phi(n)}$ son los enteros positivos menores que $n$ y primos relativos con $n$, entonces como $(a,n)=1$ if and only if $(n-a,1)=1$ tenemos:
(26)y entonces $2\sum_k a_k = n \phi(n)$.
Ejemplo: Tomar $n=30$.
Teorema: Para todo entero positivo $n$ se tiene que $\phi(n) = n \sum_{d\mid n} \mu(d)/d$
Demostración: Usar la fórmula de inversión de moebius. Alternativamente usar que $\mu(d)/d$ es multiplicativa.