3.素数和最大公因子

4. 欧几里得算法

7. 线性丢然图方程

设 \(a,b\) 是整数，且 \(d=(a,b)\)

1. 若 \(d\nmid c\)，那么 \(ax+by=c\) 没有整数解
2. 若 \(d\mid c\)，那么存在无穷多个整数解
3. 此为，若 \(x=x_0,y=y_0\) 是方程的一个特解，那么通解为 \(x=x_0+(b/d)n,y=y_0-(a/d)n\)

假设整数 \(x,y\) 满足 \(ax+by=c\)，那么由于 \(d|a,d|b\) 和[定理1.9]有 \(d|c\)；反之若 \(d\nmid c\)，那么方程不存在整数解

现在假设 \(d|c\)，由[定理3.9]，存在整数 \(s,t\) 使得 \(d=as+bt\)（1）

由 \(d|c\)，存在 e 使得 \(ed=c\)

将（1）同时乘以 e 有 \(ed=a(se)+b(te)\)，于是 \(c=a(se)+b(te)\)

因此 \(x=x_0=se,y=y_0=te\) 是方程的一个解

证明方程有无穷多个解，需要证明两件事情：

1. 证明：\(ax+by=c\) 的解形如 \(x=x_0+(b/d)n,y=y_0-(a/d)n\)
2. 证明：\(x=x_0+(b/d)n,y=y_0-(a/d)n\) 是方程 \(ax+by=c\) 的解

1) 假设 \((x_0,y_0),(x,y)\) 分别 \(ax+by=c\) 的特解和通解，即分别有 \(ax_0+by_0=c\)，\(ax+by=c\)

上两式相减有 \(a(x-x_0)+b(y-y_0)=0\) （1）

那么 \((a/d)(x-x_0)+(b/d)(y-y_0)=0\) 或 \((a/d)(x-x_0)=(b/d)(y_0-y)\)

根据[引理3.4]和 \((a/d,b/d)=1\) 有 \((a/d)|(y_0-y)\) 和 \((b/d)|(x-x_0)\)，于是存在整数 u 和 v 使得 \(u(a/d)=y_0-y\) 和 \(v(b/d)=x-x_0\) （2）

（注：[定理3.6] 有，若 \((a,b)=d\)，那么 \((a/d,b/d)=1\)）

联立（1）和（2）有 \(av(b/d)-bu(a/d)=0\)，于是 \(u=v\)

化简（2）：\(x=x_0+(b/d)n\)，\(y=y_0-(a/d)n\)（令 \(n=u=v\)）

2）\(ax+by=a[x_0+(b/d)n]+b[y_0-(a/d)n]=ax_0+by_0=c\)

\(\blacksquare\)

若 \(a_1,\dots,a_n\) 是正整数，那么方程 \(\sum\limits_{i=1}^na_ix_i=c\) 有正整数解，

当且仅当 \(d=(a_1,\dots,a_n)\) 能整除 c，即 \((a_1,\dots,a_n)|c\)

另外，当存在一个解时，那么方程有无穷多个解

证明：

(1) 若 \(n=2\)，命题成立

(2) 若 \(n\ge 3\)，

根据[定理3.9] \(a_nx_n+a_{n+1}x_{n+1}\) 所构成的集合与 \((a_n,a_{n+1})\) 的倍数构成的集合相同，

因此，对于所有整数 y，\(a_nx_n+a_{n+1}x_{n+1}=(a_n,a_{n+1})y\) 有无穷多个解

那么 \(\sum\limits_{i=1}^{n+1}a_ix_i=c\) 等价于 \(\sum\limits_{i=1}^{n-1}a_ix_i+(a_n,a_{n+1})y=c\)

由[引理3.2]，\((a_1,\dots,a_{n+1})=(a_1,\dots,a_{n-1},(a_n,a_{n+1}))\)，

注意到 \((a_1,\dots,a_{n-1},(a_n,a_{n+1}))|c\)

\(\blacksquare\)