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

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 ...

thankyou

• You don't need to factor that term, You just need to show that it is not divisible by $3,7,13,241$. – lulu May 29 at 10:51
• $65281 = 97\times 673$ – Henry May 29 at 10:53
• 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)$. – Alapan Das May 29 at 12:14
• $$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. – Daniel Fischer May 29 at 13:05
• 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. – lulu May 29 at 13:05

Base case:

$$n=5$$

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.