Prove that $37$ is a factor of $(10^{2014} + 10^{2015} + 2)^{2016} − 1$ How can I prove that $37$ is a factor of $(10^{2014} + 10^{2015} + 2)^{2016} − 1$, probably using basic number theory?
 A: HINT:
As $37\cdot27=999, 10^3\equiv1\pmod{37}$
and as $2014\equiv1,2015\equiv2\pmod3$
$10^{2014}\equiv10^1,10^{2015}\equiv10^2\pmod{37}$
So, we need  $(10+10^2+2)^{2016}\pmod{37}$
But $10+10^2+2\equiv1\pmod{37}$
A: \begin{eqnarray}
\color{red}{10^3} &\color{red}{\equiv}& \color{red}{1\,\,\, mod \,37}\\
10^{2010}=(10^3)^{67} &\equiv& 1\,\,\, mod \,37\\
10^{2014}=10^{2010}\times10^3\times10 &\equiv& 10\,\,\, mod \,37\\
10^{2015}=10^{2010}\times10^3\times100 &\equiv& 100\,\,\, mod \,37\\
\end{eqnarray}
so
\begin{eqnarray}
10^{2014}+10^{2015}+2 &\equiv& 10+100+2\,\,\, mod \,37\\
10^{2014}+10^{2015}+2 &\equiv& 1\,\,\, mod \,37\\
\Big(10^{2014}+10^{2015}+2\Big)^{2016} &\equiv& 1\,\,\, mod \,37\\
\Big(10^{2014}+10^{2015}+2\Big)^{2016}-1 &\equiv& 0\,\,\, mod \,37
\end{eqnarray}
A: Hint $\ $ Notice that $\,\ {\rm mod}\ 37\!:\,\ \color{#c00}{10^{\large 3}\equiv 1}\ $ by $\ \color{#0a0}{10^{\large 2}\! + 10 + 1} = 3\cdot 37 \equiv 0\ $ therefore
$$\begin{align} & 10^{\large 2\ +\ 3J}\ +\ 10^{\large 1\ +\ 3K} +\, 2\\[.2em]  
\equiv\ & 10^{\large 2} (\color{#c00}{10^{\large 3}})^{\large J}\!\! + 10(\color{#c00}{10^{\large 3}})^{\large K}\! + 2\\[.2em] 
\equiv\ &\color{#0a0}{10^{\large 2}\ \ \ \ \ +\ \ \ \ \ 10\ \   \ +\ \ 1} + \color{#90f}{\bf 1}\\[.2em]
\equiv\ &\ \color{#90f}{\bf 1}\end{align}$$
Remark $\, $ i.e. $\ x^{\large 2}\!+\!x\!+\!1\mid x^A\! +\! x^B\! +\! x^C\ $ if $ \ \{A,B,C\}\equiv \{2,1,0\}\pmod{\!3},\,$ see here for more.
A: Following up on Mark Bennet's hint, that $2016=36\cdot56$, we know that if $37\not\mid a$, then $a^{2016}\equiv 1$ mod $37$.  So let $a=100$.  Then
$$\begin{align}
(10^{2014}+10^{2015}+2)^{2016}
&\equiv100^{2016}(10^{2014}+10^{2015}+2)^{2016}\\
&\equiv(10^{2016}+10^{2017}+200)^{2016}\\
&\equiv(1+10+200)^{2016}\\
&\equiv211^{2016}\\
&\equiv1
\end{align}$$
since $37\not\mid211$.
A: Below is a somewhat not so elementary approach:
Notice $2016=36\times56$, and by Fermat's little theorem, for any $37\not\mid a$, we have $a^{36}\equiv1\pmod{37}$.
So $(10^{2014} + 10^{2015} + 2)^{2016} − 1\equiv-1\text{ or } 0\pmod{37}$.
But we know $10^{2016}\equiv1\pmod{37}$ so $10^{2015}\equiv10^{-1}\equiv2^{-1}\times5^{-1}\equiv19\times15\equiv26\pmod{37}$ and $10^{2015}+2\equiv28\pmod{37}$.
Moreover we see that if $10^{2014} + 10^{2015} + 2\equiv10^{2014}+28\equiv0\pmod{37}$, then $10^{2014}\equiv9\pmod{37}$.
However this is impossible: $10^1\equiv10\pmod{37}, 10^{2}\equiv26\pmod{37}, 10^{3}\equiv1\pmod{37}$.
Hence $10^{2014} + 10^{2015} + 2\not\equiv0\pmod{37}$ and $(10^{2014} + 10^{2015} + 2)^{2016}\equiv1\pmod{37}$.
Hope this helps.
