Fibonacci数の判別式（1） 初等的証明

〔Fiboncci数の判別式〕
任意の正整数 N $N$に対して次が成立する. 5N2±4 $5N^2\pm 4$のうちいずれかが平方数 ⟺ N $⟺N$はFibonacci数.

この連続記事では, Fibonacci数列の判別式について以下を目標として記します.

• Fibonacci数の判別式に対して初等的な証明を与える.
• Pell型方程式の解法について考察し, 二次体 Q(5–√) $\mathbb{Q}(\sqrt{5})$とその整数環や単数といった代数的整数論の概念について触れる.

前提知識

高校数学基礎：不等式の性質, 漸化式など

（2）の記事：https://yu200489144.hatenablog.com/entry/2020/03/14/205238

（3）の記事：https://yu200489144.hatenablog.com/entry/2020/03/14/205259

実験

 N=1, 2, 3, 5, 8, 13, …, 144 $N=1,2,3,5,8,13,\dots ,144$として 5N2±4 $5N^2\pm 4$の値を具体的に計算すると次のようになり, 定理（⟸$⟸$）の成立を確かめることができます.

5⋅12+4=9=32,5⋅22+4=24,5⋅32+4=49=72,5⋅52+4=129,5⋅82+4=324=182,5⋅132+4=849,5⋅212+4=2209=472,5⋅342+4=5794,5⋅552+4=15129=1232,5⋅892+4=39609,5⋅1442+4=10372=3222,5⋅12−4=1=12.5⋅22−4=16=42.5⋅32−4=41.5⋅52−4=121=112.5⋅82−4=316.5⋅132−4=841=292.5⋅212−4=2201.5⋅342−4=5776=762.5⋅552−4=15121.5⋅892−4=39601=1992.5⋅1442−4=10366.$$\begin{array}{rlrl}& 5\cdot 1^2+4=9=3^2,& & 5\cdot 1^2-4=1=1^2.\\ & 5\cdot 2^2+4=24,& & 5\cdot 2^2-4=16=4^2.\\ & 5\cdot 3^2+4=49=7^2,& & 5\cdot 3^2-4=41.\\ & 5\cdot 5^2+4=129,& & 5\cdot 5^2-4=121={11}^2.\\ & 5\cdot 8^2+4=324={18}^2,& & 5\cdot 8^2-4=316.\\ & 5\cdot {13}^2+4=849,& & 5\cdot {13}^2-4=841={29}^2.\\ & 5\cdot {21}^2+4=2209={47}^2,& & 5\cdot {21}^2-4=2201.\\ & 5\cdot {34}^2+4=5794,& & 5\cdot {34}^2-4=5776={76}^2.\\ & 5\cdot {55}^2+4=15129={123}^2,& & 5\cdot {55}^2-4=15121.\\ & 5\cdot {89}^2+4=39609,& & 5\cdot {89}^2-4=39601={199}^2.\\ & 5\cdot {144}^2+4=10372={322}^2,& & 5\cdot {144}^2-4=10366.\end{array}$$

この結果から n $n$が偶数のとき 5F2n+4 $5F_n^2+4$が平方数,  n $n$が奇数のときは 5F2n−4 $5F_n^2-4$が平方数になることが予想されます（ただし F1=F2=1 $F_1=F_2=1$と重複している N=1 $N=1$の場合のみ 5N2±4 $5N^2\pm 4$の両方が平方数になります）. さらに, 平方数になっている場合についてその正平方根を抽出して並べると

1, 3, 4, 7, 11, 18, 29, 47, 76, 123, …$$\begin{array}{r}1,3,4,7,11,18,29,47,76,123,\dots \end{array}$$

のような数列が得られますが, これはLucas数列（リュカ数列）と呼ばれる, Fibonacci数列との間に様々な相互的関係が成り立つことが知られている数列です. Lucas数列ははFibonacci数列と同様に, 漸化式

