100 = 31*3 + 7 より
7 = 100 + 31*(-3) ①
31 = 7*4 + 3 より
3 = 31 + 7*(-4) ②
7 = 3*2 + 1 より
7 + 3*(-2) = 1 ③
③に②を代入
7 + {31 + 7*(-4)}*(-2) = 1
7*{1 + (-4)*(-2)} + 31*(-2) = 1
7*9 + 31*(-2) = 1 ④
④に①を代入
{100 + 31*(-3)}*9 + 31*(-2) = 1
100*9 + 31*{(-3)*9 + (-2)} = 1
100*9 + 31*(-29) = 1
よって
100*9*2 + 31*(-29)*2 = 2 となるので
x=18,y=-58 は (＊)を満たす整数 x,yの組の１つ
100*x + 31*y = 2
100*18 + 31*(-58) = 2
(上の式)-(下の式)より
100(x-18) + 31(y+58) = 0
100(x-18) = -31(y+58) と加工すると、
左辺は100の倍数、右辺は31の倍数なので
100(x-18) = -31(y+58) = 100*31*n と置くことができ
x = 31n + 18
y = -100n - 58
|3x+y| = |3(31n + 18) + (-100n - 58)|
= |-7n-4|
n=1のとき |-7n-4| = |-11| = 11
n=0のとき |-7n-4| = |-4| = 4
n=-1のとき |-7n-4| = |3| = 3
n=-2のとき |-7n-4| = |10| = 10
なので n=-1のとき 最小値 3
また n=-1のとき
x = 31*(-1) + 18 = -13
y = -100*(-1) - 58 = 42
