裴蜀定理

裴蜀定理的内容

若$a,b$是整数,且$\gcd(a,b)=d$，那么对于任意的整数$x,y,ax+by$都一定是$d$的倍数，特别地，一定存在整数$x,y$，使$ax+by=d$成立。

对于方程$ax+by=1$，只有当整数$a,b$互质时，方程才有整数解。

以上内容摘自百度百科。

特此说明：以下证明纯属我自己yy，如有错误请联系我指正。

我们设$ d=\gcd(a,b) $，则显而易见，$d \mid a$，且$d \mid b$。

根据整除的性质，我们得出$ d \mid ax+by ( x,y \in Z ) $。······（式1.2.1.1）

所以根据（式1.2.1.1）以及整除的意义得出$ ax+by=dk ( k \in Z^+ ) $。

当$k=1$时，则$ax+by=d$。

根据（式1.2.1.1），我们还可以得出$d \mid x$，且$d \mid y$。

至此，定理1证毕。

我们可以看出，定理2就是定理1的特殊情况，即$d=1$时的情况。

我们可以利用反证法证明。

首先我们假设$a,b$不互质，即$\gcd(a,b) \not = 1$。······（命题1.2.2.1）

也就是$d \not = 1$。······（式1.2.2.2）

根据定理1，$ax+by=d$。

在定理2中，这个式子是$ax+by=1$。

可得$d=1$。······（式1.2.2.3）

所以，（式1.2.2.2）与（式1.2.2.3）矛盾，所以（命题1.2.2.1）为伪命题。

至此，定理2证毕。