ペル方程式(Pell Equation)は整数解を求める不定方程式の1種で、一般論が完成されている数少ない方程式である。

ペル方程式の名はオイラーが誤って命名したものとされている。ペルは実在の数学者であるが、この方程式に対する研究は全くなかった。

ペル方程式

    x2 - M y2 = c  (M は平方数でない正整数、c = +1, -1)

において、自明な解 x = 1、y = 0 以外の x、y が最も小さい正の整数である解を、そのペル方程式の最小解という。方程式の右辺 c = -1 としたときには解がない場合が多いが、しかし -1 に対する最小解が存在する場合には、必ずその最小解のほうが +1 に対する最小解よりも小さい。

例えば、M = 2 の場合の方程式については、x、y のペア (1,1)、(3,2)、(7,5)、 (17,12)、(41,29)、(99,70)、(239,169)、(577,408)... がその解であるが、 -1 に対する最小解は x=1、y=1 であり、+1 に対する最小解は x=2、y=3 である。

<関数名>
  pellEqu ---- ペル方程式 x2 - M y2 = c の最小解を得る。ただし、M は平方数でない正整数、c = 1, -1。

<形式>
  int pellEqu(long *x1, long *y1, long *x2, long *y2, int m);

<引数>
  x1, y1 (出力)ペル方程式 x2 - M y 2 = 1 に対する最小解
  x2, y2 (出力)ペル方程式 x2 - M y 2 = -1 に対する最小解
  m    (入力) ペル方程式の係数 M (1,4,9,16...以外の非平方数)

<関数値>
  c = 1 または -1 の両方に対する最小解が得られたときは 1、
  c = -1 に対する最小解が存在しなかったときは 0。
  c = 1 に対する最小解も c = 1 に対する最小解も得られなかったときは -1。

<注意事項>
  ペル方程式の解は必ず存在するが、限られた整数範囲(long整数で表現できる範囲内)のなかで解が見つからなかったときには、関数値は -1 となる。

用例

<関数本体>
  pellEqu.c

<説明>
  ペル方程式の一般解はつぎの漸化式で求められる。

      xn+1 = x1xn + M y1yn
      yn+1 = x1yn + y1xn

    ただし x1、y1は最小解を表す。したがってペル方程式を解くにはその最小解を求めればよい。
  M の値によって、最小解が意外に大きな数になることがある。例えば、M=61、c=1 に対する最小解は x=1766319049、y=226153980 にもなる。
  最小解はつぎのように漸化的に求められる。

      s0 = 0  t0 = 1
      a0 = M1/2 の整数部
      x-1 = 1  y-1 = 0  x0 = a0  y0 = 1
      sk+1 = aktk - sk  tk+1 = (M - sk+12) / tk
      ak+1 = (a0 + sk+1) / tk+1の整数部
      xk+1 = ak+1 xk + xk-1  yk+1 = ak+1 yk + yk-1

  tk+1の値が 1 になったときの、xk、ykの値がペル方程式の最小値となる。

Comments are closed.

Post Navigation