Which Fibonacci numbers are the sum of two squares?

Question

The Fibonacci numbers ($F_0=0$, $F_1=1$, $F_{n}=F_{n-1}+F_{n-2}$) have the identity $$F_{2k+1}=F_k^2 + F_{k+1}^2.$$ In particular, if $n$ is odd, then $F_n$ is a sum of two squares. Are there infinitely many even $n$ for which $F_n$ is a sum of two squares?

---

Some comments (building from my notes and also from the comments and answers below)

The set of even $n$ (nonnegative, naturally) with $F_{2n}$ the sum of two squares begins $$\{ 0,2,6,12,14,26,38,62,74,86,98,122,134,146,158,182,222,254,$$ $$326,338,366,398,446,614,626,698,722,794,866,1022,1046,\ldots\},$$ using the tables at Mersennus.net. There are five entries in this list that are not 2 mod 12: three small numbers (0, 6, 12) that can be forgiven their impertinence, but also 222 and 366 (both are 6 mod 12, and also 78 mod 144).

The list of possible indices (possible because not all of the factorizations are complete) continues $$\ldots, 1082,1226,1238,1418,1646,1814,2174,2246,2258,2282,2294,$$ $$2426,2498,2558,3002,3062,3302,3494,3662,3698,3782,3902,4058,$$ $$4106,4178,4274,4394,4478,4502,4574,4622,4682,4826,4874,4898,4934,$$ $$4946,5102,5174,5558,5594,5702,5714,5798,6074,6326,6362,6542,6614,$$ $$6638,6746,6794,6914,6998,7022,7154,7278,7286,7382,7394,7454,7494,$$ $$7538,7586,7694,7754,7838,7934,8006,8054,8138,8186,8222,8258,8486,$$ $$8522,8594,8906,9038,9074,9194,9206,9242,9326,9398,9446,9638,9662,$$ $$9782,9806,9818,9866,9902$$

This list contains two more indices that are not 2 mod 12: 7278 (possibly giving a sum of two squares) and 7494 (definitely giving a sum of two squares). Note $366-222=12^2$ and $7494-7278=6^4$. Also, all four of 222, 366, 7278, 7494 have the form $6p$ (with $p$ a prime, of course).

---

The Fibonacci numbers are periodic modulo $m$ (for any $m>1$). Considering the sequence modulo 4, for example, it repeats 0, 1, 1, 2, 3, 1. Since the sum of two squares is never 3 mod 4, we learn that $F_{6n+4}$ is never the sum of two squares. Varying the modulus allows us to eliminate many other congruence classes. There are some numbers, for example $F_{78}$, that are not the sum of two squares but do not seem to be eliminatable in this manner.

---

If $n$ is negative and even, then $F_n$ is negative. This restricts the possibilities for an algebraic family (such as the one that exists for odd-indices).

---

The Lucas numbers are $L_0=2,L_1=1,L_{n}=L_{n-1}+L_{n-2}$. The identity $F_{2n}=F_nL_n$, coupled with the easy fact that $\gcd(F_n,L_n)$ is 1 or 2, implies that $F_{2n}$ is the sum of two squares if and only if both $F_n$ and $L_n$ are.

Answer 1

This is not a solution, just some thoughts which are too long for a comment. I have added proofs of Will Jagy and Junkies comments/conjectures which are fairly interesting on their own.

First, the Fibonacci numbers are a divisibility sequence, which means that $$\gcd(F_n,F_m)=F_{\gcd(n,m)}.$$
Added: Proof of part of Will Jagy's Observation:

Claim: If $n\equiv 5\pmod{6}$ then $L_n$, and hence $F_{2n}$ are divisible by some prime $p\equiv 3 \pmod{4}$.

Proof: Look at $L_n$ modulo $4$. Then the sequence is $L(0)\equiv 2$, $L(1)\equiv 1$, $L(2)\equiv 3$, $L(3)\equiv 0$, $L(4)\equiv 3$, $L(5)\equiv 3$, $L(6)\equiv 2$, $L(7)\equiv 1$, and at this point it must repeat. The cycle length is $6$, and $L(5)\equiv 3$. This means that $L(5+6k)\equiv 3\pmod{4}$ for all $k$. Hence $L(5+6k)$ is always divisible by a prime congruent to $3$ mod $4$.

Since $L_n |L_{kn}$ when $k$ is odd, we can conclude that if $p\equiv 5 \pmod{6}$ divides $n$, then some prime $q\equiv 3\pmod{4}$ must divide $F_{2n}$. This is because either $2|n$, and hence $3|F_{2n}$, or $n$ is odd, and $L_p|L_n$ so that $q|F_{2n}$.

Added Proof Of Junkie's Comment:

