互除法与一次不定方程

为什么是这样

关键一句：若 $a=bq+r$，则 $a$、$b$ 的公约数与 $b$、$r$ 的公约数完全相同。前者能整除 $r=a-bq$，后者能整除 $a=bq+r$。公约数一个不差，最大的自然相等。于是 $(a,\,b)$ 换成更小的 $(b,\,r)$，答案不变、数变小；余数总比除数小，几步后必然除尽，这时的除数就是最大公约数。

图上看：在 $a\times b$ 的长方形里尽量多地切下边长 $b$ 的正方形，剩下 $b\times r$ 的窄条，再对它重复。最后恰好切完的小正方形能量尽每一条边，它的边长就是最大公约数。

再看 $ax+by=c$。左边总是 $\gcd(a,\,b)$ 的倍数，所以 $c$ 不是它的倍数时无解。是倍数时一定有解：把互除法每一步写成「余数＝被除数－商×除数」，从最后一步往回代，就把 $\gcd(a,\,b)$ 写成了 $ax+by$，再乘上倍数即可。

有了一组解 $(x_0,\,y_0)$，任一组解与它相减得 $a(x-x_0)=-b(y-y_0)$。$a$、$b$ 互素时 $b$ 必须整除 $x-x_0$，所以 $x$ 按 $b$ 的倍数跳，$y$ 同时按 $a$ 的倍数反向跳：直线 $ax+by=c$ 上的格点等距排开。

定量表达

互除法写成一串除法：$391=299\times1+92$，$299=92\times3+23$，$92=23\times4$，除尽了，所以 $\gcd(391,\,299)=23$。含字母的式子也能这样除：$3n+5=3(n+1)+2$，所以 $\gcd(3n+5,\,n+1)=\gcd(n+1,\,2)$，$n$ 为奇数时是 $2$，偶数时是 $1$。

求 $37x+16y=1$ 的一组解：$37=16\times2+5$，$16=5\times3+1$。倒推 $1=16-5\times3=16-(37-16\times2)\times3=16\times7-37\times3$，得 $x=-3$，$y=7$。解 $37x+16y=5$ 就乘 $5$，特解 $(-15,\,35)$，相减得 $37(x+15)=-16(y-35)$，互素，所以 $x=16k-15$，$y=-37k+35$。$k$ 换成 $k+1$ 得 $x=16k+1$，$y=-37k-2$，是同一组解，填卡时按题目给的形式对齐。系数不互素先约分：$6x+4y=10$ 化成 $3x+2y=5$ 再做。