１２.ユークリッド互除法と近似分数 12.5 Farey数列とペル方程式 ここで，Farey数列の解説も意味のあることであると思う． $n$を正の整数とする．分母が$1$以上$n$以下のすべての既約分数を増加数列になるよう並べた数列を$n$ に対応するFarey数列という． 例えば，$n=5$に対応する区間$[0,2]$におけるfarey数列は ${\small 0,\dfrac{1}{5},\dfrac{1}{4},\dfrac{1}{3},\dfrac{2}{5},\dfrac{1}{2},\dfrac{3}{5},\dfrac{2}{3},\dfrac{3}{4},\dfrac{4}{5}, 1,\dfrac{6}{5},\dfrac{5}{4},\dfrac{4}{3},\dfrac{7}{5},\dfrac{3}{2},\dfrac{8}{5},\dfrac{5}{3} ,\dfrac{7}{4},\dfrac{9}{5},2}$ である．すぐ分かるように，$1$以上の部分は$0$以上$1$以下のFarey数列に$1$を加えたものである．したがって，Farey数列の 性質を調べるには$[0,1]$の部分だけ考えればよい． Farey数列では次の命題が有効である． 命題1(加比の理) ２つの正の分数$\frac{b}{a},\frac{d}{c}$が$\frac{b}{a}$＜$\frac{d}{c}$を満たすとき次が成り立つ. 任意の正の整数$m,n$に対して $\dfrac{b}{a}$＜$\dfrac{mb+nd}{ma+nc}$＜$\dfrac{d}{c}$ が成り立つ． 逆の命題として，次が成り立つ． 命題2 ２つの正の分数$\frac{b}{a},\frac{d}{c}$の分母，分子の間に $ad-bc=1$ なる関係があるとき， $\dfrac{b}{a}$＜$\dfrac{y}{x}$＜$\dfrac{d}{c}$ を満たす任意の既約分数$\frac{y}{x}$は正の整数$m,n$を用いて $x=ma+nc,y=mb+nd$ と表せる． この２つの命題はすでに証明してある． 命題3 $a,b,c,d$は整数で$ad-bc=1$のとき， $u=ax+by,v=cx+dy$ であるなら，$x,y$の最大公約数と$u,v$の最大公約数はひとしい． したがって，$x,y$が互いに素なら$u,v$も互いに素で逆も成り立つ． 証明 $\begin{pmatrix} u \\ v \end{pmatrix}= \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} $ 及び $\begin{pmatrix} x \\ y \end{pmatrix}= \begin{pmatrix} d & -b \\ -c & a \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix}$ $(\because ad-bc=1)$ であるから命題が成り立つ． Farey数列で成り立つ性質を述べる． 性質1 ２つの正の分数$\frac{b}{a},\frac{d}{c}$が$ad-bc=1$を満たすとき，$n=\max (a,c)$に対応するFarey数列において隣り合わせである． これは命題2よりすぐに分かる． 性質2 Farey数列において，隣り合わせの分数$\frac{b}{a},\frac{d}{c} \ (\frac{b}{a}$＜$\frac{d}{c})$は$ad-bc=1$を満たす． 証明 数学的帰納法を用いる． $n=1$のときは成り立つ． $n=k$のとき成り立つと仮定する． $\frac{b}{a},\frac{d}{c}(\frac{b}{a}$＜$\frac{d}{c})$が$n=k$に対応するFarey数列の隣合う分数とする． このとき，$n=k+1$に対応するFarey数列において$\frac{b}{a},\frac{d}{c}$の間に分数があるのは，$ad-bc=1$であるから， 命題2より$\frac{b+d}{a+c}(a+c=k+1)$だけである． 一方， $\dfrac{b}{a},\dfrac{b+d}{a+c},\dfrac{d}{c}$ において， $a(b+d)-b(a+c)=1,d(a+c)-c(b+d)=1$ である．したがって，$n=k+1$に対応するFarey数列に老いても条件を満たすことが証明された． 性質2の証明はfarey数列の作り方を意味している．すなわち $n=k$に対応するFarey数列の隣り合う２つの分数$\frac{b}{a},\frac{d}{c}$のうち，$a+c=k+1$のとき間に$\frac{b+d}{a+c}$ を挿入し，$a+c$＞$k+1$のときはそのままにする． という操作で$n=k+1$のFarey数列を作ることが出来る． 実際，$n=4$に対応するFarey数列は $0,\dfrac{1}{4},\dfrac{1}{3},\dfrac{1}{2},\dfrac{2}{3},\dfrac{3}{4},1$ である．$0=\frac{0}{1},1=\frac{1}{1}$と見て，隣り合う分数の分母の和が$5$になるところに挿入し $n=5$に対応するFarey数列 $0,\dfrac{1}{5},\dfrac{1}{4},\dfrac{1}{3},\dfrac{2}{5},\dfrac{1}{2},\dfrac{3}{5},\dfrac{2}{3},\dfrac{3}{4},\dfrac{4}{5}, 1$ が得られる. ユークリッド互除法が高校の課程で扱われることになりました．無理数の連分数展開は互除法の一つの応用であり， 興味を持ってくれるのではないかとおもいまとめました． 私の書けるのはここまでです．すなわち広く知られた導入部分だけで，これからの内容は私は適任ではありません． しかるべき方のもとで学ぶか，最後に紹介しますので しかるべき書物すなわち 専門家の書いた専門書で学んでください． 最後にPell方程式の話をします． $a$が平方数でない自然数のとき，方程式 $x^2-ay^2=\pm 1$ をPell方程式といいます．この方程式の整数解を求めることが大きな目的です． Pell方程式の整数解の意味を考えて見ましょう． もちろん，双曲線上の格子点のことですが，$\sqrt{a}$の近似分数という見方をして見ましょう． $\sqrt{a}=\dfrac{y}{x}$ を満たす整数$x,y$は存在しないので， $x^2-ay^2=0$ となる整数$x,y$は存在しません．したがって， $x^2-ay^2=\pm 1$・・・@ の整数解は$\sqrt{a}$の優れた近似値である．したがって，@の整数解と$\sqrt{a}$の近似分数の関係は興味をそそられる． 詳しい内容は専門書にゆずるとして，ここでは具体的に調べてみよう． $\sqrt{2}$の近似分数と方程式 $x^2-2y^2=\pm 1$ の関係を調べよう． すでに計算したように， $\sqrt{2}=[1;2,2,\dots]$ より近似分数は次の表で与えられる． $\begin{matrix} \quad & \quad & 1 & 2 & 2 & 2 & 2 \\ b_n: & 1 & 1 & 3 & 7 & 17 & 41 \\ a_n: & 0 & 1 & 2 & 5 & 12 & 29 \end{matrix}$ $1^2-2\cdot 1^2=-1,3^2-2\cdot 2^2=1,7^2-2\cdot 5^2=-1,17^2-2\cdot 12^2=1$ 近似分数がすべてPell方程式の解になった．さらに，$x^2-2y^2=1$及び$x^2-2y^2=-1$の整数解に交互になりそうです． 次に$\sqrt{3}$の近似分数と方程式 $x^2-3y^2=\pm 1$ の関係を調べよう． まず，$\sqrt{3}$の連分数展開を求める． $x=\sqrt{3}=1+(\sqrt{3}-1)$ $\dfrac{1}{\sqrt{3}-1}=1+\dfrac{\sqrt{3}-1}{2}$ $\dfrac{2}{\sqrt{3}-1}=2+(\sqrt{3}-1)$ したがって，$1,2$が循環する．すなわち， $\sqrt{3}=[1;1,2,1,2,1,2,\dots]$ $\sqrt{3}$の近似分数を求めよう． $\begin{matrix} \quad & \quad & 1 & 1 & 2 & 1 & 2 \\ b_n: & 1 & 1 & 2 & 5 & 7 & 19 \\ a_n: & 0 & 1 & 1 & 3 & 4 & 11 \end{matrix}$ $1^2-3\cdot0^2=1,1^2-3\cdot 1^2=-2,2^2-3\cdot 1^2=1,$ $5^2-3\cdot 3^2=-2,7^2-3\cdot 4^2=1,19^2-3\cdot 11^2=-2$ このように$x^2-3y^2=1$及び$x^2-3y^2=-2$の解が交互に現れる． フェルマーは友人に次の内容の手紙を出しています． 方程式 $x^2-ay^2=1$ の最小に整数解について解を見つける一般法則を見つけて欲しい．例えば$a=61,109$の場合はどうなるか． この問題を近似分数より見つけてみましょう． まず， $x^2-61y^2=\pm 1$ を解きましょう． $\sqrt{61}$の連分数展開を求めましょう． プログラムを利用して計算してもよいですが，ここでは実際に計算して見ましょう． このような計算をすることによりいろいろ分かってくるものなのです． $[\sqrt{61}]=7, \ \ \ ;q_0=7$ $\dfrac{1}{\sqrt{61}-7}=\dfrac{\sqrt{61}+7}{12} \ \ ;q_1=1$ $\dfrac{12}{\sqrt{61}-5}=\dfrac{\sqrt{61}+5}{3} \ \ ;q_2=4$ $\dfrac{3}{\sqrt{61}-7}=\dfrac{\sqrt{61}+7}{4} \ \ ;q_3=3$ $\dfrac{4}{\sqrt{61}-5}=\dfrac{\sqrt{61}+5}{9} \ \ ;q_4=1$ $\dfrac{9}{\sqrt{61}-4}=\dfrac{\sqrt{61}+4}{5} \ \ ;q_5=2$ $\dfrac{5}{\sqrt{61}-6}=\dfrac{\sqrt{61}+6}{5} \ \ ;q_6=2$ $\dfrac{5}{\sqrt{61}-4}=\dfrac{\sqrt{61}+4}{9} \ \ ;q_7=1$ $\dfrac{9}{\sqrt{61}-5}=\dfrac{\sqrt{61}+5}{4} \ \ ;q_8=3$ $\dfrac{4}{\sqrt{61}-7}=\dfrac{\sqrt{61}+7}{3} \ \ ;q_9=4$ $\dfrac{3}{\sqrt{61}-5}=\dfrac{\sqrt{61}+5}{12} \ \ ;q_{10}=1$ $\dfrac{12}{\sqrt{61}-7}=\sqrt{61}+7 \ \ ;q_{11}=14$ したがって，$1,4,3,1,2,2,1,3,4,1,14$が循環することが分かります． 連分数展開の表示は，循環節の最初と最後に$\cdot$を頭に置いて，次のように表示します（循環小数の表示と同じ）． $\sqrt{61}=[7;\dot{1},4,3,1,2,2,1,3,4,1,\dot{14}]$ 次に$\sqrt{61}$の近似分数を求めます． ${\small \begin{matrix} \quad & \quad & 7 & 1 & 4 & 3 & 1 & 2 & 2 & 1 & 3 & 4 & 1 & 14 \\ b_n: & 1 & 7 & 8 & 39 & 125 & 164 & 453 & 1070 & 1523 & 5639 & 24079 & 29718 & 440131 \\ a_n: & 0 & 1 & 1 & 5 & 16 & 21 & 58 & 137 & 195 & 722 & 3083 & 3805 & 56353 \end{matrix}}$ それぞれの近似分数について$x^2-61y^2$を計算しよう． $7^2-61\cdot 1^2=-12$ $8^2-61\cdot 1^2=3$ $39^2-61\cdot 5^2=-4$ $125^2-61\cdot 16^2=9$ $164^2-61\cdot 21^2=-5$ $453^2-61\cdot 58^2=5$ $1070^2-61\cdot 137^2=-9$ $1523^2-61\cdot 195^2=4$ $5639^2-61\cdot 722^2=-3$ $24079^2-61\cdot 3083^2=12$ $29718^2-61\cdot 3805^2=-1$ $440131^2-61\cdot 56353^2=12$ 以上の計算より， $x=29718,y=3805$ が $x^2-61y^2=\pm 1$ の解であるあることが分かります．予想外に大きい数でした．これが最小であることの保証ではありません． これらの計算を行ったうえで，興味を持って後で紹介する 数学書を読むことが，数学を学ぶコツだと思います． フェルマーの出した問題がもう一つありました． $x^2-109y^2=\pm 1$ の整数解です． これは自分で計算してみましょう．私が計算したら次のようになりました． $\sqrt{109}=[10;\dot{2},3,1,2,4,1,6,6,1,4,2,1,3,2,\dot{20}]$ より $x=8890182,y=851525$ が解の一つです． 実際 $8890182^2-109\cdot 851525^2=-1$ となります． ここで述べた内容に興味を持ったら，是非次の参考書で学んでください． 1.小林昭七著 なっとくするオイラーとフェルマー 講談社 2.高木貞治著 初頭整数論講義 共立出版 3.G.H.ハーディー,E.M.ライト著 数論入門 丸善出版（邦訳あり） 1.は高校生向けにかかれたので読みやすいと思います． 2,3は共に９０年以上前に書かれた本で，世界的名著です． さらに，近似分数と大学入試との関連に興味を持っていいるなら，ホームページ 「青空学園」 が優れています．あわせて参考にしてください．このホームページはキーワード検索で見つけることが出来ます． 目次 |