インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

数、特に整数に関する記事。

144:フィボナッチ平方数

144は平方数であるようなFibonacci数で最大のものです。この記事では次の定理の証明を解説します:

定理(Cohn, 1964)
F_nが平方数となるのはn=0, \pm 1, 2, 12のときに限る。すなわち、平方数であるようなFibonacci数は0, 1, 144しかない。

実は、この記事では証明しませんが、冪乗数となるFibonacci数は0, 1, 8, 144のみであることがBeugeaud, Mignotte, Siksekによって証明されています(2006)。

Cohnの(第二)証明ではLucas数に関する考察が必要となります。
integers.hatenablog.com
integers.hatenablog.com

Fibonacci数とLucas数の関係

補題1 m, nは整数とする。このとき、
2F_{m+n}=F_mL_n+F_nL_m, \quad 2L_{m+n}=5F_mF_n+L_mL_n.

証明. Fibonacci数およびLucas数の一般項を用いればよい。 Q.E.D.

補題2 n3の倍数でなければF_nL_nは互いに素であり、n3の倍数ならばF_nL_nの最大公約数は2である。

証明. 補題1の2L_{m+n}=5F_mF_n+L_mL_nにおいて、m=-nとしてF_{-n}=(-1)^{n-1}F_n, L_{-n}=(-1)^nL_nを用いれば、4=(-1)^n(L_n^2-5F_n^2)が得られる。よって、F_nL_nの最大公約数の二乗は4を割り切る。つまり、最大公約数は12である。F_nおよびL_nが偶数になるのはn3の倍数のときであったから、証明が完了する。 Q.E.D.

補題3 k3の倍数でない偶数とする。このとき、
L_{n+2k} \equiv -L_n \pmod{L_k},\quad  F_{n+2k} \equiv -F_n \pmod{L_k}.

証明. kを固定してnに関する帰納法で証明する。induction stepは漸化式から自明に進むので、n=0, 1の場合に成立することを示せばよい。すなわち、示すべきはL_{2k} \equiv -2 \pmod{L_k}-①、L_{2k+1} \equiv -1 \pmod{L_k}-②、F_{2k} \equiv 0 \pmod{L_k}-③、F_{2k+1} \equiv -1 \pmod{L_k}-④である。Lucas数の記事で示した関係式からL_{2k} = L_k^2-2が成り立つ(kが偶数であることに注意)ので①がわかる。補題1から、F_{2k}=F_kL_kなので③も成立。2L_{2k+1} = 5F_{2k}+L_{2k}に①、③を適用すれば②が示され、2F_{2k+1}=F_{2k}+L_{2k}より④もわかる。 Q.E.D.

Lucas数の場合

定理 L_nが平方数ならばn=1, 3である。すなわち、平方数となるLucas数は1, 4しかない。

証明. nが偶数のとき
関係式L_{2n}=L_n^2+(-1)^{n-1}\cdot 2から、nが偶数ならば「L_n=平方数\pm 2」の形となる。これは平方数にはなり得ない。

n \equiv 1 \pmod{4}のとき
L_1=1は平方数である。n\neq 1とする。このとき、n=1+2\cdot 3^rkと書ける。ただし、rは非負整数であり、k3の倍数でない偶数。よって、補題3のL_{n+2k}\equiv -L_n \pmod{L_k}3^r回(奇数回)繰り返すことにより、L_n \equiv -L_1 \equiv -1 \pmod{L_k}が成立する。L_nが平方数ならば、-1は法L_kで平方剰余となる。しかし、Lucasの記事で示したようにL_k \equiv 3 \pmod{4}なので、L_kp \equiv 3 \pmod{4}なる素因数pをもつ。このとき、\displaystyle \left( \frac{-1}{p} \right) = 1となって、第一補充則に矛盾する。
integers.hatenablog.com

n \equiv 3 \pmod{4}のとき
L_3=4は平方数である。n \neq 3とする。このとき、n=3+2\cdot 3^rkと書ける(r, kは先ほどと同じ条件)。よって、L_n \equiv -L_3 = -4 \pmod{L_k}を得る。L_nが平方数であれば、-4が法{L_k}平方剰余となって、やはり第一補充則に矛盾する。 Q.E.D.

