Register to reply

Fermat Numbers - Factor Form Proof

by TaliskerBA
Tags: factor, fermat, form, numbers, proof
Share this thread:
TaliskerBA
#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
Wildfires and other burns play bigger role in climate change, professor finds
SR Labs research to expose BadUSB next week in Vegas
New study advances 'DNA revolution,' tells butterflies' evolutionary history
TaliskerBA
#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