1

So I have this problem, $W=3^n -n -1$. How to find all $n$ so $W$ can be divided by $5$.

what I tried: I found all the remainders of $3^n$ divided by $5$, they are: $1,3,4,2$.

if there isn't ($-n$), it's easy but with it I can't continue.

this is the solutions of the problem: $n=20k+11$, $n=20k+18$, $n=20k+17$, $n=20k$. but I don't know how to find them

thanks

Khashayar Baghizadeh
  • 1,477
18.99
  • 69

2 Answers2

2

First of all, notice that $3^4$ is congruent 1 mod 5 (by fermat's little theorem). Then, as you said, these residues are 1, 3, 4, 2, so consider next 4 cases:

  1. n is congruent 0 mod 4. now, let's see it modulo 5: $1-n-1=0 (mod 5)$. That implies $n=0 (mod5)$. Using chinese residue theorem, we obtain that $n=0 (mod 20)$

Now we have found the first solution: $n=20k$.

Use the same argument in the other congruences of $n$ mod 4 to find all the other solutions.

Hope it was useful :)

Àlex Rodríguez
  • 103
  • 8
0

Let $W_n=3^n -n -1$. Then $W_n \bmod 5$ is periodic of period $20$: $$ 0,1,1,3,1,2,2,4,2,3,3,0,3,4,4,1,4,0,0,2,0,1,1,3,\dots $$

This follows by induction because $W_n= 3^n -n1^n -1^n$ and so $W_{n+3}=5W_{n+2}-7W_{n+1}+3W_n$ because $(x-3)(x-1)^2=x^3 - 5 x^2 + 7 x - 3$.

lhf
  • 216,483
  • thanks a lot but I think this is high level math, and I'm still in highschool so... thanks anyway – 18.99 Aug 04 '20 at 14:05
  • @18.99, here is a starting point for this approach: https://en.wikipedia.org/wiki/Recurrence_relation#Solving_homogeneous_linear_recurrence_relations_with_constant_coefficients – lhf Aug 04 '20 at 14:18