>>326
a=bq+rの形を
r=a-bqの形に書き換えて、
最後の方から順に代入していけばいい。

たとえば
1071 = 1 * 1029 + 42
1029 = 24 * 42 + 21
42 = 2 * 21

から
21 = 1029 - 24 * 42 = 1029 - 24 * (1071 - 1 * 1029)
= -24 * 1071 + 25 * 1029
を得る