裴蜀定理学习笔记

# 裴蜀定理 ## 裴蜀定理的内容 ### 定理1 > 若$a,b$是整数,且$\gcd(a,b)=d$，那么对于任意的整数$x,y,ax+by$都一定是$d$的倍数，特别地，一定存在整数$x,y$，使$ax+by=d$成立。 ### 定理2 > 对于方程$ax+by=1$，只有当整数$a,b$互质时，方程才有整数解。 以上内容摘自[百度百科](https://baike.baidu.com/item/%E8%A3%B4%E8%9C%80%E5%AE%9A%E7%90%86/5186593)。 ## 裴蜀定理的证明 **特此证明：以下证明纯属我自己yy，如有错误请联系我指正。** ### 定理1证明 我们设$ 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证明 我们可以看出，定理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证毕。 ## 裴蜀定理的应用 1. 拓展欧几里得算法 ## 参考文献 1. [裴蜀定理_百度百科](https://baike.baidu.com/item/%E8%A3%B4%E8%9C%80%E5%AE%9A%E7%90%86/5186593) 2. [裴蜀定理_C/C++_a_forever_dream的博客-CSDN博客](https://blog.csdn.net/a_forever_dream/articlehttps://img.qb5200.com/download-x/details/83859354)