Demostrar que para cualquier entero positivo $a,$ $a^{561} \equiv a \pmod{561}.$

Question

Demostrar que para cualquier entero positivo $a$ , $a^{561} \equiv a \pmod{561}$ . (Por lo tanto, $561$ es un pseudoprimo con respecto a cualquier base. Dicho número se llama número de Carmichael).

Obviamente, esto funciona para $1$ pero ¿cómo puedo encontrar $2^{561}$ o cualquier otro número a la potencia de $561?$

Answer 1

El teorema de Fermat implica que $a^{(p-1)n+1} \equiv a \bmod p$ para todos los primos $p$ , todos $a$ y todos $n$ .

Desde $561=3\cdot 11\cdot 17$ , aplique esto a $(p,n)=(3,560/2)$ , $(11,560/10)$ , $(17,560/16)$ .

Answer 2

Desde $$a^{561}-a=\left(a^{560}-1\right)a,$$ vemos que $a^{561}-a$ es divisible por $a^3-a$ , por $a^{17}-a$ y por $a^{11}-a$ que dice que es divisible por $3$ , por $17$ y por $11$ que dice que es divisible por $3\cdot17\cdot11=561$ .

Answer 3

Números compuestos $n>1$ que satisfacen $a^{n-1}\equiv 1\pmod{n}$ para todos los enteros positivos $a$ con $\gcd(a,n)=1$ se llaman $\color{red}{\text{Carmichael numbers}}.$

Existe un criterio necesario y suficiente para que un número entero positivo sea Número de Carmichael conocido como el El criterio de Korselt

$\color{red}{\text{Korselt's Criterion:}}$ Un número entero positivo $n>1$ es un número de Carmichael si y sólo si $(1)$ $n$ es libre de cuadrados, $(2)$ para cualquier divisor primo $p$ de $n$ , $p-1\mid n-1$

Prueba: Pruebe usted mismo. Una aplicación fácil del Teorema Chino del Resto

Se puede comprobar, con este criterio, que $561$ es un Número de Carmichael . De hecho, son infinitamente numerosos.