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.

  • 2
    $\begingroup$ 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$." $\endgroup$ – TonyK Oct 1 at 9:14
  • $\begingroup$ 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\ \ \ \ \ \ \ \ $ $\endgroup$ – 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.

  • $\begingroup$ Sorry how is $3^n+1$ (mod4) go to $(-1)^n$ is congruent to 1(mod4)? $\endgroup$ – Dylan Y Oct 2 at 1:30
  • $\begingroup$ 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$. $\endgroup$ – TheSimpliFire Oct 2 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.