Question

Prove that 30 divides ${\mathit{n}}^{\mathbf{9}}\mathbf{-}\mathit{n}$for every nonnegative Integer n.

Short answer

It is proved that 30 divides $n^9-n$ for every nonnegative integer n

Step-by-step solution

Important Theorems and Definitions

• Chinese remainder theorem:

A system of linear congruences modulo pairwise relatively prime integers have a unique solution modulo is the product of these moduli.

Let${\mathit{m}}_{\mathbf{1}}\mathbf{,}{\mathit{m}}_{\mathbf{2}}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}{\mathit{m}}_{\mathbf{n}}$be pairwise relatively prime positive integers greater than one and${\mathit{a}}_{\mathbf{1}}\mathbf{,}{\mathit{a}}_{\mathbf{2}}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}{\mathit{a}}_{\mathbf{n}}$arbitrary integers. Then the system

$\begin{array}{r}\mathbf{x}\mathbf{\equiv }{\mathbf{a}}_{\mathbf{1}}\left(mod{m}_1\right)\\ \mathbf{x}\mathbf{\equiv }{\mathbf{a}}_{\mathbf{2}}\left(mod{m}_2\right)\\ \\ \\ \mathbf{x}\mathbf{\equiv }{\mathbf{a}}_{\mathbf{n}}\left(mod{m}_n\right)\end{array}$

has a unique solution modulo$\mathit{m}\mathbf{=}{\mathit{m}}_{\mathbf{1}}{\mathit{m}}_{\mathbf{2}}\mathbf{.}\mathbf{.}\mathbf{.}{\mathit{m}}_{\mathbf{n}}$. (That is, there is a solution xwith $\mathbf{0}\mathbf{\le }\mathit{x}\mathbf{<}\mathit{m}$, and all other solutions are congruent modulo mto this solution.)

• Fermat’s little theorem: Ifpis prime and $\mathit{p}\mathbf{†}\mathit{a}$, then${\mathit{a}}^{\mathbf{p}\mathbf{-}\mathbf{1}}\mathbf{\equiv }\mathbf{1}\mathbf{(}\mathit{m}\mathit{o}\mathit{d}\mathbf{}\mathit{p}\mathbf{)}$.

• a = b ( mod m) ( a is congruent to bmodulo m): a - bis divisible bym.

Proving that 30 divides n9-n for every nonnegative integer 

Since we know$30=5\times 2\times 3$

Therefore, if we prove that $n^9-n$is divisible by 5, 3, and 2 then it will be divisible by 30.

Since 5 is a prime, so we can apply Fermat’s little theorem.

$\begin{array}{r}{n}^{5-1}=1(mod5)\\ n^4=1(mod5)\end{array}$

We know that

$\begin{array}{r}{n}^8={\left(n^4\right)}^{2}mod5\\ n^8={\left(n^{4}mod5\right)}^{2}mod5\\ n^8=1^{2}mod5\\ n^{8}n=nmod5\\ n^9=nmod5\end{array}$

This implies,

$n^9=nmod5$

Again, since 3 is a prime, so we can apply Fermat’s little theorem.

$\begin{array}{r}{n}^{3-1}=1(mod3)\\ n^2=1(mod3)\end{array}$

We know that

role="math" localid="1668618961532" $\begin{array}{r}{n}^8={\left(n^2\right)}^{4}mod3\\ n^8={\left(n^{2}mod3\right)}^{4}mod3\\ n^8=1^{4}mod3\\ n^8=1mod3\\ n^9=nmod3\end{array}$

This implies,

$n^9=nmod3$

Again, since 2 is a prime, so we can apply Fermat’s little theorem.

$\begin{array}{r}{n}^{2-1}=1(mod2)\\ n=1(mod2)\end{array}$

We know that

$\begin{array}{r}{n}^8=(n{)}^{8}mod2\\ n^8=(nmod2{)}^{8}mod2\\ n^8=1^{8}mod2\\ n^8=1mod2\\ n^9=nmod2\end{array}$

Since$n^9=nmod5$,$n^9=nmod3$and$n^9=nmod2$, therefore from the Chinese remainder theorem

So, from the definition of congruence, we can conclude 30 divides $n^9=nmod30$.

Hence it is proved that 30 divides $n^9-n$for every nonnegative

integer n.