2
$\begingroup$

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

$\endgroup$
0
3
$\begingroup$

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

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

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

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

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

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

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.