# Show that $n^{13} - n$ is divisible by 2, 3, 5, 7, 13 [duplicate]

Show that $$n^{13} - n$$ is divisible by $$2, 3, 5, 7$$ and $$13$$

I know this has been asked before, but the other approaches seem different than mine.

Here is my approach:

Look at $$n^{13} -n \equiv 0 \bmod k$$ where $$k$$ is some positive integer. Then we can write $$n^{13} \equiv n \bmod k$$ which has the form $$n^{\phi(k) + 1} \equiv n \bmod k$$. So we can solve for $$k$$ that satisfies the equation $$\phi(k) + 1 = 13$$. The first few $$k$$ that satisfy this are $$13, 21,$$ and $$26$$. Since $$21 = 3 * 7$$ and $$26 = 2 *13$$, this shows that $$n^{13} -n$$ is divisible by $$2,3,7,13$$.

My trouble is proving this for $$5$$. I have checked the Euler totient function up to $$k= 100,000,000$$ with Mathematica. There is not an integer on this list that is divisible by $$5$$. The list seems to have stopped growing after $$42$$: $$\{ 13, 21, 26, 28, 36, 42 \}$$. Why does this method not seem to work for $$5$$?

For each $$p\in\{2,3,5,7,13\}$$, $$p-1\ | \ 12$$ thus if $$(n,p)=1$$, then $$n^{12}\equiv 1 \ \text{ (mod }p)$$ by Fermat's little theorem and $$n^{13}\equiv n^{12}\cdot n\equiv n \ \ \text{ (mod }p).$$ For $$(n,p)=p$$, it is obvious $$n^{13}-n\equiv 0 \text{ (mod }p)$$.

• Nice. I was looking for a way to prove all of them at once rather than case by case. – pmac Feb 27 '19 at 20:15

$$n^{13}-n = n(n^{12}-1)= n (n^4-1)(n^8+n^4+1)$$

Now $$5\mid n^5-n$$ by Fermat little theorem.

• Thanks. Any insight as to why my method does not work (at least practically) for $5$? – pmac Feb 27 '19 at 20:07

Hint: $$n^{13}-n=n \left( n-1 \right) \left( {n}^{2}+n+1 \right) \left( 1+n \right) \left( {n}^{2}-n+1 \right) \left( {n}^{2}+1 \right) \left( {n}^{4}- {n}^{2}+1 \right)$$

• +1 For you my dear friend – Aqua Feb 27 '19 at 20:29

The equation $$\phi(n)=12$$ indeed has only six solutions, see this duplicate:

Find all natural numbers n such that $\phi(n)$=12

Consequently we have only the numbers $$n=13,21,26,28,36,42$$, where none is divisible by $$5$$. This is the reason.