代数与通信部分习题解..doc

代数与通信部分习题解习题1.1A（P6）. 若n为奇数，证明8|n2-1。证明：n为奇数，可设n=2m+1,其中m为整数。于是n2-1=(2m+1)2-1=(4m2+4m+1)-1=4m(m+1),注意到2|m(m+1)，所以8|4m(m+1),即8|n2-1。. 若n为奇数并且n5,则。证明：n为奇数并且n5可设n=2m+1,其中m为整数且m1,于是注意到，即为整数。所以。注：当n=3时，整除变为相等，结论也成立。. 若m和n是正整数，,证明不整除。反证法：假设，由带余除法可设n=qm+r其中，于是有由假设，故，而为正整数，所以，故，即，或，所以，从而m-1=1,r-1=0,即m=2,这与矛盾，所以不整除。讨论：根据以上证明可知，或写成,其中m为奇数。4设为实数（m2）,证明证明：（1）首先证明：因为其中，所以从而有（2）再证：其中则若）则有若）则有 若）若）则有总之不论何种情况均有注：本题可推广到：设n为大于的整数，证明（）不是整数。（）不是整数。证明：（）设某个正整数使，则的各项必只有一项分母为，其余各项的分母至多可被整除，因此在上述和式中将除去的其余各项相加必得如下形式的数其中q和k是正整数，从而，其分母是偶数，分子是奇数，因此不可能等于整数。（）设某个正整数使，则的各项必只有一项分母为，其余各项的分母至多可被整除，因此在上述和式中将除去的其余各项相加必得如下形式的数或其中q和k是正整数，从而，或其分母是3的倍数，分子不是的倍数，因此不可能等于整数。.证明（）形如4m+3(mZ)的素数有无限多个。（）形如6m+5(mZ) 的素数有无限多个。证明：（）分两步来证明。首先证明形如4m+3的正整数必定含有形如4m+3的素因数。事实上，一切奇数素数都能写成4k+1或4k+3的形式，这里k是整数。而由于所以把形如4k+1的数相乘的乘积仍为4k+1形式的数。因此，把4n+3分解成素因数的乘积时，这些素因数不可能都是4m+1的形式的素数，一定有4m+3形式的素数。其次，设N任取之正整数，并设为形如4m+3的不超过之所有素数，令显然，每个都不是q的素数，否则将导致，这是不可能的。如果q本身是素数，由于，这表示q也是形如4m+3的数，显然，从而qN.这表示存在大于之形如4m+3的素数q.如果q本身不是素数，由第一步知，q一定含有形如4m+3之素因数p,同样可证明，这表示存在大于之形如4m+3的素数p.由于是任取之正整数，这样就证明了形如n+3的素数有无穷多个。（）首先证明形如6m+5的正整数必定含有形如6m+5的素因数。事实上，一切大于3的素数都能写成k+1或k+的形式，这里k是整数。而由于所以把形如k+1的数相乘的乘积仍为k+1形式的数。因此，把n+分解成素因数的乘积时，一定有m+形式的素因数。其次，设N任取之正整数，并设为形如m+的不超过之所有素数，令显然，每个都不是q的素数，否则将导致，这是不可能的。如果q本身是素数，由于，这表示q也是形如m+的数，显然，从而qN.这表示存在大于之形如m+的素数q.如果q本身不是素数，由第一步知，q一定含有形如m+之素因数p,同样可证明，这表示存在大于之形如m+的素数p.由于是任取之正整数，这样就证明了形如n+的素数有无穷多个。.设为正整数。如果n没有小于等于的素因子，则n为素数。证明：反证法。若n不是素数，设n=ab,1ab1,b1,于是a,b均有标准分解式，设为因为（a,b）=1,故是的标准分解式，再设c 的分解式为，则由此得，即，。即a和b均为正整数的n次方。习题1.2（P23）1（完全数问题）满足的正整数n叫做完全数。由于是全部小于n的正因子之和。所以n为完全数当且仅当n等于它的所有正因子(n除外)之和。（1）验证6和28是完全数。（2）证明欧拉的结果：正偶数n是完全数当且仅当,其中，并且为素数（即梅森素数）。这表明梅森素数与偶数完全数一一对应。（另一方面，至今为止没有找到一个奇完全数，也没有证明奇完全数是不存在的。）求解：（1）6=23, 即6,28都是完全数。（2）先证明充分性。由是素数知,再由是积性函数知。即是完全数。再证必要性。因为n为正偶数，故可设n=2a-1k,其中a2,k是奇数，即（2，k）=1.于是由于因此要使成立，k必含有因子，可设从而，而k与q均是k的因数，上式说明k的正因数只有这两个，从而必有q=1,而是素数，使得。2以表示正整数n 的不同素因子的个数。即，而当时 （标准分解式）时， 。证明（1）（2）（3）（这里乘积表示p遍历n的不同素因子。）证明：令a是一个不为零的整数，首先证明是积性函数。再设(n,m)=1,若n,m有一个为1，不妨n=1,这时若n,m均大于1,设分别是n,m的标准分解式，由于（n,m）=1,所以互不相同，从而也是nm的标准分解式。故,所以是积性函数。（1）易知，而是积性函数，所以（1）式左边是积性函数，而由上所证右边也是积性函数。所以只需对验证等式成立即可。这时。（2）左边为，右边为是积性函数，故只需验证当验证等式成立即可。这时（3）左边为是积性函数，注意到当（n,m）=1时故右边也为积性函数。所以只需对验证等式成立即可。这时习题1.3A（P27）1设m为正整数，对于与m互素的整数a，我们用表示同余方程的任一整数解（即。证明：（1）若则当且仅当。（2）若是模m的缩系，则也是模m的缩系。证明：（1）因为由定理1.3.5知同余方程，有解。若，再由得反之，若，得。（2）是模m的缩系，即，从而有，即，又若，由（1）的结论知（i,j=1,2, ）,由此说明也是模m的缩系。2设正整数n的十进制表示为证明：由此计算123456789被9和11除的余数。证明：（1）因为，所以，从而（2）又因为，所以，从而所以123456789被9整除；即123456789被11除余数为6。3解下列同余方程（1）（2）解：（1）（2）4对每个整数n证明（1）（2）或（3）（4）证明：（1）设。当i=0,时当i=1,时当i=2,时所以（2）设。当i=0,时当i=1,时所以或（3）设。当i=0,时当i=1,时当i=2,时所以（4）设。当i=0,时当i=1,时当i=2,时当i=3,时所以5设为奇数，证明证明：用数学归纳法。当n=1时，设，。假设n时成立，即考虑n+1情况。由知，从而，由数学归纳法知，当为奇数，有6证明（1）当时为偶数。（2）证明：（1）设是标准分解式，由引理1.2.7知，欧拉函数，因为，故标准分解式中必有某个是奇素数，比如,即是偶数，则中的因数有是偶数，所以欧拉函数为偶数。（2）设为模n的一个缩系，则有，这里均与n互素且互不相等。由引理1.1.8知，也互不相等，故也是模n的一个缩系，则有，从而由此7设证明模n的每个同余类都恰好是模m的t个同余类之并集。证明：设模n的同余类为，模m=nt 的同余类为。对于某个模n的同余类，若有，由带余除法可设，于是此说明，反之若，即有，所以即模n的每个同余类都恰好是模m的t个同余类之并集。习题.（P31）.（）对于环Zm中每个元素，m个相加为。（）设p为素数，对于域Zp中每个非零元素和正整数n,证明n个相加为当且仅当p|n.证明：（），而，所以。（）设 若，即有，或，而即不整除a,p是素数，从而由必有 反之，若，有，从而有即。习题集1.4（P37）1. 解下列同余方程(1) (2) (3) 解：（1）（32，8）=8不整除12，故原同余方程无整数解。（2）(28,116)=4|124故原同余方程有整数解。故原方程的全部整数解是，而对模116有4个解（3）(5,81)=1,故原同余方程有整数解。，对模81有一个解2解下列同余方程组解：（1）判断是否有解。因为4,5,9两两互素，故同余方程组有整数解。（2）分别解M1y1(mod4),M2y1(mod5),M31(mod9)其中M1=45，M2=36,M3=20,b1=2,b2=3,b3=7,取N1=1,N2=1,N3=5,得（3） 写出解的表达式，即原同余方程组的全部整数解是：3. 用中国剩余定理解同余方程37x31(mod77)解：原方程等价于同余方程组再解同余方程组由于7，11互素，故同余方程组有解。M1=11,M2=7，解同余方程取N1=2，N2=-3，于是即原同余方程的全部整数解为6求2400被319除的余数。解：319=1129，故相当于解方程：由欧拉定理可知，化简所以有解，有解，故由中国剩余定理知其解为，即2400被319除的余数为111。习题1.5A（P44）1. 设整数a和b模m的阶分别为s和t,并且(s,t)=1.证明ab模m的阶为st.证明：首先由条件有，由此得。若有正整数k使得，得，而b的阶是t,所以有t|sk而(s,t)=1,所以有t|k,同理可得s|k,再由(s,t)=1,得到st|k.由阶的定义知，ab模m的阶为st.（注：本题可作为结论用）. 设a对模m和模n的阶分别为s和t.证明a对模m,n的阶为s,t.证明：由条件，从而有，再由同余的性质有。 设有正整数k使，显然有（因为），从而有s|k,t|k,即k是s,t的公倍数，所以有s,t|k,从而由阶的定义知a对模m,n的阶为s,t. 习题1.5B（P44）1.解同余方程解：（1）基本思路：通过找原根将“高次同余方程”化为一次同余方程。模13有原根2，令原同余方程化为，它等价于解一次同余方程 （注：） （8，12）=4|4，此方程有解。化简为 所以，有4个解2，2+3=5，5+3=8，8+3=11，原方程有4个解，即解（2）基本思路：当模数不是素数时通常可将模数分解化为方程组（使模数变小），分别求解后再联立求解，这时要用中国剩余定理。143=1311，故原方程等价于方程组先求出的解。由（1）题的结论知解为再求出的解：2是模11的一个原根，令，化为它等价于同余方程 而（8，10）=2|8，此方程有解。化简为，解出，从而方程 有2个解1，6，故有2个解，即。原方程等价于求解 ， 其中。（有42=8种组合，即有8个方程组）利用中国剩余定理求解该方程组。的解的表达式为同余方程有解，同理有解，故的解的表达式为再将的值分别代入上式得到原方程的8组解：经计算有或按从小到大的排列最后得原方程的解：。解（3）基本思路：利用原根，将“指数同余方程”化为一次同余方程。取模17的一个原根3，有7=311,4=312,原方程化为，等价于一次同余方程：（因为），则为原方程的整数解。2. （1）写出模37的全部8次剩余和15次剩余。（2）写出模11的全部2次剩余。解：（1）先找原根。37是素数，故模37必有原根。，模37的同余类的阶数可能是1，2，3，4，6，9，12，18，36。而对模37，但故2的阶是36，2是原根；再求模37的全部8次剩余。（8，36）=4，所以全部8次剩余为或即1,16,34,26,9,33,10,12,7或按序排是1，7，9，10，12，16，26，33，34。再求模37的全部15次剩余。（15，36）=3，所以全部15次剩余为或即1,8,27,31,26,23,36,29,10,6,11,14按序排是1，6，8，10，11，14，23，26，27，29，31，36。解：（2）模11有原根，其中是2是原根。，（2，10）=2，故模11的全部2次剩余为，即或1，3，4，5，9。3设p为素数，p=2(mod3),a,bZ.证明:a3=b3(modp)当且仅当a=b(modp)证明：充分性显然，以下证明必要性。当a=b=0(modp)显然成立，不妨设。因为p为素数，故对于模p有原根，设，由a3=b3(modp)即得，从而有，再由条件p=2(mod3)知p=2+3k或(p-1)+3(-k)=1,故（3，p-1）=1,由得,得，即a=b(modp)。4设p为奇素数，中元素的阶为3，求元素的阶。解：由条件的非零元均是可逆元，且 ，或 （1）而的阶为3，故即，（1）两边乘以的逆元得，从而所以，故的阶为6。习题2.1A（P62）1. 设是群的同态，和分别为G和G的幺元素，则。证明：（1）（是G的幺元素）（是群的同态）两边右乘得即或；（2）因为（是群的同态）（由上所证），同理可证，所以2. 决定加法群Z，Q和Zm的自同构群。解：（1）求Aut(Z).设，任意,若m是正整数，由于f保持加法运算，故有，若m是负整数有，当m=0时由1题知，即任意的有，此说明Z的自同构完全由确定。设有整数k,使得，即有，而是整数，故上式成立当且仅当=1或=-1。由此得出Aut(Z)=1z，-1z，其中1z是Z到自身的恒等映射，-1z是相反数的映射，它们显然是自同构。（2）求Aut(Q).设,对于有理数，由于f保持加法运算，易知得，从而此说明，f完全由确定，令为任意的非零有理数，易知是Q到自身的同构映射。由此得（3）求Aut(Zm).设,有，故f完全由确定。令有，设则有，易验证当（r,m）=1时有是Zm到自身的同构映射。所以有（）习题2.1B（P65）1 群G的任意多个子群的交集是G的子群。证明：只需证明两个子群的情况即可。设，显然即是群G的一个非空子集。对于任意的而G1，G2是群G的子群，故，从而有，所以是群G的子群。2 每个群不能是它的两个真子群的并集。证明：用反证法。假设群G是它的两个真子群G1，G2的并，即，从而一定有两个元素，满足：，令，显然，从而有或不妨设，从而，这与矛盾。故每个群不能是它的两个真子群的并集。3 有限群G中每个元素均是有限阶的，并且元素的阶都是|G|的因子。（例如：乘法群是阶有限群，它的每个元素的阶都是的因子。）证明：设g是G的任意元素，若g是无限阶的，则1，g,g2,gk,互不相同且是G的元素，这与G是有限群矛盾，故G中每个元素均是有限阶的。设g的阶是n,则是G的子群，且阶数为n,由拉格朗日定理知n|G|,即G的每个元素的阶都是|