研究生基础数学考试复习资料 数论练习题

1、一、 整除理论1 证明：任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。2 设p是n的最小素约数，n = pn1，n1 > 1，证明：若p >，则n1是素数。证明：设不然，n1 = n2n3，n2 ³ p，n3 ³ p，于是n = pn2n3 ³ p3，  即p £，矛盾。3 设3½a2 + b2，证明：3½a且3½b。 写a = 3q1 + r1，b = 3q2 + r2，r1, r2 = 0, 1或2，   由3½a2 + b2

2、= 3Q + r12 + r22知r1 = r2 = 0，即   3½a且3½b4 证明：对于任意给定的n个整数，必可以从中找出若干个作和，使得这个和能被n整除。设给定的n个整数为a1, a2, L, an，作 s1 = a1，s2 = a1 + a2，L，sn = a1 + a2 + L + an， 如果si中有一个被n整除，则结论已真，否则存在si，sj，i < j，   使得si与sj被n除的余数相等，于是n½sj - si = ai + 1 + L + aj 5 设a，b，c是正整数，证明： 因为 ，故只须证明

3、(a, b, c)(ab, bc, ca) = (a, b)(b, c) (c, a)，此式用类似于例3的方法即可得证。6 设k是正奇数，证明：1 + 2 + + 9½1k + 2k + + 9k。设s = 1k + 2k + L + 9k，则由2s = (1k + 9k) + (2k + 8k) + L + (9k + 1k) = 10q1及2s = (0k + 9k) + (1k + 8k) + L + (9k + 0k) = 9q2得10½2s和9½2s，于是有90½2s，从而1 + 2 + L + 9 = 45½s7 设a，b是正整数，

4、证明：(a + b)a, b = ab, a + b。只须证 ，即只须证(b, a + b) = (a, b)，此式显然。8 用扩展欧几里德算法法求整数x，y，使得1387x - 162y = (1387, 162)。作辗转相除：1387 = (-162)×(-8) + 91，-162 = 91×(-2) + 20，91 = 20×4 + 11，20 = 11×1 + 9，11 = 9×1 + 2，9 = 2×4 + 1，2 = 1×2 + 0，由此得n = 6，q1 = -8，q2 = -2，q3 = 4，q4 = 1，q

5、5 = 1，q6 = 4，x = (-1)n-1Qn = 73，y = (-1)nPn = 625，又(1387, 162) = rn = 1，故1387×73 - 162×625 = 1 = (1387, 162)9. 若四个整数2836，4582，5164，6522被同一个大于1的整数除所得的余数相同，且不等于零，求除数和余数各是多少。设除数为d，余数为r，则由d½4582 - 2836 = 1746，d½5164 - 4582 = 582，d½6522 - 5164 = 1358知d½(1746, 582, 1358) = 19

6、4，由此得d = 97，r = 23或d = 194，r = 1209 证明：在1, 2, L, 2n中任取n + 1数，其中至少有一个能被另一个整除。写i = ，i = 1, 2, L, 2n，则li为1, 2, L, 2n中的奇数，即li只能取n个数值，在n + 1个这样的数中，必存在li = lj（i ¹ j），于是易知i与j成倍数关系10 求最大的正整数k，使得10k½199!。解 由定理3，199!的标准分解式中所含的5的幂指数是 = 47，而所含2的幂指数>47，所以，所求的最大整数是k = 47。11 设n是正整数，则。   

7、;解 首先，我们有                        <，所以，                .          &#

8、160;                           若上式中的等式不成立，即            ，          

9、0;                   则存在整数a,使得, 因此            ,            ,      

10、0;     ,所以            a2-2n-1=2n+1,a2=4n+2.                              &#

11、160;       但是，无论2|n 或2n,式(10)都不能成立，这个矛盾说明式（9）不能成立，即式(7)成立.12 设n是正整数，x是实数，证明：= n。由例4得 = 2x- x，于是=n = n 。 例4 设x是正数，n是正整数，则            x+x+x+ . . . +x+=nx.    解 设x=x+ , , 0in-1,则     

