Showing that the Fermat number $F_j$ divides $F_k - 2$, where $0 \le j \lt k$

107 Views Asked by At

I have been instructed to solve this problem, at least in part, by showing that $F_k\equiv 2\pmod {F_j}$.

I started out thus (edited to include tentative solution):

$$2^{2^j}+1\equiv 0\pmod {F_j}$$ $$\implies 2^{2^j}\equiv -1\pmod {F_j}$$ $$\implies 2^{2^j}2^{2^k}\equiv -2^{2^k}\pmod {F_j}$$

From here, I cannot figure out what property of either congruences or Fermat numbers can bring me closer to a solution.

Second attempt: \begin{align} 2^{2^j}+1&\equiv 0\pmod {F_j}\\ 2^{2^j}&\equiv -1\pmod {F_j}\\ (2^{2^j})^{2^{k-j}}&\equiv {(-1)}^{2^{k-j}}\pmod {F_j}\\ 2^{2^k}&\equiv 1\pmod {F_j}\\ 2^{2^k}+1&\equiv 2\pmod {F_j}\\ 2^{2^k}-1&\equiv 0\pmod {F_j}\\ \end{align} Which is to say $${F_k}-2\equiv 0\pmod {F_j}$$ $$\implies {F_j} | {F_k}-2$$by the definition of congruence

2

There are 2 best solutions below

1
On BEST ANSWER

Hint:

As you said, $2^{2^j}\equiv-1\mod F_j$.

Now $2^{2^k}=2^{2^i2^{k-j}}=(2^{2^i})^{2^{k-j}},$

and if $0\le j<k$ then $2^{k-j}$ is even.

1
On

Hint : $(F_k-1)^{2^n} =F_{k+n}-1$.