【#第一文档网# 导语】以下是®第一文档网的小编为您整理的《广东石油化工学院数学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.dywdw.cn/59bfe4d0740bf78a6529647d27284b73f2423696.html
下载此文档
搜索文档
阅读：
文档下载
2022-08-04
