Número de Fermat

número natural obtenido por (2^(2^n))+1

Un número de Fermat, nombrado en honor a Pierre de Fermat, quien fue el que formuló e investigó estos números, es un número natural de la forma , donde n es natural. De particular interés son los números primos de Fermat.

Primo de Fermat
Nombrado por Pierre de Fermat
No. de términos conocidos 5
No. conjeturado de términos 5
Subsecuencia de Números de Fermat
Primeros términos 3, 5, 17, 257, 65537
Mayor término conocido 65537
índice OEIS A019434

Pierre de Fermat conjeturó que todos los números naturales de la forma

con n natural eran números primos (después de todo, los cinco primeros términos, 3 (n=0), 5 (n=1), 17 (n=2), 257 (n=3) y 65537 (n=4) lo son), pero Leonhard Euler probó que no era así en 1732. En efecto, al tomar n=5 se obtiene un número compuesto:

4294967297 es el número más pequeño que, siendo número de Fermat, no es primo.

Actualmente, solo se conocen cinco números primos de Fermat, que son los que ya se conocían en tiempos del propio Fermat, y, a fecha de enero de 2009 solo se conoce la factorización completa de los doce primeros números de Fermat (desde n=0 hasta n=11). Estas son algunas de las conjeturas que existen hoy día sobre estos números:

  1. ¿Solo hay cinco números primos de Fermat (3, 5, 17, 257 y 65537)?
  2. ¿Existen infinitos primos de Fermat?

Algunos números de Fermat y su factorización editar

Los nueve primeros números de Fermat son los siguientes:

F0 = 21 + 1 = 3
F1 = 22 + 1 = 5
F2 = 24 + 1 = 17
F3 = 28 + 1 = 257
F4 = 216 + 1 = 65.537
F5 = 232 + 1 = 4.294.967.297
= 641 × 6.700.417
F6 = 264 + 1 = 18.446.744.073.709.551.617
= 274.177 × 67.280.421.310.721
F7 = 2128 + 1 = 340.282.366.920.938.463.463.374.607.431.768.211.457
= 59.649.589.127.497.217 × 5.704.689.200.685.129.054.721
F8 = 2256 + 1 = 115.792.089.237.316.195.423.570.985.008.687.907.853.269.984.665.640.564.039.457.584.007.913.129.639.937
= 1.238.926.361.552.897 × 93.461.639.715.357.977.769.163.558.199.606.896.584.051.237.541.638.188.580.280.321

Propiedades de los números de Fermat editar

  1. Un número de Fermat es igual al producto de todos los anteriores más 2. Esto se puede demostrar por inducción como sigue:
    • Si n=1, es verdad: F1 = F0 + 2 (5 = 3 + 2).
    • Si se cumple para k igual a n-1, se cumple para n:
 
 
 
 
  1. Corolario de la propiedad anterior: Ningún número de Fermat puede ser la suma de dos números primos. Como todos los números de Fermat son impares, uno de los sumandos debe ser 2. Entonces, el otro tendrá que ser, o bien 1 (en el caso de F0 = 3) o bien el producto de todos los anteriores... pero precisamente al ser un producto de números naturales no puede ser primo.
  2. Dos números de Fermat distintos siempre son primos entre sí (es decir, no tienen ningún factor común). Se sabe que Fn = F0·F1·...·Fn-1 + 2. Como todos los números de Fermat son impares (y por tanto 2 no puede ser un factor común), se concluye que Fn no es divisible por ninguno de los factores de los anteriores números de Fermat. Un corolario de esto es una demostración de la infinitud de los números primos (ver artículo).
  3. Carl Friedrich Gauss demostró que existe una relación entre la construcción de polígonos regulares con regla y compás y los números primos de Fermat: un polígono regular de n lados puede ser construido con regla y compás si y solo si n es, o bien una potencia de 2, o bien el producto de una potencia de 2 y primos de Fermat distintos entre sí.
  4. Todo número compuesto de Fermat   se puede descomponer en factores primos de la forma k·2n+2 + 1, con k entero positivo.
  5. La representación hexadecimal de un número de Fermat mayor es especialmente sencilla: para cada n mayor o igual que 2, Fn = 10...01hex, donde hay 2n-2 - 1 ceros.

Relación con polígonos construibles editar

 
Número de lados de polígonos construibles conocidos que tienen hasta 1000 lados (negrita) o recuento de lados impar (rojo)

Carl Friedrich Gauss desarrolló la teoría de los períodos gaussianos en su obra Disquisitiones arithmeticae y formuló una suficiente para la constructibilidad de polígonos regulares. Afirmó que esta condición también era necesaria, pero nunca publicó una prueba. Pierre Wantzel dio una prueba completa de la necesidad en 1837. El resultado se conoce como Teorema de Gauss-Wantzel:

Se puede construir un polígono regular de n lados con regla y compás si y solo si n es el producto de una potencia de 2 y primos de Fermat distintos: en otras palabras, si y solo si n es de la forma n = 2kp1p2...ps, donde k, s son enteros no negativos y los pi son primos de Fermat distintos.

Un entero positivo n tiene la forma anterior si y solo si su totiente φ(n) es una potencia de 2.

Aplicaciones de los números de Fermat editar

Generación de números pseudoaleatorios editar

Los números primos de Fermat son particularmente útiles para generar secuencias pseudoaleatorias de números en el rango 1 ... N, donde N es una potencia de 2. El método más común utilizado es tomar cualquier valor semilla entre 1 y P − 1, donde P es un primo de Fermat. Ahora, se multiplica este valor por un número A, que es mayor que la raíz cuadrada de P y es una raíz primitiva módulo P (es decir, no es un residuo cuadrático). Luego, se toma el resultado módulo P. El resultado es el nuevo valor para el generador de números pseudoaleatorios:

  (véase generador lineal congruencial, RANDU)

Esto es útil en informática, ya que la mayoría de las estructuras de datos tienen miembros con valores posibles 2X. Por ejemplo, un byte tiene 256 (28) valores posibles (0–255). Por lo tanto, para llenar un byte o bytes con valores aleatorios, se puede usar un generador de números aleatorios que produzca valores de 1 a 256, tomando el byte el valor de salida −1. Los números primos de Fermat muy grandes son de particular interés en el cifrado de datos por este motivo. Este método produce solo valores pseudoaleatorios, ya que después de P − 1 repeticiones, la secuencia se repite. Un multiplicador mal elegido puede hacer que la secuencia se repita antes de P − 1.

Véase también editar

Enlaces externos editar