Prove that $14322\mid n^{31} - n$ Im trying to prove that $ 14322 \mid n^{31} - n $, $ \forall n \in \mathbb{Z}$
My thought was to rewrite $n^{31} - n$
which a got to $$ 2(n-1)\sum_{i=0}^{n} i \sum_{k=0}^{14} n^k \sum_{j=0}^{14} (-1)^kn^k $$ but this didnt (in my opinion) contribute to much.
I tried to assume that it was false, and then try to get a contradiction.
saying that  $n^{31}-n=q\cdot 14322 + r$, $0<r<q, q\in \mathbb{Z}$ then reaching a contradiction $\Rightarrow$ $r=0$. I did not see any obvious contradiction.
Hints?
 A: If you don't know modular arithmetic then you can use little Fermat and the following
$\ \ p\mid n^p\!-\!n\mid n^{31}\!-\!n\,$ by $\,n^{\large \color{#c00}{p-1}}\!-\!1\mid n^{\color{#c00}{30}}\!-\!1\,$ by $\,\color{#c00}{p\!-\!1\mid 30}\,$ for all $\, p\mid 14322=2\cdot3\cdot7\cdot11\cdot 31$
Otherwise, the easy direction $\,\color{#90f}{(\Leftarrow)}\,$ of the following theorem 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 \ \ \color{#c00}{p\!-\!1\mid e\!-\!1}\ \, for\  all \ primes\ \ p\mid n\quad $$
Proof $\ \ \color{#90f}{(\Leftarrow)}\ \ $ Since a squarefree natural divides another natural iff all its 
prime factors do, we need only show $\rm\: p\mid a^e\!-\!a\:$ for each prime $\rm\:p\mid n,\:$ or 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 \color{#c00}{e\!-\!1 = (p\!-\!1)}k\ \Rightarrow\ a^{\large e-1} \equiv (\color{#c00}{a^{\large p-1}})^{\large k}\equiv \color{#c00}1^{\large k}\equiv 1\!\!\!\pmod p \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 \color{#0a0}{a^2}\!\mid n\mid \color{#0a0}{a^e}\!-\!a \Rightarrow\:  a^2\mid a\:\Rightarrow\!\Leftarrow$ $\rm\: (note\ \ e>1\: \Rightarrow\: \color{#0a0}{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)$.
A: One way to solve this is to break down the polynomial $n^{31}-n$ directly, taking into consideration that $x-1\mid x^q-1$:
$$\begin{align}n^{31}-n&=n(n^{30}-1)\\
&=n(n^{10}-1)(n^{20}+n^{10}+1)\\
&=n(n^6-1)(n^{24}+n^{18}+n^{12}+n^6+1)\\
&=n(n^2-1)(n^{28}+n^{26}+\dots+1)\\
&=n(n-1)(n^{29}+n^{28}+\dots+1)
\end{align}$$
Since $14322=2\cdot3\cdot7\cdot11\cdot 31$, we can use Fermat's Little Theorem on all the values $2,3,7,11,31$ with the terms $n^2-n,n^3-n,n^7-n,n^{11}-n, n^{31}-n$.  Note that we do not need a factor $n^5$ to account for all of these divisibility conditions, since $p\mid n$ is the only time when the $n$ factor is needed in $n(n^{p-1}-1)$, meaning that when $14322\mid n$, we get $14322\mid n^{31}-n$ from the single $n$ factor, and when $(14322,n)\lt 14322$ all the factors of $14322$ which are not present in $n$ appear in $n^{30}-1$.
A: The usual method to solve this is to use Fermat's Little Theorem:
$$14322=2\cdot3\cdot7\cdot11\cdot 31 $$
and you prove that $n^{31}-n$ is divisible by each prime in this factorization

Edit
 As noticed in the comment we have $n^{p}-1$ divides $n^{pq}-1$ 


*

*Fermat implies that $11$ divides $n^{11}-n$, and as $n^{10}-1$ divides $n^{30}-1$ then $n^{11}-n$ divides $n^{31}-n$ hence $11$ divides $n^{31}-n$

*As $n^{6}-1$ divides $n^{30}-1$ and then $n^{7}-n$ divides $n^{31}-n$ gives you the divisibility by $7$ and you can do the same for others

