不定方程

参考资料

• 丢番图方程 - 维基百科
• 佩尔方程 - 维基百科
• 毕达哥拉斯三元组 - 维基百科
• 不定方程 - OI Wiki

引入

不定方程（Diophantine Equation，丢番图方程）是只求 整数解（有时是正整数解）的方程。它通常变量个数多于方程个数，约束不足以「定」住唯一解，所以叫「不定」——但加上「必须是整数」这条苛刻条件后，解的结构反而变得极其丰富。

不定方程和连续情形的反差，是它最迷人的地方。同样是 $x^2+y^2=z^2$，在实数里画出来是一个圆锥面、解多得没法数；可一旦要求整数，解就稀疏而规整，全由一个 参数公式 生成。再比如 $x^n+y^n=z^n$，$n=2$ 时整数解无穷多，$n\ge3$ 时却 一个非平凡解都没有（费马大定理，Wiles 1995）。难度的跳变只在指数上，系数几乎无关紧要。

一次不定方程

二元一次

$$ax+by=c\quad(a,b,c\in\mathbb{Z},\ a,b\text{ 不全为 }0)$$

有解条件：$\gcd(a,b)\mid c$。这正是裴蜀定理（参见 整除与素数）——$ax+by$ 取遍的恰好是 $\gcd(a,b)$ 的所有倍数，所以 $c$ 必须是这个 $\gcd$ 的倍数才可能凑出来。

通解结构

设 $(x_0,y_0)$ 是一个特解，$d=\gcd(a,b)$，则全部整数解为：

$$\begin{cases}x=x_0+\dfrac{b}{d}\,t \\[4pt] y=y_0-\dfrac{a}{d}\,t\end{cases},\quad t\in\mathbb{Z}$$

为什么是这个形式？两个解相减得 $a(x-x_0)+b(y-y_0)=0$，即 $\frac ad(x-x_0)=-\frac bd(y-y_0)$。由于 $\frac ad,\frac bd$ 互素，必有 $\frac bd\mid(x-x_0)$，写成 $x-x_0=\frac bd t$ 便逼出上式。直觉上，所有解在数轴格点上 等间距排成一列，步长 $\bigl(\frac bd,-\frac ad\bigr)$ 是让方程不变的「最小整数平移」。

求特解：扩展欧几里得

先用扩展欧几里得算法求 $ax+by=\gcd(a,b)$ 的一组 $(x',y')$，再把两边同乘 $c/d$：

$$x_0=\frac{c}{d}\,x',\quad y_0=\frac{c}{d}\,y'$$

它与 一次同余方程 $ax\equiv c\pmod b$ 是同一个问题的两种写法。

完整算例：求全部正整数解

例：求 $7x+5y=100$ 的 全部正整数解。

第一步，判可解。$\gcd(7,5)=1\mid 100$，有解。

第二步，求特解。$5\equiv 5,\ 7\equiv 2\pmod 5$，先解 $7x\equiv 100\pmod 5$ 即 $2x\equiv 0\pmod 5$，得 $x\equiv 0\pmod 5$。取 $x_0=0$ 则 $y_0=20$，得一组特解 $(0,20)$（也可肉眼凑：$x=5,y=13$）。

第三步，写通解。$d=1$，$\frac bd=5,\ \frac ad=7$：

$$x=0+5t,\quad y=20-7t,\quad t\in\mathbb{Z}$$

第四步，加正整数约束 $x>0$ 且 $y>0$：

$$x=5t>0\Rightarrow t\ge 1,\qquad y=20-7t>0\Rightarrow t\le\frac{20}{7}<3\Rightarrow t\le 2$$

故 $t\in\set{1,2}$，得两组正整数解：

$$t=1:(x,y)=(5,13),\qquad t=2:(x,y)=(10,6)$$

验算 $7\times 5+5\times 13=35+65=100$、$7\times 10+5\times 6=70+30=100$，均成立。这类「鸡兔同笼 / 凑硬币」的题，套路就是 特解 $\to$ 通解 $\to$ 用正性把 $t$ 框成一段整数区间。

多元一次

$$a_1x_1+a_2x_2+\dots+a_nx_n=c$$

