代數(shù)和通信部分習(xí)題集解

1、 代數(shù)與通信部分習(xí)題解習(xí)題1.1A（P6）. 若n為奇數(shù)，證明8|n2-1。證明：n為奇數(shù)，可設(shè)n=2m+1,其中m為整數(shù)。于是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為奇數(shù)并且n5,則。證明：n為奇數(shù)并且n5可設(shè)n=2m+1,其中m為整數(shù)且m1,于是注意到，即為整數(shù)。所以。注：當(dāng)n=3時(shí)，整除變?yōu)橄嗟?，結(jié)論也成立。. 若m和n是正整數(shù)，,證明不整除。反證法：假設(shè)，由帶余除法可設(shè)n=qm+r其中，于是有由假設(shè)，故，而為正整數(shù)，所以，故，即，或，所以，從而m-1=1,r-1=0,即m=2,這與

2、矛盾，所以不整除。討論：根據(jù)以上證明可知，或?qū)懗?其中m為奇數(shù)。4設(shè)為實(shí)數(shù)（m2）,證明證明：（1）首先證明：因?yàn)槠渲?，所以從而有?）再證：其中則若）則有若）則有 若）若）則有總之不論何種情況均有注：本題可推廣到：設(shè)n為大于的整數(shù)，證明（）不是整數(shù)。（）不是整數(shù)。證明：（）設(shè)某個(gè)正整數(shù)使，則的各項(xiàng)必只有一項(xiàng)分母為，其余各項(xiàng)的分母至多可被整除，因此在上述和式中將除去的其余各項(xiàng)相加必得如下形式的數(shù)其中q和k是正整數(shù)，從而，其分母是偶數(shù)，分子是奇數(shù)，因此不可能等于整數(shù)。（）設(shè)某個(gè)正整數(shù)使，則的各項(xiàng)必只有一項(xiàng)分母為，其余各項(xiàng)的分母至多可被整除，因此在上述和式中將除去的其余各項(xiàng)相加必得如下形式的數(shù)或其

3、中q和k是正整數(shù)，從而，或其分母是3的倍數(shù)，分子不是的倍數(shù)，因此不可能等于整數(shù)。.證明（）形如4m+3(mZ)的素?cái)?shù)有無(wú)限多個(gè)。（）形如6m+5(mZ) 的素?cái)?shù)有無(wú)限多個(gè)。證明：（）分兩步來(lái)證明。首先證明形如4m+3的正整數(shù)必定含有形如4m+3的素因數(shù)。事實(shí)上，一切奇數(shù)素?cái)?shù)都能寫(xiě)成4k+1或4k+3的形式，這里k是整數(shù)。而由于所以把形如4k+1的數(shù)相乘的乘積仍為4k+1形式的數(shù)。因此，把4n+3分解成素因數(shù)的乘積時(shí)，這些素因數(shù)不可能都是4m+1的形式的素?cái)?shù)，一定有4m+3形式的素?cái)?shù)。其次，設(shè)N任取之正整數(shù)，并設(shè)為形如4m+3的不超過(guò)之所有素?cái)?shù)，令顯然，每個(gè)都不是q的素?cái)?shù)，否則將導(dǎo)致，這是不可能

4、的。如果q本身是素?cái)?shù)，由于，這表示q也是形如4m+3的數(shù)，顯然，從而qN.這表示存在大于之形如4m+3的素?cái)?shù)q.如果q本身不是素?cái)?shù)，由第一步知，q一定含有形如4m+3之素因數(shù)p,同樣可證明，這表示存在大于之形如4m+3的素?cái)?shù)p.由于是任取之正整數(shù)，這樣就證明了形如n+3的素?cái)?shù)有無(wú)窮多個(gè)。（）首先證明形如6m+5的正整數(shù)必定含有形如6m+5的素因數(shù)。事實(shí)上，一切大于3的素?cái)?shù)都能寫(xiě)成k+1或k+的形式，這里k是整數(shù)。而由于所以把形如k+1的數(shù)相乘的乘積仍為k+1形式的數(shù)。因此，把n+分解成素因數(shù)的乘積時(shí)，一定有m+形式的素因數(shù)。其次，設(shè)N任取之正整數(shù)，并設(shè)為形如m+的不超過(guò)之所有素?cái)?shù)，令顯然，每個(gè)

