Fermat Numbers - Factor Form Proof


by TaliskerBA
Tags: factor, fermat, form, numbers, proof
TaliskerBA
TaliskerBA is offline
#1
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.

Thanks
Phys.Org News Partner Science news on Phys.org
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
TaliskerBA
TaliskerBA is offline
#2
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].

Also,
[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