高校数学（1次不定方程式 ax+by=c の特殊解）

ユークリッドの互除法で1組の解を見つける

例えば、適当に問題を作ると、$42x+143y=1$

$143=42\cdot 3+17$

$42=17\cdot 2+8$

$17=8\cdot 2+1$　であるから、

$17=143-42\cdot 3$

$8=42-17\cdot 2$

$1=17-8\cdot 2$

下から順に上の式を代入して

$1=17-8\cdot 2$

$=17-(42-17\cdot 2)\cdot 2$

$=-42\cdot 2+17\cdot 5$

$=-42\cdot 2+(143-42\cdot 3)\cdot 5$

$=-42\cdot 17+143\cdot 5$

$=42\cdot (-17)+143\cdot 5$

したがって、$x=-17$、$y=5$ となりました。

（これは他の数字になることもあります）

この方法はなかなか慣れません。私はいつも次の方法で求めています。

$ 1\ \ \ \ \ \ \ \ \ 0\ \ \ \ \ \ \ \ \ 42$
$ 0\ \ \ \ \ \ \ \ \ 1\ \ \ \ \ \ \ \ \ 143$　        上の式を3倍して
$ 3\ \ \ \ \ \ \ \ \ 0\ \ \ \ \ \ \ \ \ 126$　        上の式から引いて
$ -3\ \ \ \ \ \ \ 1\ \ \ \ \ \ \ \ \ 17$　          2倍して
$ -6\ \ \ \ \ \ \ 2\ \ \ \ \ \ \ \ \ 34$　          一番上の式から引いて
$ 7\ \ \ \ \ \ \ \ \ -2\ \ \ \ \ 8$　            2倍して
$ 14\ \ \ \ \ \ \ -4\ \ \ \ \ 16$　          4番目の式から引いて
$-17\ \ \ \ \ 5\ \ \ \ \ \ \ \  1$

これで、$x=-17$、$y=5$ となりました。

問題の式の右辺と右端の数が一致すればOKです。

合同式や割り算を利用する方法などもありますので、一番使いやすい方法を見極めましょう。