Proving $n^{17} \equiv n \;(\text{mod}\; 510)$ As the title says, prove that $n^{17} \equiv n \;(\text{mod}\; 510)$. I know that you need to use the fact that $510 = 2\cdot 3\cdot 5\cdot 17$, but I can't figure out how. I've found a similar question on this forum, but can't make any sense out of the answer
 A: Note that $\,p_i\!-1 = 1,2,4,16\mid 16 = e\!-\!1,\,$ so the following theorem $(\Leftarrow)$ applies
Theorem $ $ (Korselt's Carmichael Criterion) $\ $ For  $\rm\:1 < e,n\in \Bbb N\:$ we have
$$\rm \forall\, a\in\Bbb Z\!:\ n\mid a^e\!-a\ \iff\  n\ \ is\ \  squarefree, \  and \ \ p\!-\!1\mid e\!-\!1\ \, for\  all \ primes\ \ p\mid n\qquad$$
Proof $\ \ (\Leftarrow)\ \ $ Since a squarefree natural divides another iff all its 
prime factors do, we need only show $\rm\: p\mid a^e\!-\!a\:$ for each prime $\rm\:p\mid n,\:$ i.e. that $\rm\:a \not\equiv 0\:\Rightarrow\: a^{e-1}\equiv 1\ \ ( mod\ p),\:$ which, since $\rm\:p\!-\!1\mid e\!-1,\:$ follows from $\rm\:a \not\equiv 0\:\Rightarrow\: \color{#c00}{a^{p-1} \equiv 1}\ \ ( mod\ p),\:$ by little Fermat, i.e. 
$$\rm e\!-\!1 = k(p\!-\!1)\,\Rightarrow\, a^{\large e-1} \equiv (\color{#c00}{a^{\large p-1}})^{\large k}\equiv \color{#c00}1^{\large k}\equiv 1\qquad\qquad $$
$(\Rightarrow)\ \ $ Given that $\rm\: n\mid a^e\!-\!a\:$ for all $\rm\:a\in\Bbb Z,\:$ we must show 
$$\rm (1)\ \  n\,\ is\ squarefree,\quad  and\quad  (2)\ \  p\mid n\:\Rightarrow\: p\!-\!1\mid e\!-\!1$$ 
$(1)\ \ $ If $\rm\,n\,$ isn't squarefree then
$\rm\,1\neq a^2\!\mid n\mid a^e\!-\!a \Rightarrow\:  a^2\mid a\:\Rightarrow\!\Leftarrow$ $\rm\: (note\ \ e>1\: \Rightarrow\: a^2\mid a^e)$
$(2)\ \ $ Let $\rm\ a\ $ be a generator of the multiplicative group of $\rm\:\Bbb Z/p.\:$
Thus $\rm\ a\ $ has order $\rm\:p\!-\!1.\:$ Now  $\rm\:p\mid n\mid a\,(a^{e-1}\!-\!1)\:$  but $\rm\:p\nmid a,\:$ thus $\rm\: a^{e-1}\!\equiv 1\,\ ( mod\ p),\:$ therefore $\rm\:e\!-\!1\:$ must be divisible by $\rm\:p\!-\!1,\:$ 
the order of $\rm\ a\,\ (mod\ p).\quad$ QED 
A: You would need Fermat's little theorem which states that for any natural $a$ and a prime $p$, $p$ divides $a^p - a$.
$n^{17} - n = n(n-1)(n+1)(n^2+1)(n^4+1)(n^8+1).$
Now note that:


*

*$n(n-1) = n^2 - n$.

*$n(n-1)(n+1) = n^3 - n$.     

*$n(n-1)(n+1)(n^2 + 1) = n^5 - n$.

*$n(n-1)(n+1)(n^2+1)(n^4+1)(n^8+1)=n^{17} - n.$


Can you finish the proof?
A: Well, the post you mention outlines the process somewhat. Apply Fermat's Little Theorem to acquire the following:
$n^{17} \equiv n$ (mod 17)
Now let's establish $n^{17} \equiv n$ (mod 2). This is pretty simple: $n^{17}-n = n(n^{16}-1)$, and either $n$ will be even or $n^{16}-1$ will be even. Hence, $2\, |\, n^{17} - n$, and so $n^{17} \equiv n$ (mod 2).
We note that $17 \equiv 1$ (mod 2), and so from a generalization of Fermat's Little Theorem, $n^{17} \equiv n^1$ (mod 3).
We note that $17 \equiv 1$ (mod 4), and so from the same generalization, $n^{17} \equiv n^1$ (mod 5).
Now we have all the ingredients. Since $2 \,|\, n^{17} - n$, $3\, | \,n^{17} - n$, $5\,|\,n^{17}-n$, and $17 \,|\, n^{17}-n$, it must be that $510 = 2 \cdot 3 \cdot 5 \cdot 17 \,| \,n^{17} - n$.
