裴枢定理及其证明 - I. 裴枢定理

对于 $x,y$ 的二元一次不定方程 $ax+by=c$ ，其有解的充要条件为 $\gcd (a,b)\mid c$

1.充分性证明

充分性：若 $\gcd (a,b)\mid c$ ，则 $ax+by=c$ 有解

设 $k$ 为 $a,b$ 线性组合的最小非负解

令 $q=\lfloor \frac{a}{k}\rfloor$ ，则有 $r=a\mathrm{m}\mathrm{o}\mathrm{d}k=a-qk=a-q(ax+by)=a(1-qx)+b(-qy)$

显然 $r$ 也为 $a,b$ 线性组合的解，且 $0\le r\le k$

$\because k$ 为最小非负解

$\therefore r=0$

$\therefore k\mid a$

同理 $k\mid b$

令 $d=\gcd (a,b)$ ，则 $s\mid d$ 且 $d\ge s$

$\because d\mid a,d\mid b$ 且 $s$ 为 $a,b$ 线性组合的解

$\therefore d\mid s$

$\because s>0$

$\therefore d=s$

则 $ax+by=c$ 的最小非负解为 $\gcd (a,b)$

显然 $\forall c=k\gcd (a,b),k\in {\mathbb{Z}}^{+}$ 是原方程的解

2.必要性证明

必要性：若 $ax+by=c$ 有解，则 $\gcd (a,b)\mid c$
证明：
令 $d=\gcd (a,b)$ ，则 $d\mid a,d\mid b$

$\because ax+by=c$ 有解

$\therefore d\mid ax,d\mid by$

$\therefore d\mid ax+by=c$

3.推广

对于不定方程 $x_1{y}_1+x_2{y}_2+...+x_n{y}_n=k,\forall y_i\in \mathbb{Z}$ ，其有解的充要条件为 gcd ⁡ { x i } ∣ k \gcd\{x_i\}\mid k gcd{xi​}∣k

证明略

---