5、都不是q的素?cái)?shù)，否則將導(dǎo)致，這是不可能的。如果q本身是素?cái)?shù)，由于，這表示q也是形如m+的數(shù)，顯然，從而qN.這表示存在大于之形如m+的素?cái)?shù)q.如果q本身不是素?cái)?shù)，由第一步知，q一定含有形如m+之素因數(shù)p,同樣可證明，這表示存在大于之形如m+的素?cái)?shù)p.由于是任取之正整數(shù)，這樣就證明了形如n+的素?cái)?shù)有無(wú)窮多個(gè)。.設(shè)為正整數(shù)。如果n沒(méi)有小于等于的素因子，則n為素?cái)?shù)。證明：反證法。若n不是素?cái)?shù)，設(shè)n=ab,1ab1,b1,于是a,b均有標(biāo)準(zhǔn)分解式，設(shè)為因?yàn)椋╝,b）=1,故是的標(biāo)準(zhǔn)分解式，再設(shè)c 的分解式為，則由此得，即，。即a和b均為正整數(shù)的n次方。習(xí)題1.2（P23）1（完全數(shù)問(wèn)題）滿足的正整數(shù)n

6、叫做完全數(shù)。由于是全部小于n的正因子之和。所以n為完全數(shù)當(dāng)且僅當(dāng)n等于它的所有正因子(n除外)之和。（1）驗(yàn)證6和28是完全數(shù)。（2）證明歐拉的結(jié)果：正偶數(shù)n是完全數(shù)當(dāng)且僅當(dāng),其中，并且為素?cái)?shù)（即梅森素?cái)?shù)）。這表明梅森素?cái)?shù)與偶數(shù)完全數(shù)一一對(duì)應(yīng)。（另一方面，至今為止沒(méi)有找到一個(gè)奇完全數(shù)，也沒(méi)有證明奇完全數(shù)是不存在的。）求解：（1）6=23, 即6,28都是完全數(shù)。（2）先證明充分性。由是素?cái)?shù)知,再由是積性函數(shù)知。即是完全數(shù)。再證必要性。因?yàn)閚為正偶數(shù)，故可設(shè)n=2a-1k,其中a2,k是奇數(shù)，即（2，k）=1.于是由于因此要使成立，k必含有因子，可設(shè)從而，而k與q均是k的因數(shù)，上式說(shuō)明k的正因數(shù)

7、只有這兩個(gè)，從而必有q=1,而是素?cái)?shù)，使得。2以表示正整數(shù)n 的不同素因子的個(gè)數(shù)。即，而當(dāng)時(shí) （標(biāo)準(zhǔn)分解式）時(shí)， 。證明（1）（2）（3）（這里乘積表示p遍歷n的不同素因子。）證明：令a是一個(gè)不為零的整數(shù)，首先證明是積性函數(shù)。再設(shè)(n,m)=1,若n,m有一個(gè)為1，不妨n=1,這時(shí)若n,m均大于1,設(shè)分別是n,m的標(biāo)準(zhǔn)分解式，由于（n,m）=1,所以互不相同，從而也是nm的標(biāo)準(zhǔn)分解式。故,所以是積性函數(shù)。（1）易知，而是積性函數(shù)，所以（1）式左邊是積性函數(shù)，而由上所證右邊也是積性函數(shù)。所以只需對(duì)驗(yàn)證等式成立即可。這時(shí)。（2）左邊為，右邊為是積性函數(shù)，故只需驗(yàn)證當(dāng)驗(yàn)證等式成立即可。這時(shí)（3）左邊

