引入:
1.背景:在数论中,裴蜀定理是一个关于最大公约数(或最大公约数)的定理,是法国数学家Bézout’s Lemma,又称贝祖定理。
2.(1) Z={…-3,-2,-1,0,1,2,3…}
(2) 2Z={…-6,-4,-2,0,2,4,6…}
(3) 3Z={…-9,-6,-3,0,3,6,9…}
(4) 4Z={…-12,-8,-4,0,4,8,12…}
(5) 2Z+3Z={…-3,-2,-1,0,1,2,3…}(发现等于Z)
(6) 2Z+4Z={…-6,-4,-2,0,2,4,6…}(发现等于2z)
同时发现(5)、(6)中1,2最小正整数分别是2、3的最大公约数;2、4的最大公约数,而且其他数都是这个数的倍数。
一、贝祖定理
1.若a,b为整数,且记G=gcd(a,b),那么对于任意的整数x,y,总有ax+by事G的倍数(显然成立)。
证明:a=nG, b=mG
ax+by=nGx+mGy=G(nx+my)
所以G|(ax+by)
即:G是ax+by的约数
ax+by是G的倍数
2.对于任意两个不全为0的整数a,b,一定存在两个不全为0的整数x,y(可能是负整数),使ax+by=gcd(a,b)
证明:设G为a,b的最大公约数,由1可知:
结论(1) G是ax+by的约数
ax+by是G的倍数
设s为a,b线性组合的最小正值,即:
ax+by=s,s为最小正值。
同理:
3.对于任意整数a,b,存在整数解x,y,使ax+by=gcd(a,b)。
至少存在一组解,有一组解就可以推出无数组解。
证明:设G为a,b的最大公约数,即G=gcd(a,b)
即:ax+by=G
令ax+by+ab-ab=G
ax+ab+by-ab=G
a(x+b)+b(y-a)=G
所以:若有(x,y)为一组解的话
即:(x+b,y-a)也为一组解
(x+2b,y-2a)也为一组解
(x+kb,y-ka)为解,k为整数
所以有无数解。
4.对于给定的整数a,b,方程ax+by=c,有整数解(x,y)的充要条件是c是gcd(a,b)的倍数。
证明:由2可知:ax+by=gcd(a,b)一定有整数解,且gcd(a,b)为最小整数
设c=G*p(c是G的倍数)p为整数
设有一组整数解(x,y)使ax1+by1=G1
两边同乘p: apx1+bpy1=pG1
因为Gp=c
所以apx1+bpy1=c
所以ax+by=c有一组整数解为
x=px1 y=py1
5.推论:(a,b)=1(gcd(a,b)=1),一定存在x,y为整数,使得ax+by=1。
证明:反证法:假设a,b不互质
那么a=q*gcd(a,b)
b=p*gcd(a,b)
因为ax+by=1
所以q*gcd(a,b)x+p*gcd(a,b)y=1
两边同除gcd(a,b)
qx+py=1/gcd(a,b)
如果gcd(a,b)≠1,
那么1/gcd(a,b)为小数,x,y一定不是整数
显然gcd(a,b)=1,a,b互质
6.推广:对于不定方程:
a1x1+a2x2+a3x3+……+anxn=c
满足gcd(a1,a2,a3……an)|c时,方程才有整数解
今天的文章贝祖定理_裴蜀定理什么时候学分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/45800.html