Arithmetica

フィボナッチ数と平方数, 記数法.

Arithmetica 算術ノート

トップ > 問題集 > 𝒏 + 1/𝒏 の形の数に関する問題

𝒏 + 1/𝒏 の形の数に関する問題

問題集 フィボナッチ数

問. 二つの帯分数 𝒙(𝟏/𝒙), 𝒚(𝟏/𝒚) の積が整数になるような正整数の対 (𝒙,𝒚) をすべて挙げよ. 例えば 𝟐(𝟏/𝟐) • 𝟓(𝟏/𝟓) = 𝟐.𝟓 • 𝟓.𝟐 = 𝟏𝟑 を満たす (𝟐, 𝟓) 等. 

この記事では, この問題に対する解答を記します. 当初の予定では長々とした解説を付する予定でしたが, 個人的見解に基づきその殆どを省略することとしました.



前提知識

相加相乗平均の不等式, 二次方程式の解と係数の関係, 数学的帰納法,  フィボナッチ (Fibonacci) 数列など



この問題は下の記事の演習問題ですが, ここでは元記事の内容を前提としない証明を扱います.

yu200489144.hatenablog.com





言いかえ

考えるべきなのは\ (x+(1/x))(y+(1/y))\ という式が整数値を取る場合ですが, この分数式は \begin{align} \left(x+\frac{\,1\,}{\,x\,}\right)\left(y+\frac{\,1\,}{\,y\,}\right)&=\frac{\,(x^2+1)(y^2+1)\,}{xy}\\ &=xy+\frac{\,x^2+y^2+1\,}{xy} \end{align} と変形することができ, 問題は「\ x^2+y^2+1\ が\ xy\ の倍数になるのはどのような場合か」という問いに帰着します. これから,  この整数問題について解説してゆきます.





実験

先ず説明のために,  \ (x,y)\ に小さな値を順に代入して様子をお見せしたいと思います. 下に\ x,y\le20\ の範囲で該当する対を挙げます.

\begin{align} &(1,1):\quad x^2+y^2+1=3,\ xy=1,\quad3=3\cdot1.\\ &(1,2):\quad x^2+y^2+1=6,\ xy=2,\quad6=3\cdot2.\\ &(2,1):\quad x^2+y^2+1=6,\ xy=2,\quad6=3\cdot2.\\ &(2,5):\quad x^2+y^2+1=30,\ xy=10,\quad30=3\cdot10.\\ &(5,2):\quad x^2+y^2+1=30,\ xy=10,\quad30=3\cdot10.\\ &(5,13):\quad x^2+y^2+1=195,\ xy=65,\quad195=3\cdot65.\\ &(13,5):\quad x^2+y^2+1=195,\ xy=65,\quad195=3\cdot65. \end{align}

この実験から, \ x^2+y^2+1\ が\ xy\ の倍数のとき\ x^2+y^2+1=3xy\ となるであろう, と予想を立てることができます. そこで, \ x^2+y^2+1=kxy\ が正整数解を持つような整数\ k\ を特定できないかを探ってみることにします.





\ k\ の値

\ k\ge3\ が必要であることの証明は容易です.

整数\ k\ を用いて\ x^2+y^2+1=kxy\ と置くと, 相加相乗平均の不等式により\ x^2+y^2+1\ge2xy+1\gt2xy\ が成りたつので, 少なくとも\ k\ge3\ である.

次は\ k\gt3\ の場合に解が無いことを示します. 

\ k\gt3\ なる\ x^2+y^2+1=kxy\ の正整数解が存在することを仮定して論を進める.

今から書く解法は*1, 考察するべき二次方程式が対称的であること,  即ち\ (x,y)\ の入れかえに関して条件が不変であることに着想の源があります.  具体的に言えば, 対象の二次方程式が有する一つの整数解を利用して, より小さな解を構成し, いわゆる無限降下法を成立させる方法です. ほんの少し煩雑な計算になりますので, 細かい内容を追うとなると簡単ではありません. ここでは算術的な証明を一通り紹介しますが, その後に書く幾何的解釈のほうが,  本質を掴むのに適していると思います. 


