Problem about Fermat numbers and order of an element

  • #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.
 

Answers and Replies

  • #2
695
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.
 
  • #3
i think i know how to continue the problem. thanks for your reply!
 
  • #4
695
2
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).
 
  • #5
ah yes that is what i have concluded as well. your first post still helped me to come to fact though!
 

Related Threads on Problem about Fermat numbers and order of an element

  • Last Post
Replies
1
Views
2K
Replies
8
Views
6K
Replies
7
Views
3K
  • Last Post
Replies
10
Views
6K
  • Last Post
Replies
2
Views
16K
  • Last Post
Replies
13
Views
309
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
2K
Top