# $a^{13} \equiv a \bmod N$ - proof of maximum $N$

From Fermat's Little Theorem, we know that $a^{13} \equiv a \bmod 13$. Of course $a^{13} \equiv a \bmod p$ is also true for prime $p$ whenever $\phi(p) \mid 12$ - for example, $a^{13} = a^7\cdot a^6 \equiv a\cdot a^6 = a^7 \equiv a \bmod 7$.

So far I have that the largest $N$ for which all $a^{13} \equiv a \bmod N$, is $N = 2\cdot 3\cdot 5\cdot 7\cdot 13 = 2730$

Can someone either put together an elegant proof of this, or find and prove a different limit?

• Looks right. Any such $N$ has to be square-free. So we want the largest square-free $N$ such that $\lambda(N)$ (the Carmichael function) divides $12$. – André Nicolas May 14 '15 at 16:40

## 3 Answers

Suppose that $a^{13}\equiv a\pmod N$, for every $a\in\mathbb Z$, then for every prime $p$ deviding $N$ we have $a^{13}\equiv a\pmod p$, but we have a primitive root $g$ modulo $p$, hence $$g^{12}\equiv1\pmod p$$ which means that $p-1|12$, so $p\in\{2,3,5,7,13\}$. Hence the prime factors of $N$ are from the above set. Now I prove that the number $N$ is squarefree...

Suppose not, then for some prime $p|N$ we have $a^{13}\equiv a\pmod {p^2}$ by choosing $a=p$ we get a contradiction, hence the number $N$ must be squarefree and by above arguments the number $2730$ is the largest possible value for $N$.

Putting in $a=2$, we get that $N$ divides $2^{13} - 2 = 2 \cdot 3^2 \cdot 5 \cdot 7 \cdot 13$.

On the other hand, putting in $a=3$, we get that $N$ divides $3^{13} - 3 = 2^4 \cdot 3 \cdot 5 \cdot 7 \cdot 13 \cdot 73$.

Hence $N$ must divide $2 \cdot 3 \cdot 5 \cdot 7 \cdot 13 = 2730$.

• So that's a good argument to show the limit... just need to add in the proof that 2730 is valid... – Joffan May 14 '15 at 16:44

Put $\ \color{#c00}{e = 13}\$ below.  For a simple proof of the theorem see this answer.

Theorem  (Korselt's Pseudoprime Criterion) $\$ For $\rm\:1 < e,n\in \Bbb N\:$ we have $$\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$$

The primes $\rm\,p\,$ such that $\rm\,p\!-\!1\mid\color{#0a0}{ 12}\,$ are $\,2,3,5,7,13\,$ so the largest such $\rm\,n\,$ is their product.

• @Joffan It's a hint if you don't peek at the linked proof! In any case, this shows how the argument works in general. – Bill Dubuque May 14 '15 at 17:33