7
$\begingroup$

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$

  • 0
    What makes you think it's true?2012-07-03
  • 0
    it's true until i find a counterexample.2012-07-03
  • 0
    How hard have you tried to find one?2012-07-03
  • 0
    Not much ,did you find one ?2012-07-03
  • 0
    [Wolfram](http://tinyurl.com/crv5qz7) gave up after the 6th prime...2012-07-03

1 Answers 1

8

$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$.

  • 0
    Nice.${}{}{}{}$2012-07-03
  • 0
    How 2p|(m-1)? $(2p,m-1)$ can always divide $ord_m2$ which may be less than (m-1), right?2012-07-05
  • 0
    @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$.2012-07-06
  • 0
    @Zander, thanks for your lucid explanation.2012-07-06