how to find every n>2 where 8 + 5^(n-3) + 3^(n-3) that are divisible by 8 (using induction)

Question

I need to find all natural numbers bigger then 2 where 8 + 5^(n-3) + 3^(n-3) is divisible by 8

I have already proven that it is true for all the even numbers. Now I know that it is false for odd ones, but i don't know how to prove it.

n ≥ 3; n ∈ N; base case: n = 4; 8 + 5^(4-3) + 3^(4-3) = 8 + 5 + 3 = 16; 16 mod 8 = 0

premise for any even number: n = 2k; k ∈ N; 8 + 5^(2k-3) + 3^(2k-3) = 8m; m ∈ N; ⇒ 5^(2k-3) = 8m - 8 – 3^(2k-3)

for every even number: n = 2k+2; k ∈ N; 8 + 5^(2k+2-3) + 3^(2k+2-3) = 8 + 5^(2k-3) * 5^2 + 3^(2k-3) * 3^2 = 8 + (8m - 8 - 3^2k-3) * 5^2 + 3^2k-3 * 3^2 = 8 + 200m - 200 - 25 * 3^(2k-3) + 9 * 3^(2k-3) = 200m - 192 - 16 * 3^(2k-3) = 8*(25m - 24 - 2 * 3^2k-3)

n ≥ 3 ∧ n ∈ N ∧ n=2k ∧ k ∈ N ⇒ 3^2k-3 ∈ N;

This is where i end :( ...can't figure out how to proceed with odd numbers. I need to prove that any odd number where 8 + 5^(n-3) + 3^(n-3) is not divisible by 8, so i can claim that i have found all of those that are.

Thanks for any suggestions :)

Answer 1

If $n$ is odd, $n-3$ is even. Any odd number to an even power is equivalent to $1 \pmod 8$, which you can prove by cases. So $8+5^{n-3}+3^{n-3} \equiv 2 \pmod 8$ and it is not divisible by $8$ To use induction, note that the square of any odd is $1 \pmod 8$, then it is true for $n=3$ and assuming it is true for $k$, you have $8+5^{k+2-3}+3^{k+2-3}\equiv 8+5^{k-3}5^2+3^{k-3}3^2\equiv 8+1\cdot 5^{k-3}+1\cdot 3^{k-3}\equiv 8+1(5^{k-3}+3^{k-3})\equiv 2 \pmod 8$

Answer 2

Hint $\ {\rm mod}\ 8\!:\ x\equiv\, (-3)^{n-3}\!+3^{n-3}\equiv 3^{n-3}((-1)^{n-3}+1)\equiv 0\iff (-1)^{n-3}\equiv -1\ $

But it is quite straightforward to prove by induction that $\,(-1)^k\equiv -1\iff k\,$ is odd.