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

Question

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?

Answer 1

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$

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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