数论：不定方程的引入

研究的对象：不定方程

不定方程引入：

不定方程，又称丢番图方程，定义为：未知数为整数，系数也为整数的多项式等式。

形如$a_1{x}_1^{b_1}+a_2{x}_2^{b_2}+...+a_n{x}_n^{b_n}=c$

如果我们能找到一组整数解：$x_1,x_2,...,x_n$，我们就说这个方程有解。

但是我们并不研究不定方程的一般式，而是研究其特殊的形式，即一次不定方程：

$a_1{x}_1+a_2{x}_2+...+a_n{x}_n=c$​

这个一次不定方程有解的充要条件是：

$gcd(a_1,a_2,..,a_m)|c$ （即c为这n个数的倍数的时候，该一次不定方程有解）

这个推论是由二元一次不定方程有解的情况归纳而来：

即：
对于二元一次不定方程：$ax+by=c$

此方程有解的充要条件是 : $gcd(a,b)|c$

这个结论是裴蜀定理的证明：下面将引出裴蜀定理。

裴蜀定理与不定方程的解有什么关系？？

裴蜀定理给出：

对于任何整数$a，b，m$，关于未知数$x,y$ 的一元二次不定方程$ax+by=m$​

此方程有解的充要条件是 $gcd(a,b)|m$​，由于只给了一个不定方程，所以整数解有无穷多个，每一组(x,y)都被称为裴蜀数。

裴蜀定理证明：

由于是任意整数$a,b$

所以我们先考虑0的情况：

1、当 $a=0$

该不定方程为：$by=m$ , 此方程有整数解，当且仅当 $b|m$​ 。

可以写成$gcd(0,b)|m$

写到这里突然有个想法，$gcd(0,b)$​ 这样的写法是合法的吗？

公约数的定义：如果有一个数$d$, 对于$a_1,a_2,a_3,...,a_n$，都有$d|a_i,i\in [1,n]$

这样的数就被称为这些数的公约数。

将$a_1,a_2,a_3,...,a_n$的所有公约数放入集合$D$中， D = { d ; d ∣ ( a 1 , a 2 , a 3 , . . . a n ) } D=\lbrace d;d|(a_1,a_2,a_3,...a_n)\rbrace D={d;d∣(a1​,a2​,a3​,...an​)}

最大公约数gcd的定义是：$d_{max}\in D$，使得$\forall d|d_{max}$，其中$d_{max}$被称为$gcd$。

$0$能被任意非$0$数整除，$b$最大只能被$b$整除。

当只要求$2$个整数的最大公约数的时候，有一方为$0$，那么它们的最大公因数就是另一个非零数本身。

都讲到这里了，顺便在写一下欧几里得算法的证明：

欧几里得算法证明：

考虑 $gcd(a,b)=gcd(b,amodb)$ 的证明：（面向结果证明）

任意一个整数可以写成带余除法（因为要用到$amodb$ 的形式，所以将$a$写成关于$b$的带余除法：$a=kb+c$ , $c=amodb$ 并约定$(b\ne 0)$。

设 $d$ 是$a,b$的最大公约数。

有：$d|a,d|b$。​

两边同时除以d：$\frac{a}{d}=k\frac{b}{d}+\frac{c}{d}$。

由于 $\frac{a}{d},\frac{b}{d}$都是整数，所以$\frac{c}{d}$也是一个整数。

这说明$d|c$ , 这说明 $d$ 是$(a,b,c)$​的最大公约数。

所以得到了最终的转移式子：$gcd(a,b)=gcd(b,c)$

这个证明过程告诉我们，不要忽视整数这个性质

2、当$b=0$ 的时候，这与$a=0$ 的计算过程等价，结论也等价，所以不过多赘述。

3、下面讨论 $a\ne 0,b\ne 0$ 的情况：

再次重申我们要证明的是什么？（有时候写着写着忘记要干嘛了）

证明：$ax+by=c$ 有整数解$(x,y)\iff gcd(a,b)|c$

充分性证明：

证明充分性，即证明：$ax+by=c\Rightarrow gcd(a,b)|c$​

假设$ax+by=c$有解。

设 A = { a x + b y ; ( x , y ) ∈ Z 2 } A = \lbrace ax+by ; (x,y)\in \Z^2 \rbrace A={ax+by;(x,y)∈Z2}​ ​

不妨设$c_0$为$A$的最小正整数元素：$a{x}_0+b{y}_0=c$，其中$c$表示A的任意一个正整数元素：$ax+by=c$。

作$c$对$c_0$的带余除法：$c=q{c}_0+r$ ，$0\le r<c_0$

代入原式：$ax+by=q(a{x}_0+b{y}_0)+r$​

$r=a(x-q{x}_0)+b(y-q{y}_0)$ ，显然满足$r\in A$

$\because$ $0\le r<c_0$ ，而$c_0$是$A$中的最小正元素。