12、       x+x+x+ . . . +x+= nx+i=nx+n            =n(x+)=nx.13 证明：若2n - 1是素数，则n是素数。设不然，则n = n1n2， 1 < n1 < n，则2n - 1 = < 2n + 1，表明2n - 1是合数，矛盾。同余1 求81234被13除的余数。因为82 º -1(mod 13)，所以81234 = (82)617 º (

13、-1)617 º -1 º 12 (mod 13)，即81234被13除的余数是12。2 已知99½，求a与b由 得a + b = 6或a + b = 15，从 得a - b = -2或a - b = 9，于是解关于a，b的方程组得a = 2，b = 4。3 求n =的个位数我们有            71-3, 72 -1, 74 1 (mod 10), 因此, 若       &#

14、160;    77 r (mod 4),                                         (3)则   &

15、#160;        n= 7r (mod 10).                                    (4)    现在,

16、71-1,72 1, 77 3 (mod 4), 所以, 由式(4)可知            n= 73 -7 3 (mod 10),即n的个位数是3.4 证明：若n是正整数，则13½42n + 1 + 3 n + 2由            42n+1+3n+2=        

17、60;   （mod 13）得证.5 设m > 0是偶数，a1, a2, , am与b1, b2, , bm都是模m的完全剩余系，证明：a1 + b1, a2 + b2, , am + bm不是模m的完全剩余系因为1,2, ,m与a1, ,am都是模m的完全剩余系,所以            (mod m).             

18、;         (10)同理,             (mod m).                           

19、          (11)如果a1+b1, ,am+bm是模m的完全剩余系,那么也有            (mod m).    联合上式与式(10)和(11),得到            0(mod m)，这是不可能的,所以a1+b1, ,am

20、+bm不能是模m的完全剩余系.6 证明：若2p + 1是奇素数，则(p!)2 + (-1)p º 0 (mod 2p + 1)由威尔逊定理知 -1 º (2p)! = p!(p + 1)L(2p) º (-1)p(p!)2(mod 2p + 1)，由此得(p!)2 + (-1)p º 0 (mod 2p + 1)。7 证明Wilson定理的逆定理：若n > 1，并且(n - 1)! º -1 (mod n)，则n是素数设不然，n = n1n2，1 < n1 < n，由(n - 1)! º -1 (mod n1)得0

21、º -1 (mod n1)，矛盾。8 设m > 1，(a, m) = 1，x1, x2, xj(m)是模m的简化剩余系，证明：。其中x表示x的小数部分。写axi = mqi + ri，0 £ ri < m，由xi通过模m的简化剩余系知ri通过模m的最小非负简化剩余系，于是由例1得。例1 设整数n³ 2,证明 即,在数列1,2, ,n中,与n互素的整数之和是     解 设在1,2, ,n中与n互素的j(n)个数是        

22、60;   a1, ,aj(m), (ai,n)=1, 1 ai n-1, 1 i(n),则            (n-ai,n)=1,1n-ain-1, 1£ ij(n),因此，集合a1, ,aj(m)与集合n-a1,¼ ,n-aj(m)是相同的，于是            a1+a2+ +aj(m)=(n-a1)+(n-a2)+&#

