# How to show that $2730\mid n^{13}-n\;\;\forall n\in\mathbb{N}$

Show that $2730\mid n^{13}-n,\;\;\forall n\in\mathbb{N}$

I tried, $2730=13\cdot5\cdot7\cdot3\cdot2$

We have $13\mid n^{13}-n$, by Fermat's Little Theorem.

We have $2\mid n^{13}-n$, by if $n$ even then $n^{13}-n$ too is even; if $n$ is odd $n^{13}-n$ is odd.

And the numbers $5$ and $7$, how to proceed?

• It seems like a factorization of $n^{13}-n$ should do it. – user99680 Dec 6 '13 at 21:12
• – Martin Sleziak Aug 7 '15 at 10:03
• By FLT $5|n^5 - n$ , $7|n^7 - n$ and $3|n^3 - n$. $n^13 - n = n(n^12 - 1) = n(n^6 + 1)(n^6 - 1) = n(n^6+1)(n^3 + 1)(n^3 - 1) = n(n^6+1)(n^3 + 1)(n^2 + n + 1)(n^2 - 1) = n(n^6+1)(n^3 + 1)(n^2 + n + 1)(n+1) (n-1)$. $n^7 - n = n(n^6 - 1)$ is a factor. $n^3 -n = n(n^2 - 1)$ is a factor. 5? well if $n = i \mod 5$ if i = 0 5|n if i = 1 5|n - 1. If i = 4 5|n+1. If i = 2 or 3 5|n^6+1. – fleablood Jul 5 '16 at 19:33

Like user99680,

Using Fermat's Little Theorem $p|(n^p-n)$ where $n$ is any integer and $p$ is any prime

$\displaystyle n^{13}-n=n(n^{12}-1)=n\left((n^6)^2-1\right)=n(n^6-1)(n^6+1)=(n^7-n)(n^6+1)$ which is divisible by $\displaystyle n^7-n$ which is always divisible by $7$ for all integer $n$

Similarly, $\displaystyle n^{13}-n=n(n^{12}-1)=n\left((n^4)^3-1\right)$ $\displaystyle=n(n^4-1)(n^8+n^4+1)=(n^5-n)(n^8+n^4+1)$ which is divisible by $\displaystyle n^5-n$ which is always divisible by $5$ for all integer $n$

• You have a typo: $P|(n^p-n)$ should be $p|(n^p-n)$ – PM 2Ring Aug 7 '15 at 10:29

HINT:

$$n^{13} \equiv n^5 \cdot n^5 \cdot n^3 \equiv n \cdot n \cdot n^3 \equiv n^5 \equiv n \pmod 5$$

$$n^{13} \equiv n^6 \cdot n^7 \equiv n \pmod 7$$

Also you've missed $3$ as prime factor. But that should be easy.

One Approach

If $k\mid n$, then $x^{k+1}-x\mid x^{n+1}-x$. Therefore, $$\begin{array}{} 13&\mid&n^{13}-n\\ 7&\mid&n^7-n&\mid&n^{13}-n&\text{since }6\mid12\\ 5&\mid&n^5-n&\mid&n^{13}-n&\text{since }4\mid12\\ 3&\mid&n^3-n&\mid&n^{13}-n&\text{since }2\mid12\\ 2&\mid&n^2-n&\mid&n^{13}-n&\text{since }1\mid12\\ \end{array}$$ Since the factors are all relatively prime, we have that $$2730=2\cdot3\cdot5\cdot7\cdot 13\mid n^{13}-n$$

Another Approach

Decomposing into a sum of combinatorial polynomials \begin{align} n^{13}-n &=2730\left[\vphantom{\binom{n}{2}}\right.3\binom{n}{2}+575\binom{n}{3}+22264\binom{n}{4}+330044\binom{n}{5}\\ &+2458368\binom{n}{6}+10551552\binom{n}{7}+28055808\binom{n}{8}+47786112\binom{n}{9}\\ &+52272000\binom{n}{10}+35544960\binom{n}{11}+13685760\binom{n}{12}+2280960\binom{n}{13}\left.\vphantom{\binom{n}{2}}\right]\\ \end{align}

