裴蜀定理

1 内容：

2 设 $a,b$ 是不全为零的整数，则存在整数 $x,y$, 使得 $ax+by=gcd(a,b)$.

2.1 证明：

设取 $x_0$, $y_0$ 时，$ax+by$ 的最小整数是 $s$.即 $a{x}_0+b{y}_0$ = $s$

因 $gcd(a,b)|a{x}_0$ ， $gcd(a,b)|a{y}_0$

所以 $gcd(a,b)|s$ $.........(1)$

设 $a=qs+r(0\le r\le s)$

$r=a-qs=a-q(a{x}_0+b{y}_0)=a(1-q{x}_0)+b(-q{y}_0)=ax+by$

因为 $s$ 是最小整数，$\Rightarrow r=0$

所以 $s|a$,同理 $s|b$

$\Rightarrow s|gcd(a,b)$ $..........(2)$

由 $(1)(2)$ 可得 $s=gcd(a,b)$.

证毕。

3 逆定理：

设 $a,b$ 是不全为零的整数，若 $d>0$ 是 $a,b$ 的公因数，且存在整数$x,y$, 使得 $ax+by=d$，则 $d=gcd(a,b)$。

特殊地，设 $a,b$ 是不全为零的整数，若存在整数 $x,y$, 使得 $ax+by=1$，则 $a,b$ 互质。

4 进一步结论:

对自然数 $a$、$b$ 和整数 $n$，$a$ 与 $b$ 互素，考察不定方程：
$ax+by=n$
其中 $x$ 和 $y$ 为自然数。如果方程有解，称 $n$ 可以被 $a$、$b$ 表示。

记 $C=ab-a-b$。由 $a$ 与 $b$ 互素，$C$ 必然为奇数。则有结论：

对任意的整数 $n$，$n$ 与 $C-n$中有且仅有一个可以被表示。

即：可表示的数与不可表示的数在区间 $[0,C]$ 对称（关于 $C$ 的一半对称）。$0$ 可被表示，$C$ 不可被表示；负数不可被表示，大于 $C$ 的数可被表示。

例如在 $luoguP3951$ 就只是为了求 $ab-a-b$ 的值