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.