2007级信息安全数学基础试卷-B-答案.doc

2007《信息安全数学基础》B试卷第页共NUMPAGES6页

姓名学号学院专业座位号
(密封线内不答题)
……………………………………………………密………………………………………………封………………………………………线……………………………………线………………………………………

_____________________
…

诚信应考,考试作弊将带来严重后果！
华南理工大学期末考试
《信息安全数学基础》试卷B－答案
注意事项：1.考前请将密封线内填写清楚；
2.所有答案请直接答在试卷上；
3．考试形式：闭卷；
4.本试卷共四大题，满分100分， 考试时间120分钟。
题号一二三四总分得分评卷人
选择题：（每题2分，共20分）
1．(1)。2．(4)。3．(3)。4．(2)。5．(2)。6．(3)。7．(2)。
8．(4)。9．(4)。10．(3)

二．填空题：（每题2分，共20分）
1．设m是正整数，a是满足am的整数，则一次同余式：axb(modm)有解的充分必要条件是(a,m)|b。当同余式axb(modm)有解时，其解数为d＝(a,m)。
2．设m是正整数，则m个数0,1,2,…,m－1中与m互素的整数的个数叫做m的欧拉(Euler)函数，记做(m)。
3．整数2t＋1和2t－1的最大公因数(2t＋1，2t－1)＝1。
4．设a,b是正整数，且有素因数分解，，则，
。
5．如果a对模m的指数是(m)，则a叫做模m的原根。
6．设m是一个正整数，a是满足(a,m)＝1的整数，则存在整数a，1≤a＜m，使得aa≡1(modm)。
7．Wilson定理：设p是一个素数，则(p－1)!≡－1(modp)。
8．(中国剩余定理)设m1,…,mk是k个两两互素的正整数，则对任意的整数b1,…,bk同余式组xb1(modm1)
…………
xbk(modmk)
有唯一解。令m＝m1…mk，m＝miMi，i＝1,…,k，则同余式组的解为：
x≡M1M1b1＋…＋MkMkbk(modm)，
其中MiMi≡1(modmi),i＝1,2,…,k。
9．正整数n有标准因数分解式为，则n的欧拉函数
。

10．设G和G是两个群，f是G到G的一个映射。如果对任意的a,b∈G，都有f(ab)=f(a)f(b)，那么，f叫做G到G的一个同态。

三．证明题（写出详细证明过程）：（共30分）

1．证明：形如4k+3的素数有无穷多个。（6分）

证明分两步证明。
先证形如4k＋3的正整数必含形如4k＋3的素因数。
由于任一奇素数只能写成4n＋1或4n＋3的形式，而
(4n1＋1)(4n2＋1)＝16n1n2＋4n1＋4n2＋1
＝4(4n1n2＋n1＋n2)＋1,
所以把形如4n＋1的数相乘的积仍为4n＋1形式的数。
因此，把形如4k＋3的整数分解成素数的乘积时，
这些素因数不可能都是4n＋1的形式的素数，一定含有
4n＋3形式的素数。
其次，设N是任一正整数，并设
p1,p2,…,ps是不超过N的形如4k＋3的所有素数。
令q＝4p1p2…ps－1。显然，每个pi(i＝1,2,…,s)都
不是q的素因数，否则将会导致pi|1，得到矛盾。
如果q是素数，由于
q＝4p1p2…ps－1＝4(p1p2…ps－1)＋3，即q也是
形如4k＋3的素数，并且显然qpi(i＝1,2,…,s)，
从而q>N。即q是形如4k＋3的大于N的素数。
如果q不是素数，由第一步证明知q含有形如4k＋3
的素因数p，同样可证ppi(i＝1,2,…,s)，从而p>N。
即p是形如4k＋3的大于N的素数。由于N是任意的正整数，因此证明了
形如4k＋3的素数有无穷多个。

2．．设a,b是两个整数，其中b>0。则存在唯一一对整数q,r使得a=bq+r，0r<b。（6分）

证明：存在性.考虑整数序列：
…,-3b,-2b,-b,0,b,2b,3b,…
序列的各项把实数轴划分成长度为b的区间，a一定落在其中的一个区间中。
因此，存在一个整数q使得qba<(q+1)b，
即0a-bq<b。
令r＝a-bq，则有a=bq+r，0r<b。
唯一性.假设还有一对整数q1,r1也满足：
a=bq1+r1，0r1<b。(2)
(1)和(2)两式相减得
b(q-q1)＝-(r-r1)。(3)
当qq1时，(3)式左边的绝对值大于等于b，而右边的绝对值小于b，得到矛盾。故q＝q1，r＝r1。
3．设p，q是两个不同的奇素数，n＝pq，a是与pq互素的整数。整数e和d满足(e,(n))＝1，ed1(mod(n))，1<e<(n)，1d<(n)。
证明：对任意整数c，1c<n，若aec(modn)，则有cda(mod