For what values of n (where n is a natural number) is this statement true: $3^n - n - 1 ≡ 0\pmod5$

Question

I'm clueless as where to start with this, $3^n$ seems to be of period 4, where $ - n - 1$ is of period 5.

Answer 1

$\, n = 4q\!+\!r,\ 0\le r\le 3.\,$ $\bmod 5\!:\ \color{#0a0}1 \equiv 3^{\large n}\!-n\equiv 3^{\large r} \overbrace{(3^{\large 4})^{\large q}}^{\large 3^{\Large 4} \equiv\ 1}\!-4q\!-\!r\equiv \color{#0a0}{3^{\large r}\!+q-r}$

$\,r=0\,\Rightarrow\ \color{#0a0}{1\equiv 3^{\large 0}\!+q-0}\ $ so $\,\color{#c00}{q\equiv 0\pmod{\!5}}\,$ so $\,n = 4\color{#c00}q\!+\!r=4(\color{#c00}{0\!+\!5k})\!+\!0 = 20k$

$\,r = 1,2,3\,$ are done the same way. You'll find the $\rm\color{#c00}{solutions}$ enumerated below. $\!\!\begin{array}{|r|r|} \hline n & 0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19\\ \hline n\!+\!1\bmod 5 &\color{#c00}1&2&3&4&0&1&2&3&4&0&1&\color{#c00}2&3&4&0&1&2&\color{#c00}3&\color{#c00}4&0\\ \hline 3^n\bmod 5 &\color{#c00}1&3&4&2&1&3&4&2&1&3&4&\color{#c00}2&1&3&4&2&1&\color{#c00}3&\color{#c00} 4&2\\ \hline \end{array}$

Answer 2

I would say that's a pretty good start! So $3^n-n-1$ has period $20$. Now write down $3^n \bmod 5$ for $n=1$ to $20$, and $n+1\bmod 5$ for $n=1$ to $20$, and see where they match. Of course you only need to compute $3^n$ for $n=1$ to $4$, because it repeats after that.

Answer 3

As ord$_53=4,$

it's sufficient to all $4$ distinct residuals.

For example,

Case$\#1:$ if $n=4m,3^n-n-1\equiv(3^4)^m-4m-1\equiv1^m-4m-1\pmod5$

So, we need $5|-4m\iff5|m\iff 20|4m=n$

Case$\#4:$ If $n=4m+3,3^n-n-1\equiv3^3-(4m+3)-1\equiv23-4m\pmod5$

$\iff4m\equiv23\pmod5\equiv23+5\iff m\equiv7\equiv2, m=5r+2$(say)

$n=4m+3=4(5r+2)+3\equiv11\pmod{20}$

Can you please try with $n=4m+1,4m+2$