How to prove that $4 \mid 3^{2n} - 1$

Question

Prove that $3^{2n} - 1$ is divisible by $4$ for any positive integer $n$.

My work:

Let $p(n)$ be true, and let $p(n+1)$ be true. So, $3^{2(n+1)}-1$.

Can anyone help to solve this?

Answer 1

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

$3$ is odd. So $3^n$ is odd for all positive $n$. So $3^n\pm 1$ is even.

=====

You are clearly Trying to do a proof by induction but have no idea what a proof by induction is.

So this is how you do a proof by induction:

0) Clearly identify the statement you are trying to prove in terms of a specific variable $n$.

In this case: ** $3^{2n} - 1$ is divisible by $4$**.

Now some texts will have you write that is statement notation as $P(n):$$3^{2n} - 1$ is divisible by $4$, but I don't see that as helpful if a student isn't going to know what that means. Instead we get students parroting meaningless statements such as "Let $p(n)$ be true" that the clearly don't understand but thing is ritual incantation. (What is $p(n)$? You can't let something be true; either it is or it is not, etc.)

1) Base step: You prove the statement is true for $n= 1$.

So: Prove $3^{2*1} -1$ is divisible by $4$.

The base step is often just a matter of doing a single calculation.

In this case: $3^{2*1} -1 = 3^2 - 1 = 9-1 = 8 = 4*2$ is divisible by $4$.

2) Induction step: You assume that there is an number $k$ for which the statement is true. You know there is a number $k$ for which it is true because you just showed it is true for $1$. So it is true when $n=k=1$. Then show that IF it is true for $k$ then the statement is also true for $k + 1$.

(So because you know it is true for $k=1$ then if you proof this induction step you will know it is true for $n = k + 1 =2$. Then because you know this is true for $k = 2$ that it will be true for $n = k + 1 = $. Then because you know this is true for $k = 3$ then it will be true for ....)

If $3^{2k} - 1$ is divisible by $4$. That is if $3^{2k}-1 = 4M$ for some integer $M$, your task is to prove $3^{2(k+1)} -1$ is divisible by $4$, probably by using the fact that $3^{2k} - 1$ is divisible by $4$.

So you need to prove if $3^{2k} - 1 = 4M$ then $3^{2(k+1)} - 1 = 4N$ for some integer $N$.

.....

And then we are done:

We have proven that for a) $n= 1$ then $3^{2n} -1$ is divisible by $4$. b) that if for $n=k$ that if $3^{2k} -1$ is divisible by $4$ then $3^{2(k+1)} - 1$ is divisible by $4$. So it is true for $n = 1+1=2$ and for $n=2+1 =3$, anad for $n=3+1 =4 $ and so on for all possible natural numbers $n$.

Answer 2

Hint for the induction step: Suppose $3^{2n}-1$ is divisible by $4$. Then $$3^{2(n+1)}=9\times 3^{2n}-1=9(3^{2n}-1)+9-1=9(3^{2n}-1)+8$$ must be divisible by $4$.

Answer 3

Note that

$$3\equiv -1 \mod 4 \implies 3^{2n}-1\equiv (-1)^{2n}-1\equiv 0 \mod 4$$

Answer 4

Hint: $9 \equiv 1 \pmod 4$, and $3^{2n} = {(3^2)}^n =9^n$.

Answer 5

Without using induction, observe that $$ 3^{2n}-1=9^n-1=(9-1)(9^{n-1}+9^{n-2}+\dotsb+1) $$ for $n\geq 1$ by the formula for a finite geometric series. Thus $8\mid 3^{2n} -1$ and in particular $4\mid3^{2n}-1$.

Answer 6

$3^{2n}-1=(4-1)^{2n}= 4M +1-1= 4M$