Pregunta relacionada con los pseudoprimes y los números de Carmichael

Question

Sabemos por el pequeño teorema de Fermat que si $m$ es un primo, entonces para cualquier $n \in \mathbb{Z}$ entonces $$n^m \equiv n (mod \ m).$$ Me preguntaba si había un compuesto $m$ que cumpla esta condición? (Tal vez esta condición es equivalente a ser un número de Carmichael, pero no estaba seguro...) Gracias.

Answer 1

Necesitamos demostrar dos cosas: (i) si $m$ es compuesto y $a^m\equiv a\pmod{m}$ para todos $a$ entonces $m$ es un número de Carmichael y (ii) Si $m$ es un número de Carmichael, entonces $a^m\equiv a \pmod{m}$ para todos $a$ .

Demostrar (i) es fácil. Supongamos que $a^m\equiv a\pmod{m}$ para todos $a$ . En particular, supongamos que $a$ es relativamente primo de $m$ . Entonces por división obtenemos que $a^{m-1}\equiv 1\pmod{m}$ . Desde $m$ es compuesto, se deduce que $m$ es un número de Carmichael.

Demostrar (ii) es más difícil. Necesitamos el hecho de que si $m$ es un número de Carmichael, entonces $m$ es libre de cuadrados. Las pruebas se pueden encontrar con bastante facilidad mediante la búsqueda, por lo que omitimos la prueba.

Así $m$ puede expresarse como un producto $p_1p_2\cdots p_t$ donde el $p_i$ son primos distintos.

Supongamos primero que $a$ no es divisible por $p_i$ . Entonces $a^{p_i-1}\equiv 1\pmod{p_i}$ . Según el criterio de Korselt (véase Wikipedia), tenemos $p_i-1$ divide $m-1$ . De ello se deduce que $a^{m-1}\equiv 1\pmod{p_i}$ y, por lo tanto $a^m\equiv a \pmod{p_i}$ .

Supongamos a continuación que $a$ es divisible por $p_i$ . Entonces $a^m\equiv a\pmod{p_i}$ ya que ambos son congruentes con $0$ .

Hemos demostrado que $a^m\equiv a\pmod{p_i}$ para todos los primos $p_1$ a $p_t$ . Desde el $p_i$ son distintos, se deduce que $a^m\equiv a\pmod{m}$ .

Answer 2

Claro que sí. Es un Número Carmichael por definición. $561$ es el menor número de Carmichael.