• Your second approach is what I would have tried, but seeing your result, I’m glad I didn’t try it. – Lubin Aug 7 '15 at 12:06
• Evaluating $n^{13}-n$ at $n=0$ gives $c_0$, the coefficient of $\binom{n}{0}$. Evaluating $n^{13}-n-c_0\binom{n}{0}$ at $n=1$ gives $c_1$, the coefficient of $\binom{n}{1}$. Evaluating $n^{13}-n-c_0\binom{n}{0}-c_1\binom{n}{1}$ at $n=2$ gives $c_2$, the coefficient of $\binom{n}{2}$. etc. Other than the large numbers, it is pretty simple. – robjohn Aug 7 '15 at 12:34

Notice that $n^{13}-n =n(n^{12}-1)=n(n^6+1)(n^6-1)=n(n^6+1)(n^3+1)(n^3-1)=...$

Note that $$n^{13} \equiv n^5 \cdot n^5 \cdot n^3 \equiv n \cdot n \cdot n^3 \equiv n^5 \equiv n \pmod 5 \equiv n^{13} \equiv n^6 \cdot n^7 \equiv n \pmod 7.$$

$$\, n = 2730 = 2\cdot 3\cdot 5\cdot 7\cdot 13 = \,$$ product of all primes $$\rm \,p\,$$ such that $$\rm \ \color{#c00}{p\!-\!1\mid 13\!-\!1}.\,$$ Now apply

Theorem $$\$$ For natural numbers $$\rm\:a,e,n\:$$ with $$\rm\:e,n>1$$

$$\qquad\rm n\:|\:a^{\large e}-a\:$$ for all $$\rm\:a\:\iff n\:$$ is squarefree, and prime $$\rm\:p\:|\:n\,\Rightarrow\, \color{#c00}{p\!-\!1\mid e\!-\!1}$$

Proof $$\$$ See this answer for a short simple proof.

$2730 = 2\cdot 3\cdot 5\cdot 7\cdot 13$

The Carmichael function or least universal exponent function is composed by least common multiple over prime components, so $\lambda(2730) = \text{lcm}(\lambda(2), \lambda(3), \lambda(5), \lambda(7), \lambda(13)) = \text{lcm}(1,2,4,6,12)=12$. Note also that $2730$ is square-free, so the exponent cycle will be entered by the first power ($n^1$) for all numbers. Of course numbers coprime to $2730$ enter the cycle at the zeroth power ($1$).

Thus(!) $n^{(1+12)}\equiv n^1 \bmod 2730$ as required.

Cute corollary to FLT.

If $p,q$ are primes and $p-1=m|q-1=k$ then

$p|n^p -n=n (n^m-1)|n (n^m-1)(n^{k-m} + n^{k - 2m}+...+n^m+1)=n (n^k-1)=n^q-n$.

So as $1,2,3,4,6,12$ all divide $12$, it follows $2,3,5,7,13$ all divide $n^{13}- n$.

For me personally it was hardest to see that 5 did but $n^{13}-n = (n^8 + n^4 + 1)(n^5- n)$ so ... it does.

You can find the Chinese remainder theorem very useful.

Here is some way of automating Rob John's method:

You can always use decomposition over polynomials :$$\quad\displaystyle \Pi_k(n)=k!\binom nk=\prod\limits_{i=0}^{k-1} (n-i)$$

e.g. $$\ \Pi_4(n)=(n-3)(n-2)(n-1)n$$

To solve problems of the type: "show $$m$$ divides the polynomial $$P(n)$$"

Let have a look at a simpler example using this technique :

Prove $(n^5-n)$ is divisible by 5 by induction.

Though for $$n^{13}-n$$ it is a bit tedious.

Here is a maple procedure to do it:

> binomexpansion :=proc(P)
local a,b,c,d,i,p,q:
p:=P: d:= degree(P):
printf("%a = ",P):
for i from d to 0 by -1 do
a:=coeff(p,n,i):
q:=expand(binomial(n,i)):
b:=coeff(q,n,i):
c:=a/b:
p:=p-c*q:
if((c>0)and(i<d)) then printf("+"); fi:
if(c<>0) then printf("%d(n,%d)",c,i); fi:
end do: printf("\n"):
end proc

> binomexpansion(n^13-n);

n^13-n = 6227020800(n,13)+37362124800(n,12)+97037740800(n,11)+142702560000(n,10)+
130456085760(n,9)+76592355840(n,8)+28805736960(n,7)+6711344640(n,6)+
901020120(n,5)+60780720(n,4)+1569750(n,3)+8190(n,2)


You can notice that all coefficients are divisible by $$2730=2.3.5.7.13$$.

And since the binomial coefficients are integers, you get the divisibility by $$2730$$ as a result.