# For every natural number $n$, prove that $4\mid(3^n-1)$ iff $4$ does not divide $3^n+1$

For every natural number $$n$$, prove that $$4\mid(3^n-1)$$ iff $$4$$ does not divide $$3^n+1$$.

Since it's a bi-conditional it has to be proven both ways.

It's easy to see if $$4\mid(3^n-1)$$ then $$3^n-1=4x$$ where $$x$$ is an integer then $$3^n=4x+1$$. We can plug this into $$3^n+1$$, which gives $$(4x+1)+1=4x+2$$ which is not divisible by $$4$$ because it'll always have a remainder of $$2$$.

I don't know how to prove the inverse implication "if $$4$$ does not divide $$3^n+1$$ then $$4\mid(3^n-1)$$". I thought maybe if $$4$$ does not divide $$3^n+1$$ then it can be defined as $$4k+i$$ where $$i \in \{1,2,3\}$$, but I tried plugging that into $$3^n-1$$ and it didn't work out.

• That $3^n$ is a red herring. Try this: "If $k$ is an odd number, then $4\mid (k-1)$ iff $4$ does not divide $k+1$." – TonyK Oct 1 at 9:14
• Hint  Viewed $\bmod 4\,$ it is: $\,(-1)^{\large n}\equiv 1\iff (-1)^{\large n}\not\equiv -1,\,$ which is true for any modulus $\neq 2\$ $\qquad\ \ \ \ \ \ \ \$ – Bill Dubuque Oct 1 at 14:21

Note that both numbers $$3^n-1$$ and $$3^n+1$$ are even numbers and that their difference is $$2$$. Therefore, one and only of them is a multiple of $$4$$.
Given \begin{align}3^n+1\not\equiv0\pmod4&\implies(-1)^n\not\equiv-1\pmod4\\&\implies(-1)^n\equiv1\pmod4,\end{align} we have that $$3^n-1\equiv(-1)^n-1\equiv1-1\equiv0\pmod4$$ as desired.
• Sorry how is $3^n+1$ (mod4) go to $(-1)^n$ is congruent to 1(mod4)? – Dylan Y Oct 2 at 1:30
• Because $3\equiv-1\pmod4$ so $3^n\equiv(-1)^n\pmod4$. Now we know that $(-1)^n$ can only take the values $-1$ and $1$, but we are given that $3^n+1\not\equiv0\pmod4\implies(-1)^n\not\equiv-1\pmod4$. Therefore $(-1)^n\equiv1\pmod4$. – TheSimpliFire Oct 2 at 6:35