Mathematical induction... divisible by 4

Question

Hello I need to proof that the expression $(9^{n}+3)$ is divisible by $4$.

It is true if I calculate it for $n=1$

for $n + 1$ I got stuck in here:

$9 \cdot 9^n + 3$

I don't know how to continue. Can anyone help me please?

score 2 · Answer 1 · answered Nov 03 '13 at 22:28

2

Note that

$$9^{n + 1} + 3 = 9 \cdot 9^n + 3 = 9 \cdot (4k - 3) + 3 = 4 \cdot (9k) - 24$$ for some $k$, as $9^n +3 = 4k$.

answered Nov 03 '13 at 22:28

score 2 · Answer 2 · answered Nov 03 '13 at 22:36

2

One easy way to see this, if you aren't required to use induction, is that:

$$9 \equiv 1 \pmod4 $$

and so:

$$9^n + 3 \equiv 1^n + 3 \equiv 1 +3 \equiv 4 \equiv 0\pmod4$$

answered Nov 03 '13 at 22:36

Patrick

2,106

score 1 · Accepted Answer · answered Nov 03 '13 at 22:43

Suppose $9^n + 3$ is a multiple of $4$. Then

$$ (9^{n+1}+3)-(9^n+3)=9^{n+1}-9^n =9^n(9-1)=8*9^n, $$

which is a multiple of four. The difference of $9^{n+1}+3$ and $9^n+3$ is a multiple of 4, and $9^n + 3$ is a multiple of 4, so $9^{n+1}+3$ is a multiple of 4.

Mathematical induction... divisible by 4

3 Answers3