有解条件：$\gcd(a_1,a_2,\dots,a_n)\mid c$。求解可以 逐步合并：先把 $a_1x_1+a_2x_2$ 看成一个新变量 $g_2 t_2$（其中 $g_2=\gcd(a_1,a_2)$），方程降为 $g_2t_2+a_3x_3+\dots=c$，再处理 $g_2$ 与 $a_3$，如此层层归并到二元情形。

勾股数

满足 $x^2+y^2=z^2$ 的正整数三元组 $(x,y,z)$，又称 毕达哥拉斯三元组（Pythagorean Triple）。

本原勾股数

若 $\gcd(x,y,z)=1$（等价地 $x,y$ 互素），称为 本原勾股数。所有本原勾股数都可由两个参数 $(m,n)$ 生成：

$$x=m^2-n^2,\quad y=2mn,\quad z=m^2+n^2$$

要求 $m>n>0$、$\gcd(m,n)=1$、且 $m,n$ 一奇一偶。这三条限制保证生成的三元组本原、且不重复。

例：$(m,n)=(2,1)\Rightarrow(3,4,5)$；$(m,n)=(3,2)\Rightarrow(5,12,13)$；$(m,n)=(4,1)\Rightarrow(15,8,17)$。

例：枚举 $m\le 4$ 的全部合法 $(m,n)$，生成本原勾股数表。合法要求 $m>n>0$、$\gcd(m,n)=1$、$m,n$ 一奇一偶：

$m$	$n$	$x=m^2-n^2$	$y=2mn$	$z=m^2+n^2$	三元组
$2$	$1$	$3$	$4$	$5$	$(3,4,5)$
$3$	$2$	$5$	$12$	$13$	$(5,12,13)$
$4$	$1$	$15$	$8$	$17$	$(15,8,17)$
$4$	$3$	$7$	$24$	$25$	$(7,24,25)$

为什么没有 $(3,1)$？因为 $3,1$ 都是奇数，不满足「一奇一偶」，生成的 $(8,6,10)=2\times(4,3,5)$ 不是本原解。约束的作用正是 滤掉非本原与重复。把表里任一行同乘 $k$，例如 $(3,4,5)\times 2=(6,8,10)$，就得到一般（非本原）勾股数。

tip

这个参数化背后是单位圆上的有理点。把 $x^2+y^2=z^2$ 除以 $z^2$ 得 $\bigl(\frac xz\bigr)^2+\bigl(\frac yz\bigr)^2=1$，于是找勾股数等价于找单位圆上的有理点。从定点 $(-1,0)$ 引一条有理斜率的直线去截圆，另一个交点必是有理点，斜率参数恰好对应 $(m,n)$ 之比。一条「有理斜率扫一遍」就把所有解一网打尽。

一般勾股数

把任一本原勾股数同乘以正整数 $k$，即得所有勾股数。所以本原解是「种子」，整体是它们的整数倍。

佩尔方程

形式：

$$x^2-Dy^2=1\quad(D>0,\ D\text{ 不是完全平方数})$$

这就是 佩尔方程（Pell's Equation）。$D$ 必须非平方，否则左边能因式分解、只有平凡解。

基本解与解的生成

佩尔方程总有无穷多组解，且全部由 一个 最小正整数解 $(x_1,y_1)$（称 基本解）生成：

$$x_n+y_n\sqrt D=\bigl(x_1+y_1\sqrt D\bigr)^n$$

把右边按 $a+b\sqrt D$ 展开，对照系数即得第 $n$ 组解 $(x_n,y_n)$。直觉上，$x+y\sqrt D$ 这种数在乘法下封闭，而「$x^2-Dy^2=1$」恰好说这个数的「范数」为 $1$；范数为 $1$ 的数相乘范数仍为 $1$，所以基本解的幂次源源不断地产出新解。

例：$D=2$ 的基本解是 $(3,2)$，$3^2-2\cdot2^2=1$。但基本解可能大得离谱——$D=61$ 时 $x_1=1\,766\,319\,049$，远超直觉，这也是佩尔方程出名的原因之一。

例：由 $D=2$ 的基本解 $(x_1,y_1)=(3,2)$ 递推生成多组解。有两种等价做法。

