# 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?

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
• you meant $n^{31}-n$ Apr 9 '15 at 18:04
• @Dr.SonnhardGraubner, yes, that's exactly what he wrote! Apr 9 '15 at 18:05
• Oh. It become alot more easier when I googled fermats Little Theorem... Apr 9 '15 at 18:08
• now yes he has corrected it Apr 9 '15 at 18:08
• Do you mean since $n^{31}-n = n(n^{15}-1)(n^{15}+1)$? Apr 9 '15 at 18:43

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

• $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\$ $\tag*{}$ This is a divisibility form of the congruence argument in my answer. Apr 9 '15 at 19:26
• Very true... I hope that the vertical alignment makes it a little clearer, but perhaps I could do something else to improve my answer... Apr 9 '15 at 19:38
• Yes, the alignment makes it clearer. Note that I added the expression in the comment only to help readers understand the relationship between the various methods. But if that motivates you to polish your answer then all the better! The site would be much richer if there were more collaboration. Apr 9 '15 at 19:43
• Note $\,n^J\!-\!1\mid n^{JK}\!-\!1\,$ is $\ a\!-\!1\mid a^K\!-\!1\,$ for $\,a = n^J,\,$ so we don't need to compute the quotient (cofactor) to prove that the divisibility is true. That's one of the major advantages of modular methods, e.g. $\, {\rm mod}\ n^J\!-\!1\!:\ \color{#c00}{n^J\equiv 1}\,\Rightarrow\, n^{JK}\equiv (\color{#c00}{n^J})^K\equiv \color{#c00}1^K\equiv 1\ \$ Apr 9 '15 at 19:58