Claim: The density of even Fibonacci numbers which are not divisible by some prime of the form $3+4k$ is $0$.

Proof: This is a corollary of Will Jagy's observation. Since the density of numbers which are not divisible by a prime of the form $5+6k$ is zero, it follows from the previous claim that the density of even Fibonacci numbers not divisible by a prime of the form $3+4k$ is $0$.

Conjectures and other thoughts: Recall that we can write $F_n$ as a sum of two squares if it has no prime factors of the form $3+4k$.

Conjecture 1: The only Fibonacci number of the form $F_{2n}$ which is divisible by some prime of the form $3+4k$ and can be written as the sum of two squares is $F_{12}$.

$F_{12}$ is a very special Fibonacci number for a few reasons. One is that it is the only nontrivial square. If we change the condition to a sum of two nonzero squares, then $F_{12}$ is automatically excluded. Also, since no other Fibonacci numbers are squares, nothing else is affected. Hence we can rephrase conjecture 1 as:

Conjecture 1: If $F_{2n}$ is divisible by some prime of the form $3+4k$ then it cannot be written as the sum of two nonzero squares.

One reason for this conjecture is that it checks out numerically in large range, up to $F_{1000}$. Also, it would be nice if it was true.

Assuming this, by the divisibility property, given a prime $p=3+4k$, we need only care about the first time it appears in the Fibonacci Sequence. There is a theorem which states that $$F_{p-\left(\frac{p}{5}\right)}\equiv 0 \pmod{p},\ \ \ \ \ \ \ \ \ (1) $$ where $\left(\frac{p}{5}\right)$ is the Legendre symbol. Conjecture 1 would imply that if $2n$ is divisible by $p-\left(\frac{p}{5}\right)$ for any $p\equiv 3 \pmod{4}$, then $F_{2n}$ is not the sum of two nonzero squares.

Previously, I said some things about what happens if the above were an "if and only if" for primes of the form $3+4k$ (it clearly isn't for $1+4k$) Small update: It also is just false for $3+4k$, since $3571=3+4k$, is prime and divides $F_{68}$.

Examples: The first few primes congruent to $3$ mod $4$ less then $100$ are $$3,7,11,19,23,31,41,47,59,67,71,79,83,87$$ and they divide respectively $$F_4, F_8, F_{10}, F_{18}, F_{24}, F_{30}, F_{40}, F_{48}, F_{58}, F_{68}, F_{70}, F_{78}, F_{84}, F_{88}.$$

So in particular, (assuming conjecture 1) if I want $F_{2n}$ to be a sum of two nonzero squares, $2n$ cannot be divisible by any of the above. I.e. we cannot have any of $$2|n, \ 5|n, \ 9|n,\ 29|n,\ 39|n .$$ This idea can give us a large list of primes, none of which can divide $n$, but that is about all I can get it to do.

Answer 2

Two short remarks related to this problem and Eric's conjectures:

1) In the paper

C. Ballot and F. Luca, ‘ On the equation $x^2 + dx^2 = F_n$ ’, Acta Arith. 127 (2007), 145–155.

the authors show that the equation $x^2+y^2=F_{2n}$ has no solution for most integers $n$.

2) In the problem section of the 42th volume of the Fibonacci Quarterly, 2004, it is shown that the set of integers $n$ such that $F_n$ is divisible by a prime of the form $4k+3$ has asymptotic density $\frac12$.

Answer 3

This is similar to Eric's observations. It is certainly true that there is periodicity in taking the Lucas numbers modulo some prime, and if 0 ever appears it does so in a predictable pattern. I have been playing with these, and have a simple conjecture: if $n$ is odd and $ p | n,$ where $p \equiv 5 \pmod 6,$ then $L_n$ is divisible by a prime $q \equiv 3 \pmod 4,$ where $q$ depends only on $p,$ as in the table below. Note that the bad factors all satisfy $q \equiv 11, 19 \pmod{20},$ so there may be an easy quadratic reciprocity proof for larger $p \equiv 5 \pmod 6.$ Then it is anyone's guess whether $q^2 | L_n,$ but if not then $L_n$ is not the sum of two squares. The possible use of this is in Dror's comments above and $ F_{2n} = F_n L_n.$

  p                      q
  5                     11
 11                    199
 17                   3571
 23                    139
 29                     59
 41              370248451
 47             6643838879
 53           119218851371
 59                 336419
 71        688846502588399
 83             6202401259
 89                    179
101                   7879
107        479836483312919

Answer 4

Very different aspect, but interesting to me at least. The odd index Fibonacci numbers are one branch in the Markov tree,

http://en.wikipedia.org/wiki/Markov_number

http://oeis.org/A002559

