代數(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ù)且m>1,于是注意到，即為整數(shù)。所以。注：當(dāng)n=3時，整除變?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ù)（m2）,證明證明：（1）首先證明：因為其中，所以從而有（2）再證：其中則若）則有若）則有 若）若）則有總之不論何種情況均有注：本題可推廣到：設(shè)n為大于的整數(shù)，證明（）不是整數(shù)。（）不是整數(shù)。證明：（）設(shè)某個正整數(shù)使，則的各項必只有一項分母為，其余各項的分母至多可被整除，因此在上述和式中將除去的其余各項相加必得如下形式的數(shù)其中q和k是正整數(shù)，從而，其分母是偶數(shù)，分子是奇數(shù)，因此不可能等于整數(shù)。（）設(shè)某個正整數(shù)使，則的各項必只有一項分母為，其余各項的分母至多可被整除，因此在上述和式中將除去的其余各項相加必得如下形式的

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

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

5、，令顯然，每個都不是q的素數(shù)，否則將導(dǎo)致，這是不可能的。如果q本身是素數(shù)，由于，這表示q也是形如m+的數(shù)，顯然，從而q>N.這表示存在大于之形如m+的素數(shù)q.如果q本身不是素數(shù)，由第一步知，q一定含有形如m+之素因數(shù)p,同樣可證明，這表示存在大于之形如m+的素數(shù)p.由于是任取之正整數(shù)，這樣就證明了形如n+的素數(shù)有無窮多個。.設(shè)為正整數(shù)。如果n沒有小于等于的素因子，則n為素數(shù)。證明：反證法。若n不是素數(shù)，設(shè)n=ab,1<ab<n,則，或，這與沒有小于等于的素因子的條件矛盾，故n必為素數(shù)。習(xí)題.（P11）. 對每個正整數(shù)n,證明是既約分?jǐn)?shù)。證明：，所以是既約分?jǐn)?shù)。4 設(shè)則當(dāng)且僅當(dāng)

6、。證明：設(shè)，則有。（1）若，則有，而，所以，即。（2）若，即，有，又因為，由整除的傳遞性知，即5 用輾轉(zhuǎn)相除法求963和657的最大公因子，并求出方程963x+657y=(963,657)的全部整數(shù)解。解：利用輾轉(zhuǎn)相除法。963=657×1+306657=306×2+45306=45×6+3645=36×1+936=9×4（963，657）=9，將以上倒數(shù)第2式通過回代得到963×（-15）+657×22=9即(x,y)=(-15,22)是原方程的一個解。從而全部整數(shù)解為：6 求下列方程的全部整數(shù)解（）6x+20y-15z=

7、23（）25x+13y+7z=2解：（1）因為（6，20，15）=1|23，可知方程有整數(shù)解，又因為(20,15)=5,可知20y+15z:y,zZ=5Z,因此方程等價于聯(lián)立方程組即 （i）4y-3z=1有解（y,z）=(1,1),從而4y-3z=w有解（w,w）,于是對每個wZ,方程（i）的全部整數(shù)解為而方程(ii)有解(x,w)=(3,1),從而它的全部整數(shù)解為將w代入（iii）得原方程的全部解為（2）因為（25，13，7）=1|2，所以原方程有整數(shù)解。考慮13y+7z:y,zZ=Z(因為（13，7）=1)，故原方程可轉(zhuǎn)化為解聯(lián)立方程組（y,z）=(-1,2)是13y+7z=1的一個解，故

8、（y,z）=(-w,2w)是（i）的一個解，從而(i)的全部解為而(x,w)=(1,-23)是（ii）的一個解，故它的全部解為代入（iii）得原方程的全部解為7 設(shè)n為正整數(shù)，k為正奇數(shù)。證明(1+2+n)|.證明：因為，所以只需證明，當(dāng)k是奇數(shù)時,可被整除。首先注意，當(dāng)k為奇數(shù)時，可被（a+b）整除，其中a,b均為整數(shù)。（1） 如果n是偶數(shù)，則。事實上，Sk可寫成上式右端每一項均可被（n+1）整除，故n+1|Sk.又由于右端每一項均可被整除，故有因為n+1和為Sk的真因子，且無公因數(shù)。故（2） 如果n是奇數(shù)，則。事實上，Sk可寫成上式右端每一項均可被整除，所以又上式右端每一項均可被n整除，所

9、以由于和n是Sk的真因子，且無公因數(shù)，故習(xí)題1.1C（P13）4.設(shè)n為正整數(shù)，a和b是不全為零的整數(shù)。證明（1）（2）若a和b是互素的正整數(shù)，,則a和b均為正整數(shù)的n次方。證明：（1）注意到故只需對a,b為正整數(shù)時結(jié)論成立即可。設(shè)a,b分別有分解式，其中是素數(shù)，而為非負(fù)整數(shù)，i,j=1,2,k.則有，從而其中。即（2）當(dāng)a,b中有一個為1時結(jié)論顯然成立，故不妨a>1,b>1,于是a,b均有標(biāo)準(zhǔn)分解式，設(shè)為因為（a,b）=1,故是的標(biāo)準(zhǔn)分解式，再設(shè)c 的分解式為，則由此得，即，。即a和b均為正整數(shù)的n次方。習(xí)題1.2（P23）1（完全數(shù)問題）滿足的正整數(shù)n叫做完全數(shù)。由于是全部小于

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

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

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

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

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

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

