贝祖定理

标签：... 贝祖 gcd 定理 整数 ...- 最大公约数 ax

引入：

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）使ax₁+by₁=G₁

          两边同乘p:   apx₁+bpy₁=pG₁

             因为Gp=c

             所以apx₁+bpy₁=c   

             所以ax+by=c有一组整数解为

             x=px₁    y=py₁

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.推广：对于不定方程：

             a₁x₁+a₂x₂+a₃x₃+......+a_nx_n=c

             满足gcd(a₁,a₂,a₃......a_n)|c时，方程才有整数解

 

标签：...,贝祖,gcd,定理,整数,...-,最大公约数,ax
From： https://www.cnblogs.com/ddfy198811/p/17025484.html