8、為是積性函數(shù)，注意到當(dāng)（n,m）=1時(shí)故右邊也為積性函數(shù)。所以只需對(duì)驗(yàn)證等式成立即可。這時(shí)習(xí)題1.3A（P27）1設(shè)m為正整數(shù)，對(duì)于與m互素的整數(shù)a，我們用表示同余方程的任一整數(shù)解（即。證明：（1）若則當(dāng)且僅當(dāng)。（2）若是模m的縮系，則也是模m的縮系。證明：（1）因?yàn)橛啥ɡ?.3.5知同余方程，有解。若，再由得反之，若，得。（2）是模m的縮系，即，從而有，即，又若，由（1）的結(jié)論知（i,j=1,2, ）,由此說(shuō)明也是模m的縮系。2設(shè)正整數(shù)n的十進(jìn)制表示為證明：由此計(jì)算123456789被9和11除的余數(shù)。證明：（1）因?yàn)?，所以，從而?）又因?yàn)?，所以，從而所?23456789被9整除；即12

9、3456789被11除余數(shù)為6。3解下列同余方程（1）（2）解：（1）（2）4對(duì)每個(gè)整數(shù)n證明（1）（2）或（3）（4）證明：（1）設(shè)。當(dāng)i=0,時(shí)當(dāng)i=1,時(shí)當(dāng)i=2,時(shí)所以（2）設(shè)。當(dāng)i=0,時(shí)當(dāng)i=1,時(shí)所以或（3）設(shè)。當(dāng)i=0,時(shí)當(dāng)i=1,時(shí)當(dāng)i=2,時(shí)所以（4）設(shè)。當(dāng)i=0,時(shí)當(dāng)i=1,時(shí)當(dāng)i=2,時(shí)當(dāng)i=3,時(shí)所以5設(shè)為奇數(shù)，證明證明：用數(shù)學(xué)歸納法。當(dāng)n=1時(shí)，設(shè)，。假設(shè)n時(shí)成立，即考慮n+1情況。由知，從而，由數(shù)學(xué)歸納法知，當(dāng)為奇數(shù)，有6證明（1）當(dāng)時(shí)為偶數(shù)。（2）證明：（1）設(shè)是標(biāo)準(zhǔn)分解式，由引理1.2.7知，歐拉函數(shù)，因?yàn)椋蕵?biāo)準(zhǔn)分解式中必有某個(gè)是奇素?cái)?shù)，比如,即是偶數(shù)，則中

10、的因數(shù)有是偶數(shù)，所以歐拉函數(shù)為偶數(shù)。（2）設(shè)為模n的一個(gè)縮系，則有，這里均與n互素且互不相等。由引理1.1.8知，也互不相等，故也是模n的一個(gè)縮系，則有，從而由此7設(shè)證明模n的每個(gè)同余類(lèi)都恰好是模m的t個(gè)同余類(lèi)之并集。證明：設(shè)模n的同余類(lèi)為，模m=nt 的同余類(lèi)為。對(duì)于某個(gè)模n的同余類(lèi)，若有，由帶余除法可設(shè)，于是此說(shuō)明，反之若，即有，所以即模n的每個(gè)同余類(lèi)都恰好是模m的t個(gè)同余類(lèi)之并集。習(xí)題.（P31）.（）對(duì)于環(huán)Zm中每個(gè)元素，m個(gè)相加為。（）設(shè)p為素?cái)?shù)，對(duì)于域Zp中每個(gè)非零元素和正整數(shù)n,證明n個(gè)相加為當(dāng)且僅當(dāng)p|n.證明：（），而，所以。（）設(shè) 若，即有，或，而即不整除a,p是素?cái)?shù)，從而

