论文部分内容阅读
【摘要】初等数论中，关于最大公约数的问题是竞赛中的热点之一.本文以一条重要性质及推广形式为基础，讨论了此性质及推广形式的应用.
【关键词】最大公约数;重要性质;推广形式;互素
1.重要性质简介
初等数论中，有一条重要的性质：ax+by=(a,b).它表示对任意非零整数a,b存在一对整数x，y使得ax+by一定是a，b的最大公约数.
证明如下:设非零整数a，b的最大公约数为n,则一定有n|a且n|b.a=k1n,b=k2n.
ax+by=(k1x+k2y)×n.当k1x+k2y=1时，上述等式就取得a，b的最大公约数.当k1x+k2y≠1时，那ax+by=kn是最大公约数的整数倍.
性质的第一种推广形式是裴蜀等式,该等式实际上是该性质的一种特殊形式，我们令(a,b)=1,即a，b互为素数（以下简称互素），就可以得到著名的裴蜀等式ax+by=1.这也找到了判断两个整数互素的重要方法，即如果对于任意非零的两个整数a，b，存在一组整数x，y使得ax+by=1成立，那么一定可以得出a，b互素.
证明如下：采用反证法，假设ax+by=1，a，b不互素.利用刚得出的第一条性质可以得出ax+by=(k1x+k2y)×n=1.根据最大公约数的定义n一定为整数，所以得出(k1x+k2y)一定不是整数，显然不成立.我们可以得出结论，只有一种情况是可能的:(k1x+k2y)=1,n=1这也说明了a，b一定互素.
重要性质的第二种推广形式：我们很容易从两个数的判别方法得到三个数的方法.显然存在ax+by+cz=(a,b,c)，与此同时也得到了三个数的裴蜀等式即ax+by+cz=1可以说明非零整数a,b,c互素，但值得注意的是不能说明三个整数之间两两互素.由此可以把性质推广到n个整数，即a1x1+a2x2+…+anxn=(x1,x2,…,xn),a1x1+a2x2+…+anxn=1也是n个整数的裴蜀等式.
重要性质的第三种推广形式：即已知n个整数如何判断它们两两互素.有前面的推广形式，显然a1x1+a2x2=1,a1x1+a2x2+a3x3=1,…,a1x1+a2x2+…+anxn=1一共有n-1个方程可以判断出x1,x2,…,xn任意两个整数都互素.
2.重要性质及推广形式的应用
例1 对任意整数n，证明分数21n+414n+3是即约分数.
分析 本题的实质是证明21n+4和14n+3互质，采用裴蜀等式可以很快的出结果.
观察发现[21,14]=42,可以想到证明思路.
证明 利用裴蜀等式3×(14n+3)-2×(21n+4)=1,很快就可以说明题目中的分母与分子互素，所以是即约分数.
小结 如果不利用裴蜀等式，证明会变得比较困难.事实上，2×(21n+4)-3×(14n+3)=-1,也可以说明分子和分母互素.所以|ax+by|=1可以作为判定的条件.
例2 设n为正整数，证明:（n!+1,(n+1)!+1）=1.
分析 本题目和上面的例子类似，只是告诉我们在裴蜀等式的应用过程中，选取x,y不一定是现实的数字，也有可能是一些抽象的整数，比如n.还有很重要的一点,在寻找裴蜀等式中的x，y得到ax+by=1有时候会很困难，所以需要借助一些辅助方法.
证明 根据第一条重要性质，有(n+1)×(n!+1)-1×(n+1)!-1=n.显然，n=(a,b).
一定有n|n!+1且n|(n+1)!+1,又因为n|n!和n|(n+1)!,所以可以得到n|1，即n=1.
利用裴蜀等式很容易说明（n!+1,(n+1)!+1）=1.
总结 这里有一种数论中常用的方法，若n|a+b,且有n|a，一定可以得出n|b.利用此方法和其他方法结合可以解决很多棘手的问题.
例3 可以表示成1457x+1705y的最小正整数是多少？
分析 因为对于性质一而言，本题从相反的角度来考虑问题.熟悉性质的话不难想到ax+by=(a,b).问题迎刃而解，本质为求两个数的最小公约数.
解 1705=5×11×31,1457=31×47,根据性质可以知道(a,b)=31,答案为31.
小结 对性质的灵活应用，还有关键的一点看出11|341，先分解1705比较简单.
例4 有一种盒子能装3斤糖，另外一种盒子能装6斤糖，假定每一个盒子必须装满，问：用这两种盒子能装完100斤糖吗？
分析 应用问题，利用最大公约数的性质可以快速求解.
解 利用性质3x+6y=k×(3，6),（3,6）=3，3k≠100，所以这两种盒子不可能装完一百斤糖.
小结 生活中的数论应用问题.
例5 设(a,b)=1,证明:(a+b,ab)=1.
分析 采用反证法证明，要充分利用a，b互素的已知条件.
证明 采用反证法.设(a+b,ab)=t，t为整数且不为1.因为整数a，b互素,且t|ab,t|a+b.
所以t=a或b或ab,否则与题意矛盾.
分三种情况分别讨论：
(1)t=a时，由t|a+b可以得知t|b，（a，b）=t，t≠1，所以a与b不互素.与原题意矛盾.
(2)t=b时，同上可证.
(3)t=ab时，不妨设a+bab=k,1a+1b=k,可以设b=a+r,1a+r+1a=k,整理得关于a的方程ka2+(kr-2)×a-r=0，解为a=2-kr+S2k,S=k2r2+4,所以S一定是完全平方数.
k2r2+4=u2,可以变形为k2r2-u2=4，（kr+u）×(kr-u)=4列出所有可能性：
kr+u=2和kr-u=2;kr+u=1和kr-u=4;kr+u=4和kr-u=1;三种情况下，第一组解得到kr=1,显然排除，后两组中u不是整数，排除.这就说明了(a+b,ab)=1.
总结 通过反证法不借助最大公约数的性质也可以作出此题.
例6 设(a,b)=1,证明：(a2+b2,ab)=1.
分析 此题和上面的题目类似，采用性质证明会比采用上面题目类似的证明简单.
证明 和例题五类似，采用反证法，设(a2+b2,ab)=t≠1，利用a与b互素，可以同理证出前两种情况，即t≠a,t≠b.
对于第三种情况，首先利用裴蜀等式，存在x,y使得ax+by=1.利用性质可以得到如下等式:(a2+b2)×x2+2abxy=1,将ax+by=1代入，整理得1+b(x2-y2)=n,n是(a,b)的倍数.
所以t|1+b(x2-y2),由此,因为t|b，所以t|1，得出矛盾.所以(a2+b2,ab)=1.
小结 可以发现，利用性质可以很快的得出结论，比讨论要方便得多.本题第三问也可用类似例题五的方法处理，也比较繁琐.
例7 证明:(12n+5,9n+4,6n+3)=1.
分析 采用裴蜀等式的推广形式.
证明 因为2×(9n+4)+1×(6n+3)-2×(12n+5)=1.所以原命题成立.
例8 证明:12n+5,9n+4,6n+3两两互质.
分析 利用性质的推广形式.
证明 显然4×(9n+4)-3×(12n+5)=1，有例8的结论，可知原命题成立.
小结 裴蜀等式证明两两互质，采用推广形式比较方便.
性质总结 最大公约数是初等数论中的一个重要概念，对ax+by这一性质以及推广形式的灵活应用,解决问题可以起到事半功倍的效果.对于具体问题仍然要具体分析，多种方法、思想和性质的联合应用也是解决难题的利器.
【参考文献】
[1]余红兵.数学竞赛中的数论问题(第二版).上海：华东师范大学出版社，2005（6）:5-10.
[2]华罗庚学校.华罗庚学校数学试题解析高一年级(第三版).北京：中国大百科全书出版社，1996（3）:62-63.
[3]潘承洞，潘承彪.初等数论(第二版).北京：北京大学出版社，2009(12):12.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文
【关键词】最大公约数;重要性质;推广形式;互素
1.重要性质简介
初等数论中，有一条重要的性质：ax+by=(a,b).它表示对任意非零整数a,b存在一对整数x，y使得ax+by一定是a，b的最大公约数.
证明如下:设非零整数a，b的最大公约数为n,则一定有n|a且n|b.a=k1n,b=k2n.
ax+by=(k1x+k2y)×n.当k1x+k2y=1时，上述等式就取得a，b的最大公约数.当k1x+k2y≠1时，那ax+by=kn是最大公约数的整数倍.
性质的第一种推广形式是裴蜀等式,该等式实际上是该性质的一种特殊形式，我们令(a,b)=1,即a，b互为素数（以下简称互素），就可以得到著名的裴蜀等式ax+by=1.这也找到了判断两个整数互素的重要方法，即如果对于任意非零的两个整数a，b，存在一组整数x，y使得ax+by=1成立，那么一定可以得出a，b互素.
证明如下：采用反证法，假设ax+by=1，a，b不互素.利用刚得出的第一条性质可以得出ax+by=(k1x+k2y)×n=1.根据最大公约数的定义n一定为整数，所以得出(k1x+k2y)一定不是整数，显然不成立.我们可以得出结论，只有一种情况是可能的:(k1x+k2y)=1,n=1这也说明了a，b一定互素.
重要性质的第二种推广形式：我们很容易从两个数的判别方法得到三个数的方法.显然存在ax+by+cz=(a,b,c)，与此同时也得到了三个数的裴蜀等式即ax+by+cz=1可以说明非零整数a,b,c互素，但值得注意的是不能说明三个整数之间两两互素.由此可以把性质推广到n个整数，即a1x1+a2x2+…+anxn=(x1,x2,…,xn),a1x1+a2x2+…+anxn=1也是n个整数的裴蜀等式.
重要性质的第三种推广形式：即已知n个整数如何判断它们两两互素.有前面的推广形式，显然a1x1+a2x2=1,a1x1+a2x2+a3x3=1,…,a1x1+a2x2+…+anxn=1一共有n-1个方程可以判断出x1,x2,…,xn任意两个整数都互素.
2.重要性质及推广形式的应用
例1 对任意整数n，证明分数21n+414n+3是即约分数.
分析 本题的实质是证明21n+4和14n+3互质，采用裴蜀等式可以很快的出结果.
观察发现[21,14]=42,可以想到证明思路.
证明 利用裴蜀等式3×(14n+3)-2×(21n+4)=1,很快就可以说明题目中的分母与分子互素，所以是即约分数.
小结 如果不利用裴蜀等式，证明会变得比较困难.事实上，2×(21n+4)-3×(14n+3)=-1,也可以说明分子和分母互素.所以|ax+by|=1可以作为判定的条件.
例2 设n为正整数，证明:（n!+1,(n+1)!+1）=1.
分析 本题目和上面的例子类似，只是告诉我们在裴蜀等式的应用过程中，选取x,y不一定是现实的数字，也有可能是一些抽象的整数，比如n.还有很重要的一点,在寻找裴蜀等式中的x，y得到ax+by=1有时候会很困难，所以需要借助一些辅助方法.
证明 根据第一条重要性质，有(n+1)×(n!+1)-1×(n+1)!-1=n.显然，n=(a,b).
一定有n|n!+1且n|(n+1)!+1,又因为n|n!和n|(n+1)!,所以可以得到n|1，即n=1.
利用裴蜀等式很容易说明（n!+1,(n+1)!+1）=1.
总结 这里有一种数论中常用的方法，若n|a+b,且有n|a，一定可以得出n|b.利用此方法和其他方法结合可以解决很多棘手的问题.
例3 可以表示成1457x+1705y的最小正整数是多少？
分析 因为对于性质一而言，本题从相反的角度来考虑问题.熟悉性质的话不难想到ax+by=(a,b).问题迎刃而解，本质为求两个数的最小公约数.
解 1705=5×11×31,1457=31×47,根据性质可以知道(a,b)=31,答案为31.
小结 对性质的灵活应用，还有关键的一点看出11|341，先分解1705比较简单.
例4 有一种盒子能装3斤糖，另外一种盒子能装6斤糖，假定每一个盒子必须装满，问：用这两种盒子能装完100斤糖吗？
分析 应用问题，利用最大公约数的性质可以快速求解.
解 利用性质3x+6y=k×(3，6),（3,6）=3，3k≠100，所以这两种盒子不可能装完一百斤糖.
小结 生活中的数论应用问题.
例5 设(a,b)=1,证明:(a+b,ab)=1.
分析 采用反证法证明，要充分利用a，b互素的已知条件.
证明 采用反证法.设(a+b,ab)=t，t为整数且不为1.因为整数a，b互素,且t|ab,t|a+b.
所以t=a或b或ab,否则与题意矛盾.
分三种情况分别讨论：
(1)t=a时，由t|a+b可以得知t|b，（a，b）=t，t≠1，所以a与b不互素.与原题意矛盾.
(2)t=b时，同上可证.
(3)t=ab时，不妨设a+bab=k,1a+1b=k,可以设b=a+r,1a+r+1a=k,整理得关于a的方程ka2+(kr-2)×a-r=0，解为a=2-kr+S2k,S=k2r2+4,所以S一定是完全平方数.
k2r2+4=u2,可以变形为k2r2-u2=4，（kr+u）×(kr-u)=4列出所有可能性：
kr+u=2和kr-u=2;kr+u=1和kr-u=4;kr+u=4和kr-u=1;三种情况下，第一组解得到kr=1,显然排除，后两组中u不是整数，排除.这就说明了(a+b,ab)=1.
总结 通过反证法不借助最大公约数的性质也可以作出此题.
例6 设(a,b)=1,证明：(a2+b2,ab)=1.
分析 此题和上面的题目类似，采用性质证明会比采用上面题目类似的证明简单.
证明 和例题五类似，采用反证法，设(a2+b2,ab)=t≠1，利用a与b互素，可以同理证出前两种情况，即t≠a,t≠b.
对于第三种情况，首先利用裴蜀等式，存在x,y使得ax+by=1.利用性质可以得到如下等式:(a2+b2)×x2+2abxy=1,将ax+by=1代入，整理得1+b(x2-y2)=n,n是(a,b)的倍数.
所以t|1+b(x2-y2),由此,因为t|b，所以t|1，得出矛盾.所以(a2+b2,ab)=1.
小结 可以发现，利用性质可以很快的得出结论，比讨论要方便得多.本题第三问也可用类似例题五的方法处理，也比较繁琐.
例7 证明:(12n+5,9n+4,6n+3)=1.
分析 采用裴蜀等式的推广形式.
证明 因为2×(9n+4)+1×(6n+3)-2×(12n+5)=1.所以原命题成立.
例8 证明:12n+5,9n+4,6n+3两两互质.
分析 利用性质的推广形式.
证明 显然4×(9n+4)-3×(12n+5)=1，有例8的结论，可知原命题成立.
小结 裴蜀等式证明两两互质，采用推广形式比较方便.
性质总结 最大公约数是初等数论中的一个重要概念，对ax+by这一性质以及推广形式的灵活应用,解决问题可以起到事半功倍的效果.对于具体问题仍然要具体分析，多种方法、思想和性质的联合应用也是解决难题的利器.
【参考文献】
[1]余红兵.数学竞赛中的数论问题(第二版).上海：华东师范大学出版社，2005（6）:5-10.
[2]华罗庚学校.华罗庚学校数学试题解析高一年级(第三版).北京：中国大百科全书出版社，1996（3）:62-63.
[3]潘承洞，潘承彪.初等数论(第二版).北京：北京大学出版社，2009(12):12.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文