Question

Prove that${\mathit{n}}^{\mathbf{12}}\mathbf{-}\mathbf{1}$is divisible by 35 for every integer

for which$\mathit{g}\mathit{c}\mathit{d}\mathbf{}\mathbf{(}\mathit{n}\mathbf{,}\mathbf{35}\mathbf{)}\mathbf{=}\mathbf{1}$

Short answer

It is proved that $n^{12}-1$ is divisible by 35 for every integer nfor which $\gcd (n,35)=1$

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{\dots }{\mathit{m}}_{\mathbf{n}}$be pairwise relatively prime positive integers greater than one and${\mathit{a}}_{\mathbf{1}}\mathbf{,}{\mathit{a}}_{\mathbf{2}}\mathbf{\dots }{\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{\dots }{\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 moduloto this solution.)

• Fermat’s little theorem: If pis prime and P t a, then${\mathit{a}}^{\mathbf{p}\mathbf{-}\mathbf{1}}\mathbf{\equiv }\mathbf{1}\mathbf{(}\mathbf{mod}\mathit{p}\mathbf{)}$.

• $\mathit{a}\mathbf{=}\mathit{b}\mathbf{(}\mathbf{mod}\mathit{m}\mathbf{)}$(ais congruent to bmodulo m): a - bis divisible by.

Proving that n12−1  is divisible by 35 for every integer n for which gcd⁡(n,35)=1

Given in the question

n is an integer and$\gcd (n,35)=1$

Since we know 35 = 5 x 7

Therefore, if we prove that $n^{12}-1$is divisible by 5 and 7 then it will be divisible by 35.

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}^{12}={\left(n^4\right)}^{3}mod5\\ ={\left(n^{4}mod5\right)}^{3}mod5\\ =1^{3}mod5\\ =1mod5\end{array}$

This implies,

$\begin{array}{r}{n}^{7-1}=1(mod7)\\ n^6=1(mod7)\end{array}$

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

$\begin{array}{r}{n}^{7-1}=1(mod7)\\ n^6=1(mod7)\end{array}$

We know that

$\begin{array}{r}{n}^{12}={\left(n^6\right)}^{2}mod7\\ ={\left(n^{6}mod7\right)}^{2}mod7\\ =1^{2}mod7\\ =1mod7\end{array}$

This implies,

$n^{12}\equiv 1mod7$

Since $n^{12}\equiv 1mod5\text{and}{n}^{12}\equiv 1mod7$, therefore from Chinese remainder theorem$n^{12}\equiv 1mod35$

So, from the definition of congruence, we can conclude 35 divides .

Hence it is proved that $n^{12}-1$ is divisible by 35 for every integer for which$\gcd (n,35)=1$ .