証明の都合上, 不等式評価を目的として\ x=y\ の場合を除外しておきます.

\ x=y\ のとき, \ 2x^2+1=kx^2\ より\ (k-2)x^2=1\ となるが, \ k\gt3\ においてこれは解を持たない.

続いて,

\ x\neq y\ の場合を扱うために, 正整数の対に関するこの条件 \begin{align} x^2+y^2+1=kxy,\quad x,y\in\mathbb{Z},\quad x\gt y\gt0 \end{align} を\ A_k\ と名付ける.
\ x^2+y^2+1=kxy\ が正整数解を持つことを仮定するとき, 条件\ A_k\ を満たす\ (x,y)\ が少なくとも\ 1\ 組存在する. その中の\ 1\ つを\ (p,q)\ とおく.

次に, \ x^2+y^2+1=kxy\ を満たす組であって, 今仮定した\ (p,q)\ と同じく\ y=q\ であるもの\ (r,q)\ を考察すると,  \ (r,p)\ 自体は\ A_k\ を満たしませんが,  成分を逆に並べた\ (q,r)\ は\ A_k\ を満たすことが明らかに成ります. ここではより曖昧に「\ (r,q)\ または\ (q,r)\ が\ A_k\ を満たす」ことを述べます.

このとき\ p^2+q^2+1=kpq\ であるから, \ p\ は\ x\ の二次方程式 \begin{align} x^2+q^2+1=kxq&&x^2-kqx+q^2+1=0 \end{align} に対する解の\ 1\ つである. この方程式の判別式は\ (k^2-4)q^2-4\ に等しく, 少なくとも正の値をとるので, \ x=p\ 以外の実数解\ r\ が存在する. ここで\ r\ の「数としての性質」を精査するために,  解と係数の関係を見ると \begin{align} \begin{cases} p+r=kq\\ pr=q^2+1 \end{cases} \end{align}が得られる. これを用いて, \ (q,r)\ または\ (r,q)\ が条件\ A_k\ を満たす正整数対であること, および\ r\lt p\ であることをを証明すれば善い. と言うのも, 若しそうであるならば, 〈\ A_k\ を満たす任意の組〉から〈\ A_k\ を満たす組であって\ x\ の値がそれよりも小なもの〉を生成するアルゴリズムが得られる. けれどもこれは\ x\ が常に正の数であることに矛盾するので,  解は存在しないといえるのである.

 

\ (1)\ \ q^2+r^2+1=kqr,\ \ r^2+q^2+1=krq.\
\ x=r\ が方程式の解であることから自明.


\ (2)\ \ r\in\mathbb{Z}_{\gt0}.\
整数であることは\ p+r=kq\ において\ p,\ kq\ が整数であることから, 正であることは\ pr=q^2+1\ において\ p,\ q^2+1\ が正であることから判する.


\ (3)\ \ q\gt r\ または\ r\gt q.\
\ q,r\ は異なる実数であったから自明である.


\ (4)\ \ r\lt p.\
若し\ r\ge p\ を仮定すれば, \ (q^2+1)/p=r\ge p\ 即ち\ p^2-q^2\le 1.\ \ p\gt q\ によって\ p^2-q^2\gt0\ であるから\ p^2-q^2=1\ 詰まり\ (p+q)(p-q)=1\ が得られる. しかしこれを満たす正整数\ p,q\ は存在しないので仮定は誤りである. 即ち\ r\lt p.\


こうして\ (x,y)=(p,q)\ から構成される\ (q,r)\ あるいは\ (r,q)\ は条件\ A_k\ を満たし, \ q\lt p\ かつ\ r\lt p\ のために, これはもとの解と比べて\ x\ の値の小さな組である. この解に対しても同様な構成を行うと, さらに\ x\ の値が小さな組が得られて, 以降も操作を限りなく繰りかえすことができる. しかし, これは\ x\in\mathbb{Z}_{\gt0}\ によって\ x\ が下界を持つことに反する. 

