# How will you show ? 5^n+1 is always divisible by 7 when n is a positive odd integer divisible by 3.

May 31, 2016

(see below for proof)

#### Explanation:

If $n$ is a positive odd integer divisible by $3$
we can replace $n$ with $3 \left(2 p + 1\right)$ for some $\text{odd } p \in \mathbb{Z}$

${5}^{n} + 1$
$\textcolor{w h i t e}{\text{XXX}} = {5}^{3 \left(p\right)} + 1$

$\textcolor{w h i t e}{\text{XXX}} = {125}^{p} + 1$

Noting that $125 = 7 \times 18 - 1$

we have
${5}^{n} + 1$
$\textcolor{w h i t e}{\text{XXX}} = {\left(7 \times 18 - 1\right)}^{p} + 1$

$\Rightarrow {\left({5}^{n} + 1\right)}_{\text{mod } 7} = {\left(- 1\right)}^{p} + 1$

but ${\left(- 1\right)}^{\text{any odd integer}} = - 1$

$\Rightarrow {\left({5}^{n} + 1\right)}_{\text{mod } 7} = - 1 + 1 = 0$

$\Rightarrow \left({5}^{n} + 1\right)$ is divisible by $7$