Ln+2=Ln+1+Ln,L1=1, L2=3$$\begin{array}{r}{L}_{n+2}=L_{n+1}+L_n,L_1=1,L_2=3\end{array}$$

により定義されます.

また,  5N2±4 $5N^2\pm 4$が平方数のとき, ある正整数 x $x$が存在して 5N2±4=x2 $5N^2\pm 4=x^2$つまり

x2−5N2=±4$$\begin{array}{r}{x}^2-5N^2=\pm 4\end{array}$$

が成り立つので, 証明の際にはこの方程式の正整数解について考察することになります. 以降, 文字を x,y $x,y$で統一するために N $N$を y $y$におきかえて x2−5y2=±4 $x^2-5y^2=\pm 4$と書くことにします.

以上の考察から次の定理が予想され, 次項では実際にこの定理の初等的な証明について述べたいと思います.

定理 1.1 方程式 x2−5y2=±4 $x^2-5y^2=\pm 4$の正整数解は (x,y)=(Ln,Fn) $(x,y)=(L_n,F_n)$によって与えられる. さらに, 複号は n $n$が偶数のときプラス, 奇数のときにマイナスが対応する.

初等的証明

補題 1.2  x2−5y2=±4 $x^2-5y^2=\pm 4$の正整数解 (x,y) $(x,y)$に対して

(5y−x2,x−y2)$$\begin{array}{r}(\frac{5y-x}{2},\frac{x-y}{2})\end{array}$$

を対応させる関数（写像） f $f$を考えると,  x2−5y2=±4 $x^2-5y^2=\pm 4$のいかなる正整数解 (x,y) $(x,y)$も f $f$によって繰り返し変換することで (1,1) $(1,1)$に帰着することができる.

証明. まず (5y−x)/2=X, (x−y)/2=Y $(5y-x)/2=X,(x-y)/2=Y$とおくと f $f$の対応は

f:(x,y)⟼(X,Y)$$\begin{array}{r}f:(x,y)⟼(X,Y)\end{array}$$

と表される. ここで以下を示す.

 (1) $(1)$ y≥2 $y\ge 2$のとき X, Y $X,Y$はともに正整数である.
 x2−5y2 $x^2-5y^2$は偶数より x2 $x^2$と 5y2 $5y^2$の偶奇は等しく,  x $x$と y $y$の偶奇も一致するので (5y−x)/2, (x−y)/2 $(5y-x)/2,(x-y)/2$はともに整数である. 次にそれぞれが正であることを背理法により示す.
もし仮に 5y≤x $5y\le x$であったとすると

x2−5y2≥(5y)2−5y2=20y2>4$$\begin{array}{r}{x}^2-5y^2\ge (5y{)}^2-5y^2=20y^2>4\end{array}$$

より不適なので 5y−x>0. $5y-x>0.$同様に x≤y $x\le y$を仮定したとき y≥2 $y\ge 2$に注意すると

x2−5y2≤y2−5y2=−4y2<−4$$\begin{array}{r}{x}^2-5y^2\le y^2-5y^2=-4y^2<-4\end{array}$$

と評価できて矛盾. よって X>0, Y>0. $X>0,Y>0.$

 (2) $(2)$ (X,Y) $(X,Y)$も方程式 x2−5y2=±4 $x^2-5y^2=\pm 4$の解である.
代入して計算すると

X2−5Y2=(5y−x4)2−5(x−y2)2=−4x2+20y24=−(x2−5y2)=∓4$$\begin{array}{rl}{X}^2-5Y^2& ={\left(\frac{5y-x}{4}\right)}^2-5{\left(\frac{x-y}{2}\right)}^2\\ & =\frac{-4x^2+20y^2}{4}\\ & =-(x^2-5y^2)=\mp 4\end{array}$$

となるので (X,Y) $(X,Y)$も x2−5y2=±4 $x^2-5y^2=\pm 4$を満たしている. また,  x2−5y2 $x^2-5y^2$と X2−5Y2 $X^2-5Y^2$の符号はつねに異なることもわかった.

 (3) $(3)$ y≥2 $y\ge 2$のとき Y<y. $Y<y.$
