信息安全数学基础----习题集一一、填空题1、设a=18、b=12，c=27，求a、b、c的最小公倍数[a,b,c]=.2、求欧拉函数φ(3000)=.3、设m=9，则模m的最小非负简化剩余系={}.4、设m=11，则模m的所有平方剩余=.5、设m=22，则模m的所有原根个数=.6.设m，n是互素的两个正整数，则φ(mn)=________________。
7.设m是正整数，a是满足mm的整数，则一次同余式：ax≡b(modm)有解的充分必要条件是_________________。
8.设m是一个正整数，a是满足____________的整数，则存在整数a’，1≤a’＜m，使得aa’≡1(modm)。
9.设m∈m,(m,m)=1,如果同余方程m2≡m(mod m)__________,则m叫做模m 的平方剩余.10.设m,m∈m,m>1,(m,m)=1,则使得m m≡1(mod m)成立的最小正整数m叫做m对模m的__________.二、判断题（在题目后面的括号中，对的画“√”，错的画“×”）1、若m是任意正整数,则(mm,mm)=(m,m). （）2、设m1,m2,…,m m是m个不全为零的整数，则m1,m2,…,m m与m1,|m2|,|m3|,…,|m m|的公因数相同（）3、设m是正整数,若m│mm,则m│m或m│m.（）4、设m为正整数,m,m为整数,m≡m(mod m),m│m且m>0,则mm ≡mm(mod mm).（）5、{1,-3,8,4,-10}是模5的一个完全剩余系. （）6、设m是素数,模m的最小非负完全剩余系和最小非负简化剩余系中元素个数相等.（）7、设m=17为奇素数,模m的平方剩余和平方非剩余的数量各为8. （）8、一次同余方程9m≡1(mod24)有解. （）9、设m是素数,m是模m的原根,若m m≡1(mod m),则m是m−1的整数倍.（）10、设m>1,(m,m)=1,则1=m0,m,m2,…,m ord m(m)−1构成模m的简化剩余系.（）11.m≠0,则(0,m)＝|m|.（）12.设m,m是两个互素正整数,那么m│m,m│m,则mm│m.（）13.设m是一个正整数,a,b,d都不为0，若ad≡bd(modm)。
则a≡b(modm)。
（）14.设m为正整数,a是满足(m,m)=1的整数，b为整数.若m1,m2,…,m m(m)为模m 的一个简化剩余系,则mm1+b,mm2+b,…,mm m(m)+b也为模m的一个简化剩余系.（）15.p为素数,n为整数且与p互素，则n2为模p的平方剩余.（）16.设m为正整数,设m∈m,(m,m)=1,则m是模m的平方剩余的充要条件是:m m+12≡1(mod m).（）17.3是模7的原根。
（）18.设m,m∈m,m>1,(m,m)=1,m为正整数,若m m≡1(mod m)，则ord m(m)|m.（）19.整数集关于整数的乘法构成群。
（）20.适当定义加法和乘法，集合{0,1}可以构成一个有限域。
（）三、单项选择题（把答案写在题目后面的括号中）1.设m与m是两个整数,则存在整数m,m,使得(m,m)=mm+mm，下面关于m与m线性组合描述错误的是：（）A.整数m,m的取值仅有一组唯一的值；B.整数m,m的线性和所能表示的最小的正整数是m,m最大公因数，即mm+mm= (m,m)；C.(m,m)的倍数也可以用m,m的线性和表示；D.整数m,m，可以使用辗转相除法(欧几里得算法)反推得到。
2、下面关于整除的描述错误的是：（）A.±1是任何整数的因子；B.设m,m∈m（整数集合）,c≠0m|m,m|m,则m|m±m；C.0是任何整数的倍数；D.设m,m∈m,若m|m,m≠0，则m|−m,−m|−m。
3、下面的说法正确的是：（）A.给定一个正整数m和两个整数m,m，若m≡m(mod m)，则(m−m)|mB.设m,m为整数,若m≡m(mod m m),(m=1,2,…,m)，则m≡m(mod[m1,m2,…,m m])；C.设m1,m2是两个正整数,若m1,m2分别遍历m1,m2的完全剩余系,则m2m1+ m1m2遍历模m1m2的完全剩余系；D.设m为素数,m为任意正整数,则m m−1≡1(mod m)。
4.下面哪个集合是模12的简化剩余系？()。
A.1,3,5,7B.1,5,7,9,C.1,5,7,11D.3,5,7,11。
5.一次同余方程31000m≡9(mod27)的解数是（）A.3B.2C.1D.06、下面的说法正确的是：（）A.一次同余方程21x≡55(mod77)有解；B、一次同余方程m≡6(mod15)，等价于求解一次同余方程组:{m≡2(mod3)m≡3(mod5)的解；C、一次同余方程组{m≡5 (mod13)m≡20 (mod23)有且仅有唯一的解；D.设m m,m m是正整数,对于一次同余方程组m≡m m(mod m m),m=1,2,3,若(m m,m m)=1,则同余方程组一定有解。
7、设m是奇素数,(m1,m)=1,(m2,m)=1,则下列说法错误的是:（）A.如果m1是模m的平方剩余,m2是模m的平方非剩余,则m1m2是模m的平方剩余.B.如果m1是模m的平方剩余,m2是模m的平方非剩余,则m1m2是模m的平方非剩余.C.如果m1,m2都是模m的平方剩余,则m1m2是模m的平方剩余.D.如果m1,m2都是模m的平方非剩余,则m1m2是模m的平方剩余.8、下面说法，错误的是（）A、设p为奇素数，设m∈m,(m,m)=1,若m m−12≡−1(mod m)，方程m2≡m(mod m)方程肯定无解；B、设m,m是奇素数,整数m,m,m,m两两互素.若m既是模m的平方剩余也是模m的平方剩余，则m不是模mm的平方剩余；C、设m,m是奇素数,整数m,m,m,m两两互素.若m既是模m的平方剩余也是模m的平方剩余,m既不是模m的平方剩余也不是模m的平方剩余，则mm不是模m的平方剩余；D、设m,m是奇素数,（mm,mm）=1,只有m2≡mm(mod m))和m2≡mm(mod m)同时有解，对于二次方程m2≡mm(mod mm)才有解。
9、已知5对模17的阶为16,5×5≡8(mod17),求ord17(8)的值是（）A、2B、4C、6D、810、下面说法错误的是（）A、设m是一个正合数,m m={0,1,2,3,…,m−1},则集合m m\{0}对于乘法:mm=m×m(mod m)构成一个交换群；B、设m是一个正整数,令m={…,−m,…,−2,−1,0,1,2,…,m,…},即m是所有整数的集合.对于通常意义的加法(+)，m是一个交换群；C、设m是一个素数,m m=m/mm={0,1,2,3,…,m−1},m∗=m m\{0},m∗是模m的最小非负简化剩余系.则集合m∗对于乘法:mm=m×m(mod m)构成一个交换群；D、设m是一个奇素数,m m={0,1,2,3,…,m−1},则集合m m\{0}对于乘法:mm=m×m(mod m)构成一个有限域。
11．设a,b,c是三个整数，c≠0且c|a，c|b，如果存在整数s,t,使得sa＋tb＝1，则()。
A.(a,b)=cB.c＝1C.c＝sa＋tbD.c＝±112.设a,b,c是三个不全为零的整数。
如果a=bq+c,其中q是整数，则有()。
A.(a,b)=(q,c)B.(a,b)=(b,c)C.(a,b)=cD.(a,b)=(a,c)13.下面哪个集合不是模5的一个完全剩余系？()。
A.1,3,5,7,9B.2,4,6,8,10C.0,1,2,11,13D.0,1,2,13,19。
14.下面哪个集合是模18的简化剩余系？()。
A.-1,5,7,11,13,17B.-1,5,9,11,13,15,17C.-5,1,5,7,11,17D.1,3,5,7,9.11,13,17。
15.满足56≡18(modm)的正整数m(m>2)的个数是()。
A.1B.2C.4D.516.30模23的逆元是()。
A.23B.19C.10D.417.下列一次同余式无解的是()。
A.12x≡3（mod16）B.8x≡9（mod19），C.78x≡30（mod98）D.111x≡6（mod51）。
18.下面哪个是模13的平方剩余()。
A.5B.10C.11D.719．下面各组数中，均为模14的原根的是()。
A.2,3,4,5B.3,6,8,10C.9,11,13D.3,520.定义运算：mm=m×m(mod12),下面哪个集合构成一个群.（）A.{1,2,3,4}B.{1,3,5,7}C.{1,,5,7,9}D.{1,5,7,11}四、简答题1.设m=15,m=101,求整数m,m,使得mm+mm=(m,m).（给出具体求解过程）2.设m,m∈m,m>1,(m,m)=1,m为正整数,则m m≡1(mod m)的充分必要条件是ord m(m)|m.给出充分性的证明.3.计算71005(mod15)。
（给出具体求解过程，提示：可用欧拉定理或也可中国剩余定理进行求解）4.求7模26的阶ord26(7)，并给出所有模26的阶为ord26(7)的整数g（1<g<26）。
（给出具体求解过程）5.判断同余方程x2≡3(mod11)的解的情况。
（给出具体求解过程）6.设m是一个正合数,m m={0,1,2,3,…,m−1},令m m∗=(m/mm)∗={m|m∈m m,(m,m)=1},也即模m的最小非负简化剩余系.则集合m m∗对于乘法:mm=m×m(mmmm)是否构成一个交换群？（请给出详细求解判断过程）7.a＝42，b＝164，求a和b的最大公因子（a，b）及整数x和y，使（a,b）＝ax＋by.8.证明：设m为正整数,m,m为整数,mm≡mm(mod m).若(m,m)=1,则m≡m(mod m).9.结合欧拉定理和模重复平方算法(或者平方乘算法)计算62025（mod41）10.写出模17的所有平方剩余。
11.计算5模19的指数ord19(5)。
12.设不可约多项式m(m)=m2+m+1，集合G={m0≡1,m1≡m,m2≡m+1}.若定义乘法:mm=m×m(mmmm(m))，根据群的定义，判断{G,}是否构成一个群。
五、综合题（备注，每题必须给出具体求解过程）1.解一次同余方程175x≡41081×7(mod133).2.由GF(2)上的4次不可约多项式m(m)=m4+m3+1构成有限域mm(24)，GF(24)中16个域元素，0除外，其余元素可用m的幂次方来表示:m0≡1,m1≡m,m2≡m2,m3≡m3m4≡（）m5≡m3+m+1,m6≡（）,m7≡m2+m+1,m8≡m3+m2+m,m9≡（）,m10≡m3+m,m11≡m3+m2+1, m12≡m+1, m13≡m2+m,m14≡m3+m2 ,m15≡（）（1）完成上面的填空（4分）。