『一次不定方程式』の電卓

ax+by=0の場合

一次不定方程式を解く基本となるのが右辺の定数項が0になる以下のような式です。

このような一次不定方程式を解く場合、まずyの項を右辺に移行させて式を変形します。

両辺の係数が互いに素（最大公約数が１）の場合は以下の関係に成り立ちます。

右辺が5の倍数なので左辺のxは5の倍数ということになります。

同じように左辺が3の倍数なので右辺のyは3の倍数ということになりますが、係数が負の数であるため-yが3の倍数となります。

これで一般解を求めることができました。

＜係数が互いに素ではない場合＞

係数が互いに素ではない場合、文字を対辺の倍数にすることができません。もし係数が互いに素でない場合は変形した後に、両辺を係数の最大公約数で割り一般解を求めます。

定数項が係数の倍数である場合

次に右辺の定数項がxかyの係数の倍数であるパターンを解説します。例えば以下のような一次不定方程式です。

この式では、定数項がxの係数の倍数であることがわかります。

このパターンの一次不定方程式の一般解を求めるには、まずは式を変形します。yの係数を右辺へ、定数項を左辺に移行して、左辺を整理します。

左辺の2と右辺の5が互いに素であるため、以下の関係が成り立ちます。

つまり、x-3が5の倍数、yが3の倍数ということになります。

これで一般解を求めることができました。

ax+by=cの場合

次にax+by=cの形になっている一次不定方程式の一般解の求め方を解説します。例えば以下のような一次不定方程式です。

こういった一次不定方程式の一般解を求める場合、まずひとつの整数解を求めます。xとyに値を代入してみて式が成立する値を探しましょう。ちなみに不定方程式が成り立つ解のひとつを特殊解と言います。

整数解をひとつ見つけたら、元の式から整数解を代入した式を引きます。すると定数項が相殺され0となりますので、yの項を移行させることができます。

左辺の3と右辺の2が互いに素であるため、以下の関係が成り立ちます。

つまり、x-1が2の倍数、-(y+1)が3の倍数ということになります。

これで一般解を求めることができました。

ユークリッドの互除法を用いた整数解の求め方

前章の解き方で整数解をひとつ見つけるという過程がありましたが、係数が小さい場合には簡単に見つかりますが、係数が大きくなると整数解をひとつ見つけるだけでも難しくなってしまいます。

そこで大きな係数でも整数解を見つける方法をここでは解説していきます。その方法とはユークリッドの互除法を用いた方法になります。

ユークリッドの互除法というのは、複数の数の最大公約数を見つける方法で、まず大きな数を小さな数で割って商と余りを出します。あとは割った数を余りで割るという事を繰り返して、余りが0になった時の割った数が最大公約数になります。

このユークリッドの互除法を応用して整数解を見つけます。例題として以下の一次不定方程式を解いてみます。

まずは係数の75と52にユークリッドの互除法を適用します。これは最大公約数を求めることが目的ではなく、式を応用するためにおこないます。

次に上記の式を『 割られる数 - 割る数 × 商 = 余り 』という形に変形します。このとき一番最後の余りが0になる式を不要なので取り除いておきます。

次に下から２番目の式を一番下の式に代入していきます。下から2番目の式は余りが5なので、一番下の式に左辺を代入することができます。

代入したら○×△の形になるように式を整理します。

これで下から2番目の式を代入して整理できました。同じように下から3番目、4番目と代入して整理していきます。

最後にできた式を以下のように変形してみると元の一次不定方程式の形になることがわかると思います。

つまり、( x, y ) = ( -9, 13 )が整数解のひとつとして見つかるというわけです。

＜定数項が1以外の場合＞

定数項が1以外の場合はもう１手間必要になります。例えば以下のような一次不定方程式の場合です。係数は先ほどの式と同じで定数項が2になっています。

この場合、まず定数項を1としてユークリッドの互除法で一次不定方程式の形になる式を作ります。先程と解き方は同じになるので以下の式ができます。

しかし、本来の式は定数項が2なのでこの式の両辺に2を掛けます。

これで本来の一次不定方程式の形にすることができました。つまり、整数解は( x, y ) = ( -18, 26 )ということがわかったというわけですね。