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

上野竜生です。前回はユークリッドの互除法を用いて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)

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

数学はもちろん他の科目も勉強できる「スタディサプリ」なら人気講師の授業動画で、塾にいかなくてもまるで塾にいったかのような勉強ができます。塾と比較すると格安で、しかも無料おためしもできます。当サイトオススメのサイトです。