対偶をとって Y≥y ⟹ y=1 $Y\ge y⟹y=1$を証明する.  Y≥y $Y\ge y$のとき (x−y)/2≥y $(x-y)/2\ge y$より x≥3y $x\ge 3y$であることを用いると

x2−5y2≥(3y)2−5y2=4y2≥4$$\begin{array}{r}{x}^2-5y^2\ge (3y{)}^2-5y^2=4y^2\ge 4\end{array}$$

となって, 最後の不等号で等号が成り立つ y=1 $y=1$のとき以外は不適.

以上より y≥2 $y\ge 2$のとき (x,y) $(x,y)$を f $f$で変換することによって新たな解 (X,Y)  (Y<y) $(X,Y)(Y<y)$が得られるので,  x2−5y2=±4 $x^2-5y^2=\pm 4$のいかなる解も f $f$を何回かかけることで y=1 $y=1$の場合に帰着させることができる.  y=1 $y=1$のとき x2−5=±4 $x^2-5=\pm 4$より (x,y)=(1,1), (3,1) $(x,y)=(1,1),(3,1)$が解であるが (3,1) $(3,1)$は f $f$によって (1,1) $(1,1)$に移されるので,  (1,1) $(1,1)$以外のすべての解は繰り返し f $f$をかける操作によって (1,1) $(1,1)$に変換することができる.

□$◻$

 f $f$は一対一の対応を持つ関数（全単射）なので,  f $f$による解の変換を次の図のように表したとき途中で枝分かれすることはありません.

図1. 関数 f $f$による解の変換

したがって, 最も小さい解 (x,y)=(1,1) $(x,y)=(1,1)$から始めて矢印を逆向きにたどっていけば, すべての解を回ることができます. 図では,  f $f$による対応の順番で, 解を

…, (x3,y3), (x2,y2), (x1,y1)=(1,1)$$\begin{array}{r}\dots ,(x_3,y_3),(x_2,y_2),(x_1,y_1)=(1,1)\end{array}$$

と表現しています. このとき補題の証明中に導出した不等式 Y<y  (y≥2) $Y<y(y\ge 2)$から,  (x2,y2), (x3,y3), (x4,y4), … $(x_2,y_2),(x_3,y_3),(x_4,y_4),\dots$という羅列は y $y$の値について小さい順に並んでいることがわかります. すなわち,  (xn,yn) $(x_n,y_n)$を規則

 (1) $(1)$ y≥2 $y\ge 2$つまり n≥3 $n\ge 3$のとき,  x2−5y2=±4 $x^2-5y^2=\pm 4$のすべての解を y $y$の値について昇順に並べたときに n $n$番目にあたる解を (xn,yn) $(x_n,y_n)$とする.
 (2) $(2)$ y=1 $y=1$つまり n=1,2 $n=1,2$のときは,  y $y$の値がかぶっているので (x1,y1)=(1,1), (x2,y2)=(3,1) $(x_1,y_1)=(1,1),(x_2,y_2)=(3,1)$と個別に定める.

で定義すると f $f$による変換は

(xn+1,yn+1)⟼(xn,yn)$$\begin{array}{r}(x_{n+1},y_{n+1})⟼(x_n,y_n)\end{array}$$

と表されます.

では, 補題を用いて定理を証明してみましょう.

定理 1.1 方程式 x2−5y2=±4 $x^2-5y^2=\pm 4$の正整数解は (x,y)=(Ln,Fn) $(x,y)=(L_n,F_n)$によって与えられる. さらに, 複号は n $n$が偶数のときプラス, 奇数のときにマイナスが対応する.

