Give a direct proof of $8\mid (3^n + 5^n)$ for all odd natural numbers.
I know how to prove this by induction, I am not sure how to go about it using a direct proof.
I would start by saying that $3^n + 5^n = 8k$ for some k in the naturals. But I'm not sure...
On
We have
$$3\equiv -5\mod 8$$ so for $n$ odd we have $$3^n\equiv (-5)^n\mod 8$$ and then the result follows.
On
For even $w,$ $$ 1^w \equiv 3^w \equiv 5^w \equiv 7^w \equiv 1 \pmod 8. $$ I suppose there is a hidden induction in the even part, do it for $w=2,$ then $w=4,$ and so on.
No, wait, take $k$ odd and consider $k^{w/2}$ which is also odd. It is now one of four cases, $k^{w/2} \equiv 1,3,5,7 \pmod 8,$ which all lead to $$k^w = \left( k^{w/2} \right)^2 \equiv 1 \pmod 8.$$ At this stage, one may ask whether the fact that an odd number to any positive integer power is odd comes under the heading of induction. In one way it must, but if already proven in class or the book...
For odd $n,$ take $n=w+1,$ so $$ 1^n \equiv 1, \; 3^n \equiv 3, \; 5^n \equiv 5, \; 7^n \equiv 7 \pmod 8. $$
On
Every power of $3$ is modulo $8$ congruent to either $3$ or $1$. That can be seen quickly as follows: $3^2\equiv 1$, then multiply that by $3$, getting $3$, then multiply that by $3$, getting $1$, then multiply that by $3$, getting $3$, and so on.
Similarly every power of $5$ is modulo $8$ congruent to either $5$ or $1$.
in $3^n+5^n$, you're adding either $3+5$ or $1+1$ depending on whether $n$ is odd or even.
$$5\equiv-3\pmod8$$
Using Congruence Property $\#10$ of this, $$\implies5^{2m+1}\equiv(-3)^{2m+1}\equiv-3^{2m+1}\pmod8$$
See also :
Why $a^n - b^n$ is divisible by $a-b$?
Proof of $a^n+b^n$ divisible by a+b when n is odd