不定方程式の整数解

ax+by=c (a,b,cは定数) を満たす整数 x,y を求めるのが不定方程式の整数解です。「不定」とは「定まらず」。つまり、解は１つには決まりません。

たとえば

2x+3y=7

を満たすx,y。x=2,y=1はすぐに気がつきます。ほかにも x=5,y=−1 などたくさんあります。一般的には x=3n+2 , y=−2n+1 (nは整数）が解になります。

x=2,y=1 のような具体的な値を「特殊解」、x=3n+2 , y=−2n+1 (nは整数）の形を「一般解」といいます。

2x+3y=7を満たすx,yとして、x=2,y=1はすぐに気がつきますが、2x+3y=70 を満たすx,y はどうですか？

右辺が10倍になっているので、解も10倍して x=20,y=10 にすればよいですね。

不定方程式を解く方法は、上のようにすぐにわかる場合は別として、次の２つがあります。（高校の教科書のレベルです）

(1) a,bのいずれかとcに１でない公約数があれば ax=d(ey+f) または d(ex+f)=-by の形に変形して解きます。

たとえば

4x+3y=12 は、3yと12をそれぞれ移項して

4(x-3)=−3y とします。

すると、yは4の倍数、x-3は3の倍数で、符号に注意すれば x=−3n+3 , y=4n が一般解となります。

(2) ユークリッドの互除法の計算を逆にたどって特殊解を求めます。

たとえば

16x+7y=1 は、16を7で割って商と余りを求めると 16=7×2＋2 と表せます。

次に、小さい方の7を、今の余りで割って 7=2×3＋1 です。

ここから逆算すると 1=7−2×3＝7−(16−7×2)×3=16×(−3)＋7×7 すなわち x=−3 , y=7 とすれば 16x+7y=1 になります。

特殊解が得られたら、

16x+7y=1

16×(−3)＋7×7=1

を辺々引いて 16(x+3)+7(y−7)=0 から 16(x+3)=7(7−y) となるので、x+3は7の倍数、7−yは16の倍数で、一般解 x=7n-3 , y=−16n+7 が得られます。

さて、それでは、不定方程式の整数解を求めるプログラムはどう作ればよいでしょう。

実は、(1)や(2)の変形をプログラムするより、単に整数を代入して成立するかどうかを判定する方がプログラムは簡単です。もし一般解が必要なら、特殊解が１つ見つかったところで、(2)の方法をとればよいでしょう。次のスクリプトではある範囲内での特殊解をリストアップします。

-----------------------------------------------------------

// 不定方程式 ax+by=c を解く

a=315;     // それぞれ値を代入

b=255;

c=15;

n=50;    // 調べる範囲。この場合、−24から25まで

ans=[];  // 解のリスト。はじめは空

repeat(n,i,

  x=i-n/2;

  y=(c-a*x)/b;

  if(isinteger(y),                   // ｙが整数になれば解

    ans=append(ans,[x,y]);   // 解のリストに追加

  );

);

println(ans);

 ------------------------------------------------------------------

あまり面白いプログラムではありません。手計算で出した特殊解や一般解を確かめるくらいには使えるでしょう。

＜戻る＞