跳到主要内容

不定方程

参考资料​

引入​

不定方程（丢番图方程）是只求 整数解 的方程。变量个数大于方程个数，所以「不定」。

它的解结构往往与连续情形截然不同——例如 x2+y2=z2x^2+y^2=z^2 有无穷多组整数解（勾股数），而 xn+yn=znx^n+y^n=z^n（n≥3n\ge 3）的非平凡整数解不存在（费马大定理，Wiles 1995）。

一次不定方程​

二元一次​

ax+by=c(a,b,c∈Z)ax+by=c\quad(a,b,c\in\mathbb{Z})

有解条件：gcd⁡(a,b)∣c\gcd(a,b)\mid c（裴蜀定理，参见 整除与素数）。

通解结构​

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

{x=x0+bdty=y0−adt,t∈Z\begin{cases}x=x_0+\dfrac{b}{d}t \\ y=y_0-\dfrac{a}{d}t\end{cases},\quad t\in\mathbb{Z}

求特解：扩展欧几里得​

求 ax+by=gcd⁡(a,b)ax+by=\gcd(a,b) 的一组 (x′,y′)(x',y')，然后两边乘 c/gcd⁡(a,b)c/\gcd(a,b)：

x0=cgcd⁡(a,b)x′,y0=cgcd⁡(a,b)y′x_0=\frac{c}{\gcd(a,b)}x',\quad y_0=\frac{c}{\gcd(a,b)}y'

多元一次​

a1x1+a2x2+⋯+anxn=ca_1x_1+a_2x_2+\dots+a_nx_n=c

有解条件：gcd⁡(a1,a2,…,an)∣c\gcd(a_1,a_2,\dots,a_n)\mid c。可逐步合并：先解 a1x1+a2x2=ta_1x_1+a_2x_2=t，再处理 t+a3x3+⋯=ct+a_3x_3+\dots=c。

勾股数​

满足 x2+y2=z2x^2+y^2=z^2 的正整数三元组 (x,y,z)(x,y,z)。

本原勾股数​

gcd⁡(x,y,z)=1\gcd(x,y,z)=1 的勾股数。所有本原勾股数可由参数 (m,n)(m,n) 给出：

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

要求 m>n>0m>n>0、gcd⁡(m,n)=1\gcd(m,n)=1、m,nm,n 一奇一偶。

例：(m,n)=(2,1)⇒(3,4,5)(m,n)=(2,1)\Rightarrow(3,4,5)；(m,n)=(3,2)⇒(5,12,13)(m,n)=(3,2)\Rightarrow(5,12,13)。

一般勾股数​

把本原勾股数同乘以正整数 kk 即得所有勾股数。

佩尔方程​

形式：

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

基本解​

存在最小的正整数解 (x1,y1)(x_1,y_1)，称为 基本解。所有解由它生成：

xn+ynD=(x1+y1D)nx_n+y_n\sqrt D=(x_1+y_1\sqrt D)^n

例​

D=2D=2 时，基本解 (3,2)(3,2)：32−2⋅22=13^2-2\cdot 2^2=1。

D=61D=61 时，基本解 x1=1766319049x_1=1766319049，比一般直觉大得多。

高斯整数与平方和​

高斯整数​

Z[i]={ a+bi∣a,b∈Z }\mathbb{Z}[i]=\set{a+bi\mid a,b\in\mathbb{Z}}。它是欧几里得整环，可做唯一分解。

二平方和定理​

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

例：5=12+225=1^2+2^2；33 不行（3≡3(mod4)3\equiv 3\pmod 4 出现一次）。

四平方和定理（拉格朗日）​

每个正整数都可以表为四个整数的平方和。

费马大定理​

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

无非平凡整数解。费马在 1637 年提出，Andrew Wiles 在 1995 年借助椭圆曲线与模形式理论给出完整证明。

提示

费马大定理本身没有「初等证明」（已知）。学到这里只需知道结论，并体会一句话：整数方程的难度，往往与系数无关，而与指数有关。

解题套路​

方法适用情形
代换 + 整除分析二元低次方程，缩小变量范围
取模筛除用 (modp)\pmod{p} 排除某些可能
无穷下降法假设有解构造更小的解，矛盾（费马常用）
单变量分离化为 y=f(x)y=f(x) 判断何时取整数
构造 / 因式分解如 x2−y2=(x−y)(x+y)x^2-y^2=(x-y)(x+y)
Example

求 x2+y2=xy+5x^2+y^2=xy+5 的整数解。

变形：x2−xy+y2=5⇒(2x−y)2+3y2=20x^2-xy+y^2=5\Rightarrow (2x-y)^2+3y^2=20。

由 3y2≤203y^2\le 20 得 ∣y∣≤2|y|\le 2，逐个枚举 y=−2,−1,0,1,2y=-2,-1,0,1,2 验证即可。