1次不定方程式216x+13y=9を満たす整数の組(x,y)を求めよ。
この問題の通常の解法の手順は次の通りである。
①216と13に対し、ユークリッドの互除法を行う。余りが1になるまで計算。
②余り=～の形にする。
③逆向きに代入して、216×○+13×△=1の形に変形する。
④両辺を9倍し、特殊解(9×○,9×△)
⑤特殊解から一般解を求める。
この解法のうち、③がややこしい。
それを少しでも解決したい。
a=216, b=13とし、ユークリッドの互除法を行う。計算の都度、余りをpa+qbの形で表す。
a=216, b=13とする。
216=13×16+8より、8=216-13×16=a-16b
13=8×1+5より、
5=13-8×1=b-(a-16b)=-a+17b
8=5×1+3より、
3=8-5×1=(a-16b)-(-a+17b)=2a-33b
よって、両辺を3倍して、
9=6a-99b
すなわち、216×6+13×(-99)=9
特殊解は、(x,y)=(6,-99)である。
一般解の求め方は同じ。
216x+13y=216×6+13×(-99)
216(x-6)+13(y+99)=0
216と13は互いに素だから、
(x-6,y+99)=(13k,-216k)
(x,y)=(6+13k,-99-216k)
5s+3t=kの特殊解を利用すると、216x+13y=kの特殊解を求めることができる。
(8s+5t=kでも求めことができるが、特殊解が見つけにくい。)
216x+13y=2のときは、
2=5×1-3×1=(-a+17b)-(2a-33b)=-3a+50b
よって、216×(-3)+13×50=2
216x+13y=7のとき、
7=5×2-3×1=2(-a+17b)-(2a-33b)=-4a+67b
よって、216×(-4)+13×67=7
216x+13y=53のとき、
53=35+18=5×7+3×6
=7(-a+17b)+6(2a-33b)=5a-79b
よって、216×5+13×(-79)=53
216x+13y=1のとき、
1=5×2+3×(-3)
=2(-a+17b)-3(2a-33b)=-8a+133b
よって、216×(-8)+13×133=1
(2019/1/29)
この問題の通常の解法の手順は次の通りである。
①216と13に対し、ユークリッドの互除法を行う。余りが1になるまで計算。
②余り=～の形にする。
③逆向きに代入して、216×○+13×△=1の形に変形する。
④両辺を9倍し、特殊解(9×○,9×△)
⑤特殊解から一般解を求める。
この解法のうち、③がややこしい。
それを少しでも解決したい。
a=216, b=13とし、ユークリッドの互除法を行う。計算の都度、余りをpa+qbの形で表す。
a=216, b=13とする。
216=13×16+8より、8=216-13×16=a-16b
13=8×1+5より、
5=13-8×1=b-(a-16b)=-a+17b
8=5×1+3より、
3=8-5×1=(a-16b)-(-a+17b)=2a-33b
よって、両辺を3倍して、
9=6a-99b
すなわち、216×6+13×(-99)=9
特殊解は、(x,y)=(6,-99)である。
一般解の求め方は同じ。
216x+13y=216×6+13×(-99)
216(x-6)+13(y+99)=0
216と13は互いに素だから、
(x-6,y+99)=(13k,-216k)
(x,y)=(6+13k,-99-216k)
5s+3t=kの特殊解を利用すると、216x+13y=kの特殊解を求めることができる。
(8s+5t=kでも求めことができるが、特殊解が見つけにくい。)
216x+13y=2のときは、
2=5×1-3×1=(-a+17b)-(2a-33b)=-3a+50b
よって、216×(-3)+13×50=2
216x+13y=7のとき、
7=5×2-3×1=2(-a+17b)-(2a-33b)=-4a+67b
よって、216×(-4)+13×67=7
216x+13y=53のとき、
53=35+18=5×7+3×6
=7(-a+17b)+6(2a-33b)=5a-79b
よって、216×5+13×(-79)=53
216x+13y=1のとき、
1=5×2+3×(-3)
=2(-a+17b)-3(2a-33b)=-8a+133b
よって、216×(-8)+13×133=1
(2019/1/29)
