高校では整数の章で不定方程式ax+by=1を習います。 ただし、文字はすべて整数で、aとbは「互いに素」です。
例えば
の解は
です。 ただし、この他にも(x,y)=(7,-12)、(11, -19)など、無数に解があり、その一般形は
となります。ただし、tは整数です。 この解一般を表したものを「一般解」、そのうちのひとつ（どれでも良い）を「特殊解」といいます。
高校では特殊解から一般解を出すところは説明されているのですが、特殊解の求め方については十分な説明がありません。 また、ネットにおける情報も十分ではないように思います。 そこで、今回は「特殊解の求め方」について書いてみたいと思います。
以下では「特殊解」を単に「解」ということにします。
最も良い方法を手っ取り早く知りたい人は最後の節（合同式を使う方法）だけを読んでください。
総当り方式
総当り方式というのは、整数を代入して試し、解を発見する方法です。 「総当り」というのは、整数全部を試すということではありません。 例えば先程の方程式
の場合、xならば0から3までを試せば解を発見できます。 （0からyの係数4より1だけ小さい数3まで）。 他方、yならば0から6までを試せば解を発見できます。 ですから、xで探すほうが効率が良いです。
- x=0 ならばy=1/4で不適
- x=1ならばy=-3/2で不適
- x=2ならばy=-13/4で不適
- x=3ならばy=-5で適
高校の試験ではこの方式で短時間で見つけられるような問題が多いです。 しかし、容易に想像できますが、係数が大きくなれば計算は大変になります。 例えば、
の解は
ですが、これを総当り方式でやるのは本当に大変です。 ネット情報では、このようなときに「ユークリッドの互除法を使う」と書かれていることが多いです。 次にこの方法を説明します。
ユークリッドの互除法
ユークリッドの互除法を知っている方はこの節を飛ばしてください。
2つの整数の最大公約数を求める方法のひとつに「ユークリッドの互除法」があります。 例えば、51と36の最大公約数を求めるには、次のようにします。
- 51を36で割る＝＞商が1あまりが15
- そのわり算の「割る数」を「あまり」で割る→36÷15→商が2であまりが６
- そのわり算の「割る数」を「あまり」で割る→15÷6→商が2であまりが3
- そのわり算の「割る数」を「あまり」で割る→6÷3→商が2であまりが0
割り切れたときの割る数が最大公約数。したがって、この例では3が最大公約数。
なぜ、これで最大公約数が求まるかは、教科書やネット情報を参照してください。 大事なことは、この方法ならば、
- さほど多くない計算で最大公約数が求まる
- かならず最大公約数を求めることができる
ということです。
また、 アルゴリズムがはっきりしているので、プログラムにするのも容易です。 プログラムの本ではリカーシブコールの例として取り上げられていることが多いです。
ユークリッドの互除法を用いた不定方程式の解法
はじめは、簡単な例で説明します。
まず、7と4にユークリッドの互除法を用いて最大公約数を求めます。
- 7÷4 → 商が1あまりが3
- 4÷3 → 商が1あまりが1
- 3÷1 → 商が3あまりが0
これから、最大公約数は1になります。 不定方程式を解くときには下から2番めまでの式を検算の式に変形して使います。 検算の式は、たとえば
ですが、ここでは右辺を余りだけにします。
同様に第2式から
この式の第2項の3は第1式のあまり、すなわち右辺です。 第1式を第2式に代入して
これを整理すると
この最後の式から、x=-1, y=2が不定方程式の解です。
この例では係数が小さいので割り算（検算）の式を2つしか使いませんでした。 そのため、代入は1回ですみましたが、係数が大きい場合は数回の代入が必要になることもあります。
- 割り算の下から2番めの式をベースにする
- あまりの代入は下から3番めの式から上の式に向かって順番に行う
この方法はアルゴリズムが確定しているので、かならず答えにたどり着くことができるのですが、代入の計算は結構わかりにくく慣れが必要です。 わかりにくい原因は代入後変形が必要なところですが、それを公式化してわかりやすくすることが考えられます。
互除法利用の解法を使いやすくする
さきほどの方法を分析してみます。 互除法の途中の検算の式を
となっていたとしましょう。 aとbは互除法の途中に出る数字（aは前の式の「割る数」bは「あまり」）で、qとrはこの式における商とあまりです。 下から代入を繰り返して、この式のひとつ下まで来ていたとします。 そのときの方程式が
となっていたとしましょう。 あまりrを代入すると
ですので、代入の結果得られる解はx=vとy=u-qvになります。 これを公式とみなして、順にあてはめていけば良いのです。 例をやる前に、今の公式をまとめておきます
- a÷b → 商がqあまりがr → av+b(u-qv)=1 （下の式から得られる式） → 解は x=v, y=u-qv
- b÷r → ・・・・・・・ → bu+rv=1 （下から順に得られた式） → 解は x=u, y=v
例として、7x+4y=1を解いてみます。 はじめに左から2カラム目まで（商とあまりの計算まで）行い、一番右のカラムは下から上に戻ってきます。
- 7÷4 → 商が1あまりが3 → x = -1, y=1-1*(-1)=2
- 4÷3 → 商が1あまりが1 → x = 1, y=-1
- 3÷1 → 商が3あまりが0 → 関係ないので無視
これから、x=-1, y=2が解です。
さらに複雑な方程式でやってみましょう
- 723÷431 → 商が1あまりが292 → x = 31, y=-21-1*31=-52
- 431÷292 → 商が1あまりが139 → x = -21, y=10-1*(-21)=31
- 292÷139 → 商が2あまりが14 → x = 10, y=-1-2*10=-21
- 139÷14 → 商が9あまりが13 → x = -1, y=1-9*(-1)=10
- 14÷13 → 商が1あまりが1 → x = 1, y=-1
答えはx=31、y=-52です。
慣れればできるけれど、やり方を忘れてしまいそうですね。 これに比べて、次の合同式を使う方法は覚えやすいものです。
合同式を使う方法
合同式についてはネット情報などを参考にしてください。 高校では習いませんが、それほど難しくないです。 おそらく授業2コマくらいで基本は十分教えることができます。
合同式ではまず、法を決めます。 3を法にしてみましょう。 このとき、3で割ったあまりが等しい数は合同といい、
と書きます。 法が、書き手と読み手で了解済みであれば省略されます。 たとえば、4と7は両方とも3で割ったあまりが1なので合同です。
合同式はイコールとほぼ同じように和、差、積を行えます。 両辺に同じ数を加えたり、引いたり、掛けたりしても合同は保たれます。 たとえば、さきほどの4と7に10をかけて
です。実際に3で割ったあまりは両方とも1ですから。
これは次のようになります。
なぜなら、431yの部分は431の倍数、すなわち割ったときのあまりが0ですから、723x+431yを431で割ったあまりと723xだけを431で割ったあまりは等しいからです。
また、431xは431で割り切れるので、0に合同ですから
この2つの式から、互助法のように割り算の検算のようなことをしていきます。
2つの式で引き算をする。以下modの部分は略します。
今の式と、そのひとつ前の式の差を取る。
一つ前の式から今の式の2倍を引く。
一つ前の式から今の式の9倍を引く。
差をとる
これで、x=31が得られました。 元の方程式に代入して、y=-52を得ることができます。
合同式の方法は新たに公式を暗記しなくてすみます。 分かりやすい方法なので、一番お勧めです。
