0

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.

dfdf1
  • 85
  • 4
  • 1
    See [this question](https://math.stackexchange.com/questions/7473/prove-that-gcdan-1-am-1-a-gcdn-m-1) – lulu Nov 24 '20 at 18:09
  • 1
    It would improve your setup of the problem to include a definition of Fermat number $F_n$, so that the divisibility property you want to show is framed in a clearer way. – hardmath Nov 24 '20 at 18:10
  • so I need to prove that, in order to use it with Fermat numbers? because in class I remember us proving that. – dfdf1 Nov 24 '20 at 18:29
  • I still get stuck. – dfdf1 Nov 24 '20 at 18:59
  • Do you mean $F_{n-1}$ or $F_{n}-1$? – Joshua Wang Nov 27 '20 at 17:49
  • Welcome to Mathematics Stack Exchange. Please use [MathJax](https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference). Can't you use $2^a-1|2^b-1$ if $a|b$? – J. W. Tanner Nov 27 '20 at 17:49
  • (Fn) - 1 ,and I am sorry I dont know how to use MathJax, I'll try to learn – gftyh Nov 27 '20 at 18:06
  • I need to divide them via long polynomial – gftyh Nov 27 '20 at 18:07
  • look for this question you"ll understand what I mean :Fermat numbers question – gftyh Nov 27 '20 at 18:59
  • they didnt show how they did the polynomial division in that question, and Im asking for it. – gftyh Nov 27 '20 at 19:08
  • In this question I just used the fact that in order to prove your result you just need to show that $2^{2^{n+1}}-1 \mid (2^{2^{n+1}})^{2^k}-1$ for some non negative integer $k$. Calling $t=2^{2^{n+1}}$ you just need to show that the polynomial $t-1 \mid t^{2^k}-1$ using long division. – PAM1499 Nov 27 '20 at 20:28

2 Answers2

0

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?

PAM1499
  • 1,167
  • 1
  • 7
  • 11
0

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.

PAM1499
  • 1,167
  • 1
  • 7
  • 11