証明. 補題より x2−5y2=±4 $x^2-5y^2=\pm 4$のいかなる正整数解 (x,y) $(x,y)$も f $f$によって何回か変換することで (1,1) $(1,1)$に移すことができる. 反対に,  f $f$が各 (x,y), (X,Y) $(x,y),(X,Y)$を一対一に対応させていることから,  (1,1) $(1,1)$を f $f$の逆関数 f−1 $f^{-1}$で繰り返し移してゆくと x2−5y2=±4 $x^2-5y^2=\pm 4$のすべての正整数解が得られることになる.
連立方程式

⎧⎩⎨⎪⎪⎪⎪5y−x2=Xx−y2=Y$$\begin{array}{r}\{\begin{array}{l}{\displaystyle \frac{5y-x}{2}}=X\\ {\displaystyle \frac{x-y}{2}}=Y\end{array}\end{array}$$

を x, y $x,y$について解くと x=(X+5Y)/2, y=(X+Y)/2 $x=(X+5Y)/2,y=(X+Y)/2$となるので,  f−1 $f^{-1}$は

f−1:(X,Y)⟼(X+5Y2,X+Y2)$$\begin{array}{r}{f}^{-1}:(X,Y)⟼(\frac{X+5Y}{2},\frac{X+Y}{2})\end{array}$$

という対応を持つ. したがって,

⎧⎩⎨⎪⎪⎪⎪xn+1=xn+5yn2yn+1=xn+yn2$$\begin{array}{r}\{\begin{array}{l}{x}_{n+1}={\displaystyle \frac{x_n+5y_n}{2}}\\ y_{n+1}={\displaystyle \frac{x_n+y_n}{2}}\end{array}\end{array}$$

が成立する. 第一式より yn=(2xn+1−xn)/5,$y_n=(2x_{n+1}-x_n)/5,$ yn+1=(2xn+2−xn+1)/5 $y_{n+1}=(2x_{n+2}-x_{n+1})/5$なので, 第二式に代入して

2xn+2−xn+15=12(xn+2xn+1−xn5)$$\begin{array}{r}\frac{2x_{n+2}-x_{n+1}}{5}=\frac{1}{2}(x_n+\frac{2x_{n+1}-x_n}{5})\end{array}$$

これを整理すると xn+2=xn+1+xn $x_{n+2}=x_{n+1}+x_n$となり,  x1=1, x2=3 $x_1=1,x_2=3$と合わせると xn=Ln. $x_n=L_n.$同様にして yn=Fn $y_n=F_n$も得られるので x2−5y2=±4 $x^2-5y^2=\pm 4$の解は (x,y)=(Ln,Fn) $(x,y)=(L_n,F_n)$によって与えられる.
また, 補題の証明中の (2) $(2)$の議論より x2−5y2 $x^2-5y^2$と X2−5Y2 $X^2-5Y^2$の符号はつねに異なっていたことを考えれば, 定理の後半が導かれる.

□$◻$

証明に用いた関数 f, f−1 $f,f^{-1}$の対応の様子を具体的に書き出すと次のようになります.

図2. 関数 f, f−1 $f,f^{-1}$による解の変換

上記の証明は, この関数 f−1 $f^{-1}$によって (1,1) $(1,1)$を繰り返し変換してゆくと, その像が x2−5y2=±4 $x^2-5y^2=\pm 4$のすべての正整数解をわたることを利用して xn, yn $x_n,y_n$についての連立漸化式を導き, その解が xn=Ln, yn=Fn $x_n=L_n,y_n=F_n$であることを示す, という流れになっています.

これで定理を初等的に証明することができたわけですが, まだ 1 $1$つ疑問が残っています. それは, なぜ補題において関数 f $f$を

f:(x,y)⟼(5y−x2,x−y2)$$\begin{array}{r}f:(x,y)⟼(\frac{5y-x}{2},\frac{x-y}{2})\end{array}$$

によって定義するとうまく解を構成できたのかということです. （2）および（3）の記事では a+b5–√  (a,b $a+b\sqrt{5}(a,b$は有理数) $)$という形の「数」に着目し, この初等的証明の背景にあったもう一つの証明方法について書きたいと思います.