$\therefore$ $r$ 不是正元素， 即$r=0$，所以$c$对$c_0$的带余除法为：$c=q{c}_0$

也就是说$A$中任意一个正元素$c$，都存在$c_0|c$。

$\because ax+by=c，\forall c\in A,c_0|c$

$\therefore$ , $c_0|ax$ , $c_0|by$

$\because x,y\in \mathbb{Z}$

$\therefore c_0|a,c_0|b$ 即 $c$ 是$a,b$​​的公约数。

这是一个关键的进展！

接下来，我们只要证明 $gcd(a,b)=c_0$

就能得到：$gcd(a,b)|c$

设$d$为$a,b$的任意正公约数，$a=kd,b=ld$​。

$ax+by=kdx+ldy=(kx+ly)d=c_0$​

$\therefore d|c_0$

$\therefore gcd(a,b)=c_0$

$\therefore \forall a,b,c\in \mathbb{Z},ax+by=c$ 有解 $\Rightarrow gcd(a,b)|c$

充分性证毕

必要性证明：

证明当$gcd(a,b)|c$的时候，$ax+by=c$ 有解：

这个问题等价于证明：当$gcd(a,b)=c_0$时，$ax+by=c_0$有解：

设$d=gcd(a,b)$

等式两边同时除以$d$，等式就被转换为：$a^{\prime }x+b^{\prime }y=1$ 其中 $gcd(a^{\prime },b^{\prime })=1$​

问题就转化为证明这个等式成立：$a^{\prime }x+b^{\prime }y=1$。

这个求解的过程可以由欧几里得算法顺带求出。

令$a^{\prime }=a,b^{\prime }=b$

模拟求$gcd(a,b)$的过程：

$a=k_{1}b+r_1$

$\Rightarrow a=b,b=r_1$

$b=k_2{r}_1+r_2$

$r_1=k_3{r}_2+r_3$

$...$​

$r_{n-1}=k_{n+1}{r}_n+r_{n+1}...(3)$

$r_n=k_{n+2}{r}_{n+1}+r_{n+2}....(2)$​

$r_{n+1}=k_{n+3}{r}_{n+2}...(1)$​​

$gcd=r_{n+2}$

欧几里得算法在$r=0$​的时候停止，并返回$b$，也就是$(1)$式子

所以，可以得到$r_{n+2}=1$

$r_n=k_{n+2}{r}_{n+1}+\mathrm{1...}(2)$

联立$(2),(3)$消去$r_{n+1}$：

$$\{\begin{array}{l}{k}_{n+2}{r}_{n+1}=1-r_n\\ k_{n+2}{r}_{n+1}=k_{n+2}{r}_{n-1}-k_{n+1}{k}_{n+2}{r}_n\end{array}$$

得：

$$(k_{n+2}{k}_{n+1}-1)r_n+1=k_{n+2}{r}_{n-1}...(1^{\prime })$$

联立$(1^{\prime }),(3)$消去$r_n$：

$$\{\begin{array}{l}{r}_{n-2}=k_n{r}_{n-1}+r_n\\ (k_{n+2}{k}_{n+1}-1)r_n+1=k_{n+2}{r}_{n-1}\end{array}$$
得：
$$(k_{n+2}{k}_{n+1}-1)r_{n-2}+1=(k_{n+2}{k}_{n+1}{k}_n-k_n+k_{n+2})r_{n-1}...(2^{\prime })$$
我们观察式子的结构不难发现：

这个式子只包含$r_i,r_{i-1}$这两个已知量，以及常数1，以及$r_i,r_{i-1}$前面的系数。

所以，我们可以通过不断的消去$r_i$，使得最终的式子只包含$(a,b,k)$。

最终的形式一定可以化简：$ax+by=1$。​

必要性证毕。

战术总结：

本节内容的主要内容如下：

1、不定方程的简单介绍。

2、裴蜀定理介绍。

3、裴蜀定理的证明：

• 先证明充分性：

  • 假定$ax+by=c$有解，证出$\forall c\in A,c_0|c$，进而得出$c_0|a,c_0|b$，即$c_0$是$a,b$的公约数
  • 接着证明$a,b$的任意约数$d$，都有$d|c_0$，得出$c_0$是$a,b$的最大公约数。
  • 此时证出：若$ax+by=c_0$有解，则$c_0=gcd(a,b)$
  • 在等式两边乘以任意整数可得：若$ax+by=c$有解，则$gcd(a,b)|c$

• 再证明必要性：

  • 即证明当$c_0=gcd(a,b)$的时候，是否$ax+by=c_0$成立
  • 两边除以$c_0$，问题便转为证明：当$gcd(a,b)=1$ 时，$a^{\prime }x+b^{\prime }y=1$成立。
  • 这个等式由欧几里得算法可以得出是有解的。