不定方程

不定方程Summary参考资料​

丢番图方程 - 维基百科

佩尔方程 - 维基百科

毕达哥拉斯三元组 - 维基百科

不定方程 - OI Wiki

引入​

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

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

一次不定方程​

二元一次​

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

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

通解结构​

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

{x=x0+bdty=y0−adt,t∈Z\begin{cases}

x=x_0+\dfrac{b}{d}t \\[4pt]

y=y_0-\dfrac{a}{d}t

\end{cases},t\in\mathbb{Z}⎩⎨⎧​x=x0​+db​ty=y0​−da​t​,t∈Z

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

求特解：扩展欧几里得​

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

x0=cdx′,y0=cdy′x_0=\frac{c}{d}x',y_0=\frac{c}{d}y'x0​=dc​x′,y0​=dc​y′

它与 一次同余方程 ax≡c(modb)ax\equiv c\pmod bax≡c(modb) 是同一个问题的两种写法。

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

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

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

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

第三步，写通解。d=1d=1d=1，bd=5,ad=7\frac{b}{d}=5,\frac{a}{d}=7db​=5,da​=7：

x=0+5t,y=20−7t,t∈Zx=0+5t,y=20-7t,t\in\mathbb{Z}x=0+5t,y=20−7t,t∈Z

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

x=5t>0 ⟹ t≥1,y=20−7t>0 ⟹ t≤207<3 ⟹ t≤2x=5t>0\implies t\ge 1,y=20-7t>0\implies t\le\frac{20}{7}<3\implies t\le 2x=5t>0⟹t≥1,y=20−7t>0⟹t≤720​<3⟹t≤2

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

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

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

多元一次​

a1x1+a2x2+⋯+anxn=ca_1x_1+a_2x_2+\dots+a_nx_n=ca1​x1​+a2​x2​+⋯+an​xn​=c

有解条件：gcd⁡(a1,a2,…,an)∣c\gcd(a_1,a_2,\dots,a_n)\mid cgcd(a1​,a2​,…,an​)∣c。求解可以 逐步合并：先把 a1x1+a2x2a_1x_1+a_2x_2a1​x1​+a2​x2​ 看成一个新变量 g2t2g_2 t_2g2​t2​（其中 g2=gcd⁡(a1,a2)g_2=\gcd(a_1,a_2)g2​=gcd(a1​,a2​)），方程降为 g2t2+a3x3+⋯=cg_2t_2+a_3x_3+\dots=cg2​t2​+a3​x3​+⋯=c，再处理 g2g_2g2​ 与 a3a_3a3​，如此层层归并到二元情形。

勾股数​

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

本原勾股数​

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

x=m2−n2,y=2mn,z=m2+n2x=m^2-n^2,y=2mn,z=m^2+n^2x=m2−n2,y=2mn,z=m2+n2

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

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

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

mmmnnnx=m2−n2x=m^2-n^2x=m2−n2y=2mny=2mny=2mnz=m2+n2z=m^2+n^2z=m2+n2三元组222111333444555(3,4,5)(3,4,5)(3,4,5)333222555121212131313(5,12,13)(5,12,13)(5,12,13)444111151515888171717(15,8,17)(15,8,17)(15,8,17)444333777242424252525(7,24,25)(7,24,25)(7,24,25)

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

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

一般勾股数​

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

佩尔方程​

形式：

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

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

基本解与解的生成​

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

xn+ynD=(x1+y1D)nx_n+y_n\sqrt D=\bigl(x_1+y_1\sqrt D\bigr)^nxn​+yn​D​=(x1​+y1​D​)n

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

例：D=2D=2D=2 的基本解是 (3,2)(3,2)(3,2)，32−2⋅22=13^2-2\cdot2^2=132−2⋅22=1。但基本解可能大得离谱——D=61D=61D=61 时 x1=1766319049x_1=1766319049x1​=1766319049，远超直觉，这也是佩尔方程出名的原因之一。

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

其一，乘幂展开：(xn+yn2)=(3+22)n(x_n+y_n\sqrt 2)=(3+2\sqrt 2)^n(xn​+yn​2​)=(3+22​)n。算 n=2n=2n=2：

(3+22)2=9+122+8=17+122 ⟹ (x2,y2)=(17,12)(3+2\sqrt 2)^2=9+12\sqrt 2+8=17+12\sqrt 2\implies(x_2,y_2)=(17,12)(3+22​)2=9+122​+8=17+122​⟹(x2​,y2​)=(17,12)

验算 172−2×122=289−288=117^2-2\times 12^2=289-288=1172−2×122=289−288=1，对。

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

xn+1=3xn+4yn,yn+1=2xn+3ynx_{n+1}=3x_n+4y_n,y_{n+1}=2x_n+3y_nxn+1​=3xn​+4yn​,yn+1​=2xn​+3yn​

从 (3,2)(3,2)(3,2) 滚动：

nnnxnx_nxn​yny_nyn​xn2−2yn2x_n^2-2y_n^2xn2​−2yn2​111333222111222171717121212111333999999707070111444577577577408408408111

例如 x3=3×17+4×12=99x_3=3\times 17+4\times 12=99x3​=3×17+4×12=99、y3=2×17+3×12=70y_3=2\times 17+3\times 12=70y3​=2×17+3×12=70，且 992−2×702=9801−9800=199^2-2\times 70^2=9801-9800=1992−2×702=9801−9800=1。每滚一步范数恒为 111，源源不断产出新解。

费马无穷递降法​

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

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

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

算例：证 x4+y4=z2x^4+y^4=z^2x4+y4=z2 无正整数解​

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

x2=m2−n2,y2=2mn,z=m2+n2x^2=m^2-n^2,y^2=2mn,z=m^2+n^2x2=m2−n2,y2=2mn,z=m2+n2

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

n=2ab,x=a2−b2,m=a2+b2n=2ab,x=a^2-b^2,m=a^2+b^2n=2ab,x=a2−b2,m=a2+b2

代回 y2=2mn=2(a2+b2)(2ab)=4ab(a2+b2)y^2=2mn=2(a^2+b^2)(2ab)=4ab(a^2+b^2)y2=2mn=2(a2+b2)(2ab)=4ab(a2+b2)，即：

(y2)2=ab(a2+b2)\left(\frac{y}{2}\right)^2=ab(a^2+b^2)(2y​)2=ab(a2+b2)

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

a=p2,b=q2,a2+b2=r2a=p^2,b=q^2,a^2+b^2=r^2a=p2,b=q2,a2+b2=r2

最后一式给出 p4+q4=r2p^4+q^4=r^2p4+q4=r2——又一组同型解！而 r≤r2=a2+b2=m≤m2

费马大定理​

xn+yn=zn(n≥3)x^n+y^n=z^n(n\ge 3)xn+yn=zn(n≥3)

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

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

高斯整数与平方和​

高斯整数​

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

二平方和定理​

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

例：5=12+225=1^2+2^25=12+22 可以；333 不行（3≡3(mod4)3\equiv3\pmod43≡3(mod4) 且只出现一次）；45=9×5=62+3245=9\times5=6^2+3^245=9×5=62+32 可以（333 出现两次）。背后的原因是：4k+14k+14k+1 型素数在高斯整数里能再拆成两个共轭因子，4k+34k+34k+3 型则保持「素」，只有成对出现才拼得回平方和。

四平方和定理​

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

常见构造与技巧​

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

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

例（取模筛除）：证 x2−3y2=2x^2-3y^2=2x2−3y2=2 无整数解。看模 333：右边 222，左边 x2−3y2≡x2(mod3)x^2-3y^2\equiv x^2\pmod 3x2−3y2≡x2(mod3)。而平方模 333 只能是 000 或 111（02≡0,12≡1,22≡10^2\equiv 0,1^2\equiv 1,2^2\equiv 102≡0,12≡1,22≡1），凑不出 222，故无解。挑模数的诀窍是 让某个变量项消失——这里 3y23y^23y2 在模 333 下自动归零，只剩 x2x^2x2 与常数比对。

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

例（韦达跳跃，Vieta Jumping）：这是把方程视作某个变量的一元二次、用根与系数关系「跳」出新解的技巧。看方程 x2−kxy+y2=1x^2-kxy+y^2=1x2−kxy+y2=1 找正整数解。固定 yyy，视作关于 xxx 的二次方程 x2−(ky)x+(y2−1)=0x^2-(ky)x+(y^2-1)=0x2−(ky)x+(y2−1)=0。若 (x,y)(x,y)(x,y) 是一组解且 x≥yx\ge yx≥y，由韦达定理另一根 x′=ky−x=y2−1xx'=ky-x=\frac{y^2-1}{x}x′=ky−x=xy2−1​ 也是整数解，且 x′=y2−1x≤y2−1y