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