$3^n-1$ is divisible by $4 \implies n $ is even

Question

What is the easiest ways to prove this: $3^n-1$ is divisible by $4 \implies n $ is even? Moreover, how would I figure out that $n$ must be even if I didn't know the result?

My approach is this: suppose $n=2k+1$. Consider $3^{2k+1}-3$. If we show that it is divisible by $4$, it will follow that $3^n-1$ has remainder $2$ in the division by $4$ if $n$ is odd. We have $3^{2k+1}-3=3(3^k-1)(3^k+1)$. Each of the two brackets is divisible by $2$, so the whole thing is divisible by $4$. Is this correct?

Answer 1

$$3^n - 1 \equiv (-1)^n - 1 = \begin{cases} 0 & n~\text{is even} \\ -2 & n~\text{is odd} \end{cases}$$

Answer 2

We have that

$$3^n-1\equiv (-1)^n+1\mod 4$$

and thus $$4|3^n-1\iff n=2k$$

Answer 3

hint:Assume $$n=2k$$ $$\quad{3^n-1=3^{2k}-1=\\\underbrace{(3^{k}-1)}_{even}\times\underbrace{(3^{k}+1)}_{even}=\\2q\times 2q'=\\4qq'\\4|\underbrace{(3^{2k}-1)}_{n=2k}}$$

Answer 4

Hint $$3^n-3^{n-2}=3^{n-2}(9-1)$$ is always divisible by $4$. Therefore, $$4 | 3^n-1 \Leftrightarrow 4|3^{n-2}-1$$

Answer 5

We can use the identity

$a^n - b^n = (a - b) \displaystyle \sum_0^{n - 1} a^{n - 1 - k}b^k: \tag 0$

$3^n - 1 = (3^1 - 1^1) \displaystyle \sum_0^{n - 1} 3^{n - 1 - k} 1^k = 2 \sum_0^{n - 1} 3^{n - 1 - k}; \tag 1$

now if

$4 = 2^2 \mid 3^n - 1 = 2 \displaystyle \sum_0^{n - 1} 3^{n - 1 - k}, \tag 2$

then

$2 \mid \displaystyle \sum_0^{n - 1} 3^{n - 1 - k}; \tag 3$

now if $n$ were odd, the sum would consist of an odd number of odd integers $3^{n - 1 - k}$, hence would itself be odd. If, however, $n$ is even, the sum consists of an even number of odd integers, hence is itself even. Thus (3) binds precisely when $n$ is even, and thus

$4 \mid 3^n -1 \Longleftrightarrow n \; \text{is even.} \tag 4$

Answer 6

If you know modulo arithmetic $3^n \equiv (-1)^n \equiv 1\mod 4 \iff n$ is even

So $3^n - 1\equiv 1-1\equiv 0 \mod 4 \iff n$ is even.

If you don't know moulo arithmetic then just... do it.

Let $n = 2k$ and notice $3^{2k} - 1 = 9^k - 1= (8 + 1)^k - 1 =8^k + 8^{k-1}k + {k\choose 2}8^{k-2} + ...... + 8k + 1 - 1= 8^k + 8^{k-1}k + {k\choose 2}8^{k-2} + ...... + 8k$ is divisible by $4$.

But If $n = 2k + 1$ then $3^{2k + 1} - 1 = 9^k*3 - 1 =(8+1)^k*3 - 1= 3((8 + 1)^k - 1 =8^k + 8^{k-1}k + {k\choose 2}8^{k-2} + ...... + 8k + 1)-1 = 3((8 + 1)^k - 1 =8^k + 8^{k-1}k + {k\choose 2}8^{k-2} + ...... + 8k) + 3-1 = 3((8 + 1)^k - 1 =8^k + 8^{k-1}k + {k\choose 2}8^{k-2} + ...... + 8k) + 2$.

$3((8 + 1)^k - 1 =8^k + 8^{k-1}k + {k\choose 2}8^{k-2} + ...... + 8k)$ is divisible by $4$ so $3((8 + 1)^k - 1 =8^k + 8^{k-1}k + {k\choose 2}8^{k-2} + ...... + 8k)+2$ will have remainder $2$ when divided by $4$.

Answer 7

If $n = 2k$ then

$$ (4-1)^n = 4^n-n 4^{n-1}+\cdots - n 4 + 1 $$

hence in this case

$$ 3^{n}-1 \equiv 0 \mod 4 $$