これでLucas数の場合の定理が証明できましたが、実はFibonacci数の場合に利用します。これだけでは足りず、次の命題も必要となります:

命題 L_n=2m^2なる整数mが存在すれば、n=0, \pm 6である。

証明. まず、nが奇数か偶数かで分ける。偶数の場合は、更にn \equiv 0 \pmod{4}n \equiv 2 \pmod{4}で分けます。n \equiv 2 \pmod{4}の場合は、更にn\equiv 6 \pmod{8}n \equiv 2 \pmod{8}で分ける。

nが奇数のとき
L_n = 2m^2と仮定する(mは整数)。このとき、L_nは偶数なのでn3の倍数。また、nは奇数の場合を考えているので、n \equiv \pm 3 \pmod{12}である。Lucas数の記事で示したようにL_{n+12} \equiv L_n \pmod{8}なので、L_n \equiv L_{\pm 3} \equiv 4 \pmod{8}が成り立つ。よって、2m^2 \equiv 4 \pmod{8}、すなわち、m^2 \equiv 2 \pmod{4}となる。しかし、2は法4で平方非剰余であるため、矛盾が生じる。

n \equiv 0 \pmod{4}のとき
L_0=2\cdot 1^2である。n \neq 0ならばn=2\cdot 3^rkと書ける(r, kは前証明と同じ条件)。よって、2L_n \equiv -2L_0 = -4 \pmod{L_k}を得る。前証明と同じ理由により、2L_nは平方数にはなり得ない。従って、もし、L_n=2m^2であれば2L_n = (2m)^2となって矛盾する。

n \equiv 6 \pmod{8}のとき
L_6=2\cdot 3^2である。n \neq 6のとき、n=6+2\cdot 3^rkであり、2L_n \equiv -2L_6 = -36 \pmod{L_k}を得る。今回はk4の倍数なので、L_k6と互いに素である(L_n3の倍数になることとn \equiv 2 \pmod{4}が同値であった)。よって、やはり第一補充則よりこの場合も2L_nは平方数になり得ない(6と互いに素な素因数pでないと\displaystyle \left( \frac{-36}{p} \right)が考えられない)。

n \equiv 2 \pmod{8}のとき
L_{-n} = L_nに注意すれば、-n \equiv 6 \pmod{8}であることから、L_n = 2m^2\Longrightarrow -n=6 \Longrightarrow n=-6となる。 Q.E.D.*1

定理の証明

それではFibonacci平方数が0, 1, 144のみであることを証明しましょう。

n \equiv 1 \pmod{4}のとき
F_1 = 1は平方数である。n \neq 1ならばn=1+2\cdot 3^rkと書ける(r, kはいつもの)。よって、補題3F_{n+2k} \equiv -F_n \pmod{L_k}より、F_n \equiv -F_1 =-1 \pmod{L_k}を得る。やはり、第一補充則によりF_nは平方数にはなり得ない。

n \equiv 3 \pmod{4}のとき
F_{-n}=F_nより、F_nが平方数ならば-n \equiv 1 \pmod{4}から-n=1となって、n=-1となる。

nが偶数のとき
補題1よりF_n = F_{n/2}L_{n/2}である。よって、補題2および素因数分解の一意性から、n3の倍数でなければF_{n/2}=a^2, L_{n/2}=b^2n3の倍数ならばF_{n/2}=2a^2, L_{n/2}=2b^2となるような整数a, bが存在する。L_{n/2}=b^2ならば、定理よりn/2=1, 3、すなわち、n=2, 6を得る。nが3の倍数でないときなので、n=2L_{n/2}=2b^2ならば、命題よりn/2=0, \pm 6、すなわち、n=0, \pm 12を得る。F_{-12}=-144は平方数ではないので、n=0, 12

以上、n=0, \pm 1, 2, 12であることが示された。 Q.E.D.

*1:この証明は、例えばL_62\times平方数であることが効いている。このことが、\bmod{8}まで分割して考察する理由である。