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
NASA's space station Robonaut finally getting legs
Free the seed: OSSI nurtures growing plants without patent barriers
Going nuts? Turkey looks to pistachios to heat new eco-city
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