# Which Fibonacci numbers are the sum of two squares?

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?

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.

-
This question might be hard. If you really want to know the answer you could try a probabilistic model (which would prove nothing but might give you a good guess). I think probably $n=2$ mod 12 is the only case you care about (as long as $n>12$) and then you get lucky with 14,26,38 but are unlucky with 50 because there's a factor of 11. You want to try and guess the probability that a large fib number with $n=2 mod 12$ is divisible by an odd power of 11, 19, ... and then take the product and hope :-) – Kevin Buzzard Jun 12 '11 at 21:20
Small observation: since $F_{2n}=(2F_{n-1}+F_n)F_n$, and $\text{gcd}(2F_{n-1}+F_n,F_n)|2$, this implies that if $F_{2n}$ is a sum of squares then so is $F_n$, as well as $2F_{n-1}+F_n=F_{n-1}+F_{n+1}$. – Dror Speiser Jun 12 '11 at 22:21
Also $L_{30}$ is the sum of two squares, go figure. – Will Jagy Jun 12 '11 at 23:01
I think it was an Olympiad problem once: show that the set of $n$ such that $F_n$ has a prime divisor that is 3 mod 4 has (natural) density 1/2. None of the odd $n$ have such a divisor from your square relation of above, and then one can show that almost all (but not all) the even $n$ have such a divisor. – Junkie Jun 13 '11 at 5:46
I wanted to double-vote this question, and I find the discussion of it really interesting. – Mark Bennet Jun 13 '11 at 22:13

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

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.

-
I am confused by "If it was always the first, we would have the following if and only if statement" - it could still be the case that $F_{2n}$ is divisible by a prime congruent to 3 mod 4 but in even power? (As you mention yourself earlier, the condition for being a sum of two squares is an if-condition, not an if-and-only-if.) – Vladimir Dotsenko Jun 13 '11 at 8:45
$F_{12} =144$. – Emil Jeřábek Jun 13 '11 at 11:10
@Vladimir, @Emil: There were several problems with what I had previously said. (It was just some "thoughts") I updated things so that it makes more sense, and is not so bad. – Eric Naslund Jun 13 '11 at 16:12
Very nice. Evidently I wrote out a little table with $F_n$ mod 3 and mod 4, but did not do the same for $L_n.$ – Will Jagy Jun 13 '11 at 17:24
The quality you describe, $\gcd(F_a,F_b)=F_{\gcd(a,b)}$ is called strong divisibility; divisibility itself means only that $F_a|F_b$ when $a|b.$ – Charles Apr 14 '15 at 23:08

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

-
Right. I just wanted to point out these references. The paper by Ballot and Luca does not mention any results on fibonacci that can be written as a sum of two squares, so maybe the problem is still open. – J.C. Ottem Jun 13 '11 at 18:30
Good point, it much nicer to have on hand. – Eric Naslund Jun 13 '11 at 18:59
@J.C. Ottern: +1, this is very useful. I also misunderstood something, the first claim is implies the second but not necessarily vice versa!! – Eric Naslund Jun 13 '11 at 22:09

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

-
Also, you might have used this, but I'll put the link for any others reading the comments who want to play around with numerics: This page: mersennus.net/fibonacci has lists of the complete factorization of the first 1000 Fibonacci numbers and the first 1000 Lucas Numbers. – Eric Naslund Jun 13 '11 at 2:53
@Eric: $F_{12}=12^2$ is divisible by $3$. – Emil Jeřábek Jun 13 '11 at 11:18
@Will Jagy: I added a proof of your observation at the end of my answer. – Eric Naslund Jun 13 '11 at 16:59

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

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

-

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

-

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.

-