<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] 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$.
</s>