Question -

Prove that for $n \geq 5, f_{n}+f_{n-1}-1$ has at least $n+1$ prime factors, where $f_{n}=2^{2^{n}}+1$

My proof - I proved it using induction,but i got stucked in base case step,

for $n=5$ we get after lots of factoring that $f_{5}+f_{4}-1$ = $3 \cdot 7 \cdot 13 \cdot 241 .(2^{16}-2^8+1)$

Now i am not able to factor $(2^{16}-2^8+1)$ , i tried mod $3,7,19,13,9$ but none of them working ...


  • 3
    $\begingroup$ You don't need to factor that term, You just need to show that it is not divisible by $3,7,13,241$. $\endgroup$ – lulu May 29 at 10:51
  • 1
    $\begingroup$ $65281 = 97\times 673 $ $\endgroup$ – Henry May 29 at 10:53
  • 1
    $\begingroup$ See, $-2^8=2^8-2^9=(2^7+2^7)+2^9-2^(10)=(2^7+2^7)-(2^9)+(2^5.2^5)$. Also, $2^{16}=2^9.2^7$. So, $2^{16}-2^8+1=[(2^9.2^7)+(2^7.2^7-2^9.2^5)+(2^7.2^5-2^7.2^5)]+[-(2^5.2^5)--(2^7+2^7)+2^9]+(2^5-2^5)+1=(2^9+2^7+2^5+1).(2^7-2^5+1)$. $\endgroup$ – Alapan Das May 29 at 12:14
  • 1
    $\begingroup$ $$2^{2^n} + 2^{2^{n-1}} + 1 = \frac{2^{3\cdot 2^{n-1}} - 1}{2^{2^{n-1}} - 1}$$ and $\gcd \bigl(2^{2^n} + 2^{2^{n-1}} + 1, 2^{2^{n-1}} - 1\bigr) \mid 3$. So for a non-obvious prime factor $p$ of $f_n + f_{n-1} - 1$, the order of $2$ modulo $p$ is $3\cdot 2^{n-1}$, whence $p \equiv 1 \pmod{3\cdot 2^{n-1}}$. For $n = 5$, you get $p \equiv 1 \pmod{48}$, and then $97$ is the first candidate to check. $\endgroup$ – Daniel Fischer May 29 at 13:05
  • 1
    $\begingroup$ If you want another method, note that $3^{65281}\not \equiv 3\pmod {65281}$. That proves $65281$ isn't a prime. Again, though, I think brute force is easier. $\endgroup$ – lulu May 29 at 13:05

Base case:


By the question and the comments, we get $$f_5+f_4+1=3\times7\times13\times97\times241\times673$$, so base case finished.

Let $p(n)$ be the number of distinct prime factors of $n$.

Assume the proposition is true for integer $k\ge5$, i.e. $$p(f_k+f_{k-1}+1)=p\Big(2^{2^{k+1}}+2^{2^k}+1\Big)\ge k+1$$. Then we let $K=2^{2^k}$.

So $$p(f_k+f_{k-1}+1)=p\big(K^2+K+1\big)\ge k+1$$

When $n=k+1$,

$$p(f_{k+1}+f_{k}+1)=p\big(K^4+K^2+1\big)= p\Big(\big(K^2+K+1\big) \big(K^2-K+1\big) \Big)$$. As the number of distinct prime factors of $K^2+K+1 $ is larger than $k+1$, also $K^2+K+1$ and $K^2-K+1$ are coprime, so $K^2-K+1$ has at least one prime factor which is not a prime factor of $K^2+K+1$, so $$p(f_{k+1}+f_{k}+1)=p\big(K^4+K^2+1\big)\ge k+1+1=k+2 $$, as desired.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.