次: 一次不定方程式の解の存在 上: 一次不定方程式 前: 一次不定方程式

不定方程式

未知数が$x$と$y$，あるいは$x,\ y,\ z$など2個以上あり，係数が整数である方程式， 例えば

$$2x+3y=1,\ xy-2x-3y+1=0,\ \dfrac{1}{x}+\dfrac{1}{y}+\dfrac{1}{z}=1,\ x^2-3y^2=1$$

のようなものでは，実数の解は無数にある．解が定まらないので不定方程式という． ところが，これらの方程式を満たす整数の組となると， 有限個であったり，すべてが書き下せたり，あるいは存在しなかったり，様相が一変する．

整数係数の方程式を「ディオファントスの方程式」ともいう． ディオファントス(Diophantos 前3世紀ごろ)は アレキサンドリアで活躍したとされるギリシア時代の数学者である． 幾何学的であったそれまでの数学に代数学を導入,著書のなかで二次方程式や不定方程式を解いた．

$2x+4y-3z=5$のような一次不定方程式の整数解を考える． その整数解の集合がどのような構造をもっているのか， これが整数の主要な問題の一つである．

まず二変数の場合に調べ，それを一般化するという方向で考えよう． $a$と$b$が互いに素なとき一次不定方程式$ax+by=k$に関して次の事実が成立する．

1. 整数解が存在する．
2. すべての解を一般的な形にかける．
3. 解を構成するアルゴリズムがある．

本節ではこれを示すいくつかの方法をまとめた後， 一般的に整数係数の一次不定方程式

$$a_1x_1+a_2x_2+\cdots +a_nx_n =k$$

を考え，解の存在と一般解構成のアルゴリズムが存在することを示す．