<s>[INST] $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?
 [/INST] 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$
</s>