# 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

#### Solutions Collecting From Web of "Proving $n^{17} \equiv n \;(\text{mod}\; 510)$"

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:

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

Can you finish the proof?

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$$

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

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$.