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

一、 整除理论1 证明：任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。2 设p是n的最小素约数，n = pn1，n1 1，证明：若p ，则n1是素数。证明：设不然，n1 = n2n3，n2 p，n3 p，于是n = pn2n3 p3， 即p ，矛盾。3 设3a2 + b2，证明：3a且3b。 写a = 3q1 + r1，b = 3q2 + r2，r1, r2 = 0, 1或2， 由3a2 + b2 = 3Q + r12 + r22知r1 = r2 = 0，即 3a且3b4 证明：对于任意给定的n个整数，必可以从中找出若干个作和，使得这个和能被n整除。设给定的n个整数为a1, a2, L, an，作 s1 = a1，s2 = a1 + a2，L，sn = a1 + a2 + L + an， 如果si中有一个被n整除，则结论已真，否则存在si，sj，i 47，所以，所求的最大整数是k = 47。11 设n是正整数，则。解 首先，我们有 ，所以， . 若上式中的等式不成立，即 ， 则存在整数a,使得, 因此 , , ,所以 a2-2n-1=2n+1,a2=4n+2. 但是，无论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,则 x+x+x+ . . . +x+= nx+i=nx+n =n(x+)=nx.13 证明：若2n - 1是素数，则n是素数。设不然，则n = n1n2， 1 n1 n，则2n - 1 = 0是偶数，a1, a2, , am与b1, b2, , bm都是模m的完全剩余系，证明：a1 + b1, a2 + b2, , am + bm不是模m的完全剩余系因为1,2, ,m与a1, ,am都是模m的完全剩余系,所以 (mod m).(10)同理, (mod m). (11)如果a1+b1, ,am+bm是模m的完全剩余系,那么也有 (mod m).联合上式与式(10)和(11),得到 0(mod m)，这是不可能的,所以a1+b1, ,am+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 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)个数是 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)+ +(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的简化剩余系，则(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)，再由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 (mod pq)。13 计算12996227(mod 37909)二、 同余方程1 解同余方程 325x 20 (mod 161)解：方程即是 3x20(mod 161).解同余方程 161y-20(mod 3), 即 2y1(mod 3),得到 y2 (mod 3),因此,方程(6)的解是x=114 (mod 161).2 证明：同余方程a1x1 + a2x2 + + anxn b (mod m)有解的充要条件是(a1, a2, , an, m) = db。若有解，则恰有dmn -1个解，mod m必要性显然，下证充分性。当n = 1时，由定理2知命题成立。假设n = k时结论已真，考虑a1x1 + a2x2 + L + akxk + ak + 1xk + 1 b (mod m)，令(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)有解，其解数为dm1d1mk -1 = dmk，mod m。由归纳原理知命题对于一切n 1成立。3 解同余方程f(x) = 3x2 + 4x - 15 0 (mod 75)因75 = 352，先解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)，于是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，22，由孙子定理得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 - 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的所有二次剩余的乘积与对模p同余设x1, x2, L, xk为模p的所有二次剩余，则x1x2Lxk 1222L (mod p)。8 设p是奇素数，证明：模p的两个二次剩余的乘积是二次剩余；两个二次非剩余的乘积是二次剩余；一个二次剩余和一个二次非剩余的乘积是二次非剩余。设a，b为模p的二次剩余，有 11 1 (mod p)，再设c，d为模p的二次非剩余，有 (-1)(-1) 1 (mod p)，以及 1(-1) 1 (mod p)知结论成立。9 设p，q是两个不同的奇素数，且p = q + 4a，证明：由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 1，模m有原根，d是j(m)的任一个正因数，证明：在模m的简化剩余系中，恰有j(d)个指数为d的整数，并由此推出模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个二次非剩余，在模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 + + (p - 1)n 0 (mod p)当p - 1n时，则1n + 2n + L + (p - 1)n p - 1 0 (mod p)，当p - 1 n时，设g是p的一个原根，则1n + 2n + L + (p - 1)n (1g)n + (2g)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 + 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)和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即可。假设nm时结论也成立。当n=m+1时，若f(x)在Fx上可约，则存在次数小于m的多项式f1(x)和g1(x)使得f(x)= f1(x)g1(x)，由归纳假设知存在f1(x)在F上的分裂域E1，包含f1 (x)的所有根1, 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上的有限扩域。证明 因为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的aiF，使得a0+a1+ann = 0。亦即满足Fx中多项式。故E是F的一个代数扩域。定理8 令K是域F的有限扩域，而E是域K的有限扩域，那么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，0js在K上的线性无关性可知，(j=1,2,s)。由i，0ir在F上的线性无关性可知aij=0，(i=1,2,r; j=1,2,s)。也就是说，(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的不等于零的元对于乘法来说，做成一个群。这个群的的阶为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 (n1)。那么多项式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)的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是有限域E= GF(pn)的子域，是E的素域，由E:TT: = E: =n可知T: =m必整除n；T是元素个数为pm的有限域。这样T是xq-x (q=pm)在上的分裂域。注意T是E的子域，故T=aE|aq-a=0。这样E中元素个数为pm的子域T有且仅有一个，由xq-x在E中的一切根组成。得证。定理5 一个有限域E是它的素域的一个单扩域。证明 设E含有q个元。E的非零元对E的乘法来说作成一个交换群G，它的阶是q-1。令m是G的元的阶中最大的一个，那么由引理，aim=1，对于任意aiG。这就是说，多项式xm-1至少有q-1个不同的根。因此mq-1，但是由于m整除G的阶，故m q-1，所以m=q-1。也就是说G有一个元a，它的阶为q-1，因而G是一个循环群(a)。这样E是添加a于所得的单扩域E=(a)。定理得证。定理5.3.6 域的乘群的任何有限子群是循环群。证明：设G是域F的有限子乘群，令m是G中所有元素的阶的最小公倍数，由拉格朗日定理G中任意元素的阶均为群G的阶的因子， 因而若设c为G中阶为m的元素，则m|G|。 另一方面，G中的元素均满足方程xm-l=0，而多项式f(x)=xm-lFx在F上最多有m个不同的根， 故|G|m，由此得|G|=m，所以G=(c)。例6.2.7利用多项式f(x)=x2-2构造一个有限域，并找出这个域中的本原元。解：这里只给出了构造域的多项式，并未给出构造域所需的欧氏环，因而需要选择一个欧氏环，并保证f(x)为此域中的不可约多项式。 注意到在F3中f(0)=1，f(1)=f(2)=2，因而该多项式是F3x中的一个不可约多项式， 以此可以构造一个具有9个元素的有限域F。域F中的元素都可以看做是二维向量(a,b)，其中a,bF3=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,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)取模的结果的向量表示 表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 设3a2 + b2，证明：3a且3b。4 证明：对于任意给定的n个整数，必可以从中找出若干个作和，使得这个和能被n整除。5 设a，b，c是正整数，证明：6 设k是正奇数，证明：1 + 2 + + 91k + 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，使得10k199!。12 设n是正整数，则。13 设n是正整数，x是实数，证明：= n。14 证明：若2n - 1是素数，则n是素数。15 证明：对于任意给定的正整数n，必存在连续的n个自然数，使得它们都是合数。二、 同余1 求81234被13除的余数。2 已知99，求a与b3 求n =的个位数4 证明：若n是正整数，则1342n + 1 + 3 n + 25 设m 0是偶数，a1, a2, , am与b1, b2, , bm都是模m的完全剩余系，证明：a1 + b1, a2 + b2, , am + bm不是模m的完全剩余系6 证明：若2p + 1是奇素数，则(p!)2 + (-1)p 0 (mod 2p + 1)7 证明Wilson定理的逆定理：若n 1，并且(n - 1)! -1 (mod n)，则n是素数8 设m 1，(a, m) = 1，x1, x2, xj(m)是模m的简化剩余系，证明：。其中x表示x的小数部分。9 设m与n是正整数，证明：j(mn)j(m, n) = (m, n)j(m)j(n)10 设x1, x2, xj(m)是模m的简化剩余系，则(x1x2xj(m)2 1 (mo