23、188; +(n-aj(m),            2(a1+ +aj(m)=nj(n),            a1+ +aj(m)= (n).9 设m与n是正整数，证明：j(mn)j(m, n) = (m, n)j(m)j(n) 设 ，则由此得j(mn)j(m, n) = (m,n) = (m, n)j(m)j(n)。10 设x1, x2, xj(m)是模m的简化剩余系，

24、则(x1x2xj(m)2 º 1 (mod m)设x1, x2, xj(m)是模m的简化剩余系，则(x1x2xj(m)2 º 1 (mod m)。解 记P = x1x2xj(m)，则(P, m) = 1。又记yi =，1 £ i £ j(m)，则y1, y2, , yj(m)也是模m的简化剩余系，因此(mod m)，再由Euler定理，推出P2 º Pj(m) º 1 (mod m)。11 证明：1978103 - 19783能被103整除。因103 = 2353，显然1978103 - 19783 º 0 (mod 23)

25、，再由1978100 º 1 (mod 53)得1978103 - 19783 º 0 (mod 53)，故1978103 - 19783 º 0 (mod 103)。12 设p，q是两个不同的素数，证明：pq - 1 + qp - 1 º 1 (mod pq)。由费马定理qp - 1 º 1 (mod p)，pq - 1 º 1 (mod q)，pq - 1 + qp - 1 º 1 (mod p)，pq - 1 + qp - 1 º 1 (mod q)，故pq - 1 + qp - 1 º 1 (mo

26、d pq)。13 计算12996227(mod 37909)二、 同余方程1 解同余方程 325x º 20 (mod 161)解：方程即是             3x20(mod 161).    解同余方程             161y-20(mod 3), 即     

27、;       2y1(mod 3),得到 y2 (mod 3),因此,方程(6)的解是x=114 (mod 161).2 证明：同余方程a1x1 + a2x2 + + anxn º b (mod m)有解的充要条件是(a1, a2, , an, m) = d½b。若有解，则恰有d×mn -1个解，mod m必要性显然，下证充分性。当n = 1时，由定理2知命题成立。假设n = k时结论已真，考虑a1x1 + a2x2 + L + akxk + ak + 1xk + 1 º b (mod m)，

28、令(a1, a2, L, ak, m) = d1，(d1, ak + 1) = d，因为同余方程ak + 1xk + 1 º b (mod d1)有解，其解数为d，mod d1，记m = d1m1，则解数为dm1，mod m。现在固定一个解xk + 1，由归纳假定知a1x1 + a2x2 + L + akxk º b - ak + 1xk + 1 (mod m)有解，其解数为d1 mk -1，mod m，从而a1x1 + a2x2 + L + akxk + ak + 1xk + 1 º b (mod m)有解，其解数为dm1×d1mk -1 = d

29、15;mk，mod m。由归纳原理知命题对于一切n ³ 1成立。3 解同余方程f(x) = 3x2 + 4x - 15 º 0 (mod 75)因75 = 3×52，先解f(x) º 0 (mod 3)，用逐一代入法得解x º 0 (mod 3)；再解f(x) º 0 (mod 52)，用逐一代入法得f(x) º 0 (mod 5)的解为x º 0，2 (mod 5)，对于x º 0 (mod 5)，令x = 5t代入f(x) º 0 (mod 25)得t º 2 (mod 5)，于是

30、x = 5(2 + 5t2) = 10 + 25t2，即x º 10 (mod 25)是f(x) º 0 (mod 25)的一个解，对于x º 2 (mod 5)，令x = 2 + 5t代入f(x) º 0 (mod 25)得t º 4 (mod 5)，于是x = 2 + 5(4 + 5t2) = 22 + 25t2，即x º 22 (mod 25)是f(x) º 0 (mod 25)的一个解；最后构造同余方程组x º b1 (mod 3)，x º b2 (mod 25)，b1 = 0，b2 = 10，2

31、2，由孙子定理得f(x) º 0 (mod 75)的两个解x º 10，72 (mod 75)。4 4x20 + 3x12 + 2x7 + 3x - 2 º 0 (mod 5)原同余方程等价于2x4 + 2x3 + 3x - 2 º 0 (mod 5)，将x = 0，±1，±2 代入，知后者有解x º ±1 (mod 5)。5 判定 2x3 - x2 + 3x - 1 º 0 (mod 5)是否有三个解2x3 - x2 + 3x - 1 º 0 (mod 5)等价于x3 - 3x2 + 4x -

32、 3 º 0 (mod 5)，又x5 - x = (x3 - 3x2 + 4x - 3)(x2 + 3x + 5) + (6x2 - 12x + 15)，其中r(x) = 6x2 - 12x + 15的系数不都是5的倍数，故原方程没有三个解；6 求出模23的所有的二次剩余和二次非剩余模23的所有的二次剩余为x º 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 (mod 23)，二次非剩余为x º 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22 (mod 23)。7 设p是奇素数，证明：模p的所有二次剩余的

33、乘积与对模p同余设x1, x2, L, xk为模p的所有二次剩余，则x1x2Lxk º 1222L (mod p)。8 设p是奇素数，证明：模p的两个二次剩余的乘积是二次剩余；两个二次非剩余的乘积是二次剩余；一个二次剩余和一个二次非剩余的乘积是二次非剩余。设a，b为模p的二次剩余，有 º 1×1 º 1 (mod p)，再设c，d为模p的二次非剩余，有 º (-1)(-1) º 1 (mod p)，以及º 1×(-1) º 1 (mod p)知结论成立。9 设p，q是两个不同的奇素数，且p = q + 4

34、a，证明：由p = q + 4a知p，q同为4k + 1或同为4k + 3，当p，q同为4k + 1时，有 ，当p，q同为4k + 3时，有 。10 a，b，c是正整数，(a, b) = 1，2b，b < 4ac，求的关系若a为奇数，有 ，若a为偶数，于是4ac - b与b同为8k ± 1或同为8k ± 3，即 ，设a = 2aa1，a1为奇数，有 = 。三、 原根与指标1 求模14的全部原根x º 3，5 (mod 14)是模14的全部原根。2 设m > 1，模m有原根，d是j(m)的任一个正因数，证明：在模m的简化剩余系中，恰有j(d)个指数为d的

35、整数，并由此推出模m的简化剩余系中恰有j(j(m)个原根因g1, g2, L, gj(m)构成模m的简化剩余系，由d = dm(gl) = 得 ，则(l,j(m) = ，1 £ l £ j(m) Û (t, d) = 1，1 £ t £ d，故恰有j(d)个t，使得(t, d) = 1，从而知故恰有j(d)个l，使得dm(gl) = d。特别地，取d = j(m)知模m的简化剩余系中恰有j(j(m)个原根。3 设p = 2n + 1是一个奇素数，证明：模p的全部二次非剩余就是模p的全部原根在模p的简化剩余系中有 = 2n -1个二次非剩余，在模

36、p的简化剩余系中有j(j(p) = j(2n) = 2n -1个原根，又设g是模p原根，则 º -1 (mod m)，即g是模p的二次非剩余。4 设m ³ 3, g1、g2都是模m的原根, 则g = g1g2不是模m的原根存在一个l，(l,j(m) = 1，使得g2 º g1l (mod m)，于是g1g2 º g1l +1 (mod m)，又由m ³ 3知j(m)是偶数，l是奇数，l + 1是偶数，(l + 1,j(m) ¹ 1，故g = g1g2不是模m的原根5 设p是奇素数，证明：当且仅当p - 1n时，有1n + 2n + +

37、 (p - 1)n º 0 (mod p)当p - 1½n时，则1n + 2n + L + (p - 1)n º p - 1 0 (mod p)，当p - 1 n时，设g是p的一个原根，则1n + 2n + L + (p - 1)n º (1×g)n + (2×g)n + L + (p - 1)gn º 1n + 2n + L + (p - 1)ngn (mod p)，得1n + 2n + L + (p - 1)n(1 - gn) º 0 (mod p)，由(1 - gn) 0 (mod p)知1n + 2n +

38、L + (p - 1)n º 0 (mod p)。6 求8次同余方程x8 º 23 (mod 41) 因为d=(n, j(m)=(8, j(41)=(8, 40)=8, ind23=36又36不能被8整除，所以同余方程无解。四、 扩域定理1令E是F的一个扩域，而S1，S2是E的两个子集，那么F(S1)(S2)=F(S1S2)= F(S2)(S1)证明 F(S1)(S2)是一个包含F，S1，S2的E的子域，而F(S1S2)是包含F和S1S2的E的最小子域。因此F(S1)(S2)F(S1S2) (1)另一方面，F(S1S2)是包含F，S1，S2的E的子域，因而是包含F(S1)和

39、S2的E的子域。但F(S1)(S2) 是包含F(S1)和S2的E的最小子域。因此F(S1)(S2)F(S1S2) (2)由(1)(2)得F(S1)(S2)=F(S1S2)。同样可以得到F(S1S2)= F(S2)(S1)。定理得证。定理5 给定域F的一元多项式环Fx的一个n次多项式f(x)，一定存在f(x)在F上的分裂域E。证明 用归纳法：当n=1时，E=F即可。假设n£m时结论也成立。当n=m+1时，若f(x)在Fx上可约，则存在次数小于m的多项式f1(x)和g1(x)使得f(x)= f1(x)g1(x)，由归纳假设知存在f1(x)在F上的分裂域E1，包含f1 (x)的所有根1,

40、2, , n1。g1(x)视为F(1, 2, , n1)上的次数小于n的多项式，故存在g1(x)在F(1, 2, , n1)上的分裂域E，包含g1 (x)的所有根。从而E含有f(x)的所有根，是f(x)在F上的分裂域。若f(x)在Fx上不可约，由定理3，存在F的单代数扩域K(K=F()含有f(x)的一个根。于是在Kx中f(x)=(x-)g(x)，再利用归纳假设，由于g(x)的次数为n-1，故存在g(x)在K上的分裂域E，包含g (x)的所有根，从而E也含有f(x)在F上的所有根，是f(x)在F上的分裂域。证毕。定理6 设是Fx中一个n次不可约多项式f(x)的一个根，则F()是F上的有限扩域。证

41、明 因为F()中每一元都可以表示成F上次数小于n的的多项式，故1，2，n，是F()的一组生成元，又a0+a1+an-1n-1 = 0可推出ai =0，所以F()是F上的n维向量空间，有一组基为1，2，n-1，即F() 是F上的一个有限扩域，并且(F():F)=n。关于有限扩域，有下列重要结论。定理7 域F的有限扩域一定是F的代数扩域。证明 设(E:F)=n，则存在一组基1，2，n-1，而n+1个向量1，2，n，从而线性相关。即存在n+1个不全为0的aiÎF，使得a0+a1+ann = 0。亦即满足Fx中多项式。故E是F的一个代数扩域。定理8 令K是域F的有限扩域，而E是域K的有限扩域

42、，那么E也是域F的有限扩域，且(E:F)=(E:K)(K:F)。证明 设(K:F)=r，(E:K)=s，而1, 2, , r是向量空间K在域F上的一个基，1, 2, , s是向量空间E在域K上的一个基。下面证rs个元构成向量空间E在域F上的一个基。ij (i=1,2,r; j=1,2,s) (1)显然，向量空间E中任意元素都可以表示rs个元系数为F上元的线性组合。下证(1)中元素在F上线性无关。若，那么。由j，0£j£s在K上的线性无关性可知，(j=1,2,s)。由i，0£i£r在F上的线性无关性可知aij=0，(i=1,2,r; j=1,2,s)。也就

43、是说，(1)的rs个元为E在F上的一组基。六、有限域 定理1 一个有限域E有pn个元素，这里p是E的特征，而n是E在它的素域上的次数。证明 E为有限域，其特征一定为素数p。把E所含的素域记作。因为E只含有限个元，所以它一定是的一个有限扩域，(E：)=n。这样，E的每个元可以唯一的写成a11+ann的形式，这里aiÎ，而1，n是向量空间E在上的一个基。由于只有p个元，所以对于每一个ai有p中选择法，因而E一共有pn个元。定理2 令有限域E的特征为素数p，E所含的素域为，而E有q=pn个元。那么E是多项式xq-x在上的分裂域。任何两个这样的域都是同构的。证明 E的不等于零的元对于乘法来说

44、，做成一个群。这个群的的阶为q-1，单位元是1。所以q-1=1，ÎE，¹0。由于0q=0，所以有q=，ÎE。因此用1，q来表示E的元，在E里多项式 而且显然 E=(1，q)。这样，E是多项式xq-x在上的分裂域。特征为p的素域都同构，而多项式xq-x在同构的域上的分裂域都同构。定理3 令是特征为p的素域，而q=pn (n³1)。那么多项式xq-x在上的分裂域E是一个有q个元的有限域。证明 E=(1，q)，这里i是f(x)= xq-x在域E里的根。由于E的特征是p，f(x)的导数f(x)= pn xq-1-1= -1。所以f(x)与f(x)互素。这样f(x

45、)的q个根都不相同。f(x) 的q个根可以看成E的一个子域E1，这是因为这就是说，仍是f(x)的根而属于E1，因而E1是E的一个子域。但E1含，也含一切i，所以E1就是多项式xq-x在上的分裂域。这样E=E1，而E恰有q个元，得证。以上证明了给定素数p和正整数n，有且只有(在同构意义下)一个恰好含pn个元的有限域存在。有限域通常称作Galois域，有pn个元素的有限域通常记作GF(pn)。定理4 (i) 有限域GF(pn)的子域是GF(pm)的形式，其中m|n。 (ii) 对n的任一因子m，有限域GF(pn)有且仅有一个子域GF(pm)。定理4同上节定理6。这里我们来证明该定理。证明 设T是有

46、限域E= GF(pn)的子域，是E的素域，由E:TT: = E: =n可知T: =m必整除n；T是元素个数为pm的有限域。这样T是xq-x (q=pm)在上的分裂域。注意T是E的子域，故T=aÎE|aq-a=0。这样E中元素个数为pm的子域T有且仅有一个，由xq-x在E中的一切根组成。得证。定理5 一个有限域E是它的素域的一个单扩域。证明 设E含有q个元。E的非零元对E的乘法来说作成一个交换群G，它的阶是q-1。令m是G的元的阶中最大的一个，那么由引理，aim=1，对于任意aiÎG。这就是说，多项式xm-1至少有q-1个不同的根。因此m³q-1，但是由于m整除G的

47、阶，故m £q-1，所以m=q-1。也就是说G有一个元a，它的阶为q-1，因而G是一个循环群(a)。这样E是添加a于所得的单扩域E=(a)。定理得证。 域的乘群的任何有限子群是循环群。证明：设G是域F的有限子乘群，令m是G中所有元素的阶的最小公倍数，由拉格朗日定理G中任意元素的阶均为群G的阶的因子， 因而若设c为G中阶为m的元素，则m|G|。 另一方面，G中的元素均满足方程xm-l=0，而多项式f(x)=xm-lÎFx在F上最多有m个不同的根， 故|G|m，由此得|G|=m，所以G=(c)。利用多项式f(x)=x2-2构造一个有限域，并找出这个域中的本原元。解：这里只给出了

48、构造域的多项式，并未给出构造域所需的欧氏环，因而需要选择一个欧氏环，并保证f(x)为此域中的不可约多项式。 注意到在F3中f(0)=1，f(1)=f(2)=2，因而该多项式是F3x中的一个不可约多项式， 以此可以构造一个具有9个元素的有限域F。域F中的元素都可以看做是二维向量(a,b)，其中a,bÎF3=0,1,2。在域F中注意到x22(mod x2-2)，因而可定义域F中的加法与乘法运算如下：(a1,b1)+(a2,b2)=(a1+a2,b1+b2)。(a1,b1)(a2,b2)=(a1b2+a2b1, b1b2+2a1a2)接下来利用高斯算法寻找这个域中的本原元。首先取1=(1,

49、0)=x，为了计算1的阶，先来计算1=(1,0)=x的各个幂次对f(x)取模的结果x01 (mod x2-2), x1x (mod x2-2), x22 (mod x2-2)x32x (mod x2-2)，x42x21(mod x2-2)，以二维向量表示为 表6-3 1=(1,0)=x各个幂次的向量表示因而1=(1,0)=x的阶为4，即在高斯算法中有t1=4。由于t1q-1=8，因而1不是本原元，接着转至第3步，需要选择一个不是1的幂次的元素，例如可以选=(1,2)=x+2，则2=(x+2)2x(modx2-2)=(1,0)， 类似地可以得到=(1,2)=x+2的各个幂次对f(x)取模的结果的

50、向量表示 表6-4 =(1,2)=x+2的各个幂次的向量表示因而的阶s=8=q-1，则令2=，算法停止；2就是F中的本原元。一、 整除理论1 证明：任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。2 设p是n的最小素约数，n = pn1，n1 > 1，证明：若p >，则n1是素数。3 设3½a2 + b2，证明：3½a且3½b。4 证明：对于任意给定的n个整数，必可以从中找出若干个作和，使得这个和能被n整除。5 设a，b，c是正整数，证明：6 设k是正奇数，证明：1 + 2 + + 9½1k + 2k + + 9k。7 设a，b是正整数，证明：(a + b)a, b = ab, a + b。8 用扩展欧几里德算法法求整数x，y，使得1387x - 162y = (1387, 162)。9 若四个整数2836，4582，5164，6522被同一个大于1的整数除所得的余数相同，且不等于零，求除数和余数各是多少。10 证明：在1, 2, L, 2n中任取n + 1数，其中至少有一个能被另一个整除。11 求最大的正整数k，使得10k½199!。12 设n是正整数，则。13 设n是正整数，x是实数，证明：= n。14 证明：若