广东石油化工学院数学2009级初等数论复习资料
说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。
1.设r是正奇数,证明:对任意的正整数n,有 n 2|1r 2 r n r。 解 对于任意的正整数a,b以及正奇数k,有 ak bk = (a b)(ak 1 ak 2b ak 3b2 bk 1) = (a b)q, 其中q是整数。记s = 1r 2 r n r,则 2s = 2 (2 r n r) (3 r (n 1)r) (n r 2 r) = 2 (n 2)Q, 其中Q是整数。若n 2s,由上式知n 22,因为n 2 > 2,这是不可能的,所以n 2 |s。2.证明:存在无穷多个正整数a,使得 n4 a(n = 1, 2, 3, ) 都是合数。 解 取a = 4k4,对于任意的nN,有 n4 4k4 = (n2 2k2)2 4n2k2 = (n2 2k2 2nk)(n2 2k2 2nk)。 因为 n2 2k2 2nk = (n k)2 k2 k2, 所以,对于任意的k = 2, 3, 以及任意的nN,n4 a是合数。 3.证明:若a被9除的余数是3,4,5或6,则方程x3 y3 = a没有整数解。 解 对任意的整数x,y,记 x = 3q1 r1,y = 3q2 r2,0 r1, r2 < 3。 则存在Q1, R1, Q2, R2Z,使得 x3 = 9Q1 R1,y3 = 9Q2 R2 , 其中R1和R2被9除的余数分别与r13和r23被9除的余数相同,即 R1 = 0,1或8,R2 = 0,1或8。 (1) 因此 x3 y3 = 9(Q1 Q2) R1 R2 。 又由式(1)可知,R1 R2被9除的余数只可能是0,1,2,7或8,所以,x3 y3不可能等于a 。 4.证明:若n是正整数,则21n4是既约分数。 14n3解 (21n 4, 14n 3) = (7n 1, 14n 3) = (7n 1, 1) = 1。 注:一般地,若(x, y) = 1,那么,对于任意的整数a,b,有 (x, y) = (x ay, y) = (x ay, y b(x ay)) = (x ay, (ab 1)y bx), 因此,xay是既约分数。 (ab1)ybx5.用辗转相除法求(125, 17),以及x,y,使得 125x 17y = (125, 17)。 解 做辗转相除法: 125 = 717 6,q1 = 7,r1 = 6, 17 = 26 5, q2 = 2,r2 = 5, 6 = 15 1, q3 = 1,r3 = 1, 5 = 51, q4 = 5。 由定理4,(125, 17) = r3 = 1。 利用定理2计算(n = 3) 1 / 14 P0 = 1,P1 = 7,P2 = 27 1 = 15,P3 = 115 7 = 22, Q0 = 0,Q1 = 1,Q2 = 21 0 = 2,Q3 = 12 1 = 3, 取x = (1)3 1Q3 = 3,y = (1)3P3 = 22,则 1253 17(22) = (125, 17) = 1。 6.求(12345, 678)。 解 (12345, 678) = (12345, 339) = (12006, 339) = (6003, 339) = (5664, 339) = (177, 339) = (177, 162) = (177, 81) = (96, 81) = (3, 81) = 3。 7.写出51480的标准分解式。 解 我们有 51480 = 225740 = 2212870 = 236435 = 2351287 = 2353429 = 23532143 = 233251113。 8.求最大的正整数k,使得10k199!。 解 由定理3,199!的标准分解式中所含的5的幂指数是 [199][199][199]55253所以,所求的最大整数是k = 47。 9.设x与y是实数,则 = 47, [2x] [2y] [x] [x y] [y]。 (1) 解 设x = [x] ,0 < 1,y = [y] ,0 < 1,则 [x] [x y] [y] = 2[x] 2[y] [ ], (2) [2x] [2y] = 2[x] 2[y] [2] [2]。 (3) 如果[ ] = 0,那么显然有[ ] [2] [2]; 如果[ ] = 1,那么与中至少有一个不小于1,于是 2[2] [2] 1 = [ ]。 因此无论[ ] = 0或1,都有[ ] [2] [2],由此及式(2)和式(3)可以推出式(1)。 10.若a > 1,a n 1是素数,则a = 2,并且n是素数。 解 若a > 2,则由 an 1 = (a 1)(an 1 an 2 1) 可知a n 1是合数。所以a = 2。 若n是合数,则n = xy,x > 1,y > 1,于是由 2xy 1 = (2x 1)(2x(y 1) 2x(y 2) 1) 以及2x 1 > 1可知2n 1是合数,所以2n 1是素数时,n必是素数。 注:若n是素数,则称2n 1是Mersenne数。 11.求N =an1an2a1a0被7整除的条件,并说明1123456789能否被7整除。 a1a0a2a1a0100a5a4a3103(mod7),。 解 100 1,101 3,102 2,103 1 (mod 7),因此 Nan1an2即 a2a1a0a5a4a3a8a7a67N 7a2a1a0a5a4a3a8a7a62 / 14 由于 789 456 123 1 = 455,7455, 所以71123456789。 12.说明2251是否被641整除。 解 依次计算同余式 22 4,24 16,28 256,216 154,232 1 (mod 641)。 因此 2251 0 (mod 641), 即6412251。 13.求(25733 46)26被50除的余数。 解 利用欧拉定理有 (25733 46)26 (733 4)26 = [7(72)16 4]26 [7( 1)16 4]26 = (7 4)26 326 = 3(35)5 3(7)5 = 37(72)2 21 29 (mod 50), 即所求的余数是29。 14.求n =777的个位数。 解 我们有 71 3,72 1,74 1 (mod 10), 因此,若 77 r (mod 4), 则 n =777 77 (mod 10)。 现在77 (1)7 1 3 (mod 4),所以由式(1)得到 n =777 73 (3)3 7 3 (mod 10), 即n的个位数是3。 注:一般地,若求abc对模m的同余,可分以下步骤进行: (ⅰ) 求出整数k,使ak 1 (mod m); (ⅱ) 求出正整数r,r < k,使得bc r (mod k); (ⅲ) abc a r (mod m)。 15.证明:若n是正整数,则1342n + 1 3 n + 2 。 解 由 42n + 1 3 n + 2 = 442n 93 n = 416n 93 n 43n 93 n = 133 n 0 (mod 13) 得证。 16.证明:若2|a,n是正整数,则 a2n 1 (mod 2n + 2)。 解 设a = 2k 1,当n = 1时,有 a2 = (2k 1)2 = 4k(k 1) 1 1 (mod 23), 即式(4)成立。 设式(1)对于n = k成立,则有 a2k 1 (mod 2k + 2) a2k= 1 q2k + 2, 3 / 14 (1) (1) 其中qZ,所以 = (1 q2k + 2)2 = 1 q 2k + 3 1 (mod 2k + 3), 其中q 是某个整数。这说明式(4)当n = k 1也成立。 由归纳法知式(1)对所有正整数n成立。 17.设n的十进制表示是13xy45z,若792n,求x,y,z。 解 因为792 = 8911,故 792n 8n,9n及11n。 我们有 以及 8n 845z z = 6, a2k19n 91 3 x y 4 5 z = 19 x y 9x y 1, (1) 11n 11z 5 4 y x 3 1 = 3 y x 113 y x。 (2) 由于0 x, y 9,所以由式(1)与式(2)分别得出 x y 1 = 9或18, 3 y x = 0或11。 这样得到四个方程组: xy1a, 3yxb其中a取值9或18,b取值0或11。在0 x, y 9的条件下解这四个方程组,得到x = 8,y = 0,z = 6。 18.设整数n 2,证明: 1in(i,n)1i1n(n), 21n(n)。 2即在数列1, 2, , n中,与n互素的整数之和是解 设在1, 2, , n中与n互素的(n)个数是 a1, a2, , a(n),(ai, n) = 1,1 ai n 1,1 i (n), 则 (n ai, n) = 1,1 n ai n 1,1 i (n), 因此,集合{a1, a2, , a(n)}与集合{n a1, n a2, , n a(n)}是相同的,于是 a1 a2 a(n) = (n a1) (n a2) (n a(n)), 2(a1 a2 a(n)) = n(n), 因此 a1 a2 a(n) =19.设nN,证明: (ⅰ) 若n是奇数,则(4n) = 2(n); (ⅱ) (n) =1n(n)。 21n的充要条件是n = 2k,kN; 24 / 14 (ⅲ) (n) =n的充要条件是n = 2k3l,k, lN; (ⅳ) 若6n,则(n) 131n; 313(ⅴ) 若n 1与n 1都是素数,n > 4,则(n) n。 解 (ⅰ) 我们有 (4n) = (22n) = (22)(n) = 2(n); (ⅱ) 若n = 2k,则 (2k) =2k(1若(n) =1)2k11n, 221n,设n = 2kn1,2|n1,则由 21n= (n) = (2kn1) = (2k)(n1) =2k 1(n1) 21k(n1)1(n1) =2n1 n2n12n11l)3(11)1n。 233推出(n1) = n1,所以n1 = 1,即n = 2k; (ⅲ) 若n = 2k3l,则 (n) = (2k)(3l) =2k(1|n1,则由 若(n) =n,设n = 2k3ln1,61311(n1) n(n)(2k3ln1)(2k)(3l)(n1)n33n1推出(n1) = n1,所以n1 = 1,即n = 2k3l; |n1,则 (ⅳ) 设n = 2k3ln1,6(n) = (2k)(3l)(n1) =2k3l(n1)131kl123n1n; 33(ⅴ) 因为n > 4,所以n 1与n 1都是奇素数,所以n是偶数。 因为n 1 > 3,所以n 1与n 1都不等于3,当然不被3整除,所以3n,因此6n。再由上面已经证明的结论(ⅳ),即可得到结论(ⅴ)。 |1n 2n 3n 4n的充要条件是4n。 20.设n是正整数,则5解 因为(5) = 4,所以,由定理2 k4 1 (mod 5),1 k 4。 因此,若n = 4q r,0 r 3,则 1n 2n 3n 4n 1r 2r 3r 4r 1r 2r (2)r (1)r (mod 5),(1) 用r = 0,1,2,3,4分别代入式(1)即可得出所需结论。 21.将211 1 = 2047分解因数。 解 由例5,若p211 1,则p 1 (mod 22),即p只能在数列 23,45,67,,22k 1, 5 / 14 中。逐个用其中的素数去除2047,得到 232047,2047 = 2389。 方程x2 dy2 = 1的解。 22.求不定方程3x 6y = 15的解。 解 (3, 6) = 315,所以方程有解。 由辗转相除法(或直接观察),可知x = 1,y = 1是 3x 6y = 3 的解,所以x0 = 5,y0 = 5是原方程的一个解。由定理2,所求方程的解是 x52t5t, tZ。 y23.求不定方程3x 6y 12z = 15的解。 解 原方程等价于 x 2y 4z = 5。 依次解方程 t 4z = 5, x 2y = t, 分别得到 t14u, uZ, z1uxt2vytv, vZ。 将式(2)与式(3)中的t消去,得到 x14u2vy14uv, u, vZ。 z1u24.将1930写成三个分数之和,它们的分母分别是2,3和5。 解 设 1930x2y3z5, 则 15x 10y 6z = 19。 依次解方程 5t 6z = 19, 15x 10y = 5t, 得到 t16u, uz45uZ, xt2v, vZ。 yt3v6 / 14 (1) (2) (3) (1) (2) 从式(1)与式(2)中消去t,得到 x16u2vy16u3v, u, vZ。 z45u取u = 0,v = 0,得到x = 1,y = 1,z = 4,因此 19114。 3023525. 甲物每斤5元,乙物每斤3元,丙物每三斤1元,现在用100元买这三样东西共100斤,问各买几斤? 解 设买甲物x斤,乙物y斤,丙物z斤,则 5x 3y 13z = 100, x y z = 100。 消去z,得到 7x 4y = 100。 显然x = 0,y = 25是方程(1)的解,因此,方程(18)的一般解是 x4ty257t , tZ 因为x 0,y 0,所以 0 t 3。 即t可以取值t1 = 0,t2 = 1,t3 = 2,t4 = 3。相应的x,y,z的值是 (x, y, z) = (0, 25, 75),(4, 18, 78),(8, 11, 81),(12, 4, 84)。 26.求不定方程x 2y 3z = 7的所有正整数解。 解 依次解方程 t 3z = 7, x 2y = t, 得到 t13uz2u, uZ, xt2vyv, vZ。 从上式中消去t,得到 x13u2vyv, u, vZ。 z2u要使x 1,y 1,z 1,则应有 3u 2v 0,v 1,1 u 0。 所以 3u 2v 2,u 1 23 u 1, 7 / 14 (1) (1) (2) 即 u = 1。由此及式(2),有 3 2v 0,v 1 2 v 1, 3所以v = 1。将u = 1,v = 1代入式(1),得到原方程的唯一一组正整数x = 2,y = 1,z = 1。 27.解同余方程 325x 20 (mod 161) (1) 解 同余方程(1)即是 3x 20 (mod 161)。 解同余方程 161y 20 (mod 3), 2y 1 (mod 3), 得到y 2 (mod 3),因此方程(1)的解是 x 2021613= 114 (mod 161)。 27.解同余方程6x 7 (mod 23)。 解 依次得到 6x 7 (mod 23) 5x 73 2 (mod 23) 3x 24 8 (mod 23) 2x 8(7) 10 (mod 23) x 5 (mod 23)。 28.求整数n,它被3,5,7除的余数分别是1,2,3。 解 n是同余方程组 n 1 (mod 3),n 2 (mod 5),n 3 (mod 7) 的解。在孙子定理中,取 m1 = 3,m2 = 5,m3 = 7,m = 357 = 105, M1 = 35,M2 = 21,M3 = 15, M1 = 1,M2 = 1,M3 = 1, 则 n 135(1) 2211 3151 52 (mod 105), 因此所求的整数n = 52 + 105t,tZ。 29.解同余方程 5x2 6x 49 0 (mod 60)。 解 因为60 = 345,所以,同余方程(15)等价于同余方程组 5x2 6x 49 0 (mod 3) 5x2 6x 49 0 (mod 4) 5x2 6x 49 0 (mod 5)。 分别解同余方程(16),(17),(18)得到解 x1(1) 1,x2(1) 1 (mod 3), x1(2) 1,x2(2) 1 (mod 4), x1(3) 1 (mod 5), 这样,同余方程(1)的解x可由下面的方程组决定: x a1 (mod 3),x a2 (mod 4),x a3 (mod 5), 其中a1 = 1或 1,a2 = 1或 1,a3 = 1。利用孙子定理,取 m1 = 3,m2 = 4,m3 = 5,m = 60, M1 = 20,M2 = 15,M3 = 12, 8 / 14 (1) (2) (3) (4) M1 = 2,M2 = 1,M3 = 3, 则 x 40a1 15a2 36a3 (mod 60)。 将a1,a2,a3所有可能的取值代入上式,得到方程(1)的全部解是 x1 401 151 361 1 (mod 60), x2 40(1) 151 361 19 (mod 60), x3 401 15(1) 361 31 (mod 60), x4 40(1) 15(1) 361 11 (mod 60)。 30.解同余方程 x3 3x 14 0 (mod 45)。 解 原同余方程等价于同余方程组 x3 3x 14 0 (mod 9), (1) x3 3x 14 0 (mod 5)。 (2) 先解同余方程(1)。容易验证,同余方程x3 3x 14 0 (mod 3)的解是x 2 (mod 3)。 令x = 2 3t并代入方程(7),得到 (2 3t)3 3(2 3t) 14 0 (mod 9), (3) 容易看出,这是一个对于任何整数t都成立的同余式,所以,方程(9)的解是t 0,1,2 (mod 3),于是方程(1)的解是 x 2,5,8 (mod 9)。 (4) 再解同余方程(2)。用x = 0,1,2,3,4去验证,得到(2)的解是 x 1,2 (mod 5)。 因此,原同余方程的解是下面六个同余方程组的解: x a1 (mod 9), a1 = 2,5,8, x a2 (mod 5), a2 = 1,2。 利用孙子定理解这六个方程组,记 m1 = 9,m2 = 5,m = 45,M1 = 5,M2 = 9,M1 = 2,M2 = 1, 则 x 10a1 9a2 (mod 45)。 将a1和a2的不同取值代入,得到所求的解是 x1 102 91 11 (mod 45), x2 102 92 2 (mod 45), x3 105 91 41 (mod 45), x4 105 92 32 (mod 45), x5 108 91 26 (mod 45), x6 108 92 17 (mod 45)。 31.解同余方程 2x2 13x 34 0 (mod 53)。 (1) 解 容易验证,同余方程 2x2 13x 34 0 (mod 5) (2) 有两个解x 1,2 (mod 5)。 令 x = 1 5t, (3) 代入同余方程 2x2 13 34 0 (mod 52), (4) 得到 9 / 14 2(1 5t)2 13(1 5t) 34 0 (mod 25), 45 45t 0 (mod 25), 9t 9 (mod 5),t 1 (mod 5)。 (5) 于是,将式(5)与式(3)联合,得到方程(4)的解 x = 1 5(1 5t1) = 4 25t1,t1Z。 (6) 将式(6)中的x代入同余方程(1),得到 2(4 25t1)2 13(4 25t1) 34 0 (mod 53), 50 725t1 0 (mod 53), 2 29t1 0 (mod 5), t1 2 (mod 5)。 将上式与(6)联合,得到同余方程(1)的一个解 x = 4 25t1 = 4 25(2 5t2) 54 (mod 53)。 (ⅱ) 从同余方程(2)的另一个解 x 2 (mod 5)出发利用上述方法,可以求出同余方程(11)的另一个解。(略,请读者补足)。 32.判定同余方程2x3 3x 1 0 (mod 7)是否有三个解。 解 因为24 1 (mod 7),所以,原方程与 42x3 43x 4 0 (mod 7) 即 x3 2x 3 0 (mod 7) 等价。由于 x7 x = ( x3 2x 3)(x4 2x2 3x 4) 12x2 16x 12, 所以,原方程的解数小于3。 33.解同余方程 3x14 4x10 6x 18 0 (mod 5)。 解 由Fermat定理,x5 x (mod 5),因此,原同余方程等价于 2x2 x 3 0 (mod 5)。 (1) 将x 0,1,2 (mod 5)分别代入方程(1)进行验证,可知这个同余方程解是x 1 (mod 5)。 34.判断方程x2 5 (mod 11)有没有解。 解 因为 1115()52555545321 (mod 11), 11方程有解。 35.已知563是素数,判定方程x2 429 (mod 563)是否有解。 解 利用已有的定理,有 (429)(31113)(3)(11)(13)56356356356356331563111156311315631563563(1)22()(1)22()(1)22(563) 31113224()()()(1)(1)1。31113方程有解。 【例5】判断3是否是模17的平方剩余。 10 / 14 17131317222(解)=1==-1 1733所以,3是模17的平方非剩余。(不但如此,17也是3的平方非剩余,即2是3的平方非剩余) 【例6】判断同余方程x≡137(mod 227)是否有解。 (解)已知137与227均为奇数,所以 22713711372279022=1= 22713713722325255=== 137137137137=1137151221372==-1 55所以,方程无解。 2137901235另法: ==2272272272272271512522722=-=1 2272275==-1 【例7】判断同余方程x≡-1(mod 365)是否有解,若有解,求解数。 (解)由于365=5·73,所以 2x12x≡-1(mod 365) 2x1225mod5 mod7311==1 573所以方程有解,且解数为4。 【例8】判断同余方程x≡2(mod 3599)是否有解,若有解,求解数。 (解)由于3599=59·61,所以 211 / 14 2x22x≡2(mod 3599) 2x2mod59 mod61因为59≡3(mod 8),即22x=-1,故方程≡2(mod 59)无解,从而原方程无解。 59x2 12345 (mod 3371) (1) 38.已知3371是素数,判断方程 是否有解。 解 利用Jacobi符号的性质,有 (12345)(2232)(33713371(1)33712182)(4)(279)33713371337133711279122279 279123123()(1)22(279)2792323131323()(1)22()1。233因此,方程(1)无解。 39.判断137是否为模227的平方剩余。 解:首先,227是素数。其次,计算 (1)(23)13722712≡-1(mod 227) 所以,137是模227的平方非剩余。 40.求ord33(4)、ord33(5)、ord33(7)的值。 (解)(33)=20,故由推论知只需计算4、5、7(mod 33)即可,其中i=1, 2, 4, 5, 10。 10545≡1(mod 33),5≡23(mod 33),5≡1(mod 33), 1075≡10(mod 33),7≡1(mod 33) iii所以,ord33(4)=5,ord33(5)=10,ord33(7)=10。 41.由ord17(5)=16可知5是模17的原根,由原根5就可以求出17的所有原根: 3551≡5(mod 17),5≡6(mod 17),5≡14,(mod 17) 11957≡10(mod 17),5≡12(mod 17),5≡11,(mod 17) 15513≡13(mod 17),5≡6(mod 17) 42.求出模25的所有原根。 12 / 14 (解)首先,(25)=20,((25))=(20)=8。故25若有原根,则其必有8个原根。 计算2≡7(mod 25),2≡24≡-1(mod 25),所以2是模25的一个原根。 20的简化剩余系为{1, 3, 7, 9, 11, 13, 17, 19},25的所有原根为: 51021≡2,23≡8,27≡3,29≡12,211≡23, 213≡17,217≡22,219≡13(mod 17) 即模25的原根为:2, 3, 8, 12, 13, 17, 22, 23。 43.求模41的所有原根。 (解)(m)=(41)=40=2·5,q1=2,q2=5,mq1=20,mq2=8,故3只需验证 g8,g20≡1? (mod 41) 验算:2≡10,2≡1(mod 41),2不是原根。 82038≡1(mod 41),3不是原根。 420=240≡1(mod 41),4不是原根。 58≡18,520≡1(mod 41),5不是原根。 68≡10,620≡40≡-1(mod 41),6是原根。 再由(41)=40的简化剩余系为 1,3,7,9,11,13,17,19, 21,23,27,29,31,33,37,39 共有((41))= (40)=16个数,那么原根为 61≡6,63≡11,……,639≡7(mod 41) 244.设模数m=41=1681,求模m的原根。 (解)已知6是模41的原根,故由2,6或6+41=47是模41=1681的原根。计算 2640≡143≡1+41·3(mod 412), 4740≡1518≡1+41·37(mod 412) 即 240640≠1(mod 412),47≠1(mod 41) 2所以6和47都是模1681的原根(因(41)=1640=41·40)。 另由定理5.2.3,6和47是所有模41的原根。 13 / 14 45.设模数m=2·41=3362,求模m的原根。 241(解)由44题知6和47是模41的原根,故由定理4知,6+41=1687和47是模2·=3362的原根。 22214 / 14 本文来源:https://www.wddqw.com/doc/59bfe4d0740bf78a6529647d27284b73f2423696.html