この証明から, \ x^2+y^2+1=kxy\ が\ k\gt3\ において正整数解を持っていたとすると, \ x=y\ の場合も\ x\neq y\ の場合もおかしなことが起こると判ったので, 解を持つという仮定は誤りであるといえます.

何れの場合も解の存在は不合理であるから, \ x^2+y^2+1=kxy\ は\ k\gt3\ において正整数解を持たない. よって\ k=3\ における\ x^2+y^2+1=3xy\ の正整数解の決定に帰着する.





図解

ここで,  以上に見た無限降下法の図解を紹介しておこうと思います.


先ず, \ (x,y)\ 直交座標平面において, 曲線\ x^2+y^2+1=kxy\ は\ x=y\ に関して対称な二次曲線であり, より詳しく言えば双曲線の正部分に当ります.

図 1. 曲線群\ x^2+y^2+1=kxy,\ \ k\in\{1,2,3,\ldots,12\}\


内側から\ k=3,4,5,\ldots\ に対応する双曲線で, \ k\leq2\ の場合はそもそも\ x^2+y^2+1=kxy\ なる実数\ x,y\ が存在しないために描画されていない点にご注意ください.


ここで, 曲線\ A_k:x^2+y^2+1=kxy,\ \ x,y\in\mathbb{Z},\ \ x\gt y\gt0\ の上に整点\ (p,q)\ が存在することを仮定して, \ A_k\ に属する他の整点を構成します. 但し,  議論の都合により\ (p,q)\ は充分に原点から離れているものとします.  この二次方程式のもう一つの解\ r\ から作られる点\ (r,q)\ は\ (p,q)\ と\ y\ 座標が等しく, 従って,  \ (p,q)\ を通る\ x\ 軸の並行線\ y=q\ と双曲線とが交わる点に成ります. 双曲線の形を考えれば,  元の点\ (p,q)\ は領域\ x\gt y\ に在る点であったので,  次の\ (r,q)\ は反対に\ x\lt y\ の領域の点であるはずです.  これを直線\ x=y\ に関して対称移動すると,  対称点は領域\ x\gt y\ に入り,  条件\ A_k\ を満たす組が得られます.

図 2. 解の構成


この操作を続けると, 新しく作られる整点は次第に双曲線の頂点\ (1,1)\ に接近して, \ k=3\ ならばここに到達し, \ k\geq4\ ならば, \ x,y\ が正のまま負の無限大へと彷徨いつづけることに成ります. これらの差異を生じているのは, 頂点\ x=y=1/\sqrt{k-2}\ の張る領域\ y\leqslant1/\sqrt{k-2}\ の中に整点が存在しているか否か, ということであります.





上り

\ k=3\ の場合の等式は \begin{align} x^2+y^2+1=3xy \end{align} の形をしていますが, 先ほどの図解法によれば, この方程式のすべての解を再帰的に得ることができます. どの整点も繰りかえし変換して「左下」の点\ (1,1)\ に帰着することができたので, 今度は「左下」の点から経路を遡れば善いのです. 変換の規則を見れば, 上り路が分岐することも有りませんので, 単純な漸化式によって解を記述できることまで判ります.

\ (x,y)\ 平面の第一象限上の双曲線\ x^2+y^2+1=3xy\ を\ C\ と書く. \ (X,Y)\ が\ C\ 上の整点であるならば,
\ ({\rm I})\ 直線\ y=Y\ と曲線\ C\ のもう一つの交点を取る.
\ ({\rm II })\ その交点を直線\ x=y\ に関して対称移動する.
という二つの操作を繰りかえすことによって, 点\ (1,1)\ に帰結することが可能である. 逆に, 点\ (1,1)\ からこの手順を行えば, 曲線\ C\ 上の点を一度ずつ渡ることができる.

 

