2

I'm trying to do the following question and am a bit stuck. Would appreciate a hint over a full solution if possible. Here $F_n$ denotes the $n$-th Fibonacci number, and at this point in the question we have already shown $F_{2n}=F_n(F_{n-1}+F_{n+1})$ and $F_{2n+1}=F_n^2+F_{n+1}^2$ for all $n \ge 1$.

Given $m \ge 1$ and $p$ an odd prime dividing $F_m$ determine whether the following statements are true or false:

  1. if $m$ is odd, then $p \equiv 1 \pmod 4$

  2. if $m$ is even, then $p \equiv 3 \pmod 4$

My line of thinking so far: I know (by Fermat's little theorem) that $x^2 \equiv -1 (\text{ mod p})$ has a solution iff $p \equiv 1 \pmod 4$. So if I can find such an $x$, or show none exist, then I am done. Especially in the $m$ odd case, by writing $m=2n+1$ we have $F_n^2+F_{n+1}^2 \equiv 0 \pmod p$ which implies $(F_n+F_{n+1})^2 \equiv -2F_nF_{n+1} \pmod p$. But I don't see how to progress any further on that front and have a feeling I'm going down a rabbit hole. My other thought is that since p is odd, we know $p$ must be congruent to one of $1$ or $3 \bmod 4$, so we can try and get a contradiction by assuming one or the other. No luck here either.

Bernard
  • 175,478
Mr_Random_Guy
  • 390

2 Answers2

3

Your original idea is solid.

The first claim follows from Cassini's identity: $$F_n^2=(-1)^{n+1}+F_{n-1}F_{n+1}$$

To see this, suppose $n+1$ is odd and that $p$ is an odd prime dividing $F_{n+1}$. We instantly get that $$F_n^2\equiv -1\pmod p$$ and we are done.

lulu
  • 70,402
2

We have $F_{10}=55$ for $m=10$. Since $p=5$ divides $F_{10}$, but $5\not\equiv 3\bmod 4$, statement $2.$ is false.

Statement 1. is proved in Lemma 2 here - if I understood correctly. Note that it implies that every Fibonacci number $F_{2n+1}$ is the sum of two squares by Fermat's result.

Dietrich Burde
  • 130,978
  • Thanks for the counter example, did you have a way of narrowing down or did you just evaluate every $F_m$ (as luck would have it I stopped after $m=9$)? Also any luck on statment 1? – Mr_Random_Guy Apr 28 '20 at 13:10
  • This is late but for future readers, since $F_{2n} = F_n(F_{n+1} + F_{n-1})$ then if $p$ divides $F_n$, it divides $F_{2n}$. Then for some odd $n$ there is a prime of the form $4k+1$ which divides $F_n$ and hence also divides $F_{2n}$. A good way to find this counterexample is then to find some odd n such that a prime of the form $4k+1$ divides $F_n$. $F_5 = 5$ so 5 divides $F_{10}$ even without calculating. – Ogglie Ostrich May 16 '23 at 14:10