16、解的表達式，即原同余方程組的全部整數(shù)解是：3. 用中國剩余定理解同余方程37x31(mod77)解：原方程等價于同余方程組再解同余方程組由于7，11互素，故同余方程組有解。M1=11,M2=7，解同余方程取N1=2，N2=-3，于是即原同余方程的全部整數(shù)解為6求2400被319除的余數(shù)。解：319=11×29，故相當(dāng)于解方程：由歐拉定理可知，化簡所以有解，有解，故由中國剩余定理知其解為，即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的階

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

18、，12）=4|4，此方程有解?；啚樗裕?lt;1>有4個解2，2+3=5，5+3=8，8+3=11，原方程有4個解，即解（2）基本思路：當(dāng)模數(shù)不是素數(shù)時通?？蓪⒛?shù)分解化為方程組（使模數(shù)變小），分別求解后再聯(lián)立求解，這時要用中國剩余定理。143=13×11，故原方程等價于方程組先求出的解。由（1）題的結(jié)論知解為再求出的解：2是模11的一個原根，令，化為它等價于同余方程 <2>而（8，10）=2|8，此方程有解?；啚?，解出，從而方程<2> 有2個解1，6，故有2個解，即。原方程等價于求解 ， <3>其中。（有4×2=8種組合，即

19、有8個方程組）利用中國剩余定理求解該方程組。<3>的解的表達式為同余方程有解，同理有解，故<3>的解的表達式為再將的值分別代入上式得到原方程的8組解：經(jīng)計算有或按從小到大的排列最后得原方程的解：。解（3）基本思路：利用原根，將“指數(shù)同余方程”化為一次同余方程。取模17的一個原根3，有7=311,4=312,原方程化為，等價于一次同余方程：（因為），則為原方程的整數(shù)解。2. （1）寫出模37的全部8次剩余和15次剩余。（2）寫出模11的全部2次剩余。解：（1）先找原根。37是素數(shù)，故模37必有原根。，模37的同余類的階數(shù)可能是1，2，3，4，6，9，12，18，36。而對

20、模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設(shè)p為素數(shù)，p=2(mod3),a,bZ.證明:a3=b3(modp)當(dāng)

21、且僅當(dāng)a=b(modp)證明：充分性顯然，以下證明必要性。當(dāng)a=b=0(modp)顯然成立，不妨設(shè)。因為p為素數(shù)，故對于模p有原根，設(shè)，由a3=b3(modp)即得，從而有，再由條件p=2(mod3)知p=2+3k或(p-1)+3(-k)=1,故（3，p-1）=1,由得,得，即a=b(modp)。4設(shè)p為奇素數(shù)，中元素的階為3，求元素的階。解：由條件的非零元均是可逆元，且 ，或 （1）而的階為3，故即，（1）兩邊乘以的逆元得，從而所以，故的階為6。習(xí)題2.1A（P62）1. 設(shè)是群的同態(tài)，和分別為G和G的幺元素，則。證明：（1）（是G的幺元素）（是群的同態(tài)）兩邊右乘得即或；（2）因為（是群的同

22、態(tài)）（由上所證），同理可證，所以2. 決定加法群Z，Q和Zm的自同構(gòu)群。解：（1）求Aut(Z).設(shè)，任意,若m是正整數(shù)，由于f保持加法運算，故有，若m是負(fù)整數(shù)有，當(dāng)m=0時由1題知，即任意的有，此說明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è),對于有理數(shù)，由于f保持加法運算，易知得，從而此說明，f完全由確定，令為任意的非零有理數(shù)，易知是Q到自身的同構(gòu)映射。由此得（3）求Aut(Zm).設(shè),有，故f完全由確定。令有，設(shè)則有，易驗證當(dāng)（r,m）=1時有是Zm到自身的同構(gòu)映射。所以有（）習(xí)題2.1B（P65）1 群G的任意多個子群的交集是G的子群。證明：只需證明兩個子群的情況即可。設(shè)，顯然即是群G的一個非空子集。對于任意的而G1，G2是群G的子群，故，從而有，所以是群G的子群。2 每個群不能是它的兩個真子群的并集。證明：用反證法。假設(shè)群G是它的兩個真子群G1，G2的并，即，從而一定有兩個元素，滿足：，令，顯然，從而有或不妨設(shè)，從而，這與矛盾。故每個群不能是它的兩個真子群的并集。3 有限群G中每個元素均是有限階的，并且元素的階都是|G|的因子。（例如：乘法群是階有