1、1代数与通信部分习题解习题 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,则 。)!1(.31(| n证明：n 为奇数并且 n5 可设 n=2m+1,其中 m 为整数且 m1,于是)!1(.312(n)!12)(. )!2(.1.312 mm 1.m )!2(.)12()12( (.mn注意到 ，即)!2|1,.)!2(|1(,)!2| mm)!(.为整数
2、。所以 。)!1(.312(| nn注：当 n=3 时，整除变为相等，结论也成立。. 若 m 和 n 是正整数， ,证明 不整除 。2m1n反证法：假设 ，由带余除法可设 n=qm+r 其中 ，于是12|n mrZq0,有 12).)2(rmqmqrn2由假设 ，故 ，而 为正整数，所以 ，12|nm12|rm12,rm 12rm故 ，即 ，或 ，所以 ，从r001r而 m-1=1,r-1=0,即 m=2,这与 矛盾，所以 不整除 。3n讨论：根据以上证明可知 ，或写成 ,其中 m 为奇数。12|q3|214设 为实数（m2）,证明12,.n1212.1.nn12证明：（1）首先证明： 212
3、12.1.nnn因为 其中 ，所以,iii0,i12121212.1nnn n从而有 121212. .nnn（2）再证： 122其中 则,21 ,0,1,221若） 则0,有,22211,21211 若） 则,21有221 ,2121, 212121 若）若） 则,02有1211,2121212总之不论何种情况均有 121212注：本题可推广到： .2 21211 nnn 设 n 为大于的整数，证明3（） 不是整数。n1.321（） 不是整数。.5证明：（）设某个正整数 使 12lln，则 的各项必只有一, n1.3项分母为 ，其余各项的分母至多可被 整除，因此在上述和式中将除去 的其余各l
4、21l l2项相加必得如下形式的数 )12(kql其中 q 和 k 是正整数，从而，)12()(1.321 kqknlll其分母是偶数，分子是奇数，因此不可能等于整数。（）设某个正整数 使 ，则 的各项必只有,l13ll .5n一项分母为 ，其余各项的分母至多可被 整除，因此在上述和式中将除去 的其余各l31l l31项相加必得如下形式的数或)13(kql )23(1kql其中 q 和 k 是正整数，从而，或)1()(2.5131knlll 2323. qkqlll其分母是 3 的倍数，分子不是的倍数，因此不可能等于整数。.证明（）形如 4m+3(mZ)的素数有无限多个。（）形如 6m+5(m
5、Z) 的素数有无限多个。证明：（）分两步来证明。首先证明形如 4m+3 的正整数必定含有形如 4m+3 的素因数。事实上，一切奇数素数都能写成 4k+1 或 4k+3 的形式，这里 k 是整数。而由于 1)4(1416)4( 21221221 kkk所以把形如 4k+1 的数相乘的乘积仍为 4k+1 形式的数。因此，把 4n+3 分解成素因数的乘积4时，这些素因数不可能都是 4m+1 的形式的素数，一定有 4m+3 形式的素数。其次，设 N 任取之正整数，并设 为形如 4m+3 的不超过之所有素数，令kp,.2114q显然，每个 都不是 q 的素数，否则将导致 ，这是不可能的。),.21(ki
6、p|i如果 q 本身是素数，由于 ，这表示 q 也.21kp3)1.(421kpq是形如 4m+3 的数，显然 ，从而 qN.这表示存在大于之形如 4m+3 的素数 q.ip如果 q 本身不是素数，由第一步知，q 一定含有形如 4m+3 之素因数 p,同样可证明，这表示存在大于之形如 4m+3 的素数 p.),.21(kip由于是任取之正整数，这样就证明了形如n+3 的素数有无穷多个。（）首先证明形如 6m+5 的正整数必定含有形如 6m+5 的素因数。事实上，一切大于 3的素数都能写成k+1 或k+的形式，这里 k 是整数。而由于 1)6(1)(63)16( 212212121 kk所以把形
7、如k+1 的数相乘的乘积仍为k+1 形式的数。因此，把n+分解成素因数的乘积时，一定有m+形式的素因数。其次，设 N 任取之正整数，并设 kp,.21为形如m+的不超过之所有素数，令 .621kq显然，每个 都不是 q 的素数，否则将导致 ，这是不可能的。),.21(kip1|ip如果 q 本身是素数，由于 ，这表示 q 也是形如m+的数，5).(21kp显然 ，从而 qN.这表示存在大于之形如m+的素数 q.i如果 q 本身不是素数，由第一步知，q 一定含有形如m+之素因数 p,同样可证明，这表示存在大于之形如m+的素数 p.),.21(kip由于是任取之正整数，这样就证明了形如n+的素数有
8、无穷多个。.设 为正整数。如果 n 没有小于等于 的素因子，则 n 为素数。nn证明：反证法。若 n 不是素数，设 n=ab,11,b1,于是 a,b 均有标准分解式，设为 11.,.ksabpq因为（a,b）=1,故 是 的标准分解式，再设 c 的分解式为11.ksabbpq，则11.kscdpq11 11. .ks ksabncndncpq由此得 ，即 ，,(2,.)iijjanbijs()kcap。即 a 和 b 均为正整数的 n 次方。1.sdbq习题 1.2（P23）1 （完全数问题）满足 的正整数 n 叫做完全数。由于 是全部小于()2()nn 的正因子之和。所以 n 为完全数当且
9、仅当 n 等于它的所有正因子(n 除外) 之和。（1）验证 6 和 28 是完全数。（2）证明欧拉的结果：正偶数 n 是完全数当且仅当 ,其中 ，并且12()a2a为素数（即梅森素数） 。这表明梅森素数与偶数完全数一一对应。 （另一方面，至今1a为止没有找到一个奇完全数，也没有证明奇完全数是不存在的。 ）求解：（1）6=23,2(6)236,87,()81247128即 6,28 都是完全数。（2）先证明充分性。由 是素数知 ,再由 是积性函数知1a1(,)a。即21 1)()(22()2a aaan n 是完全数。9再证必要性。因为 n 为正偶数，故可设 n=2a-1k,其中 a2,k 是奇
10、数，即（2，k）=1.于是112()2)()(1)aaaakk由于 因此要使(,1),a成立，k 必含有 因子，可设 从而2(ka(2),aq，而 k 与 q 均是 k 的因数，上式说明 k 的正因数只有这()2)aqq两个，从而必有 q=1,而 是素数，使得 。1a1()an2以 表示正整数 n 的不同素因子的个数。即 ，而当时()n (1)0（标准分解式）时， 。证明1.reep()r（1） ()|(|2ndn（2） ()|()1ndn（3） （这里乘积 表示 p 遍历 n 的不同素因子。 ）()|()ndpn|pn证明：令 a 是一个不为零的整数， ，首先证明 是积性函数。()afaf再
11、设(n,m)=1,若 n,m 有一个为 1，不妨 n=1,这时 ()0()()()()0,( ()mnma anfnfn若 n,m 均大于 1,设 分别是 n,m 的标准分解式，1212.,.sr eeeepq由于（n,m）=1, 所以 互不相同，从而1,rsq也是 nm 的标准分解式。故122.sreeenmpq,所以 是积性函数。()()( ()nmnma afaf()naf（1）易知 ，而 是积性函数，所以)1|1n(),1（1）式左边 是积性函数，而由上所证右边 也是积性函数。所以只1*f ()2nf需对 验证等式成立即可。这时enp。2 ()|()|()|()|.|()|1ee ep
12、dppp（2）左边为 ，右边为 是积性函数，故只需验证当*1()1nf验证等式成立即可。这时en102| ()()(1)().()1e eedp ppdd（3）左边为 是积性函数，注意到()* |png当（n,m）=1 时 故右边也为1212| |. ()rspnmmgpqg积性函数。所以只需对 验证等式成立即可。这时e 2| ()|()(1)()().()1()e e edp pdpp习题 1.3A（P27）1设 m 为正整数，对于与 m 互素的整数 a，我们用 表示同余方程1的任一整数解（即 。证明：(od)ax11,(od)Zm（1）若 则 当且仅当 。,(,),b()b1(od)b（2
13、）若 是模 m 的缩系，则 也是模 m 的缩系。12().r1()2,.mr证明：（1）因为 由定理 1.3.5 知同余方程 ，,),a()ax有解。若 ，再由 得(mod)bx(odb11,odaZ11()b反之，若 ，得 。1()a 11a（2） 是模 m 的缩系，即 ，从而有 ，2(),.r(,)ir11,(mod)iirZr即 ，又若 ，由（1）的结论知 （i,j=1,2, 1()im1od)ijr(od)ij）,由此说明 也是模 m 的缩系。1()2,.m2设正整数 n 的十进制表示为 201.10(9)kiaa证明： 01.(od)m1knaa由此计算 123456789 被 9 和 11 除的余数。