11、由必有 反之，若，有，從而有即。習(xí)題集1.4（P37）1. 解下列同余方程(1) (2) (3) 解：（1）（32，8）=8不整除12，故原同余方程無(wú)整數(shù)解。（2）(28,116)=4|124故原同余方程有整數(shù)解。故原方程的全部整數(shù)解是，而對(duì)模116有4個(gè)解（3）(5,81)=1,故原同余方程有整數(shù)解。，對(duì)模81有一個(gè)解2解下列同余方程組解：（1）判斷是否有解。因?yàn)?,5,9兩兩互素，故同余方程組有整數(shù)解。（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） 寫(xiě)出

12、解的表達(dá)式，即原同余方程組的全部整數(shù)解是：3. 用中國(guó)剩余定理解同余方程37x31(mod77)解：原方程等價(jià)于同余方程組再解同余方程組由于7，11互素，故同余方程組有解。M1=11,M2=7，解同余方程取N1=2，N2=-3，于是即原同余方程的全部整數(shù)解為6求2400被319除的余數(shù)。解：319=1129，故相當(dāng)于解方程：由歐拉定理可知，化簡(jiǎn)所以有解，有解，故由中國(guó)剩余定理知其解為，即2400被319除的余數(shù)為111。習(xí)題1.5A（P44）1. 設(shè)整數(shù)a和b模m的階分別為s和t,并且(s,t)=1.證明ab模m的階為st.證明：首先由條件有，由此得。若有正整數(shù)k使得，得，而b的階是t,所以有

13、t|sk而(s,t)=1,所以有t|k,同理可得s|k,再由(s,t)=1,得到st|k.由階的定義知，ab模m的階為st.（注：本題可作為結(jié)論用）. 設(shè)a對(duì)模m和模n的階分別為s和t.證明a對(duì)模m,n的階為s,t.證明：由條件，從而有，再由同余的性質(zhì)有。 設(shè)有正整數(shù)k使，顯然有（因?yàn)椋瑥亩衧|k,t|k,即k是s,t的公倍數(shù)，所以有s,t|k,從而由階的定義知a對(duì)模m,n的階為s,t. 習(xí)題1.5B（P44）1.解同余方程解：（1）基本思路：通過(guò)找原根將“高次同余方程”化為一次同余方程。模13有原根2，令原同余方程化為，它等價(jià)于解一次同余方程 （注：） （8，12）=4|4，此方程有解。

14、化簡(jiǎn)為 所以，有4個(gè)解2，2+3=5，5+3=8，8+3=11，原方程有4個(gè)解，即解（2）基本思路：當(dāng)模數(shù)不是素?cái)?shù)時(shí)通?？蓪⒛?shù)分解化為方程組（使模數(shù)變?。謩e求解后再聯(lián)立求解，這時(shí)要用中國(guó)剩余定理。143=1311，故原方程等價(jià)于方程組先求出的解。由（1）題的結(jié)論知解為再求出的解：2是模11的一個(gè)原根，令，化為它等價(jià)于同余方程 而（8，10）=2|8，此方程有解?；?jiǎn)為，解出，從而方程 有2個(gè)解1，6，故有2個(gè)解，即。原方程等價(jià)于求解 ， 其中。（有42=8種組合，即有8個(gè)方程組）利用中國(guó)剩余定理求解該方程組。的解的表達(dá)式為同余方程有解，同理有解，故的解的表達(dá)式為再將的值分別代入上式得到原

15、方程的8組解：經(jīng)計(jì)算有或按從小到大的排列最后得原方程的解：。解（3）基本思路：利用原根，將“指數(shù)同余方程”化為一次同余方程。取模17的一個(gè)原根3，有7=311,4=312,原方程化為，等價(jià)于一次同余方程：（因?yàn)椋?，則為原方程的整數(shù)解。2. （1）寫(xiě)出模37的全部8次剩余和15次剩余。（2）寫(xiě)出模11的全部2次剩余。解：（1）先找原根。37是素?cái)?shù)，故模37必有原根。，模37的同余類(lèi)的階數(shù)可能是1，2，3，4，6，9，12，18，36。而對(duì)模37，但故2的階是36，2是原根；再求模37的全部8次剩余。（8，36）=4，所以全部8次剩余為或即1,16,34,26,9,33,10,12,7或按序排是1

