>>74
まず a, b が互いに素なので、ある整数 p, q が存在して pa + qb = 1 と
表せる(a > b と仮定)。任意に 1 ≦ s ＜ b を固定する。このとき、任意の
整数 t に対して

(sp - tb)a + (sq + ta)b = s

が成り立つ。すると a, b > s から sp - tb, sq + ta は異符号となるはずで
あり、ちょうどそれらの符号が反転する境の t = t0 が存在する。すなわち
sp - t0 b > 0, sq + t0 a < 0 かつ sp - (t0 + 1)b < 0, sq + (t0 + 1)a > 0
である。いま、n (> ab) を整数 k ≧ 0 を用いて n = (a + k)b + s と表せば

x = sp - t0 b
y = sq + (t0 + 1)a + k

は自然数であり ax + by = (a + k)b + s = n を満たす。