贝祖定理_裴蜀定理什么时候学

贝祖定理_裴蜀定理什么时候学引入: 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=

引入:

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

(0)
编程小号编程小号
上一篇 2023-09-06 15:11
下一篇 2023-09-06

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注