16、，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設(shè)p為素?cái)?shù)，p=2(mod3),a,bZ.證明:a3=b3(modp)當(dāng)且僅當(dāng)a=b(modp)證明：充分性顯然，以下證明必要性。當(dāng)a=b=0(modp)顯然成立，不妨設(shè)。因?yàn)閜為素?cái)?shù)，故對(duì)于模p有原根，設(shè)，由a3=b3(modp)

17、即得，從而有，再由條件p=2(mod3)知p=2+3k或(p-1)+3(-k)=1,故（3，p-1）=1,由得,得，即a=b(modp)。4設(shè)p為奇素?cái)?shù)，中元素的階為3，求元素的階。解：由條件的非零元均是可逆元，且 ，或 （1）而的階為3，故即，（1）兩邊乘以的逆元得，從而所以，故的階為6。習(xí)題2.1A（P62）1. 設(shè)是群的同態(tài)，和分別為G和G的幺元素，則。證明：（1）（是G的幺元素）（是群的同態(tài)）兩邊右乘得即或；（2）因?yàn)椋ㄊ侨旱耐瑧B(tài)）（由上所證），同理可證，所以2. 決定加法群Z，Q和Zm的自同構(gòu)群。解：（1）求Aut(Z).設(shè)，任意,若m是正整數(shù)，由于f保持加法運(yùn)算，故有，若m是負(fù)整數(shù)

18、有，當(dāng)m=0時(shí)由1題知，即任意的有，此說(shuō)明Z的自同構(gòu)完全由確定。設(shè)有整數(shù)k,使得，即有，而是整數(shù)，故上式成立當(dāng)且僅當(dāng)=1或=-1。由此得出Aut(Z)=1z，-1z，其中1z是Z到自身的恒等映射，-1z是相反數(shù)的映射，它們顯然是自同構(gòu)。（2）求Aut(Q).設(shè),對(duì)于有理數(shù)，由于f保持加法運(yùn)算，易知得，從而此說(shuō)明，f完全由確定，令為任意的非零有理數(shù)，易知是Q到自身的同構(gòu)映射。由此得（3）求Aut(Zm).設(shè),有，故f完全由確定。令有，設(shè)則有，易驗(yàn)證當(dāng)（r,m）=1時(shí)有是Zm到自身的同構(gòu)映射。所以有（）習(xí)題2.1B（P65）1 群G的任意多個(gè)子群的交集是G的子群。證明：只需證明兩個(gè)子群的情況即可。

19、設(shè)，顯然即是群G的一個(gè)非空子集。對(duì)于任意的而G1，G2是群G的子群，故，從而有，所以是群G的子群。2 每個(gè)群不能是它的兩個(gè)真子群的并集。證明：用反證法。假設(shè)群G是它的兩個(gè)真子群G1，G2的并，即，從而一定有兩個(gè)元素，滿足：，令，顯然，從而有或不妨設(shè)，從而，這與矛盾。故每個(gè)群不能是它的兩個(gè)真子群的并集。3 有限群G中每個(gè)元素均是有限階的，并且元素的階都是|G|的因子。（例如：乘法群是階有限群，它的每個(gè)元素的階都是的因子。）證明：設(shè)g是G的任意元素，若g是無(wú)限階的，則1，g,g2,gk,互不相同且是G的元素，這與G是有限群矛盾，故G中每個(gè)元素均是有限階的。設(shè)g的階是n,則是G的子群，且階數(shù)為n,由拉格朗日定理知n|G|,即G的每個(gè)元素的階都是