丢番图方程

有些问题只有整数解才有意义：你买不了 2.7 只鸡，也无法用三分之一枚硬币付账。丢番图方程就是要求解必须为整数的方程，得名于古希腊数学家丢番图。同一个方程在实数范围内或许有无穷多解，作为整数解却可能只有寥寥几个，甚至一个也没有。

最简单也最重要的情形是关于两个未知数 x 与 y 的线性丢番图方程 a x + b y = c。它有整数解，当且仅当 gcd(a, b) 整除 c。当解存在时，可用扩展欧几里得算法求出一组解，再让 x 与 y 以与 b、a 相关的步长朝相反方向滑动，从而生成其余全部解。

超出线性情形，难度便陡然爆发。像 3、4、5 这样的勾股数满足整数方程 x^2 + y^2 = z^2，但费马的论断 — 当 n 大于 2 时 x^n + y^n = z^n 没有正整数解 — 悬而未决长达三百五十多年。一般而言，并不存在一种统一的方法能判定任意丢番图方程是否有整数解，这一事实本身就是一条著名的定理。