一次不定方程式の整数解がユークリッドの互除法で求められるというのがよく分かりません。ax∔by＝１でa、bが互いに素であれば整数解をもつので、最大公約数は1であるのでユークリッドの互除法を使って最大公約数が1であるっていうのを求めるっていう所までは分かります。だけど、そっから整数解を求めていく手順がよくわかりません。数弱なので分かりやすく説明していただけると嬉しいです。

大事なのは、ax+byで作れる整数どうしをどれだけ足そうが引こうがax+byで表せる整数しか作れないということ。

与えられた整数a,bに対し集合S={ax+by|x,yは整数}を考えると、Sは加法について閉じている。

aやbもax+byで作れる整数(x,y)=(1,0),(0,1)なので、思う存分足し引きして1を作ってくれということ。

a,bが互いに素なら互除法の手順で必ず1が作れるから互除法を使う。

別にax+byの形を崩して計算する必要は全くない。

31x+21y=1なら

31=31×1+21×0…①

21=31×0+21×1…②

①-②

10=31×1+21×(-1)…③

②-③×2

1=31×(-2)+21×3