同余：拓展欧几里得定理

0x22 拓展欧几里德

0x22.1 裴蜀（Bézout）定理(用于求解“不定方程”的相关问题)

内容：设 a , b是不全为零的整数 ，对于任意整数 x , y ，满足 $gcd ⁡ ( a , b)| (ax+by)$ ，且存在整数x，y使得： $a x + b y = gcd ⁡ ( a , b )$

推论1：(感觉不像推论)

$\gcd(a,b)\mid c⟺∃x,y∈Z,ax+by=c$

方程$ ax+by=d(d=gcd(a,b)) $即为丢番图方程。

• 逆定理推论

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

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

推论2：$\forall a,b,z\in\mathbb{N^{*}},\gcd(a,b)=1\\\exists x,y\in\mathbb{N^{}} ,ax+by=ab−a−b+z$

即两互质的数 a , b，表示不出的最大的数为ab−a−b。

推论2 进一步的结论：

对自然数 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 的数可被表示。