# Prove that $4$ divides $3^{2m+1} - 3$

Prove that $4$ divides $3^{2m+1} - 3$.

By plugging in numbers I can see this is true, but I can't figure out a way to prove this, I was thinking maybe proving first that it is divisible by $2$, and concluding its divisible by $4$.

• $3^2=1\pmod{4}\implies3^{2m}=1\pmod{4}\implies3^{2m+1}=3\pmod{4}\implies$ ...
– Did
Jun 10 '16 at 19:01
• You can say more: $3^{2m+1}-3$ is in fact always divisible by $24$ ;) See JasonM's answer for an idea of how you might prove this. Jun 10 '16 at 21:08

$3^{2m+1}-3=3(3^m-1)(3^m+1)$, and both of the factors $3^m \pm 1$ are even, so their product is divisible by 4.

• In fact, either $3^m +1$ or $3^m -1$ must be divisible by 4.
– Hrhm
Jun 10 '16 at 19:03
• @Hrhm True, since they are consecutive even numbers Jun 10 '16 at 19:05

There's actually the stronger result

$$3^{2m +1} - 3 = 3(9^m - 1) = 24\sum_{i=1}^m 9^{m-i}$$

There are generally several ways to approach these types of divisibility problems. I am showing two of them.

By Mathematical Induction: Putting $m=0$ we have $3^{2m+1}-3=0$, which is obviously divisible by $4$. Now let $4\mid 3^{2m+1}-3$ for some $m\in N_0$. Let $3^{2m+1}-3=4k$, for some $k\in N_0$. Now $3^{2(m+1)+1}-3=9(3^{2m+1}-3)+24=9\cdot 4k+24=4(9k+6)$, which is also divisible by $4$. So we see that $4\mid 3^{2m+1}-3$ for all $m\in N_0$.

By Modular Arithmetic: We see that $3^2\equiv1\pmod{4}$. So for any $m\in N_0$, $3^{2m}\equiv1\pmod{4}$ and $3^{2m+1}\equiv3\pmod{4}$. That is, $4\mid 3^{2m+1}-3$.

$$3^{2m+1}-3=(4-1)^{2m+1}-3=\sum\limits_{i=0}^{2m+1}{\left( \begin{matrix} 2m+1 \\ i \\ \end{matrix} \right)}{{4}^{2m+1-i}}{{(-1)}^{i}}\,\,\,-3$$ $$3^{2m+1}-3=\underbrace{\sum\limits_{i=0}^{2m}{\left( \begin{matrix} 2m+1 \\ i \\ \end{matrix} \right)}{{4}^{2m+1-i}}{{(-1)}^{i}}}_{4q}\,\,\,-4=4(q-1)$$

Here is a different approach.

Note that $3^{2m+1}-3 = 3(3^{2m}-1)$, so it enough to show that $4$ divides $3^{2m}-1$.

To do this, write $3^{2m}-1$ in base $3$ as $\underbrace{22\dots2_3}_{2m \text{ copies of 2}}$ and note that $4_{10} = 11_3$. Thus, we have : $$\frac{3^{2m}-1}{4}=\frac{22\dots2_3}{11_3} = {2020\dots202}_{3}$$

## Proof by induction:

First, show that this is true for $m=1$:

$3^{2+1}-3=24$

Second, assume that this is true for $m$:

$3^{2m+1}-3=4k$

Third, prove that this is true for $m+1$:

$3^{2(m+1)+1}-3=$

$3^{2m+3}-3=$

$9\cdot(\color\red{3^{2m+1}-3})+24=$

$9\cdot\color\red{4k}+24=$

$4\cdot(9k+6)$

Please note that the assumption is used only in the part marked red.

$3=-1(\mod 4)$, $3^{2m}=1(\mod 4)$ and $3^{2m+1}=3(\mod 4) \implies 3^{2m+1}-3=0(\mod 4)$

Let $S(m)$ be the statement: $3^{2m+1}-3$ is divisible by 4

Basis step: $S(1)$:

$\Rightarrow 3^{2(1)+1}-3=3^{2+1}-3$

$\hspace{26 mm}=3^{3}-3$

$\hspace{26 mm}=27-3$

$\hspace{26 mm}=24$, which is divisible by $4$

Inductive step:

Assume $S(k)$ is true, i.e. assume that $3^{2k+1}-3$ is divisible by 4

$\hspace{59 mm}\Rightarrow 3^{2k+1}-3=4A$; $A\in\mathbb{N}$

$\hspace{59 mm}\Rightarrow 3^{2k+1}=4A+3$

$S(k+1)$: $3^{2(k+1)+1}-3$

$\hspace{12.5 mm}=3^{2k+2+1}-3$

$\hspace{12.5 mm}=3^{2k+3}-3$

$\hspace{12.5 mm}=3^{2}\bullet{3^{2k+1}}-3$

$\hspace{12.5 mm}=9(4A+3)-3$

$\hspace{12.5 mm}=36A+27-3$

$\hspace{12.5 mm}=36A+24$

$\hspace{12.5 mm}=4(9A+6)$, which is divisible by $4$

So, $S(k+1)$ is true whenever $S(k)$ is true.

Therefore, $3^{2m+1}-3$ is divisible by 4.

• In your basis step do you mean (27 - 3) = 24 which is divisible by 4 ? Jun 19 '16 at 18:19
• Thanks for pointing that out Jun 19 '16 at 18:27