Taking notation from the book by Cusick and Flahive, we have the Markov (or Markoff) equation $$m^2 + m_1^2 + m_2^2 = 3 m m_1 m_2,$$ where it follows from the process that generates the tree that $$ \gcd(m, m_1) = \gcd (m_1, m_2) = \gcd(m_2,m) = 1.$$ Then C+H define $u$ on pages 10 and 18 as the smallest positive integer such that $ \pm m_1 u \equiv m_2 \pmod m.$ Then we define an integer $v$ by $mv = u^2 + 1.$

It follows from $mv = u^2 + 1$ that every Markov number is represented, and primitively, as the sum of two squares.

At some point I had a proof (well, I think I did) that the Markov discriminants $$ 9 m^2 - 4 $$ were also the sum of two squares, although sometimes not primitively because these are divisible by 4 when $m$ is even. I cannot recall the proof but it was short and elementary.

PROOF: That was fun. We have $ m^2 + m_1^2 + m_2^2 = 3 m m_1 m_2$ in positive integers. We know from $ v m = u^2 + 1$ that $m$ is not divisible by any prime $q \equiv 3 \pmod 4,$ simply because any $k^2 +1$ is never divisible by such a prime, since $(-1|q)=-1.$ Now, take $\delta = \pm 1,$ and assume $$ 3 m \equiv 2 \delta \pmod q.$$ Then $ m^2 + m_1^2 + m_2^2 \equiv 2 \delta m_1 m_2 \pmod q,$ so then $ m^2 + m_1^2 - 2 \delta m_1 m_2 + m_2^2 \equiv 0 \pmod q,$ finally $$ m^2 + (m_1 - \delta m_2)^2 \equiv 0 \pmod q.$$ But this is a contradiction, as $m$ is not divisible by $q.$ So, in fact $ 3 m \neq \pm 2 \pmod q,$ then $9 m^2 - 4 \neq 0 \pmod q$ for any prime $q \equiv 3 \pmod 4.$

Answer 5

Since $F_{2n}=F_n L_n$ here is an observation about Lucas numbers being sum of squares, unfortunately it doesn't answer the question (hopefully some other identity might help).

Claim: If $L_{2n}$ is sum of two squares, $L_{10n}$ is sum of two squares too and $L_{10n}/L_{2n}$ is expressible as sum of two squares not depending on factorization.

An identity is $$ L_{2n}^2 - 4 = 5 F_{2n}^2 $$

which allows computing $\sqrt{-5} \pmod {L_{2n}}$ (A)

Another identity is:

$$L_{10n}=L_{2n}^5-5 L_{2n}^3 + 5 L_{2n} = (L_{2n}^4 - 5 L_{2n}^2 + 5) L_{2n} $$

Solving the quartic $= 0$ over $\mathbb{R}$ gives 3 roots all of them involving $\sqrt{+5}$, one of them is $ -\sqrt{\frac{1}{2} \, \sqrt{5} + \frac{5}{2}}$.

After squaring: $$ \sqrt{5} \equiv 2 L_{2n}^2-5 \pmod{L_{10n}/L_{2n}} $$

Combining with (A) we have $\sqrt{-1} \pmod{L_{10n}/L_{2n}}$ which allows efficiently expressing $L_{10n}/L_{2n}$ as a sum of two squares without factoring.

Probably this is just an identity I didn't know.

sage code for computing the root

def LU2(n):
    """
    lucas number
    """
    pr.<Z>=ZZ[]
    K.<v>=NumberField(Z**2-5,'a')
    gr=(1+v)/2
    return ZZ (gr**n + (-gr)**(-n))

def root1(n):
    """
    square root of -1 mod L_{10n}/L_{2n}
    """
    L=LU2(10*n)
    F=LU2(2*n)
    N=L/F #L_{10n}/L_{2n}
    assert F^5-5*F^3+5*F == L
    K=IntegerModRing(N)
    sp5=((2*K(F)^2-5) )
    sm5=(K(2)/fibonacci(10*n))
    assert sp5**2==5
    assert sm5**2== -5
    rootm1=sp5/sm5
    assert rootm1**2 == -1
    return N,rootm1

Answer 6

If we assume the conjecture that $6$ is the only even number such that $F_{2n}$ is the sum of two squares then $2$ cannot divide $n$. Then we also have $F_{2n}=F_n*L_n$ and so if $F_{2n}$ is the sum of two squares $F_n$ is the sum of two squares since n is odd so $F_{2n}$ is the sum of two squares if $L_n$ is the sum of two squares. Also if $n$ is odd and $F_{2n}$ is the sum of two squares then $L_n$ is the sum of two squares.
So if we assume the question is equivalent to the following are there an infinite number of odd $n$ such that $L_n$ is the sum of two squares.