この手順によって, \ \ell\ 番目に得られる点が\ (F_{2\ell+1},F_{2\ell-1}),\ (F_{2\ell-1},F_{2\ell+1})\ であることを帰納的に証明する. ある\ \ell\ において上の二点が得られたと仮定するとき, \ \ell+1\ 回目の操作\ ({\rm I})\ における交点の\ x\ 座標は, 二次方程式 \begin{align} x^2-3F_{2\ell+1}x+F_{2\ell+1}^2+1=0 \end{align} の解\ x\ の内\ F_{2\ell-1}\ でないほうの解に等しい. 解と係数の関係式および Fibonacci 数列の定義漸化式によって \begin{align} 3F_{2\ell+1}-F_{2\ell-1}&=2F_{2\ell+1}+F_{2\ell}\\ &=F_{2\ell+1}+F_{2\ell+2}\\ &=F_{2\ell+3} \end{align} であるから, \ \ell+1\ 回目の手順によって得られる点は\ (F_{2\ell+3},F_{2\ell+1}),\ (F_{2\ell+1},F_{2\ell+3})\ である. \ \ell=1\ のときは明白であるから, 数学的帰納法の原理によって証明が完了する.

纏めます.

以上から, 条件を満たす組は次の通りである.
\begin{align} (x,y)\in\{(1,1),(F_{2\ell-1},F_{2\ell+1}),(F_{2\ell+1},F_{2\ell-1})\mid\ell\in\mathbb{Z}_{\gt0}\}. \end{align}





Pell 方程式

この問題を Fibonacci 数の判定式についての記事の演習問題としていたのは, 当然方程式\ x^2-5y^2=\pm4\ の正整数解を使っても答えを得ることができるからです. その解法は, \ xy\ が\ x^2+y^2+1\ を割りきるとき \begin{align} x^2+y^2+1=3xy \end{align} であることを証明するところまでは同じですが, この二次式を対角化 (平方完成) して \begin{align} (2x-3y)^2-5y^2&=-4 \end{align} の Pell 方程式に帰結させる点において異なります. 今回扱った論法は (1) の記事で紹介した初等的解法と似ていますが, こんな風に, 座標平面で見ることもできたのですね.





*1:今回紹介する解法はいわゆる Viete の構成法 (Vieta jumping) に基づいています.  

[tex: ]


ALIA VERITAS AD ALIAM SEMPER VIAM STERNIT
ひとつの真理の考究は, かならずまたひとつの真理への道を拓く


フィボナッチ数とは, 黄金比の冪を √5 を用いて表示したときに, 無理数部に現れる分数の二倍である.

\begin{align} (F_n)_{n\geqslant0}=\;&0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89,\ 144,\ 233,\ 377,\ 610,\ 987,\ \\&1597,\ 2584,\ 4181,\ 6765,\ 10946,\ 17711,\ 28657,\ 46368,\ 75025,\ \ldots. \end{align}



平方数とは, 或る整数の平方に等しい数である.

\begin{align} (n^2)_{n\geqslant0}=\;&0,\ 1,\ 4,\ 9,\ 16,\ 25,\ 49,\ 64,\ 81,\ 100,\ 121,\ 144,\ 169,\ 196,\ 225,\ 256,\ \\&289,\ 324,\ 361,\ 400,\ 441,\ 484,\ 529,\ 576,\ 625,\ \ldots. \end{align}



pic-Arithmetica

算 術 ノ ー ト

Arithmētica はラテン語の第一変化名詞で, 算術や初等的な整数論を意味します. 当ブログでは, 算術と整数論, 特にフィボナッチ数や平方数に関する事柄, 面白いと感じた問題, そして数論における定理について, 気ままに記事を投稿します. 記事の内容に関する誤植や新しい発見などが有りましたら, 私の Twitter アカウント (@Numerus_A) までご報告頂けますと幸いに思います.

読者になる