代数与通信部分习题解
习题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为奇数并且n≥5,则n|(1?111??...?)(n?1)!。 23n?1证明：n为奇数并且n≥5可设n=2m+1,其中m为整数且m>1,于是
(1?111??...?)(n?1)! 23n?1?11?1???1???...?((2m?1)?1)! ?23?(2m?1)?1????111??111?????1???...??????...???(2m)!
m??m?1m?22m????23＝??1?????1??11?1???1??????...?????(2m)! 2m??22m?1?mm?1????1?11?(2m?1)???...??(2m)!
2m2(2m?1)m(m?1)???1?11?n???...??(2m)!
2m2(2m?1)m(m?1)??注意到2m|(2m)!,2(2m?1)|(2m)!,...,m(m?1)|(2m)!，即
?1?11??...??2m2(2m?1)?(2m)!
m(m?1)??为整数。所以n|(1?111??...?)(n?1)!。 23n?1mn注：当n=3时，整除变为相等，结论也成立。
３. 若m和n是正整数，m?3,证明2?1不整除2?1。
反证法：假设2?1|2?1，由带余除法可设n=qm+r其中q,r?Z,0?r?m，于是有
mn2n?1?2qm?r?1?(2m)q?12r?2r?1?(2?1)((2)?...?2?1)2?2?1
1
mmqmrr??
由假设2?1|2?1，故2?1|2?1，而2?1,2?1为正整数，所以2m?1?2r?1，故2m?1?2r?1，即0?2?2?2，或0?2mrm?1mnmrmr?2r?1?1，所以2m?1?2r?1?1，从
而m-1=1,r-1=0,即m=2,这与m?3矛盾，所以2m?1不整除2n?1。
讨论：根据以上证明可知3|22q?1?1，或写成3|2m?1,其中m为奇数。
4．设?1,?2,...,?n,为实数（m≥2）,证明
[?1]?[?2]?...?[?n]?[?1??2?...??n]?[?1]?[?2]?...?[?n]?n?1.
[2?1]?[2?2]?[?1]?[?2]?[?1??2]
证明：（1）首先证明：
[?1]?[?2]?...?[?n]?[?1??2?...??n]?[?1]?[?2]?...?[?n]?n?1.
因为?i?[?i]?{?i},其中0?{?i}?1,i?1,2,...,n，所以
[?1]?[?2]?...?[?n]??1??2?...??n?[?1]?[?2]?...?[?n]?n?[?1]?[?2]?...?[?n]?n?1从而有
[?1]?[?2]?...?[?n]?[?1??2?...??n]?[?1]?[?2]?...?[?n]?n?1.
（2）再证：[2?1]?[2?2]?[?1]?[?2]?[?1??2]
?1?[?1]?{?1},?2?[?2]?{?2},其中0?{?1}?1,0?{?2}?1,则
2?1?2[?1]?2{?1},2?2?2[?2]?2{?2},
若１）0?{?1}?11,0?{?2}?,则 22[2?1]?2[?1],[2?2]?2[?2],[?1??2]?[?1]?[?2],有 [2?1]?[2?2]?2[?1]?2??2??[?1]???2??[?1??2],
若２）
11?{?1}?1,?{?2}?1,则 22[2?1]?2[?1]?1,[2?2]?2[?2]?1,[?1??2]?[?1]?[?2]?2,有
[2?1]?[2?2]?2[?1]?1?2??2??1?[?1]???2??[?1]?[?2]?2?[?1]???2??[?1??2],11 若３）若２）0?{?1}?,?{?2}?1,则
22[2?1]?2[?1],[2?2]?2[?2]?1,[?1??2]?[?1]?[?2]?1,有 [2?1]?[2?2]?2[?1]?2??2??1?[?1]???2??[?1??2],
总之不论何种情况均有
[2?1]?[2?2]?[?1]?[?2]?[?1??2]
注：本题可推广到：
2
[2?1]?[2?2]?...?[?n]?[?1]???2??...?[?n]?[?1??2?...??n]
５．设n为大于１的整数，证明 （１）1?（２）1?111??...?不是整数。 23n111不是整数。 ??...?352n?1ll?1证明：（１）设某个正整数l,使2?n?2，则1?111??...?的各项必只有一项23n1的其余各项相2l分母为2l，其余各项的分母至多可被2l?1整除，因此在上述和式中将除去加必得如下形式的数
q
2l?1(2k?1)其中q和k是正整数，从而
1?111q12q?2k?1??...??l?1?l?l， 23n2(2k?1)22(2k?1)其分母是偶数，分子是奇数，因此不可能等于整数。
（２）设某个正整数l,使3?2n?1?3项分母为3，其余各项的分母至多可被3相加必得如下形式的数
ll?1ll?1，则1?111的各项必只有一??...?352n?11的其余各项l3整除，因此在上述和式中将除去
qq或 l?1l?13(3k?1)3(3k?2)其中q和k是正整数，从而
1?111q13q?3k?1??...??l?1?l?l，或 352n?13(3k?1)33(2k?1)111q13q?3k?2??...??l?1?l?l 352n?13(3k?2)33(3k?2)1?其分母是3的倍数，分子不是３的倍数，因此不可能等于整数。
６.证明
（１）形如4m+3(m∈Z)的素数有无限多个。 （２）形如6m+5(m∈Z) 的素数有无限多个。 证明：（１）分两步来证明。
首先证明形如4m+3的正整数必定含有形如4m+3的素因数。事实上，一切奇数素数都能写成
3
4k+1或4k+3的形式，这里k是整数。而由于
(4k1?1)(4k2?1)?16k1k2?4k1?4k2?1?4(4k1k2?k1?k2)?1
所以把形如4k+1的数相乘的乘积仍为4k+1形式的数。因此，把4n+3分解成素因数的乘积时，这些素因数不可能都是4m+1的形式的素数，一定有4m+3形式的素数。
其次，设N任取之正整数，并设p1,p2,...,pk为形如4m+3的不超过Ｎ之所有素数，令
q?4p1p2...pk?1
显然，每个pi(i?1,2,...,k)都不是q的素数，否则将导致pi|1，这是不可能的。
如果q本身是素数，由于q?4p1p2...pk?1＝q?4(p1p2...pk?1)?3，这表示q也是形如4m+3的数，显然q?pi，从而q>N.这表示存在大于Ｎ之形如4m+3的素数q.
如果q本身不是素数，由第一步知，q一定含有形如4m+3之素因数p,同样可证明
p?pi(i?1,2,...,k)，这表示存在大于Ｎ之形如4m+3的素数p.
由于Ｎ是任取之正整数，这样就证明了形如４n+3的素数有无穷多个。
（２）首先证明形如6m+5的正整数必定含有形如6m+5的素因数。事实上，一切大于3的素数都能写成６k+1或６k+５的形式，这里k是整数。而由于
(6k1?1)(6k2?1)?36k1k2?6(k1?k2)?1?6(6k1k2?k1?k2)?1
所以把形如６k+1的数相乘的乘积仍为６k+1形式的数。因此，把６n+５分解成素因数的乘积时，一定有６m+５形式的素因数。
其次，设N任取之正整数，并设
p1,p2,...,pk
为形如６m+５的不超过Ｎ之所有素数，令
q?6p1p2...pk?1
显然，每个pi(i?1,2,...,k)都不是q的素数，否则将导致pi|1，这是不可能的。
如果q本身是素数，由于q?6(p1p2...pk?1)?5，这表示q也是形如６m+５的数，显然q?pi，从而q>N.这表示存在大于Ｎ之形如６m+５的素数q.
如果q本身不是素数，由第一步知，q一定含有形如６m+５之素因数p,同样可证明
p?pi(i?1,2,...,k)，这表示存在大于Ｎ之形如６m+５的素数p.
由于Ｎ是任取之正整数，这样就证明了形如６n+５的素数有无穷多个。 ７.设n?2为正整数。如果n没有小于等于n的素因子，则n为素数。
2证明：反证法。若n不是素数，设n=ab,1
没有小于等于n的素因子的条件矛盾，故n必为素数。
4
习题１.１Ｂ（P11）
１. 对每个正整数n,证明
21n?4是既约分数。
14n?321n?4是既约分数。
14n?3证明：所以(21n?4,14n?3)?(7n?1,14n?3)?(7n?1,1)?1，4． 设a,b,c?Z,a?0则a|bc当且仅当
a|c。 (a,b)证明：设(a,b)?d，则有(ab,)?1。 dd（1）若a|bc，则有
abaaabc，而(,)?1，所以|c，即|c。 dd(a,b)(a,b)dd（2）若
aa|c，即c，有ad又因为dc|bc，由整除的传递性知abc，即a|bc c，
d(a,b)5． 用辗转相除法求963和657的最大公因子，并求出方程
963x+657y=(963,657)
的全部整数解。
解：利用辗转相除法。 963=657×1+306 657=306×2+45 306=45×6+36 45=36×1+9 36=9×4
（963，657）=9，
将以上倒数第2式通过回代得到 963×（-15）+657×22=9 即(x,y)=(-15,22)是原方程的一个解。 从而全部整数解为：
?x??15?657t(t?Z) ??y?22?963t6． 求下列方程的全部整数解 （１）6x+20y-15z=23 （２）25x+13y+7z=2
解：（1）因为（6，20，15）=1|23，可知方程有整数解，又因为(20,15)=5,可知{20y+15z:y,z∈Z}=5Z,因此方程等价于联立方程组
5