ユークリッドの互除法の応用

上野竜生です。前回はユークリッドの互除法を用いてa,bが互いに素なとき，ax+by=1を満たす整数x,yを求めることをしました。今回はその部分はできるものとして応用を紹介していきたいと思います。

右辺=1ではないとき

7x+5y=1を満たす整数x,yはx=3,y=-4があります。

（１）　7×3+5×(-4)=1なので両辺を123倍すると
7×369+5×(-492)=123　となるのでx=369,y=-492

（２）a,bが互いに素でない場合，ax+by=d(=aとbの最大公約数)を満たす整数(x,y)が求められます。

両辺を3で割ると7x+5y=41
以下(1)と同様にするとx=123,y=-164

1組ではなく，すべて求めるとき

（１）1組見つけることができれば両辺をひけばOKです。先ほどの例題と同様にして1組(x,y)=(72,-96)を見つけたとします。

7x　+　5y　  =24
7×72+5×(-96)=24

両辺をひくと

7(x-72)+5(y+96)=0　つまり7(x-72)=-5(y+96)

7と5は互いに素だからx-72は5の倍数。よってx-72=5k(kは整数)とおける。

x=5k+72を元の式に代入するとy=-7k-96

よって(x,y)=(5k+72,-7k-96) (kは整数)

（２）自然数とは1以上の整数なので（１）のあとx≧1,y≧1を解けば良い。

\( 5k+72 \geq 1 \)より\( k \geq -\frac{71}{5}\)

\( -7k-96 \geq 1\)より\( k \leq -\frac{97}{7} \)

kは整数よりk=-14

これらを（１）の答えに代入して(x,y)=(2,2)

基本的にすべての解を見つけることができればあとはどうにでもなります。ここまでのやり方を学習しておけばこのタイプは応用できます。