《裴蜀定理的应用》由会员分享，可在线阅读，更多相关《裴蜀定理的应用（3页珍藏版）》请在金锄头文库上搜索。
1、裴 蜀 定 理 的 应 用胡 生 淼(湖北省仙桃中学,433000)收稿日期:2003 - 04 - 12(本讲适合高中)裴蜀定理是数论中一个十分重要的基本 定理,在各级各类数学竞赛中出现了很多以 其为背景的试题.因此,了解该定理有助于我 们揭示问题的实质,做到有的放矢. 裴蜀定理 设a、b、d是整数,则(a,b)=d的充要条件是d|a,d|b,存在整数u、v, 使得ua+vb=d. 推论1 (a,b) = 1的充要条件是,存在 整数u、v,使得ua+vb= 1. 从而,当(a,b) = 1时,ua+vb可表示所有整数.由此,又得到下面的推论. 推论2 a、b均为正整数时,(a,b) = 1的
2、充要条件是,存在正整数u、v,使得ua-vb= 1. 下面结合实例介绍裴蜀定理在数学竞赛中的应用. 例1 集合M= u|u= 12m+ 8n+ 4l,m、n、lZ与N= u|u= 20p+ 16q+ 12r,p、q、rZ的关系为( ) .(A)M=N (B)M?N,N?M(C)Mk时,i与i-qk同色 (i-qk 0) .据题设可知存在整数x、y使得i=xk+yn.由1in- 1可知,x、y的取值无外乎 以下三种情形:(1)x 0 ,y= 0; (2)x 0 ,y 0.(1)时结论成立,而(3)可化为(2)讨论.因为由(a)可知,i和n-i= ( -x)k+ ( -y+1)n同色.若-y+ 1
3、 = 0 ,则化为(1) .若-y+1 -y) ,这时又分为三6中 等 数 学类:(i)k=i;(ii)ki; (iii)kn 1.已知2m- 1个盒子中装有一些球,如果给其中的2n- 1个盒子中添加一个球,则称为一次操作.证明:当(m,n) = 1时,不论2m- 1个盒子里已有多少个球,经有限次操作后,总能使所有盒子里的球一样多.(提示:(m,n) = 1 ,存在正整数a、b,使得na-mb= 1.令x= 2m- 1 ,y= 2n- 1 ,则2bm= (x+ 1)b,2an= (y+ 1)a.从而,(y+ 1)a= 2(x+ 1)b.由二项式定理展开知,存在正整数M、N,使得yM=xN+ 1
4、 ,即(2n- 1)M= (2m- 1)N+ 1.以下仿例5即可证得. )4.给定正整数a、b、c,定义函数f(x,y,z) =ax+by+cz,其中x、y、zZ.试求f(x,y,z)的最小正整数值.(提示:记fmin=ax0+by0+cz0=d0.设(a,b,c)=d,显然有d|d0,从而dd0.另一方面,由裴蜀定理知,存在整数x、y、z,使得ax+by+cz=d.因为d0最小,故d0d.所以,d0=d,即fmin= (a,b,c) .)5.若p、q互质,且p、qN,则存在最小的m=pq-p-q+ 1 ,使得对所有nm,n都可写成n=px+qy(x、y是非负整数) .(提示:只须证pq-p-q不可表示为px+qy.反证法.若pq-p-q=ap+bq(a、b非负) ,则pq=(1 +a)p+ (1 +b)q,因此,p| (1 +b) ,q| (1 +a) .令1 +a=aq, 1 +b=bp(a 、b1) ,得pq= (a+b)pq.但a+b= 1 ,矛盾. )72004年第3期
