$a^{13} \equiv a \bmod N$ a prueba de máximo $N$

Question

A partir de Fermat Poco Teorema, sabemos que $a^{13} \equiv a \bmod 13$. De curso $a^{13} \equiv a \bmod p$ también es cierto para el prime $p$ siempre $\phi(p) \mid 12$ - por ejemplo, $a^{13} = a^7\cdot a^6 \equiv a\cdot a^6 = a^7 \equiv a \bmod 7$.

Hasta ahora me tiene que el mayor $N$ para que todos los $ a^{13} \equiv a \bmod N$ $N = 2\cdot 3\cdot 5\cdot 7\cdot 13 = 2730$

Alguien puede poner juntos una elegante prueba de esto, o buscar y probar diferentes límite?

Answer 1

Supongamos que $a^{13}\equiv a\pmod N$, para cada $a\in\mathbb Z$, a continuación, para cada prime $p$ deviding $N$ tenemos $a^{13}\equiv a\pmod p$, pero tenemos una raíz primitiva $g$ modulo $p$, por lo tanto $$ g^{12}\equiv1\pmod p $$ lo que significa que $p-1|12$, lo $p\in\{2,3,5,7,13\}$. Por tanto, los factores primos de a $N$ desde el anterior conjunto. Ahora puedo comprobar que el número de $N$ es squarefree...

Supongamos que no, entonces para algunos prime $p|N$ tenemos $a^{13}\equiv a\pmod {p^2}$ eligiendo $a=p$ obtenemos una contradicción, por lo tanto el número de $N$ debe ser squarefree y por los argumentos anteriores, el número de $2730$ es el valor más grande posible para $N$.

Answer 2

Poniendo en $a=2$, obtenemos que $N$ divide $2^{13} - 2 = 2 \cdot 3^2 \cdot 5 \cdot 7 \cdot 13$.

Por otro lado, la puesta en $a=3$, obtenemos que $N$ divide $3^{13} - 3 = 2^4 \cdot 3 \cdot 5 \cdot 7 \cdot 13 \cdot 73$.

Por lo tanto $N$ debe dividir $2 \cdot 3 \cdot 5 \cdot 7 \cdot 13 = 2730$.

Answer 3

Poner $\ \color{#c00}{e = 13}\ $ por debajo. $ $ Para una simple prueba del teorema ver esta respuesta.

Teorema $ $ (Korselt del Pseudoprime Criterio) $\ $ $\rm\:1 < e,n\in \Bbb N\:$ hemos $$\rm \forall\, a\in\Bbb Z\!:\ n\mid a^{\large\color{#c00}{e}}\!-a\ \iff\ n\ is\ squarefree,\ \ and \ \ p\!-\!1\mid \color{#0a0}{e\!-\!1}\ \, for\ all \ primes\ \ p\mid n$$

Los números primos $\rm\,p\,$ tal que $\rm\,p\!-\!1\mid\color{#0a0}{ 12}\,$ $\,2,3,5,7,13\,$ por lo que el más grande de $\rm\,n\,$ es su producto.