次: 演習問題 上: 連分数による解の構成 前: ペル方程式の解の構成

解構成のアルゴリズム

ペル方程式の解の構成理論ができたのだから，実際にプログラムを作って いくつかの解を求めよう． そのためには，まず解を構成する手順を書き出し，適切なプログラム言語を定め， 翻訳しなければならない．

$D$に対して $x^2-Dy^2= \pm 1$の $x+\sqrt{D} y >1$のなかでの最小解を求める手順 は次の通りである．

1. $D$を決める．
2. $\sqrt{D}$の整数部分を$q_0$， $x_1= \dfrac{1}{\sqrt{D}-q_0}$と置く．
3. $P_{-1}=1,P_0=q_0,Q_{-1}=0,Q_0=1$とし，$n \ge 1$に対し次の過程を繰り返す．
   1. $$x_n= \frac{1}{x_{n-1}-q_{n-1}}$$で$x_n$を定め， $x_n$の整数部分を$q_n$と置く．
   2. 
      
      $$\left\{ \begin{array}{l} P_n=q_n \cdot P_{n-1}+P_{n-2} \\ Q_n=q_n \cdot Q_{n-1}+P_{n-2} \end{array} \right.$$
      
      

4. $x_{k+1}=x_1$となったとき，この過程を終える．その$k$に対して， 最小解 $x=P_{k-1},\,y=Q_{k-1}$が得られる．

UBASIC によるプログラム

この手順を実行するプログラム言語を探す． 高等学校の教科書に載っている BASIC は， 数値が一定の桁の有効数字をもつ小数表示の近似実数である． $1/3 や \sqrt{2}$と置けば， $0.33333333,\ 1.41421356 \ (有効桁まで)$となる． 大きい数も有効桁までしか正しく表示されない． 従ってこのままでは$x_{k+1}=x_1$の判断ができない．

UBASIC という， BASIC を改良し，大きい整数も不動点表示をせずそのまま で扱え，有理数も分母分子を（約分して）別々に保持するようにした言語がある． それを用いる．// が分数である． UBASIC でも無理数は近似数になり，そのままでは 比較できないので，$x_{k+1}=x_1$の判断をさせるために， $x_n=S+T \sqrt{D}$と 二つの有理数に分けそれぞれを比較することにする．

三項間漸化式を解くのには工夫がいる．$P_n$，$Q_n$の値を順次入れていく変数を二つずつ 用意し交互に用いるようにする．

次に掲げるのは $D=2$ から $D=1999$ まで， $x^2-Dy^2= \pm 1$の 最小解を書き出すプログラムである．

10  open "pell.txt" for create as #1
20  for D=2 to 1999
30  if D=(isqrt(D))^2 then 220 else 40
40  Q0=isqrt(D)
50  S1=Q0//(D-Q0^2):T1=1//(D-Q0^2)
60  X=S1+T1*(sqrt(D)):PA=Q0:QA=1:PB=1:QB=0:S=S1:T=T1
70  Q=int(X):PB=PA*Q+PB:QB=QA*Q+QB
80  K=K+1
90  S0=S
100  S=(Q-S)//(T^2*D-(Q-S)^2):T=T//(T^2*D-(Q-S0)^2)
110  X=S+T*(sqrt(D))
120  if S=S1 and T=T1 then goto 190 else 130
130  Q=int(X):PA=PB*Q+PA:QA=QB*Q+QA
140  K=K+1
150  S0=S
160  S=(Q-S)//(T^2*D-(Q-S)^2):T=T//(T^2*D-(Q-S0)^2)
170  X=S+T*(sqrt(D))
180  if S=S1 and T=T1 then goto 200 else 70
190  print #1,"&",PA,"&",QA,"&",K:goto 210
200  print #1,"&",PB,"&",QB,"&",K
210  K=0
220  next D
230  end

$D=331$までの6桁以上の解

こうして得られた最小解のなかで6桁以上になるものを以下に掲げ，最後に$D=1999$を載せる．

$$\begin{array}{rrrr} D&P&Q&k \\ 94 & 2143295 & 221064 ... ...00729 & 12 \\ 241 & 71011068 & 4574225 & 17 \end{array}$$ $$\begin{array}{rrrr} D&P&Q&k \\ 241 & 2167554245 & 139... ... 331 & 2785589801443970 & 153109862634573 & 34 \end{array}$$

また，1999は素数で，
         $P=4027701399389138208695911951306886478800$
         $Q=90084665203202024260494303744425250249$
        $k= 84$
である．