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
    Jun 10 '16 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$ Jun 10 '16 at 21:08
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
    Jun 10 '16 at 19:03
  • $\begingroup$ @Hrhm True, since they are consecutive even numbers $\endgroup$
    – JasonM
    Jun 10 '16 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
    Jun 19 '16 at 18:19
  • $\begingroup$ Thanks for pointing that out $\endgroup$ Jun 19 '16 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.