teorema de Fermat

Fermat, teorema de

 
mat. Teorema postulado por P. de Fermat según el cual dado un entero a, no divisible por un número primo, p, se cumple que a p-1 - 1 es divisible por p.
Ejemplos ?
Puesto que 3 16 ≡ 1 (mod 17) — como indica el Pequeño teorema de Fermat —, se deduce que, si n es un entero, entonces 3 4+16 n ≡ 3 4 × (3 16) n ≡ 13 × 1 n ≡ 13 (mod 17).
Las propiedades más profundas acerca de los números se estudian en la teoría de números, campo matemático que nos ha dado resultados populares como el último teorema de Fermat.
En 1992 surgieron otra clase algoritmos basados en curvas elípticas, pero que tampoco eran deterministas. Finalmente, en 1999 Manindra Agrawal estudió una variante del pequeño teorema de Fermat.
Con base en esta caracterización, en el año 2002 presentaron su algoritmo en el artículo PRIMES is in P. El algoritmo AKS está basado en una generalización del pequeño teorema de Fermat hacia los polinomios.
El Teorema de Fermat establece que si p es un número primo, entonces la congruencia es válida para cualquier número a no divisible por p.
Si el último teorema de Fermat fuese falso, entonces existiría una curva elíptica tal que no puede asociarse con ninguna forma modular, y por lo tanto la conjetura de Taniyama-Shimura sería falsa.
Desafortunadamente si el resultado es 1 no es posible asegurar a ciencia cierta que el número n es primo, ya que el inverso del teorema de Fermat no es válido: existen números compuestos a tales que a n-1 equiv 1 pmod n.
La historia de la comprobación probabilista de primalidad tiene sus raíces en Pierre Fermat, quien postuló en 1640 el Pequeño teorema de Fermat Sea n primo.
Utilización del pequeño teorema de Fermat para comprobar la primalidad: en el caso de F5, a Fermat le hubiera bastado con ver que existe un a tal que 1≤a≤F 5 -1 tal que a (F 5 - 1) mod F 5 1) (a =3).
Con estas premisas, se puede desarrollar el siguiente algoritmo: función primo(n) principio a:=uniforme(1..n-1); si a n-1 mod n = 1 entonces devuelve verdadero sino devuelve falso fsi fin Sabemos que n es compuesto cuando la función devuelve el valor falso, por el teorema de Fermat.
En cambio, cuando el algoritmo devuelve el valor verdadero no podemos afirmar que n sea primo. Necesitaríamos el recíproco y el contrapositivo del teorema de Fermat.
Sin embargo, a la vista de la definición de f (x), del pequeño teorema de Fermat se sigue que cada elemento 1, 2, .., p − 1 es una raíz de f (x) (por lo que, a fortiori, es una raíz de f (x) módulo p).