# 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

• Do you know that $n^{17}$ is congruent to $n$ modulo $2$, $3$, $5$, and $17$ separately? – Lubin Feb 17 '15 at 4:48

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?

• Ah, I think I see it this way. Using FLT, we show that 2, 3, 5, and 17 divide $n^{17} - n$. Thus, 510 divides it, so $n^{17} \equiv n \;(\text{mod}\; 510)$ – wlyles Feb 17 '15 at 5:58

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

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