裴蜀（贝祖）定理

letianJOE · 2024-01-30 17:25:53 · 个人记录

先学习前置知识 GDC&LCM，戳这里

定理

有 a,b \in \mathbb{Z}，那么一定有整数 x,y 使得 ax+by=\gcd(a,b)

如果方程

ax+by=c

有整数解，那么方程满足

\gcd(a,b) \mid c

否则方程无整数解

由定理1推出。

如果

ax+by=1

有整数解，那么

\gcd(a,b)=1

也就是 a,b 互质。

根据辗转相除法的过程判断即可，证明不难但是很长。

由于 \gcd(a,b) 是 a,b 的因子，所以可得

代入方程可得 $p \times \gcd(a,b) \times x+q \times \gcd(a,b) \times y=c

如果 x,y 是整数的话，那么

根据这个式子可得 $\gcd(a,b) \mid c$。反之 $x,y$ 不为整数的话 $\gcd(a,b) \nmid c

得证

由于 \gcd(a,b) 是 a,b 的因子，所以可得

代入方程可得 $p \times \gcd(a,b) \times x+q \times \gcd(a,b) \times y=1

如果两边同除一个 \gcd(a,b)，那么方程不变，也就是

px+qy=\frac{1}{\gcd(a,b)}

根据这个式子，如果 a,b 不互质，那么

\gcd(a,b)>1

那么方程左边为整数，右边为小数。方程没有整数解。

否则方程有整数解。

模板题