2014/08/27

ペル方程式に関する基本的な性質まとめ

分野: 整数問題  レベル: 最難関大学

整数 $x$ と $y$ に関する不定方程式:$x^2-dy^2=1$ をペル方程式と言う

ペル方程式について入試レベルで知っておくと便利な知識を整理しました。

より一般に,$x^2-dy^2=n$ という形の不定方程式をペル方程式と呼ぶこともありますが,ここでは「ペル型方程式」と呼んで区別します。

二次の不定方程式をペル方程式に帰着させる

二次の不定方程式 $ax^2+bxy+cy^2+dx+ey+f=0$ の多くがペル型方程式に帰着できます。

例1

$3x^2-5y^2=4$
両辺 $3$ 倍して $3x=X, y=Y$ とおくと,
$X^2-15Y^2=12$ となりペル型方程式に帰着される。
$(x, y)$ が整数なら$(X,Y)$ も整数なので上記のペル型方程式の整数解$(X,Y)$ が求まればもとの整数解も全て求まる。

例2

$x^2+2xy-y^2-3=0$
平方完成するとペル型方程式に帰着される:
$(x+y)^2-2y^2=3$
ここで,$x+y=X, y=Y$ とおくと,
$X^2-2Y^2=3$ となる。$(x, y)$ が整数なら$(X,Y)$ も整数なので上記のペル型方程式の整数解$(X,Y)$ が求まればもとの整数解も全て求まる。

ペル方程式についての性質

ペル方程式 $x^2-dy^2=1$ について考えます。

まず,$(x,y)$ が解なら$(x,-y)$ なども解なので $x,y$ が共に非負である解を考えます。
次に,$x=1, y=0$ は自明な解なのでそれ以外の解について考えます。

$d$ が平方数の場合,左辺が$(x+\sqrt{d}y)(x-\sqrt{d}y)$ と因数分解できるので簡単に解けます。なので以下では $d$ が平方数でない場合の定理を述べます。

定理1:ペル方程式には必ず自明でない解が無限個存在する
定理2:ペル方程式の解の中で $x+\sqrt{d}y$ を最小にするような解を$(x_0, y_0)$ とおく。すると,自然数 $n$ を用いて
$x+\sqrt{d}y=(x_0+\sqrt{d}y_0)^n$ という形で書ける$(x,y)$ もまたペル方程式の解であり,それで全てを尽くす。
定理3:上記の$(x_0,y_0)$ を見つけるそれなりにはやいアルゴリズムがある

定理の証明は難しいので割愛します,より詳細を知りたい方はペル方程式(英語サイト)を参照して下さい。証明を知らなくても入試で不利になることはありません。定理2を背景とする問題はたまに出題されます。

ペル方程式の解について

  • 定理2における$(x_0, y_0)$ を初期解と言います。初期解を求めてしまえば定理2によりペル方程式の一般解が求められます。
  • 定理2と関連して:ペル方程式の解が $1$ つ見つかればそれをもとに無限個の解を作り出すことが出来ます。→ブラーマグプタの恒等式の一番下参照。
  • 初期解を求めるのは簡単ではありません。例えば $d=61$ の場合だと初期解は$(x_0,y_0)=(1766319049,226153980)$ です。直感では無理ですね。そこで定理3が活躍するのです。
  • 一般のペル型方程式については定理1は成り立ちません。
    例えば,$x^2-3y^2=-1$ について考えると,$x^2+1=3y^2$ となり平方剰余の考え方から左辺は絶対に $3$ の倍数にならないので整数解は持ちません。→平方剰余と基本的な問題
ペル方程式の世界はもっともっと広いですが,自分も深く理解していないので概観になってしまいましたm(__)m

Tag: 不定方程式の解き方6パターン

分野: 整数問題  レベル: 最難関大学