11-01一次方程式の整数解を求める(難易度1)

方程式$37x-90y=1$について、$x$と$y$の整数解をすべて求めよ

互除法を使い代表解を求めよう

$a=90、b=37$とおくと
 $90=37\times2+16$ から $16=a-2b$
 $37=16\times2+5$ から $5=b-2(a-2b)=-2a+5b$
 $16=5\times3+1$ から $1=a-2b-3(-2a+5b)=7a-17b$
つまり、$37\cdot(-17)-90\cdot(-7)=1$
 $37(x+17)-90(y+7)=0$
 $37(x+17)=90(y+7)$
 $37$と$90$は互いに素であるため、$x+17$は$90$の倍数、$y+7$は$37$の倍数である。
つまり、$x+17=90k$、$y+7=37k(kは整数)$と表すことができるため
 $x=90k-17、y=37k-7(kは整数)$

 


$3x-2y=1$程度であれば、代表解$x=3、y=4$とすぐにわかるのですが、
数字が大きくなると、すぐに見つけることが難しくなるので
互いに素の数の最大公約数が1になることを考慮して、互除法を利用します。
互除法を見ていくと
 $a=b×①+c$
 $b=c×②+d$
 $c=d×③+1$
となり、最後は+1となります。
これを逆して、順番にたどっていくことで、$ax$と$by$の和が$1$になる$x$と$y$の整数がわかります。
 $a=b×①+c →c=a-b×①$
 $b=c×②+d →d=b-c×② →d=b-(a-b×①)×②$
 $c=d×③+1 →1=c-d×③ →1=a-b×①-\{b-(a-b×①)×②\}×③$

シェアする

  • このエントリーをはてなブックマークに追加

フォローする