Prove that $14322\mid n^{31} - n$

Solution 1:

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

Solution 2:

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

Solution 3:

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