# proving that $2^{m-1}$ has reminder $1$ when divided by $m$

Let $$m = \frac{4^p - 1}{3}$$

Where $p$ is a prime number exceeding $3$. how to prove that $2^{m-1}$ has reminder $1$ when divided by $m$

-
What makes you think it's true? –  Gerry Myerson Jul 3 '12 at 10:30
it's true until i find a counterexample. –  Frank Jul 3 '12 at 10:34
How hard have you tried to find one? –  Gerry Myerson Jul 3 '12 at 10:42
Not much ,did you find one ? –  Frank Jul 3 '12 at 10:58
Wolfram gave up after the 6th prime... –  draks ... Jul 3 '12 at 11:09

$2^{2p}=4^p=3m+1\equiv 1 \pmod m$ so the result follows if $2p\mid m-1$.
Since $m$ is odd $2\mid m-1$, and by Fermat's Little Theorem $p\mid 4^p-4=3(m-1)$. Since $p>3$ is prime we must have $p\mid m-1$.
Nice.${}{}{}{}$ –  Gerry Myerson Jul 3 '12 at 12:45
How 2p|(m-1)? $(2p,m-1)$ can always divide $ord_m2$ which may be less than (m-1), right? –  lab bhattacharjee Jul 5 '12 at 11:44
@lab, $3(m-1)=4^p-4$ which is divisible by $2$ and by Fermat is also divisible by $p$. So $2p|3(m-1)$, and since $\gcd(2p,3)=1$ then $2p|(m-1)$. Perhaps I should have presented that step first, but it doesn't require consideration of $ord_m 2$. –  Zander Jul 6 '12 at 3:51