2元1次不定方程式とAtCoder ABC186 E-Throne（前編）

１．はじめに

高校の数学Aで習う、2元1次不定方程式とABC186 E-Throne について書いていきます。前編では2元1次不定方程式の解法について、記していきます。

２．5x+3y=1 のような、xとyの係数が互いに素である場合

x=2 , y=-3 のような解を見つけ、5x+3y=1 から x=2 , y=-3 を代入した、　　5･2+3･(-3)=1 を引くと、5(x-2)=-3(y+3) が得られます。ここで、5と3が互いに素であることから、x-2=3k , y+3=-5k （kは整数）が得られます。このことから、x=3k+2 , y=-5k-3 となります。

さてこのとき、5x=5(3k+2)=3(5k+3)+1 と変形できるので、5x を 3 で割ると、1 余るということが分かります。このことを 5x ≡ 1 (mod 3 ) と書きます。逆に、 5x ≡ 1 (mod 3 ) を整数 x が満たすとき、5x は 3 で割ると 1 余る数なので、5x を 3 で割った商を q とすると、5x=3q+1 と書けるので、  5x-3q=1 が得られ、-q=y とおくと、5x+3y=1 が得られます。

３．5x+3y=2 のような場合

具体的な解の１つが、x=4 , y=-6 のように、２．のときの2倍になります。あとは、２．と同じ要領で x=3k+4 , y=-5k+6 が得られます。

さて、このとき 5x=5(3k+4)=3(5k+6)+2 となり、5x を 3 で割ると 2余ることが分かります。

４．10x+6y=24 のように、x と y の係数が 1 以外の最大公約数 g を持ち、右辺が g で割り切れる場合

両辺を 2 で割り、5x+3y=2 が得られるので、２．や３．の形にできます。

５．10x+6y=1 のように、x と y の係数が 1 以外の最大公約数 g を持ち、右辺が g で割り切れない場合

左辺は、2(5x+3y) で偶数、右辺は奇数なので解はないことが分かります。

６．217x+67y=1 のように、x と y の係数の絶対値 　が大きく、具体的な解が求めにくい場合

ユークリッドの互除法を用います。217=67×3+16…① , 67=16×4+3…② , 16=3×5+1…③ , 3=1×3+0…④ より、217 と 67 の最大公約数は 1 と分かりました。これを③から逆順に使い、1=16-3×5 、ここに②から得た 3=67-16×4 を代入し、1=16-(67-16×4)×5 で、変形し 1=21×16-67×5 、ここに①から得た 16=217-67×3 を代入し、1=21×(217-67×3)-67×5 で、変形し 　　　　1=217×21+67×(-68) が得られます。ここから、217x+67y=1 を満たす特殊解（具体的な解の１つ）が、( x , y ) = ( 21 , -68 ) であることが分かります。

次回の中編では、拡張ユークリッドの互除法について書いていきます。