Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Problem about Fermat numbers and order of an element

  1. Nov 12, 2011 #1
    Let Fn = 22n + 1 be the nth Fermat number and suppose that p|Fn, where p is a prime (possibly Fn itself). Show that [itex] 2^{2^{n+1}} \equiv 1 (mod p) [/itex] so that [itex] ord_p(2)|2^{n+1} [/itex]. Use this to show that [itex] ord_p(2) = 2^{n+1} [/itex].

    So far i have shown that [itex] 2^{2^{n+1}} \equiv 1 (mod p) [/itex] so that [itex] ord_p(2)|2^{n+1} [/itex]. But what I'm having trouble showing now is that 2n+1 is the smallest possible number k such that [itex] 2^k \equiv 1 (mod p) [/itex]. I know that the order of 2 must be some power of 2 so I have tried to use a contradiction argument assuming that there exists a 2k such that [itex] 2^{2^k} \equiv 1 (mod p) [/itex]. then i have [itex] 2^{2^{n+1}} \equiv 2^{2^k} (mod p) [/itex] so [itex] 2^{2^{n+1}-2^k} \equiv 1 (mod p) [/itex]. but i can't seem to find a contradiction.

    can someone give me some hints to continue? thanks.
  2. jcsd
  3. Nov 13, 2011 #2
    [itex]2^{2^{n+1}-2^k} = 2^{\left(2^k + 2^{k+1} + 2^{k+2} + ... + 2^n\right)} = 2^{2^k} \cdot 2^{2^{k+1}} \cdot 2^{2^{k+2}} \cdot ~...~ \cdot 2^{2^n}[/itex], but [itex]2^{2^k}[/itex] was 1 modulo p... See if you can unwind the whole thing to get [itex]2^{2^{k+1}} \equiv 1 \pmod p[/itex], at which point you can find your contradiction.

    Be careful, however (you probably know this already), with arguments that cancel something on both sides of a congruency. [itex]10 \equiv 6 \pmod 4[/itex], but [itex]5 \not\equiv 3 \pmod 4[/itex]. What you cancel out in your case are expressions congruent to 1 mod p, which, since they are 1 multiplying something, can be removed.
  4. Nov 13, 2011 #3
    i think i know how to continue the problem. thanks for your reply!
  5. Nov 14, 2011 #4
    Oops... I used a neat trick to conclude something stupid. Sorry, it was Sunday. :)

    Successive squares of [itex]2^{2^k}[/itex] will also be congruent to 1, which contradicts the initial statement that [itex]2^{2^n} \equiv -1 \pmod p[/itex] (since p has to be odd to divide Fn).
  6. Nov 14, 2011 #5
    ah yes that is what i have concluded as well. your first post still helped me to come to fact though!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook