词条 | 裴蜀定理 |
释义 | 在数论中,裴蜀定理是一个关于最大公约数(或最大公约式)的定理。 简介裴蜀定理(或贝祖定理)得名于法国数学家艾蒂安·裴蜀,说明了对任何整数a、b和它们的最大公约数d,关于未知数x和y的线性丢番图方程(称为裴蜀等式):若a,b是整数,且(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。 它的一个重要推论是:a,b互质的充要条件是存在整数x,y使ax+by=1. 证明(1)若b=0,则(a,b)=a.这时定理显然成立。 (2)若a,b不等于0. ∵(a,b)=(a,-b)∴不妨设a,b都大于零,a>=b,(a,b)=d 对ax+by=d,两边同时除以d,可得(a1)x+(b1)y=1,其中(a1,b1)=1。 转证(a1)x+(b1)y=1。由带余除法: a1=(q1)b1+(r1),其中0=<r1<b1 b1=(q2)(r1)+(r2),其中0=<r2<r1 (r1)=(q3)(r2)+(r3),其中0=<r3<r2 ..... (rn-3)=(qn-1)(rn-2)+(rn-1) (rn-2)=(qn)(rn-1)+(rn) (rn-1)=(qn+1)(rn) 于是,有(a1,b1)=(b1,r1)=(r1,r2)=...=(rn-1,rn)=1 故 (rn-2)=(xn)(rn-1)+1 即1=(rn-2)-(xn)(rn-1) 由倒数第三个式子(rn-1)=(rn-3)-(xn-1)(rn-2)代入上式,得 1=[1+(xn)(xn-1)](rn-2)-(xn)(rn-3) 然后用同样的办法用它上面的等式逐个地消去(rn-2),...(r1), 可证得1=(a1)x+(b1)y。 n个整数间的裴蜀定理设a1,a2,a3......an为n个整数,d是它们的最大公约数,那么存在整数x1......xn使得x1*a1+x2*a2+...xn*an=d。 特别来说,如果a1...an互质(不是两两互质),那么存在整数x1......xn使得x1*a1+x2*a2+...xn*an=1。 任意主理想环上的情况裴蜀可以推广到任意的主理想环上。设环A是主理想环,a和b 为环中元素,d是它们的一个最大公约元,那么存在环中元素x和y使得: ax + by = d 这是因为在主理想环中,a和b的最大公约元被定义为理想aA + bA的生成元。 定理在数论中,裴蜀定理是一个关于最大公约数(或最大公约式)的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀,说明了对任何整数a、b和它们的最大公约数d,关于未知数x和y的线性丢番图方程(称为裴蜀等式): ax + by = m 有解当且仅当m是d的倍数。裴蜀等式有解时必然有无穷多个整数解,每组解x、y都称为裴蜀数,可用辗转相除法求得。 例如,12和42的最大公因子是6,则方程12x + 42y = 6有解。事实上有(-3)×12 + 1×42 = 6及4×12 + (-1)×42 = 6。 特别来说,方程 ax + by = 1 有解当且仅当整数a和b互素。 裴蜀等式也可以用来给最大公约数定义:d其实就是最小的可以写成ax + by形式的正整数。这个定义的本质是整环中“理想”的概念。因此对于多项式整环也有相应的裴蜀定理。 历史历史上首先证明关于整数的裴蜀定理的并不是裴蜀,而是17世纪初的法国数学家克劳德-加斯帕·巴歇·德·梅齐里亚克(Claude-Gaspard Bachet de Méziriac)。他在于1624年发表的著作《有关整数的令人快乐与惬意的问题集》(Problèmes plaisans et délectables qui se font par les nombres)第二版中给出了问题的描述和证明[1]。 然而,裴蜀推广了梅齐里亚克的结论,特别是探讨了多项式中的裴蜀等式,并给出了相应的定理和证明[2]。 整数中的裴蜀定理对任意两个整数a、b设d是它们的最大公约数。那么关于未知数x和y的线性丢番图方程(称为裴蜀等式): ax + by = m 有整数解(x,y)当且仅当m是d的倍数。裴蜀等式有解时必然有无穷多个解。 裴蜀定理参见理想 (环论) 欧几里德整环 欧几里德引理 主理想环 整除 裴蜀定理-参考来源^ 原版的网上版本(法文) ^ 证明的网上版本(法文) 闵嗣鹤、严士健,初等数论,高等教育出版社,2003。 唐忠明,抽象代数基础,高等教育出版社,2006。 裴蜀定理版(1)若a,b是整数,且(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。它的一个重要推论是:a,b互质的充要条件是存在整数x,y使ax+by=1. 裴蜀定理证明设存在x,y使ax+by=d,d是ax+by取值中的最小正整数,d≠1。再设am+bn=e,则e≥d .若d不整除e,对e做带余除法.必定存在p,r使e=pd+r.r<d则r=e-pd=(m-px)a+(n-py)b.存在整数m-px,n-py使ax+by=r<d,与d的最小性矛盾。所以d整除e.令m=1,n=0,则d整除a;同理d整除b.所以d=(a,b).a,b互质时,d=1 推广以上定理可推广到n个,n≥2 如1st IMO 1959第1题:证明对任意自然数n,(21n+4)/(14n+3)为既约分数。证明:很容易看出3(14n+3)-2(21n+4)=1,由裴蜀定理,21n+4与14n+3互质,故(21n+4)/(14n+3)为既约分数。Q.E.D. 另如:5x+4y+3z可表示全部整数.因为3,4,5互质,所以5x+4y+3z可以等于1,则必定可以等于其他任意整数 |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。