初等数论入门 Lesson 9 一次与二次不定方程

一次不定方程

解决：$ax+by=c$

其实就是我们之前学过的拓欧，步骤可以简化如下：

1. 贝祖定理判定存在性
2. 扩欧求特解
3. 通解含参
4. 不等式锁参

本原勾股数组

我们要找出满足 $x^2+y^2=z^2$ 的正整数三元组 $(x,y,z)$

本原的概念（Primitive Pythagorean Triple）：$\gcd(x,y,z)=1$

我们因此能推出几个性质：

1. 性质一：不能同时为偶数

2. 性质二：不能同时为奇数

   我们设 $x=2k+1$，$y=2l+1$，则 $x^2+y^2\equiv 2\pmod 4$，但平方数模4只能余0或1，矛盾

3. 方程代数变形，设 $x$ 为偶数，我们变为：

   $$x^2=z^2-y^2=(z-y)(z+y)$$

   因为 $z,y$ 均为奇数，我们设 $z-y=2u,\;z+y=2v$，则：

   $$x^2=(2u)(2v)=4uv\Rightarrow \left(\frac x 2\right)^2=uv$$

4. 证明 $u,v$ 均是完全平方数

   1. 证：$\gcd(u,v)=1$

      设 $d=\gcd(u,v)$，则有 $d\mid y,\;d\mid z$，但 $\gcd(y,z)=1$ （本原勾股数组定义），故 $d=1$

   2. $uv$ 为完全平方数，故各自只能是完全平方数

5. 我们设 $u=n^2,v=m^2$，有 $\gcd(n,m)=1$

   所以 ：

   • $\dfrac x 2=\sqrt{uv}=mn\Rightarrow x=2mn$
   • $y=m^2-n^2$
   • $z=m^2+n^2$

6. 由奇偶性可得 $m,n$ 必然一奇一偶

综上，所有本原勾股数组均可用上面方法生成

佩尔方程

Pell‘s Equation

标准形式：

$$x^2-Dy^2=1$$

其中 $D$ 不是完全平方数

• 核心定理： 一定存在无穷多解 $(x,y)$

• 最小解：满足 $x+y\sqrt D$ 最小的一组解

• 幂次生成全体解：

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