Fermat numbers question

Question

I am looking for direction in my question. The question is to prove, by long polynomial division, that: \begin{equation} 2^{2^{n+1}}-1\ |\ 2^{F_n-1}-1 \end{equation}

I have tried a lot of things, like calling:\begin{equation} t=2^{2^n} \end{equation} and trying long polynomial division right away, but none of this worked successfully.

Answer 1

With the tip given by lulu you have $gcd(2^{2^{n+1}}-1,2^{F_n-1}-1)=2^{gcd(2^{n+1},F_n-1)}-1=2^{gcd(2^{n+1},2^{2^{n}})}-1$. Notice that for all $n \in \mathbb{N}$ $n+1\leq 2^n$(use induction to see this). Hence $2^{n+1} \mid 2^{2^n}$ and $gcd(2^{n+1},2^{2^{n}})=2^{n+1}$. So, $gcd(2^{2^{n+1}}-1,2^{F_n-1}-1)=2^{2^{n+1}}-1$ and we have that $2^{2^{n+1}}-1 \mid 2^{F_n-1}-1$.

Another try Notice (again) that $n+1\leq 2^n$. Hence there is some $k \in \mathbb{N}$ such that $(n+1)+k=2^n$. Then $2^{2^n}=2^{(n+1)+k}=2^{n+1} \cdot 2^k$. Notice then that $$ 2^{F_n-1}-1=2^{2^{2^n}}-1=2^{2^{n+1} \cdot 2^k}-1=(2^{2^{n+1}})^{2^k}-1. $$ So, to prove that $2^{2^{n+1}}-1 \mid 2^{F_n-1}-1$ is equivalent to prove that $2^{2^{n+1}}-1 \mid (2^{2^{n+1}})^{2^k}-1$. Now call $t=2^{2^{n+1}}$ and you need to prove that $t-1 \mid t^{2^k}-1$. Can you use long division to finish this?

Answer 2

If you want to see how to use Polynomial long division as described in here https://en.wikipedia.org/wiki/Polynomial_long_division to show that $t-1 \mid t^{2^k}-1$ let's do it.

Here the dividend is $t^{2^{k}}-1$ and the divisor is $t-1$. The first step of Polynomial long division is to divide the first term of the dividend ($t^{2^{k}}$) by the highest term of the divisor ($t$) $$ \frac{t^{2^{k}}}{t}=t^{2^{k}-1}. $$ Now we multiply the divisor ($t-1$) by the result just obtained ($t^{2^{k}-1}$) to get $$ t^{2^{k}-1}(t-1)=t^{2^{k}}-t^{2^{k}-1}. $$ Now subtract the product just obtained ($t^{2^{k}}-t^{2^{k}-1}$) from the appropriate terms of the original dividend ($t^{2^{k}}-1$) and we get $t^{2^{k}-1}-1$. Now we repeat the process with $t^{2^{k}-1}-1$ as the dividend. Repeating the process one gets $t^{(2^{k}-1)-1}-1=t^{2^{k}-2}-1$. And in the $r-1$-th step one gets $t^{2^{k}-r}-1$(prove it). Suppose WLOG that we must stop the process at this step. This means that the degree of the polynomial $t^{2^{k}-r}-1$ is smaller then the degree of the polynomial $t-1$. Since the degree of $t-1$ is $1$ we know that the degree of $t^{2^{k}-r}-1$ must be $0$. Hence we must have that $r=2^k$ and that $t^{2^{k}-r}-1=t^0-1=0$. So we have that the remainder of the long division is $0$. And we are done.