Prove $3^{2n}-5$ is a multiple of $4$

Question

I have the following problem:

Prove using induction that $3^{2n} -5 $ is always a multiple of $4$.

To solve it, I did the following:

1. Base Case (ie. for $n=1$):

   $3^2-5=4(1)$ therefore valid for $n=1$

2. Assume true for $n=k$:

   $3^{2k}-5=4a$

3. Consider for $n=k+1$

   $3^{2(k+1)}-5$ $=3^{2k}+9-5=4a+9$

However, I have clearly made a mistake somewhere. Where have I gone wrong?

Answer 1

$$ 3^{2k+2} -5 = 9 \cdot 3^{2k}-5 = 9 (4a+5)-5 = 36a+40 = 4b$$

Answer 2

You get wrong here

$$3^{2(k+1)}-5 \not \Rightarrow 3^{2k}\color{red}{+9}-5=...$$

since $$3^{2(k+1)}=3^{2k+2}=3^{2k}\cdot 3^2$$

thus we should have

Base case

• $n=1 \implies 3^2-5=4$

Induction step

• assume $3^{2n}-5\equiv 0 \pmod 4$

• $3^{2n+2}-5=9\cdot 3^{2n}-5\equiv 3^{2n}-5 \equiv 0 \pmod 4$

As an alternative without induction, simply note that

$$3^{2n}-5\equiv (-1)^{2n}-1\equiv 1-1 \equiv 0 \pmod 4$$

Answer 3

You wrote that $3^{2k + 1} = 3^{2k} + 9$, which is very wrong. And even if you meant $3^{2(k + 1)} = 3^{2k} + 9$, it is exactly as wrong.

---

What is correct is that

$$3^{2(k + 1)} = 9 \cdot 3^{2k}.$$

Now use the induction hypothesis applied to $3^{2k}$.

Answer 4

Do note that $3^{2(k+1)} \neq 3^{2k}+9$ instead $3^{2(k+1)}=9 \cdot 3^{2k}$.

For solving correctly, write $9=8+1$ in $9 \cdot 3^{2k}$. You'll get a way to proceed from there.

Answer 5

By induction, $n=k+1$ step: Suppose $3^{2k}-5=4x$

$$3^{2(k + 1)}-5 = 9 (3^{2k})-5=(8+1)3^{2k}-5=(8\times3^{2k})+(3^{2k}-5)=(8\times3^{2k})+4x=4 \left(2\times3^{2k}+x\right)$$

Answer 6

Proposition $$3^{2n} -5 \equiv 0 \pmod4 \implies 3^{2n}\equiv 1 \pmod4 $$ Proof by Induction

• $n = 1:$ $$\left(3^{2\cdot1} \right)\equiv 9^1 \equiv 1\pmod4 \quad\checkmark$$
• $n =n:$ $$\left(3^{2n}\right)\equiv 9^n \equiv 1^n\equiv 1 \pmod4 \quad\checkmark$$
• $n =(n+1):$ $$\left(3^{2(n+1)}\right)\equiv 9^{(n+1)} \equiv 9^n\cdot9\equiv 1^n\cdot1\equiv 1 \pmod4 \quad\checkmark$$ $\tag*{$\Box$}$