この記事では, 以下を目標として上記の定理を証明します.
- 初等整数論によって Fibonacci 平方数の定理を証明する.
2022 年 9 月追記 : 大幅に内容を修正し, 証明法を新しくしました*1.
前提
具体的には, 二つの数列は次のようなものです. \begin{align} \begin{array}{c|ccccccccc} i&\cdots&-3&-2&-1&0&1&2&3&\cdots\\\hline L_i&\cdots&-4&3&-1&2&1&3&4&\cdots\\ F_i&\cdots&2&-1&1&0&1&1&2&\cdots \end{array}\end{align} \begin{align} &(L_i)_{i\gt0}=1,\ 3,\ 4,\ 7,\ 11,\ 18,\ \ldots,\\ &(F_i)_{i\gt0}=1,\ 1,\ 2,\ 3,\ 5,\ 8,\ \ldots. \end{align}
証明 (数学的帰納法). のときおよびのときは正しい. 先ず一行目の式について, あるとにおいて等号が成りたつならば, それらを辺々足してに対する等式が得られ. また辺々を引けばの場合が得られ, 再帰的に確かめることができる. 二行目の等式も同様である.
続いて, 合同式論から平方剰余に関する定理を紹介します.
証明. (略)
第一補充則の説明は省きますが, 本記事の証明を通して用いる下線部分は, Fermat の小定理を使ってそれよりも簡潔に導出することができるので, その証明を述べます.
証明. 仮に平方数にを加えた数がで割って余る素因子を持つとするならば, Fermat の小定理の式 \begin{align} (NN)^{\frac{p-1}{2}}\equiv1\ \ (\mathrm{mod}.p) \end{align} からなる合同式が導かれる. これはを意味するのであるが, は以上の法であるから, 非合理である.
平方数よりもだけ大きい数を素因子分解してゆくと次の系列が得られ, 確かにの倍数よりもだけ大きい素因子は現れていないことが窺えます.
\begin{align} 1&\;,\\ 2=&\;2,\\ 5=&\;5,\\ 10=&\;2\times5,\\ 17=&\;17,\\ 26=&\;2\times13,\\ 37=&\;37,\\ 50=&\;2\times5^2,\\ 65=&\;5\times13,\\ 82=&\;2\times41,\\ 101=&\;101,\\ 122=&\;2\times61,\\ 145=&\;5\times29,\\ 170=&\;2\times5\times17,\\ 197=&\;197,\\ {2}{2}{6}=&\;{2}\times{1}{1}{3},\\ 257=&\;257,\\ 290=&\;2\times5\times29,\\ 325=&\;5^2\times13,\\ 362=&\;2\times181,\\ 401=&\;401,\\ 442=&\;2\times13\times17,\\ 485=&\;5\times97,\\ 530=&\;2\times5\times53,\\ 577=&\;577,\\ 626=&\;2\times313,\\ 677=&\;677,\\ 730=&\;2\times5\times73,\\ 785=&\;5\times157,\\ 842=&\;2\times421,\\ 901=&\;17\times53,\\ 962=&\;2\times13\times37,\\ &\vdots \end{align}
概略
扨て, 整数について, これが平方数であるか否かを表現する不定方程式, \begin{align} mm=N \end{align} の解法には様々なものが存在しますが, 今回は主題となる方程式の解を決定するにあたって, ある「特殊な形の整数」の素因子と剰余を見てゆきます. 文字を奇素数とするとき, 先述の命題によれば, 合同方程式 \begin{align} xx\equiv-1\ \ ({\rm mod}.p) \end{align} が解を持つためにはがの倍数であることが少なくとも必要でありました. ここにおいて, 若しの倍数よりもだけ大きいある整数をもって, \begin{align} F_n\equiv-1\ \ ({\rm mod}.M) \end{align} を成立させることができれば, がで割って余る素因子を必ず持つ*2ので, が平方数になることはにより否定されることになります. 詰まり, 解になりうる整数の候補を絞りこむことができるのです.
この解法の妥当性を示すために, 下に数列の素因子分解の列を纏めます. それぞれの番号について, となる型の素数が存在しているか否かを確かめてみてください. \begin{align} 2=&\;2,\\ 2=&\;2,\\ 3=&\;\textbf{3},\\ 4=&\;2^2,\\ 6=&\;2\times\textbf{3},\\ 9=&\;\textbf{3}^2,\\ 14=&\;2\times\textbf{7},\\ 22=&\:2\times\textbf{11},\\ 35=&\;5\times\textbf{3},\\ 56=&\;2^3\times\textbf{7},\\ 90=&\;2\times5\times\textbf{3}^2,\\ 145=&\;(5\times29),\\ 234=&\;2\times13\times\textbf{3}^2,\\ 378=&\;2\times(\textbf{3}^3\times\textbf{7}),\\ 611=&\;13\times\textbf{47},\\ 988=&\;2^2\times13\times\textbf{19},\\ 1598=&\;2\times29\times\textbf{31},\\ 2585=&\;5\times(\textbf{11}\times\textbf{47}),\\ 4182=&\;2\times(17\times41)\times\textbf{3},\\ 6766=&\;2\times17\times\textbf{199},\\ 10947=&\;(41\times89)\times\textbf{3},\\ 17712=&\;2^2\times13\times(\textbf{3}\times\textbf{227}),\\ 28658=&\;2\times89\times(\textbf{7}\times\textbf{23}),\\ 46369=&\;89\times521,\\ &\vdots \end{align} このように計算してゆくと, 残念ながら偶数番目の Fibonacci 数の中には反例になるものが幾つか現れてしまいます. 然し偶数番目の項の問題は, 素因子分解を考えることによって奇数番目の項の問題に帰結する (後述) ので, これを懸念する必要は有りません.
フィボナッチ数の算術的性質
二次方程式の二つの解を, 大きいほうから順にと書きます. すると, 再帰的な二つの等式 \begin{align} \left( \begin{array}{l} \phi^{i+2}=\phi^{i+1}+\phi^i\\\bar\phi^{i+2}=\bar\phi^{i+1}+\bar\phi^i \end{array} \right. \end{align} が成立します. これは, 黄金比の累乗を配列した \begin{align} 1,\ \phi,\ \phi^2,\ \phi^3,\ \ldots \end{align} という数列が, Lucas 数列, Fibonacci 数列と同じく「直前の二項を足して次の項が得られる」という規則と, 「直前の項に一律の比を乗じて次の項が得られる」という幾何数列の規則とを, 併せもっていることを意味しています. このような足し算の規則が類似しているために, 四つの数列 \begin{align} &1,\ \phi,\ \phi^2,\ \phi^3,\ \ldots,\\ &1,\ \bar\phi,\ \bar\phi^2,\ \bar\phi^3,\ \ldots,\\ &2,\ 1,\ 3,\ 4,\ \ldots,\\ &0,\ 1,\ 1,\ 2,\ \ldots,\\ \end{align} はとても好い相性を有し, 例えば次のような等式を組むことができます.
証明. およびのときは正しい. 各等式について, あるとにおける等号が成りたつならば, それらを辺々足しあわせてに対する等式が得られ. また辺々を引けばの場合が得られるから, 再帰的に確かめることができる.
にからの値を代入して数字にするとこの通りになります. \begin{align} \phi^0&=\frac{2+0\sqrt{5}}{2}\ (=1),\\ \phi^1&=\frac{1+1\sqrt{5}}{2}\ \left(=\frac{1+\sqrt{5}}{2}\right),\\ \phi^2&=\frac{3+1\sqrt{5}}{2}\ \left(=\frac{3+\sqrt{5}}{2}\right),\\ \phi^3&=\frac{4+2\sqrt{5}}{2}\ (=2+\sqrt{5}),\\ \phi^4&=\frac{7+3\sqrt{5}}{2},\\ \phi^5&=\frac{11+5\sqrt{5}}{2},\\ \phi^6&=\frac{18+8\sqrt{5}}{2}\ (=9+4\sqrt{5}),\\ &\ \\ \phi^{-1}&=\frac{-1+\sqrt{5}}{2}\ \left(=\frac{2}{1+\sqrt{5}}\right). \end{align}
証明. 指数法則を \begin{align} &\phi^{n}\bar{\phi}^n=(\phi\bar{\phi})^n\\ i.\ e.\ &\;\frac{L_n+\sqrt{5}F_n}{2}\cdot\frac{L_n-\sqrt{5}F_n}{2}=(-1)^n\\ i.\ e.\ &\;L_nL_n-5F_nF_n=4(-1)^n \end{align} と変形すれば, ここに命題の式が現れる.
証明. 指数法則を
とする. は無理数であるので, 有理数部と無理数部のそれぞれについて両辺は一致する.
上記の加法定理は一見すると複雑ですが, の場合に得られる二倍公式は, これよりも少し簡潔になります. これらの等式から解るように, 二数列には三角函数との類似性があります.
証明. 加法定理と先の命題によって, \begin{align} 2F_{2n}&=L_nF_n+F_nL_n=2L_nF_n,\\ 2L_{2n}&=L_nL_n+5F_nF_n\\ &=L_nL_n+\left(L_nL_n-4(-1)^n\right)\\ &=2L_nL_n-4(-1)^n. \end{align} 故に命題が成りたつ.
次の積和等式もまた三角函数の式と類似しています.
証明. 加法定理と符号の反転式によって,
故に命題が成立する.
積和等式は, この順番で暗記して, 実用できるようにしておくと便利です.
証明. 積和等式に代入すれば,
故に命題が成立する.
ここから, 数列に現れる素数はとのみであることが判ります. また, の式も同様であり, 次のような積の式に分解します.
証明. 積和等式によれば明白である.
三角函数との対応を表に示します.
フィボナッチ数の数論的性質
証明. 数列およびをを法として還元した剰余の列は周期的であり, 共に長さの循環節を有する. 故に命題が成りたつ.
証明. 数列をを法として還元した剰余の列は周期的であり, 長さの循環節を有する. 故に命題が成りたつ.
証明. 積和等式によって, \begin{align} L_{3n}+(-1)^nL_n=L_{2n}L_{n} \end{align} が成りたつ. 由って, はにより割りきれる.
一般に, を奇数とすれば, がの倍数になります.
証明
をで割ったときの余りがである場合, である場合, 偶数である場合の三つに分けて平方数を検索します.
証明 についてが平方数であることは自明. それ以外の場合, と置けばであり, \begin{align} F_{4n'+1}+1=F_{2n'+1}L_{2n'}. \end{align} 整数から素因子を抽出してとするとき, は法においてまたはに合同になり, が得られる. 故には型の素因子を有し, も同じである. ここに第一補充則を適用すれば, 証明が完成される.
証明 が奇数であるならばとは相等しいから, の倍数よりもだけ大きい番号に関する命題 14 において, の符号を反転すればこの命題に達する.
偶数の番号の場合は, 上記と異なり剰余の理論のみによって証明することが難しいと言ってよいです (例えばはの倍数よりもだけ大きい素因子を持たない). 故に二倍公式 \begin{align} F_{n}=L_{n/2}F_{n/2} \end{align} を用いてを因数分解した上で考察することにします. 等式によれば, 番号を同じくする Lucas 数と Fibonacci 数の最大公約はとに限られることが判るので, が平方数であるならば, か, かの何れかが平方数でなければなりません. 詰まり, が平方数であるか否かという問題は, が偶数である場合, という数とという数の形状に関する問題に帰結するということです. これと同様の推論を繰りかえすと, またはを平方数にする奇数を把握することによって, Fibonacci 平方数の問題が解決されるであろうと見当が付きます.
または, 先ほどの分解式に現れたが平方数または平方数の倍になる整数を全て見つけることによっても, 証明が可能です (当に参考文献にあった方法です). 少し先取りの説明のようになりますが, 単なる Lucas 平方数の問題は, 簡易な初等整数論による解法が存在する (演習問題を参照) のに対して, 平方数の二倍については, これまでの Fibonacci 数に対する考察と同様に, 積和等式から型の因子を構成する必要が生じます.
証明 についてが平方数の倍であることは自明. それ以外の場合, と置けばであり, \begin{align} F_{4n'+3}+2=F_{2n'+3}L_{2n'}. \end{align} 整数から素因子を抽出してとするとき, は法においてまたはに合同になり, が得られる. 故には型の素因子を有し, も同じである. ここに第一補充則を適用すれば, 証明が完成される.
証明 が奇数であるならばとは相等しいから, の倍数よりもだけ大きい番号に関する命題 16 において, の符号を反転すればこの命題に達する.
証明を簡潔にするために, 平方数または平方数の二倍である数の全体をと書くことにします. \begin{align} S=\{0,1,4,9,\ldots\}\cup\{0,2,8,18,\ldots\}. \end{align} これから用いるのは, 最大公約数がまたはである整数とについての, ならばかつという性質です.
証明 についてが平方数であることは明白である. それ以外のに対して, 先ずとして素因子を抽出し, 帰納法によって, なる場合のあらゆるがの要素でないことを証明する.
なる番号について
二倍公式によればがの要素であるためにはもまたの要素でなければならないから, これまでの証明によって が必要である. この内とのみが充分性を有する.
なる番号について
二倍公式によればがの要素であるためにはもまたの要素でなければならないから, の証明によりが必要である. この内のみが充分性を有する. 但だし Fibonacci 数列の第十二項とはである.
なる番号について
二倍公式によればがの要素であるためにはもまたの要素でなければならないから, の証明によってが必要である. 然し \begin{align} F_{24}=L_{12}F_{12}=322\times144=2\times7\times23\times12^2 \end{align} であり, これは充分性を有しない.
なる番号について
あるについて, が如何なる奇数においてもの要素でないことを仮定とする. そのときがの要素になるためには, 二倍公式に現れる因子がの要素でなければならないが, 仮定によってこれは不可能である. のとき, 既にがの要素になるは存在しないのであるから, この結果はあらゆるについても同じである.
以上によって次の事実が得られたことになります.
演習問題
奇数番目に現れる平方数はとのみである.
参考文献
[1] J. H. E. Cohn (1964), "Lucas and Fibonacci numbers and some Diophantine equations," Glasgow Mathematical Journal, Vol. 7, Issue 1; pp. 24-28.
*1:修正前の内容につきましては Mathlog の記事をご覧ください. リンク : https://mathlog.info/articles/447