3
$\begingroup$

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$.

$\endgroup$
2
  • 5
    $\begingroup$ $3^2=1\pmod{4}\implies3^{2m}=1\pmod{4}\implies3^{2m+1}=3\pmod{4}\implies$ ... $\endgroup$
    – Did
    Commented Jun 10, 2016 at 19:01
  • $\begingroup$ 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. $\endgroup$ Commented Jun 10, 2016 at 21:08

8 Answers 8

22
$\begingroup$

$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.

$\endgroup$
2
  • 4
    $\begingroup$ In fact, either $3^m +1$ or $3^m -1$ must be divisible by 4. $\endgroup$
    – Hrhm
    Commented Jun 10, 2016 at 19:03
  • $\begingroup$ @Hrhm True, since they are consecutive even numbers $\endgroup$
    – JasonM
    Commented Jun 10, 2016 at 19:05
9
$\begingroup$

There's actually the stronger result

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

$\endgroup$
6
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

$$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)$$

$\endgroup$
3
$\begingroup$

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}$$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ In your basis step do you mean (27 - 3) = 24 which is divisible by 4 ? $\endgroup$
    – TAPLON
    Commented Jun 19, 2016 at 18:19
  • $\begingroup$ Thanks for pointing that out $\endgroup$
    – Tazwar
    Commented Jun 19, 2016 at 18:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .