How to prove that for $p=2n+1$ the expression $3^p+1$ is divisible by 4?

Question

Well, I tried to solve it like this:

$3^{2n-1}+1=3\cdot3^{2n}+1\implies3^{2n}$ will be always odd $\implies3^{2n}=2t+1$
$3\cdot3^{2n}+1= 3\cdot(2t+1)+1= 6t+3+1=6t+4=4\ (\frac{3}{2}t+1)$

But because I'm dealing with integers, I'm suspicious of this solution.

Any other tips on how to solve this problem?

Answer 1

By the rules of modular aritmetic, we have: $$3^{2n+1}+1\equiv(-1)^{2n+1}+1\equiv-1+1\equiv 0 \mod \; 4$$

Answer 2

It's easy using modular arithmetic:

$$3^{2n+1}+1\equiv(-1)^{2n+1}+1=-1+1=0\pmod4.$$

---

You could get your approach to work by saying $3^{2n}=9^n=(2\times4+1)^n=\color{red}4t+1.$

Answer 3

Just do it by induction:

$p(0)=2(0)+1=1$, $3^{P(0)}+1=4$, and $4($mod$4)=0$

Assume $[3^{p(n)}+1]($mod$4)=0$

Then $[3^{p(n+1)}+1]($mod$4)=[3^{p(n+1)-p(n)}3^{p(n)}+1]($mod$4)=[9*3^{p(n)}+1]($mod$4)$

$=[8*3^{p(n)}+3^{p(n)}+1]($mod$4)=[3^{p(n)}+1]($mod$4)=0$

This completes the proof