Fermat Numbers - Factor Form Proof

[TaliskerBA]

Let k\in\mathbb{N}, and q be a prime factor of F_{k}=2^{2^{k}}+1.

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


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

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

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

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


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

Thanks

 

[TaliskerBA]

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 q | F_{k} = 2^{2^{k}} + 1 \Leftrightarrow 2^{2^{k}}\equiv -1 (mod q)

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

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

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

F_{k} = F_{k-1}F_{k-2}F_{k-3}...(2^{2^{l-1}} - 1) + 2.

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

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

Also,
F_{k+1} -2 = F_{k}F_{k-1}...F_{2}F_{1} = 0 (mod q) since q | F_{k}. So 2^{2^{k+1}} + 1 - 2 = 0 (mod q) \Rightarrow 2^{2^{k+1}} = 1 (mod q)

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

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

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

So, therefore, having exhausted all other possibilities, gcd(q-1,2^{k+1}) = 2^{k+1}, finishing the proof.