Número de Carmichael

Número de Carmichael

En teoría de números, los números de Carmichael son los números compuestos n que satisfacen la congruencia

a^{n-1} \equiv 1 \pmod n para todo entero \ a primo relativo con \ n.

Los números de Carmichael reciben su nombre por el matemático Robert Daniel Carmichael que los estudió.

Relevancia

El Teorema de Fermat establece que si p es un número primo, entonces la congruencia

a^{p-1}\equiv 1 \pmod p

es válida para cualquier número \ a no divisible por \ p.

Dicho de otra manera, si a no es divisible por p entonces p divide a ap-1-1:

\ p | a^{p-1}-1.

Para determinar si un número n es primo o no, se escoge un número a que sea primo relativo con n y se calcula \ a^{n-1}\pmod n. Si el resultado es diferente a 1, el número es compuesto con toda certeza.

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. Estos números se denominan pseudoprimos en la base a, por lo que la prueba propuesta no es en realidad una verdadera prueba de primalidad.

Los números de Carmichael son entonces números pseudoprimos en cualquier base: son los números para los que la prueba anterior falla para cualquier elección de base que sea primo relativo con el número dado.

Ejemplos

Los primeros números de Carmichael son

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633,\ldots

El primer número de Carmichael es

n=561 = 3\times 11\times 17,

por lo que no es primo. Sin embargo

\ a^{560}-1 es divisible por 561 para cualquier \ a coprimo con 561.

Referencias

  • Carmichael, R. D. (1912) On composite numbers P which satisfy the Fermat congruence a^{P-1}\equiv 1\bmod P. Am. Math. Month. 19 22–27.
  • Erdős, Paul (1956). On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4, 201 –206.
  • Alford, Granville and Pomerance (1994). There are infinitely many Carmichael numbers, Ann. of Math. 140(3), 703–722.

Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • Número de Carmichael — En teoría de números, un número de Carmichael N es un número entero positivo compuesto tal que, para todo entero positivo a coprimo con N, aN es congruente con a módulo N ( …   Enciclopedia Universal

  • Número de Poulet — En matemáticas, específicamente en teoría de números, un número n, se denomina fermatiano o de Poulet si cumple la congruencia Un ejemplo de estos números son todos los primos impares, los números de Fermat, los números de Mersenne, los números… …   Wikipedia Español

  • Número de Giuga — Un Número de Giuga es un número compuesto n tal que cada uno de sus factores primos pi es un divisor de . Otra comprobación es si la congruencia es cierta, siendo B un número de Bernoulli. Los números Giuga reciben su nombre del matemático… …   Wikipedia Español

  • Número primo — Un número primo es un número natural mayor que 1, que tiene únicamente dos divisores distintos: él mismo y el 1. Se contraponen así a los números compuestos, que son aquellos que tienen algún divisor natural aparte de sí mismos y del 1. El número …   Wikipedia Español

  • Número de Knödel — Dado un número natural n, un número de Knödel es un número compuesto m con la propiedad de que cada i < m coprimo con m satisface . El conjunto de todos los números naturales dado n se denomina el conjunto de los números de Knödel Kn. Nótese… …   Wikipedia Español

  • Teorema de Carmichael — Este artículo habla del teorema de Carmichael de los números de Fibonacci. También existe otro teorema de Carmichael aplicado a la definición recursiva de la función de Carmichael. El teorema de Carmichael, nombrado así en honor al matemático… …   Wikipedia Español

  • Función de Carmichael — En Teoría de números, la función de Carmichael de un entero positivo n, denotada λ(n), se define como el menor entero m tal que cumple: para cada número entero a coprimo con n. En otras palabras, define el exponente del grupo multiplicativo de… …   Wikipedia Español

  • Rashad Carmichael — Données générales Nom complet Rashad Bernard Carmichael Nationalité  États Unis Date de naissance …   Wikipédia en Français

  • Eddie Carmichael — Liste des personnages de l’univers de Harry Potter Cet article est une liste référençant les personnages de l univers de Harry Potter. Les personnages principaux peuvent être identifiés dans les articles suivants : Harry Potter Ron Weasley… …   Wikipédia en Français

  • Test de primalidad — El 39º número primo de Mersenne era el mayor conocido hasta la fecha de creación de este artículo. La cuestión de la determinación de si un número n …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”