フィボナッチ数の平方数は 0, 1, 144 のみ 資料: [Cohn ]
フィボナッチ数 $(\ldots, F_0, F_1, F_2, \ldots) = (\ldots, 0, 1, 1, \ldots), F_{n+2} = F_{n+1} + F_n$ のうち、平方数は $F_0 = 0, F_{-1} = F_1 = F_2 = 1, F_{12} = 144$ のみであることを示す。
黄金比を $\phi := (1 + \sqrt{5}) / 2$ とし、その共役を $\overline \phi = (1 - \sqrt{5}) / 2$ とすると、フィボナッチ数は $F_n = (\phi^n - {\overline\phi}^n) / \sqrt{5}$ である。これの性質を調べるため、同じような漸化式で定義されるリュカ数列 $(\ldots, L_0, L_1, L_2, \ldots) = (\ldots, 2, 1, 3, \ldots), L_{n+2} = L_{n+1} + L_n$ を定義し、それとの関係式を利用する。
$L_n, F_n = x^2, 2x^2$ を満たす $n$ の性質を調べるのが方針である。その途中で以下の補題とその系を用いる。
補題: $p \equiv 3 \pmod 4$ なる素数 p に対して $A \equiv -1 \pmod {p}$ が成立する場合、 $A$ は平方数ではない。
系: $m \equiv 3 \pmod 4$ なる正の有理整数 m に対して $A \equiv -B^2 \pmod {m}$ が成立する場合、 $A$ は平方数ではない。
フィボナッチ数列: $(\ldots, F_0, F_1, F_2, \ldots) = (\ldots, 0, 1, 1, \ldots), F_{n+2} = F_{n+1} + F_n$
リュカ数列: $(\ldots, L_0, L_1, L_2, \ldots) = (\ldots, 2, 1, 3, \ldots), L_{n+2} = L_{n+1} + L_n$
閉じた式での表現は以下の通り:
フィボナッチ数列: $F_n = (\phi^n - {\overline\phi}^n) / \sqrt{5}$
リュカ数列: $L_n = \phi^n + {\overline\phi}^n$
$p \equiv 3 \pmod 4$ なる素数 p に対して $A \equiv -1 \pmod {p}$ が成立する場合、 $A$ は平方数ではない。
証明
$m \equiv 3 \pmod 4$ なる正の有理整数 m 、および m と互いに素な有理整数 B に対して $A \equiv -B^2 \pmod {m}$ が成立する場合、 $A$ は平方数ではない。
証明
(cong-L) $2 | k$ のとき、 $L_{n+2k} \equiv -L_n \pmod{L_k}$
(cong-F) $2 | k$ のとき、 $F_{n+2k} \equiv -F_n \pmod{L_k}$
証明
(per-L2) $3 | m \Leftrightarrow 2 | L_m$
(per-L3) $m \equiv 2 \pmod{4} \Leftrightarrow 3 | L_m$
(per-L4) $2 | k, 3 \not | k$ のとき、 $L_{k} \equiv 3 \pmod{4}$
(per-L8) $L_{n+12} \equiv L_n \pmod{8}$
証明
(F-even) $F_{2m} = F_mL_m$
(gcd-3) $\mathrm{gcd}(F_{3m}, L_{3m}) = 2$
(gcd-not-3) $3 \not| n$ のとき、 $\mathrm{gcd}(F_{n}, L_{n}) = 1$
証明
なお、フィボナッチ数列とリュカ数列の最初の数項を載せておく。
$n$ 0
1
2
3
4
5
6
7
8
9
10
11
12
$L_n$ 2
1
3
4
7
11
18
29
47
76
123
199
322
$F_n$ 0
1
1
2
3
5
8
13
21
34
55
89
144
数列 $L_n$ と $F_n$ に対して、それが $x^2$ や $2x^2$ の形で表せるのがいつなのかを調べる。 $L_n$ のケースが $F_n$ のケースの証明に必要なので、両方調べなければならない。
$L_n = x^2$ となるのは $n = 1, 3$ のときのみ。
証明
$L_n = L_{n/2}^2 \pm 2$ であり、 2 だけ離れている平方数のペアは存在しないので、この場合はあり得ない。
$L_1 = 1$ は平方数である。 $n \ne 1$ のとき、ある有理整数 $d \ge 2$ と奇数 $c$ を使って $n = 1 + 2^dc$ と表せる。
(*) $k = 2^{d-1}$ は偶数であって 3 の倍数でない。この k に対して (cong-L) を使用すると、使用回数 $c$ は奇数であるため $L_n \equiv -L_1 = -1 \pmod{L_k}$ が言える。 (per-L4) から $L_k \equiv 3 \pmod 4$ であったため、系 2 から $L_n$ は平方数ではない。
ここで使用した (*) の議論は今後も何度も使用する。
$L_3 = 4$ は平方数である。 $n \ne 3$ のとき、ある有理整数 $d \ge 2$ と奇数 $c$ を使って $n = 3 + 2^dc$ と表せる。そのあとは (*) の議論を使用する。
$L_n = 2x^2$ となるのは $n = 0, \pm 6$ のときのみ。
証明
(per-L2) から、 $L_n$ が偶数であるためには $3|n$ でなければならない。
$n$ が奇数の場合 ($n \equiv \pm 3 \pmod{12}$ の場合)、(per-L8) と $L_{\pm 3} = \pm 4$ (複号同順) から、 $L_n \equiv 4 \pmod 8$ が言える。これを満たす $2x^2$ の形の整数は存在しない。これから $6|n$ が言える。
$L_0 = 2$ は条件を満たす。
(**) $n \ne 0$ のとき、(*) の議論を使うと $L_n \equiv -L_0 = -2 \pmod{L_k}, L_k \equiv 3 \pmod 4$ なる k が存在するが、 $L_n/2 \equiv -1 \pmod {L_k}$ であるから $L_k/2$ は平方数ではあり得ない。
$L_6 = 18$ は条件を満たす。
(**) の議論をそのまま使うと $L_n/2 \equiv -9 \pmod {L_k}$ なる k が構築できる。ここで k を 4 の倍数としてとることができるので、(per-L3) から $L_k$ は 3 の倍数ではなく、特に 9 と互いに素である。
$L_{-6} = 18$ は条件を満たす。それ以外は (2) と同様。
$F_n = x^2$ となるのは $n = 0, \pm 1, 2, 12$ のときのみ。
証明
$m$ を有理整数として $n=2m$ としてよい。
$F_n=F_mL_m$ と (gcd-3) および (gcd-not-3) から、 $(F_m, L_m) = (2x^2, 2y^2)$ あるいは $(F_m, L_m) = (x^2, y^2)$ が成立する。($x, y$ は有理整数)
$3|m$ のとき、(gcd-3) から $(F_m, L_m) = (2x^2, 2y^2)$ である。
定理 4 から、 $m = 0, \pm 6$ である。その中で $F_{2m}$ が平方数になるのは $m = 0, 6$ ($n = 0, 12$ ) のみである。
$3 \not| m$ のとき、(gcd-not-3) から $(F_m, L_m) = (x^2, y^2)$ である。
定理 3 から、 $m = 1$ ($n = 2$ ) である。このとき実際に $F_{2m} = F_2 = 1$ は平方数。
$n \equiv 1 \pmod 4$ のとき:
$n=1$ のとき $F_n = F_1 = 1$ は平方数。
$n \ne 1$ のとき、ある有理整数 $d \ge 2$ と奇数 $c$ を使って $n = 1 + 2^dc$ と表せる。 そのあとは (*) の議論を使う。
$n \equiv -1 \pmod 4$ のとき:
$n=-1$ のとき $F_n = F_{-1} = 1$ は平方数。
$n \ne -1$ のとき、ある有理整数 $d \ge 2$ と奇数 $c$ を使って $n = -1 + 2^dc$ と表せる。 そのあとは (*) の議論を使う。
[Cohn ]: https://math.la.asu.edu/~checkman/SquareFibonacci.html