Factoring $F_{1001}$

Question

The question is asking me to prove that $F_{1001}$ is congruence to $1 \bmod 4$. I knew that if $n$ is odd then all prime odd divisor $p$ of $F_n$ satisfy $p \equiv 1 \pmod{4}$. However, my question is how to find the odd prime divisor? How do we factor out such a big fibonacci number?

Answer 1

Factoring big numbers that don't have an immediate product representation is pretty much impossible, without the correspondingly big computers to churn out the numbers. However, we can prove that $F_{1001}\equiv1\pmod{4}$ much easily.

First note that $F_0\equiv0\equiv8\equiv F_6\pmod{4}$, and that $F_1\equiv1\equiv13\equiv F_7\pmod{4}$. One can then easily prove by induction that $$F_n\equiv F_{n+6}\pmod{4}.$$ Therefore, $$F_{1001}\equiv F_{6\cdot166+5}\equiv F_5\equiv5\equiv1\pmod{4},$$as we wanted.

Answer 2

It is actually possible to factor $F_{1001}$.

\begin{align*} F_{1001}=&13^2\cdot89\cdot233\cdot8009\cdot8581\cdot741469\cdot988681\cdot4832521\cdot159607993\\ &\cdot1929584153756850496621\cdot5811794973846976755532222929865278366042132879433\\ &\cdot46051361876019993056032153159112764928518076136032760569320871268374299454861127226737142167112433 \end{align*}

---

We have the factorizations \begin{align*} F_7&=13,\\ F_{11}&=89,\\ F_{13}&=233,\\ F_{77}&=13\cdot89\cdot988681\cdot4832521,\\ F_{91}&=13^2\cdot233\cdot741469\cdot159607993,\\ F_{143}&=89\cdot233\cdot8581\cdot1929584153756850496621. \end{align*} To factor $F_{1001}$, we first divide out by the primes that we have already found: $$F_{1001}=13^2\cdot89\cdot233\cdot8581\cdot741469\cdot988681\cdot4832521\cdot159607993\cdot1929584153756850496621\cdot C$$ where $C$ denotes a $151$-digit composite number. Suppose that $p$ is a prime number dividing $C$. Then the Fibonacci entry point $a_p$ must equal $1001$. One useful fact about Fibonacci entry points is that if $p\equiv1,4\pmod{5}$ then $a_p\bigm|p-1$ and if $p\equiv2,3\pmod{5}$ then $a_p\bigm|p+1$.

By the Chinese remainder theorem, $p$ has a remainder of $1$ or $3002$ or $3004$ or $4003$ modulo $5005$. We can do a little better by noting that $p$ must be congruent to 1 modulo 4 (by URL's comment on his answer). Then $p$ has a remainder of $1$ or $8009$ or $14013$ or $18017$ modulo $20020$. This immediately finds the prime factor $8009$ of $C$. Factoring the rest of $C$ is more challenging and is best done with the ECM.