其一，乘幂展开：$(x_n+y_n\sqrt 2)=(3+2\sqrt 2)^n$。算 $n=2$：

$$(3+2\sqrt 2)^2=9+12\sqrt 2+8=17+12\sqrt 2\Rightarrow(x_2,y_2)=(17,12)$$

验算 $17^2-2\times 12^2=289-288=1$，对。

其二，线性递推（更适合手算），由 $(x_{n+1}+y_{n+1}\sqrt 2)=(x_n+y_n\sqrt 2)(3+2\sqrt 2)$ 展开对照系数得：

$$x_{n+1}=3x_n+4y_n,\qquad y_{n+1}=2x_n+3y_n$$

从 $(3,2)$ 滚动：

$n$	$x_n$	$y_n$	$x_n^2-2y_n^2$
$1$	$3$	$2$	$1$
$2$	$17$	$12$	$1$
$3$	$99$	$70$	$1$
$4$	$577$	$408$	$1$

例如 $x_3=3\times 17+4\times 12=99$、$y_3=2\times 17+3\times 12=70$，且 $99^2-2\times 70^2=9801-9800=1$。每滚一步范数恒为 $1$，源源不断产出新解。

费马无穷递降法

无穷递降法（Infinite Descent）是费马留给数论的招牌武器，专门用来证明「某方程 没有 正整数解」。

它的逻辑是这样：假设方程有正整数解，就从中取一个「最小」的解，然后通过代数构造，造出一个 更小 的正整数解。但正整数不可能无限变小（没有无穷下降的正整数链），矛盾。于是「有解」的假设被推翻。

最经典的应用是证明 $x^4+y^4=z^2$ 无正整数解（进而推出 $n=4$ 的费马大定理）：从一组解出发，利用勾股数的参数化，能造出一组 $z$ 更小的解，无限递降导致矛盾。这个方法本质上是 最小反例 + 自我繁殖出更小反例 的归谬，思想极简却威力惊人。

算例：证 $x^4+y^4=z^2$ 无正整数解

反设有解，取 $z$ 最小 的一组正整数解，可设 $\gcd(x,y)=1$（否则约去公因子得更小的 $z$，与最小矛盾）。把方程看成勾股数 $(x^2)^2+(y^2)^2=z^2$，$(x^2,y^2,z)$ 是本原勾股数，故存在互素、一奇一偶的 $m>n>0$ 使（不妨设 $y^2$ 为偶）：

$$x^2=m^2-n^2,\quad y^2=2mn,\quad z=m^2+n^2$$

由第一式 $x^2+n^2=m^2$ 又是一组本原勾股数（$\gcd(m,n)=1$ 保证），再参数化：存在互素的 $a>b>0$ 使

$$n=2ab,\quad x=a^2-b^2,\quad m=a^2+b^2$$

代回 $y^2=2mn=2(a^2+b^2)(2ab)=4ab(a^2+b^2)$，即

$$\left(\frac y2\right)^2=ab\,(a^2+b^2)$$

而 $a,b,a^2+b^2$ 两两互素，三个互素的数之积是完全平方，则每个都必是完全平方：

$$a=p^2,\quad b=q^2,\quad a^2+b^2=r^2$$

最后一式给出 $p^4+q^4=r^2$——又一组同型解！而 $r\le r^2=a^2+b^2=m\le m^2<m^2+n^2=z$，新解的 $r$ 严格小于原来的 $z$。这与「$z$ 已是最小」矛盾。于是原方程无正整数解。无穷递降的骨架在此一览无余：由一组解机械地造出 $z$ 更小的同型解，而正整数不能无限下降。

费马大定理

$$x^n+y^n=z^n\quad(n\ge 3)$$

无非平凡整数解（即不存在 $xyz\ne0$ 的整数解）。这就是 费马大定理（Fermat's Last Theorem）。费马于 $1637$ 年在书页边写下它，声称有「绝妙证明但空白太小写不下」，此后困扰数学界 $358$ 年，直到 $1995$ 年 Andrew Wiles 借助椭圆曲线与模形式理论给出完整证明。

tip

费马大定理至今没有已知的「初等证明」。学到这里只需记住结论，并体会它带来的那句心得：整数方程的难度，往往与系数无关，而与指数有关。 费马本人只对 $n=4$ 用无穷递降法给出了证明，欧拉补上 $n=3$，剩下的无穷多个指数花了三个世纪才被一举攻克。

