Monday, 6 July 2015

divisibility - For every natural number $n$, prove that $4mid(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.

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...