当前位置：文档之家 › 数论例题

数论例题

  • 格式：doc
  • 大小：2.45 MB
  • 文档页数：29

竞赛中的数论问题【知识点介绍】初等数论也叫做整数论，其研究对象是整数，由于其形式简单，所用知识不难理解，因而常常出现在数学竞赛中．数学竞赛中的数论问题主要涉及奇数和偶数，约数与倍数，素数与合数，平方数、整除、同余、不定方程、数论函数[x ]和欧拉函数、数的非十进制等．处理竞赛中的数论问题要求熟悉基本知识，灵活地运用一些常用技巧．在本讲中，如没有特别说明，所用的字母均表示整数．1．整除设a 、b 是两个整数，b ≠0，则一定有且仅有两个整数q 和r ，使得a =bq +r (0≤r <|b |)成立，其中q 叫做商，r 叫做余数．当r =0时，称b 整除a (或a 能被b 整除)，记作b |a ．此时a 叫b 的倍数，b 叫a 的约数(因数)．设n 是正整数，k 是不小于2的整数，则存在惟一的一组小于k 的非负整数12,,,m a a a ，且10a >，使得12121m m m m n a k a k a k a ---=++++ ，这就是n 的k 进制表示．设a 、b 是两个不全为0的整数，若整数d 既能整除a 又能整除b ，则称d 是a 、b 的公约数，a 、b 的公约数中的最大者称为a 、b 的最大公约数，记为(a ，b )．若(a ，b )=1，则称a 、b 是互素(互质)的．设a 、b 是两个都不为0的整数，若m 是a 的倍数，同时又是b 的倍数，则称m 是a 、b 的公倍数，a 、b 的公倍数中最小的正数称为a 、b 的最小公倍数，记为[a ，b ]．对任意的正整数a 、b 有：(a ，b ) [a ，b ]=ab ．对非零整数a 、b 、c 、m 、n ，有以下性质：(1) 若|,|c b b a ，则|c a ;(2) 若|b a ，则|bm am ;(3) 若|,|c a c b ，则|c ma nb +;(4) 若(,)1a b =，且|a bc ，则|a c ;(5) 若(,)1a b =，且|,|a c b c ，则|ab c .2．同余设m 是一个不小于2的正整数，且|m a b -，则称,a b 对模m 同余，记作(mod )a b m º．设,,,,a b c d m 是整数，且0m >，则(1)若)(mod m b a ≡，且)(mod m c b ≡，则)(mod m c a ≡；(2)若)(mod m b a ≡，且)(m o d m c b ≡，则)(m o d m d b c a +≡+且)(mod m bd ac ≡；(3)若)(mod m b a ≡，且正整数c 满足|(,,)c a b m ，则).(mod cm c b c a ≡． 3．素数与合数若一个大于1的整数除了1和本身外再无其它的正约数，则称这个数为素数（质数）．每一个大于1的整数都可分解成素数的乘积，而且不计因数的顺序时，这种表示是惟一的，即.......2121n n p p p n ααα⋅=．正整数n 的素数分解式为.......2121n n p p p n ααα⋅=，则n 的正约数的个数为 )1)......(1)(1()(21+++=n n d ααα，n 的所有正约数的和为)....1)...(...1)(...1(22222121121k k k k p p p p p p p p p ααα++++++++++++每连续n 个整数中，与n 互质的整数的个数是)11)......(11)(11()(21kp p p n n ---=ϕ. 4．不定方程若00(,)x y 是方程ax by c +=的一个正整数解，则方程的一切整数解可以表示为)(.,00Z t at y y bt x x ∈⎩⎨⎧+=-= 方程222x y z +=满足(,)1x y =且y 是偶数的一切正整数解为2222,2,x a b y ab z a b =-==+（这里(,)1a b =，,a b 一奇一偶，且a b >）．[典型例题]例 1 (2007年广西预赛试题)已知三个正整数x ，y ，z 的最小公倍数是300，并且222320,230,x y z x y z +-=⎧⎨-+=⎩则方程组的解(x ，y ，z )= . 解 记方程组中的两个方程为（1），（2），消去x 得038522=+-z yz y ，即0))(35(=--z y z y ，所以035=-z y ，或0=-z y ．若0=-z y ，则由(1)得x y =-，不合题意．由035=-z y 和（1）得x z x y 5,3==，即::1:3:5x y z =，于是，令)(5,3,*N k k z k y k x ∈===，有15300k =，20k =，从而(x ，y ，z )=(20，60，100)．例2 （2008年全国高中数学联赛试题） 方程组0,0,0x y z xyz z xy yz xz y ++=⎧⎪+=⎨⎪+++=⎩的有理数解(,,)x y z 的个数为 （ B ）A. 1B. 2C. 3D. 4[解] 若0z =，则00.x y xy y +=⎧⎨+=⎩，解得00x y =⎧⎨=⎩，或11.x y =-⎧⎨=⎩， 若0z ≠，则由0xyz z +=得1xy =-． ①由0x y z ++=得z x y =--． ②将②代入0xy yz xz y +++=得220x y xy y ++-=． ③ 由①得1x y=-，代入③化简得3(1)(1)0y y y ---=. 易知310y y --=无有理数根，故1y =，由①得1x =-，由②得0z =，与0z ≠矛盾，故该方程组共有两组有理数解0,0,0x y z =⎧⎪=⎨⎪=⎩或1,1,0.x y z =-⎧⎪=⎨⎪=⎩说明：上述两个例题都是求不定方程组的整数解，这类问题通常是想办法将其转化成不定方程来进行求解。

例3 (2007年安徽省预赛试题)设A =100101102103…499500是一个1203位正整数，由100到500的全体三位数按顺序排列而成，那么A 被126除的余数是( )（A ）78． （B ）36． （C ）6． （D ）0．分析 972126⨯⨯=，因此只要求出A 被2，7，9除的余数，就可求出A 被126除的余数．解 注意到972126⨯⨯=,)2(mod 0≡A ,).9(mod 6534013002401600500...102101100≡⨯≡⨯=⨯=++++≡A 又),7(mod 1103-≡所以).7(mod 6300100101102...497498499500≡≡+-++-+-≡A综上， )126(mod 6≡A ．故选（C ）.例4 (2007年浙江省预赛试题)已知a =}2007200720072007 重，则a 的末两位数字是( )（A ）01． （B ）07． （C ）43． （D ）49．分析 求a 的末两位数字，即求a 被100除的余数，因此考虑用同余性质解题．解 记N k =}200720072007k 重．则20062006200720077(mod100)N N N =≡.又 4724011(m o d 100)n n =≡，200520052006(2007)(1)13(mod4)N N N =≡-=-≡. 所以 200637743(mod100)N ≡≡.因此，a 的末两位数字是43．故选（C ）． 说明 一般地，对于正整数a 、m ，数列{(mod )}n a m 是周期数列．例5 (2007年安徽省预赛试题)在正整数构成的等差数列1，3，5，7，…中删去所有和55不互质的项之后，把余下的各项按从小到大的顺序排成一个数列{}n a ．易见123451,3,7,9,13a a a a a =====，…….那么2007a 等于( )（A ）9597． （B ）5519． （C ）2381． （D ）2759．分析 考虑正整数列1，2，3，4，5，6，7，…其中每连续110个数与2，5，11都互质的数的个数都一样多，可以求出，不与2，3，5都互质的数也可以求出，这样把这个正整数列进行分段，能计算出余下的数的个数．解法1 {}n a 可以看作是在正整数列1，2，3，4，5，6，7…中删去所有可能被2，5或11整除的项之后，把余下的各项按从小到大的顺序排成的数列，于是余下的项是所有与1101152=⨯⨯互质的项．而每连续110个整数中，与110互质的数有40)1111)(511)(211(110)110(=---⨯=ϕ个． 又750402007+⨯=，而正整数列中第7个与110互质的数是19，所以551919501102007=+⨯=a ．故选（B ）． 解法2 {}n a 可以看作是在正整数列1，2，3，4，5，6，7…中删去所有可能被2，5或11整除的项之后，把余下的各项按从小到大的顺序排成的数列．由容斥原理，从1到正整数m 中，不能被2，5或11整除的项的个数是]110[]55[]22[]10[]11[]5[]2[m m m m m m m m x m -+++---= (其中[]x 表示不超过x 的最大整数．由m m m m m m m m m m x m 114)1111)(511)(211(11055221011522007=---=-+++---=≈， 得55194112007≈⨯≈m ． 而2007]1105519[]555519[]225519[]105519[]115519[]55519[]25519[55195519=-+++---=x ，且5519与110互质，从而20075519a =．故选（B ）．例6 （2008年全国数学高中联赛试题） 求满足下列关系式组2222,50,x y z z y z ⎧+=⎨<≤+⎩的正整数解组(,,)x y z 的个数．分析：此问题是二次不定方程，且有约束条件，因此要进行适当的转化求解。

[解] 令r y z =-，由条件知050r <≤，方程化为222()2x z r z ++=，即2222x zr r z ++=． （1）因0y z r -=>，故22222z x y z x =+->，从而z x >．设0p z x =->．因此（1）化为22220zp p zr r -+++=． （2）下分r 为奇偶讨论，（ⅰ）当r 为奇数时，由（2）知p 为奇数．令121r r =+，121p p =+，代入（2）得221111112()10p p zp zr r r +-++++=． （3）（3）式明显无整数解．故当r 为奇数时，原方程无正整数解．（ⅱ）当r 为偶数时，设12r r =，由方程（2）知p 也为偶数．从而可设12p p =，代入（2）化简得2211110p zp zr r -++=． （4）由（4）式有221111()0z p r p r -=+>，故11p r>，从而可设11p r a =+，则（4）可化为2211()0r a za r +-+=，2211220r ar za a +-+=． （5） 因21122r z r a a=++为整数，故212a r ． 又1122()z z x p r a >-==+，因此22111()2()r a r za r a a ++=>+，得2212a r <，a <．因此，对给定的11,2,,25r =⋅⋅⋅，解的个数恰是满足条件a <的212r 的正因数a 的个数1()N r ．因212r 不是完全平方数，从而1()N r 为212r 的正因数的个数21(2)r σ的一半．即211()(2)/2N r r σ=．由题设条件，1125r ≤≤．而25以内有质数9个：2，3，5，7，11，13，17，19，23．将25以内的数分为以下八组：：012341{2,2,2,2,2}A =，2{23,25,27,211}A =⨯⨯⨯⨯，223{23,25}A =⨯⨯，34{23}A =⨯，25{23}A =⨯，1{3,5,7,11,13,17,19,23}B =，222{3,5}B =，3{35,37}B =⨯⨯，从而易知012341()(2)(2)(2)(2)(2)1234515N A N N N N N =++++=++++=，2()(23)46424N A N =⨯⨯=⨯=，(.)6234)32(21))32(2(21)32(232=⨯=⨯=⨯⨯=⨯σσN 3()9218N A =⨯=， (.)9236)32(21))32(2(21)32(25222=⨯=⨯=⨯⨯=⨯σσN 4()12N A =，5()10N A =，1()3824N B =⨯=，2()5210N B =⨯=，3()9218N B =⨯=，将以上数相加，共131个．因此解的个数共131．例7 (2007年天津预赛试题)方程2232007x y +=的所有正整数解为 . 分析 本方程不能通过分解求出其正整数解，我们用同余方法．解 方程两边模3得，()0mod3x ≡．设13x x =，代入方程，约去3 ，再两边模3得，()0mod3y ≡．设13y y =，则原方程化为22113223x y +=，于是11x ≤1114x ≤≤．因为02≡x 或1,02≡y 或1(mod 4)，()2233mod4≡，所以1x 为偶数，于是{}12,4,8,10,14x ∈．经验证，1114,3x y ==，所以42,9x y ==．说明：该问题就是运用一个数的平方关于模4的余数而求出该不定方程的解。

合集下载

数论专题一

数论专题一


例题4、学校打算在1月4日或1月10日组织同学们 看电影，确定好日期后，老师告诉了班长，但是 由于“四”和“十”发音接近，班长有10%的可 能性听错（把4听成10或者把10听成4），班长又 把日期告诉了小明，小明也有10%的可能性听错。 那么小明认为看电影的日期是正确的可能性为 _____%；
考点：概率问题 详解：小明认为正确的情况有两种：（1）班长正 确、小明正确，共（1−10%）×（1−10%）=81%； （2）两人都错误，10%×10%=1%。共 81%+1%=82%。 评注：本题最容易的错误答案是81%。
例题9、如果一个四位数与一个三位数的和是 1999，并且四位数与三位数是由7个不同的数字 组成的。问这样的四位数共有多少个？
解：我们不妨设这个四位数为abcd,三位数为efg.由题意得： abcd +ef g 1 9 9 9 ,显然a=1,且b+e=9 c+f=9 d+g=9.我 们知道：7+2=6+3=5+4=9+0=9(1和8不能选，因为1已经 用过了），又因为e不能为0，那么b就不能为9，则b共有7 种选择（0、2、3、4、5、6、7）。当b确定后，e也就随 之确定，所以c只剩下6种取法，同理f就确定了，d就只剩 下4种取法，d确定后，g也就确定了 所以一共：7×6×4=168（个）
例题8、 有4个不同的数字共可组成18个不同的 4位数。将这18个不同的4位数由小到大排成一 排，其中第一个是一个完全平方数，倒数第二 个也是完全平方数。那么这18个数的平均数是 多少？
解：4个不同的数可以组成24个不同的数，但是现在题目 中说有18个不同的数，那只有一种可能，4个数中有一个 是0. 设另外3个数分别为：a,b,c 且a＜b＜c 4个数中最小的数为a0bc,倒数第二大的数为cb0a 这个时候我们就要涉及到尝试法:a0bc最小可以为1023， 但是1023不是完全平方数，完全数最接近1023的是 32²=1024，然后4201不是完全平方数。继续假设 a0bc=33²=1089，而9801=99²，成立。 所以a=1,b=8.c=9 然后把18个罗列出来算平均数=6444
高考数论必考经典题型-第一讲

高考数论必考经典题型-第一讲


因为 d = 0, 故: d = 2a2.
所以 公比 q = a3 = a2 + d = 3a2 = 3.
a2
a2
a2
2
考点: 等差数列的通项公式，等比数列的中项公式，公比的定义。
例 6. 已知等差数列 {an} 的前 n 项和 Sn, 且 a1 = 1, S11 = 33. 设 bn = 比数列, 并求其前 n 项和 Tn.
可以得到这是一个首项为 a1 = 2, 公差为 d = 7 的等差数列.
故这些数构成的数列为: an = 2 + 7(n − 1) = 7n − 5.
由于需要在 100 之内, 因此： 7n − 5 ≤ 100, 即：n ≤ 15.
由等差数列的求和公式： Sn =
(a1 + an)n 2
， 可 得 这 些 数 之 和 为:
1 2
2
·
1
−
1 2
1
−
1 2
5
1 = 1 − 2n .
25
考点: 等差数列的通项公式，等差数列的求和公式，等比数列的通项公式，等比数列的求和公式，
等比数列的定义。
例
7.
若
x = y,
且两个数列:
x,
a1,
a2,
y
和
x,
b1,
b2,
b3,
y
均为等差数列,
求:
a1 − x y − b3
=
?
解析: 设两个等差数列的公差分别为: d1 和 d2, 则由等差数列的通项公式: an = a1 + (n − 1)d ,
可得 a1 = x + d1, y = x + 3d1; y = b3 + d2, y = x + 3d2.
100个数论经典例题

100个数论经典例题

100个数论经典例题数论经典例题是学习数论的重要方式，它们体现了数论的基本概念和重要定理。

下面列举了100个数论经典例题及其相关参考内容，帮助读者更好地理解和掌握数论的基础知识。

1. 证明：对任意正整数n，有$n^2\equiv 0\pmod{2}$。

解答：正整数的平方一定是偶数，因为偶数乘以偶数还是偶数。

2. 证明：对任意正整数n，有$n^3\equiv n\pmod{3}$。

解答：利用模运算的性质，$n\equiv 0, 1, 2 \pmod{3}$，分别代入得到$n^3\equiv 0, 1, 8 \equiv 0, 1 \pmod{3}$。

3. 证明：对任意正整数n，有$n^2\equiv 0$ 或 $1 \pmod{4}$。

解答：正整数的平方一定是偶数，因此$\pmod{4}$下只有两个可能性，即0或1。

4. 证明：对任意正整数n，有$n^m\equiv n \pmod{m}$。

解答：利用数论基本定理得到$n^m\equiv n\pmod{m}$。

5. 证明：对任意正整数n，如果$n^2$是完全平方数，则n也是完全平方数。

解答：设$n^2 = k^2$，则$(n+k)(n-k) = 0$，即$n+k = 0$或$n-k = 0$，因此n是完全平方数。

6. 证明：对任意正整数n，如果$n^2$是立方数，则n也是立方数。

解答：设$n^2 = k^3$，则$(n^{\frac{2}{3}})^3 = k^3$，因此n是立方数。

7. 证明：对任意正整数n，如果$n^2$是素数，则n是素数。

解答：反证法，假设n不是素数，则n可以表示为两个正整数的乘积，因此$n^2$也可以表示为两个正整数的乘积，与$n^2$是素数矛盾。

8. 证明：存在无穷多个素数。

解答：利用反证法和欧几里得定理可以证明存在无穷多个素数。

9. 证明：存在无穷多个不能表示为两个素数之和的正整数。

解答：利用哥德巴赫猜想的推广版本可以证明。

《数论》第一章补充例题

《数论》第一章补充例题

《数论》第一章补充例题整除性理论是初等数论的基础.本章要介绍带余数除法,辗转相除法,最大公约数,最小公倍数,算术基本定理以及它们的一些应用.1整数的整除性例1设A={d1,d2,···,dk}是n的所有约数的集合,则}{nnn,,···,B=d1d2dk也是n的所有约数的集合.解由以下三点理由可以证得结论:(i)A和B的元素个数相同;(ii)若di∈A,即di|n,则(iii)若di=dj,则问:d(1)+d(2)+···+d(1997)是否为偶数?n解对于n的每个约数d,有n=d·n,因此,n的正约数d与是成对地出现的.只有n2当d=n,即d=n时,d和才是同一个数.故当且仅当n是完全平方数时,d(n)是奇数.nini|n,反之亦然;=nj.例2以d(n)表示n的正约数的个数,例如:d(1)=1,d(2)=2,d(3)=2,d(4)=3,···.因为442<1997<452,所以在d(1),d(2),···,d(1997)中恰有44个奇数,故d(1)+d(2)+···+d(1997)是偶数.问题d2(1)+d2(2)+···+d2(1997)被4除的余数是多少?例3证明:存在无穷多个正整数a,使得n4+a(n=1,2,3,···)都是合数.??例题中引用的定理或推论可以在教材相应处找到.1解取a=4k4,对任意的n∈N,有n4+4k4=(n2+2k2)2?4n2k2=(n2+2k2+2nk)(n2+2k2?2nk).由n2+2k2?2nk=(n?k)2+k2??k2,所以,对于任意的k=2,3,···以及任意的n∈N,n4+a是合数.例4设a1,a2,···,an是整数,且n∑k=1ak=0,n∏k=1ak=n,则4|n.解如果2??n,则n,a1,a2,···,an都是奇数.于是a1+a2+···+an是奇数个奇数之和,不可能等于零,这与题设矛盾,所以2|n,即在a1,a2,···,an中至少有一个偶数.如果只有一个偶数,不妨设为a1,那么2??ai(2??k??n).此时有等式a2+···+an=?a1,在上式中,左端是(n?1)个奇数之和,右端是偶数,这是不可能的,因此,在a1,a2,···,an 中至少有两个偶数,即4|n.例5若n是奇数,则8|n2?1.解设n=2k+1,则n2?1=(2k+1)2?1=4k(k+1),在k与k+1中有一个偶数,所以8|n2?1.2带余数除法例1设a,b,x,y是整数,k和m是正整数,并且a=a1m+r1,0??r1<m,b=b1m+r2,0??r2<m,则ax+by和ab被m除的余数分别与r1x+r2y和r1r2被m除的余数相同.特别地,ak与k被m 除的余数相同.r1解由ax+by=(a1m+r1)x+(b1m+r2)y=(a1x+b1y)m+r1x+r2y可知,若r1x+r2y被m除的余数是r,即r1x+r2y=qm+r,0??r<m,2则ax+by=(a1x+b1y+q)m+r,0??r<m,即ax+by被m除的余数也是r.例2设a1,a2,···,an为不全为零的整数,以y0表示集合A={y|y=a1x1+···+anxn,xi∈Z,1??i??n}中的最小正数,则对任何的y∈A,y0|y;特别地,y0|ai,1??i??n.′解设y0=a1x′1+···+anxn,?y∈A,由带余除法,?q,r0∈Z,使得y=qy0+r0,0??r0<y0.因此′r0=y?qy0=a1(x1?qx′1)+···+an(xn?qxn)∈A.如果r0=0,那么,因为0<r0<y0,所以r0是A中比y0还小的正数,这与y0的定义矛盾.所以r0=0,即y0|y.显然ai∈A(1??i??n),所以y0整除每个ai(1??i??n).例3任意给出的五个整数中,必有三个数之和被3整除.解设这五个数是ai,i=1,2,3,4,5,记ai=3qi+ri,0??ri<3,i=1,2,3,4,5.分别考虑以下两种情形:(i)若r1,r2,···,r5中数0,1,2都出现,不妨设r1=0,r2=1,r3=2,此时a1+a2+a3=3(q1+q2+q3)+3可以被3整除;(ii)若r1,r2,···,r5中数0,1,2至少有一个不出现,这样至少有三个ri要取相同的值,不妨设r1,r2,r3=r(r=0,1或2),此时a1+a2+a3=3(q1+q2+q3)+3r可以被3整除.例4设a0,a1,···,an∈Z,f(x)=anxn+···+a1x+a0,已知f(0)与f(1)都不是3的倍数,证明:若方程f(x)=0有整数解,则3|f(?1)=a0?a1+a2?···+(?1)nan.证对任意整数x,都有x=3q+r,r=0,1或2,q∈Z.(i)若r=0,即x=3q,q∈Z,则f(x)=f(3q)=an(3q)n+···+a1(3q)+a0=3Q1+a0=3Q1+f(0),3其中Q1∈Z,由于f(0)不是3的倍数,所以f(x)=0;(ii)若r=1,即x=3q+1,q∈Z,则f(x)=f(3q+1)=an(3q+1)n+···+a1(3q+1)+a0=3Q2+an+···+a1+a0=3Q2+f(1),其中Q2∈Z.由于f(1)不是3的倍数,所以f(x)=0.因此若f(x)=0有整数解x,则必是x=3q+2=3q′?1,q′∈Z,于是0=f(x)=f(3q′?1)=an(3q′?1)n+···+a1(3q′?1)+a0=3Q3+a0?a1+a2?···+(?1)nan.其中Q3∈Z.所以3|f(?1)=a0?a1+a2?···+(?1)nan.例5设n是奇数,则16|n4+4n2+11.证我们有n4+4n2+11=(n2?1)(n2+5)+16.由上节例题知道,8|n2?1,由此及2|n2+5得到16|(n2?1)(n2+5).例6证明:若a被9除的余数是3,4,5或6,则方程x3+y3=a没有整数解.证?x,y∈Z,记x=3q1+r1,y=3q2+r2,0??r1,r2<3.则存在Q1,R1,Q2,R2∈Z,使得x3=9Q1+R1,y3=9Q2+R2,3和r3被9除的余数相同,即其中R1和R2被9除的余数分别与r12R1=0,1或8,R2=0,1或8.因此x3+y3=9(Q1+Q2)+R1+R2.(2.1)又由式(2.1)可知,R1+R2被9除的余数只可能是0,1,2,7或8,所以,x3+y3不可能等于a .例7证明:方程22a21+a2+a3=1999(2.2)无整数解.证若a1,a2,a3都是奇数,则存在整数A1,A2,A3,使得22a21=8A1+1,a2=8A2+1,a3=8A3+1,于是22a21+a2+a3=8(A1+A2+A3)+3.4由于1999被8除的余数是7,所以a1为奇数.由式(2.2),a1,a2,a3中只有一个奇数,设a1为奇数,a2,a3为偶数,则存在整数A1,A2,A3,使得22a21=8A1+1,a2=8A2+r,a3=8A3+s,于是22a21+a2+a3=8(A1+A2+A3)+1+r+s,22其中r和s是整数,而且只能取值0或4.这样a21+a2+a3被8除的余数只可能是1或5, 但1999被8除的余数是7,所以这样的a1,a2,a3也不能使式(2.2)成立.3最大公约数例1(105,140,350)=(105,(140,350))=(105,70)=35.21n+4例2证明:若n是正整数,则是既约分数.14n+3证由辗转相除法得到(21n+4,14n+3)=(7n+1,14n+3)=(7n+1,1)=1.??4辗转相除法例1用辗转相除法求(125,17),以及x,y,使得125x+17y=(125,17).解作辗转相除法:125=7×17+6,17=2×6+5,6=1×5+1,5=5×1,q1=7,r1=6,q2=2,r2=5,q3=1,r3=1,q4=5.由推论1.1,(125,17)=r3=1.利用定理1计算(这里n=3)P0=1,P1=7,P2=2·7+1=15,P3=1·15+7=22,Q0=0,Q1=1,Q2=2·1+0=2,Q3=1·2+1=3,取x=(?1)3?1Q3=3,y=(?1)3P3=?22,则125·3+17·(?22)=(125,17)=1.例2在m个盒子中放若干个硬币,然后以下述方式往这些盒子里继续放硬币:每一次在n(n<m)个盒子中各放一个硬币.证明:若(m,n)=1,那么无论开始时每个盒子中有多少个硬币,经过若干次放硬币后,总可使所有盒子含有同样数量的硬币.5证由于(m,n)=1,所以存在整数x,y,使得mx+ny=1.因此对于任意的自然数k,有1+m(?x+kn)=n(km+y),这样,当k充分大时,总可找出正整数x0,y0,使得1+mx0=ny0.上式说明,如果放y0次(每次放n个),那么在使m个盒子中各放x0个后,还多出一个硬币.把这个硬币放入含硬币最少的盒子中(这是可以做到的),就使它与含有最多硬币的盒子所含硬币数量之差减少1.因此经过若干次放硬币后,必可使所有盒子中的硬币数量相同.5素数与算术基本定理例1写出51480的标准分解式.解我们有51480=2·25740=22·12870=23·6435=23·5·1287=23·5·3·429=23·5·32·143=23·32·5·11·13.例2设a,b,c是整数,证明:(i)(a,b)[a,b]=ab;(ii)(a,[b,c])=[(a,b),(a,c)].证为了叙述方便,不妨假定a,b,c是正整数.(i)设a=pααβ11pα22···p1β2βkk,b=p1p2···pkk,其中p1,p2,···,pk是互不相同的素数,αi,βi(1??i??k)都是非负整数.由推论3.3,有(a,b)=pλ11pλ22···pλkk,λi=min{αi,βi},1??i??k,[a,b]=pμ11pμ22···pμkk,μi=max{αi,βi},1??i??k.由此知∏k(a,b)[a,b]=pλi+μi∏kαi=pmin{αi,βi}+max{αi,βi}∏ki=pii+βi=ab;i=1i=1i=1(ii)设a=∏kpα∏kii,b=∏kpβii,c=pγii,i=1i=1i=1其中p1,p2,···,pk是互不相同的素数,αi,βi,γi(1??i??k)都是非负整数.由推论3.3,有(a,[b,c])=∏kpλii,[(a,b),(a,c)]=∏kpμii,i=1i=16其中,对于1??i??k,有λi=min{αi,max{βi,γi}},μi=max{min{αi,βi},min{αi,γi}},不妨设βi??γi,则min{αi,βi}??min{αi,γi},所以μi=min{αi,γi}=λi,即(a,[b,c])=[(a,b),(a,c)].7。