3
$\begingroup$

How can I prove that $37$ is a factor of $(10^{2014} + 10^{2015} + 2)^{2016} − 1$, probably using basic number theory?

$\endgroup$
  • 1
    $\begingroup$ Note that $2016=36\times 56$ $\endgroup$ – Mark Bennet Jan 17 '17 at 15:36
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ ah, thank you so much! $\endgroup$ – tostito Jan 17 '17 at 15:39
3
$\begingroup$

\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}

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.