Register to reply

Fermat Numbers - Factor Form Proof

by TaliskerBA
Tags: factor, fermat, form, numbers, proof
Share this thread:
Nov14-12, 10:57 PM
P: 26
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.

Phys.Org News Partner Science news on
Scientists discover RNA modifications in some unexpected places
Scientists discover tropical tree microbiome in Panama
'Squid skin' metamaterials project yields vivid color display
Nov15-12, 11:49 AM
P: 26
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.

Register to reply

Related Discussions
Fermat Numbers General Math 0
Utility of Form factor and Crest factor in an AC waverform Classical Physics 2
Fermat Numbers Calculus & Beyond Homework 9