$3^n-1$ is divisible by $4 \implies n $ is even 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?
 A: We have that
$$3^n-1\equiv (-1)^n+1\mod 4$$
and thus $$4|3^n-1\iff n=2k$$
A: 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$$
A: $$3^n - 1 \equiv (-1)^n - 1 = \begin{cases} 0 & n~\text{is even} \\ -2 & n~\text{is odd} \end{cases}$$
A: 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$
A: 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$.
A: 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}}$$
A: 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
$$
