1

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

Bernard
  • 175,478
Elhamer Yacine
  • 17

3 Answers3

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.

TonyK
  • 64,559
  • 1
    Sorry, but how do I exactly prove that $3^n - n - 1$ has period 20? I know that $3^n$ is of period 4, and $n+1\ mod \ 5$ is of a 5 one. I assume there's a specific theorem or something to credit in the written solution. – Elhamer Yacine Dec 28 '18 at 23:39
  • $20$ is the least common multiple of $4$ and $5$. Think about it a bit. – TonyK Dec 29 '18 at 00:39
1

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$

lab bhattacharjee
  • 274,582
  • Yeah, this is a nicer solution, exactly what I was looking for. the final results are: $n\ =\ {20k,\ 20k+17,\ 20k+18,\ 20k+11}$. – Elhamer Yacine Dec 29 '18 at 00:16
  • @ElhamerYacine We don't need to repeat the whole derivation for each remainder $, r = n\bmod 4.,$ Rather we can do it once $\rm\color{#0a0}{generically}$ then substitute for each $,r,,$ e.g. see my answer. – Bill Dubuque Dec 29 '18 at 00:23
0

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

Bill Dubuque
  • 272,048
  • Yeah this a nice addition. Anyways, suppose the expression was instead in the form: $a^n - n - 1 ≡ 0\ (\ mod\ 5\ )$ where $a^n$ is of period 5, here I wouldn't have to go the long route, since both of the conjoined expressions are of the same period, there are only 5 possibilities (that is $n=5k+r$ where $0≤r≤5$). furthermore, when we have two conjoined expressions with different cycling periods their lcm is equal to the number of "possibilities", right? – Elhamer Yacine Dec 29 '18 at 00:36
  • @Elhamer By Fermat, $\bmod 5!:\ a\not\equiv 0,\Rightarrow, a^4\equiv 1,$ so $a$ has order a divisor of $4$ (so it can't have period $5)\ $ – Bill Dubuque Dec 29 '18 at 00:42
  • Hmm, can you please link me the specific theorem? – Elhamer Yacine Dec 29 '18 at 00:46
  • also, is the lcm part of my first response correct? – Elhamer Yacine Dec 29 '18 at 00:47
  • Fermat's little Theorem. Yes, lcm arguments like that work in the appropriate context. – Bill Dubuque Dec 29 '18 at 00:51
  • @Elhamer I added a brute-force enumeration table to my answer to better illustrate that. That method won't work well for larger numbers. – Bill Dubuque Dec 29 '18 at 01:09
  • Indeed, I see that it is more inclusive/general. – Elhamer Yacine Dec 29 '18 at 12:43