高斯整数与平方和

高斯整数

$\mathbb{Z}[i]=\set{a+bi\mid a,b\in\mathbb{Z}}$ 称为 高斯整数（Gaussian Integer）。它是一个欧几里得整环，同样有带余除法和唯一分解。把数论搬进复平面后，许多实整数的问题（尤其是平方和）会突然变简单——因为 $a^2+b^2=(a+bi)(a-bi)$，平方和被「因式分解」了。

二平方和定理

正整数 $n$ 能表为两个整数的平方和 $\iff$ $n$ 的每个形如 $4k+3$ 的素因子都出现 偶数次。

例：$5=1^2+2^2$ 可以；$3$ 不行（$3\equiv3\pmod4$ 且只出现一次）；$45=9\times5=6^2+3^2$ 可以（$3$ 出现两次）。背后的原因是：$4k+1$ 型素数在高斯整数里能再拆成两个共轭因子，$4k+3$ 型则保持「素」，只有成对出现才拼得回平方和。

四平方和定理

拉格朗日四平方和定理（Lagrange's Four-Square Theorem）：每个正整数都可以表为四个整数的平方和。 两个平方不够（受 $4k+3$ 限制），但放宽到四个，限制就彻底消失，无一例外。

常见构造与技巧

方法	适用情形
代换 + 整除分析	二元低次方程，缩小变量范围
取模筛除	用 $\pmod{p}$ 排除不可能的取值
因式分解	凑成 $(x-a)(y-b)=c$，再枚举 $c$ 的因子
不等式夹逼	用大小关系把变量框在有限范围内枚举
无穷递降	假设有解构造更小的解，导出矛盾
韦达跳跃	视作一元二次，用根与系数关系换出新解

tip

「取模筛除」是性价比最高的第一招：很多方程在某个合适的模下左右两边的取值范围对不上，立刻判定无解。比如 $x^2\equiv0,1\pmod4$，所以 $x^2+y^2$ 模 $4$ 只能是 $0,1,2$，永远凑不出 $3$——这一句话就能毙掉一大批方程。动手解题前，先试几个小模数往往事半功倍。

例（取模筛除）：证 $x^2-3y^2=2$ 无整数解。看模 $3$：右边 $2$，左边 $x^2-3y^2\equiv x^2\pmod 3$。而平方模 $3$ 只能是 $0$ 或 $1$（$0^2\equiv 0,\ 1^2\equiv 1,\ 2^2\equiv 1$），凑不出 $2$，故无解。挑模数的诀窍是 让某个变量项消失——这里 $3y^2$ 在模 $3$ 下自动归零，只剩 $x^2$ 与常数比对。

例（取模筛除）：证 $x^2+y^2+z^2=2024$ 之类时先验模 $8$。平方模 $8$ 只能取 $\set{0,1,4}$，三个这样的数相加，模 $8$ 落在有限集合内；若右边模 $8$ 不在该集合，立判无解。这是「三平方和」问题的常用第一刀。

例（韦达跳跃，Vieta Jumping）：这是把方程视作某个变量的一元二次、用根与系数关系「跳」出新解的技巧。看方程 $x^2-kxy+y^2=1$ 找正整数解。固定 $y$，视作关于 $x$ 的二次方程 $x^2-(ky)x+(y^2-1)=0$。若 $(x,y)$ 是一组解且 $x\ge y$，由韦达定理另一根 $x'=ky-x=\frac{y^2-1}{x}$ 也是整数解，且 $x'=\frac{y^2-1}{x}\le\frac{y^2-1}{y}<y\le x$，得到一组更小的解 $(y,x')$。以 $k=3$ 为例，从 $(x,y)=(2,1)$（验 $4-6+1=-1$，取 $x^2-3xy+y^2=-1$ 一支）出发，跳出 $(5,2),(13,5),(34,13),\dots$——相邻两项满足 $x_{n+1}=3x_n-x_{n-1}$，正是斐波那契的奇数下标项。韦达跳跃既能 向下递降证无解，也能 向上递推生成全部解，看用哪个方向。