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

Fermat Numbers - Factor Form Proof

  1. Nov 14, 2012 #1
    Let [itex]k\in\mathbb{N}[/itex], and [itex]q[/itex] be a prime factor of [itex]F_{k}=2^{2^{k}}+1[/itex].

    Deduce that gcd[itex](q-1,2^{k+1})=2^{k+1}[/itex].

    [itex]q|F_{k}[/itex] [itex] \Rightarrow [/itex] [itex] mq = 2^{2^{k}}+1[/itex] for some [itex]m\in\mathbb{N}[/itex]

    [itex] 2^{2^{k}}=q-1+(m-1)q[/itex] [itex] \Rightarrow [/itex] [itex] 2^{2^{k}}=q-1[/itex] (mod [itex]q[/itex])

    [itex]2^{k+1}|2^{2^{k}}[/itex] since [itex]k+1\leq 2^{k}, \forall k\in \mathbb{N}[/itex]

    So [itex]2^{2^{k}}=n2^{k+1}[/itex] for some [itex]n\in \mathbb{N}[/itex].

    I think I'm missing something, so any nudge in the right direction would be much appreciated.

  2. jcsd
  3. Nov 15, 2012 #2
    Got there in the end. Here is the proof I used, I thought I'd post it as it was quite fun to prove in the end. I would also appreciate it if anyone can point out errors. Also, apologies for poor presentation I'm fairly new to Latex.

    Since [itex]q | F_{k} = 2^{2^{k}} + 1[/itex] [itex]\Leftrightarrow[/itex] [itex]2^{2^{k}}\equiv -1 [/itex] (mod [itex]q[/itex])

    Noting that [itex]2^{2^{k}} - 1 = (2^{2^{k-1}} +1)(2^{2^{k-1}} - 1) = F_{k-1}(2^{2^{k-1}} - 1)[/itex] you can write [itex]F_{k}[/itex] as:

    [itex]F_{k} = 2^{2^{k}} + 1 + (2 - 2) = 2^{2^{k}} - 1 + 2 = F_{k-1}(2^{2^{k-1}} - 1) + 2 = F_{k-1}F_{k-2}(2^{2^{k-2}} - 1) + 2 = F_{k-1}F_{k-2}...F_{2}F_{1} + 2 [/itex]

    So for any [itex] l =1,2, ..., k-1 [/itex] we can write [itex]F_{k}[/itex] as:

    [itex]F_{k} = F_{k-1}F_{k-2}F_{k-3}...(2^{2^{l-1}} - 1) + 2 [/itex].

    Assume that for some [itex] l =1,2,...,k-1 [/itex] we have [itex] 2^{2^{l}}\equiv 1 [/itex] (mod [itex]q[/itex]), then [itex](2^{2^{l-1}} - 1) = 0 [/itex] (mod [itex]q[/itex]) and [itex]F_{k} - 2 = 0 [/itex] (mod [itex]q[/itex] ) [itex] = F_{k} [/itex] since [itex]q | F_{k}[/itex]. So [itex] 2|q \Rightarrow q=2 [/itex], but [itex] F_{k} = 2^{2^{k}} + 1 [/itex] is odd, so we have a contradiction. Thus [itex] 2^{2^{l}} \not \equiv 1 [/itex] (mod [itex]q[/itex]) [itex] \forall [/itex] [itex] l = 1,...,k [/itex] since also, already shown that [itex]2^{2^{k}}\equiv -1 [/itex] (mod [itex]q[/itex])

    Now, since [itex]q[/itex] is prime, using Fermat's Little Theorem [itex] 2^{q-1} = 1 [/itex] (mod [itex]q[/itex]) since [itex] q \not | [/itex] [itex] 2 [/itex].

    [itex]F_{k+1} -2 = F_{k}F_{k-1}...F_{2}F_{1} = 0 [/itex] (mod [itex]q[/itex]) since [itex] q | F_{k} [/itex]. So [itex] 2^{2^{k+1}} + 1 - 2 = 0 [/itex] (mod [itex]q[/itex]) [itex] \Rightarrow 2^{2^{k+1}} = 1 [/itex] (mod [itex]q[/itex])

    Noting that [itex]x^a \equiv 1 [/itex] (mod [itex]m[/itex]) and [itex]x^b \equiv 1 [/itex] (mod [itex]m[/itex]) [itex] \Rightarrow x^{gcd(a,b)} \equiv 1 [/itex] (mod [itex]m[/itex]), we get the result:

    [itex] 2^{gcd(q-1,2^{k+1})} \equiv 1 [/itex] (mod [itex]q[/itex])

    Now, since [itex]gcd(q-1,2^{k+1})[/itex] must be a divisor of [itex]2^{k+1}[/itex] it must be of the form [itex] 2^{l} [/itex] for some [itex] l=0,...,k+1 [/itex] , but it can't be any [itex] l = 1,...,k [/itex] since otherwise [itex] 2^{2^{l}}\equiv 1 [/itex] (mod [itex]q[/itex]) contradicting our earlier result. Also, it can't be [itex] 2^{l=0} = 1 [/itex] since otherwise [itex] 2^{gcd(q-1,2^{k+1})} = 2 \equiv 1 [/itex] (mod [itex]q[/itex]) [itex] \Rightarrow q = 1 [/itex] which is a contradiction, because [itex] q [/itex] is prime.

    So, therefore, having exhausted all other possibilities, [itex] gcd(q-1,2^{k+1}) = 2^{k+1} [/itex], finishing the proof.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook