资源描述：
《离散数学 作业及答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2011-2012学年第一学期离散数学作业及参考答案---信息安全10级5-11.利用素因子分解法求2545与360的最大公约数。解：掌握两点：(1)如何进行素因子分解从最小素数2开始到不超过n的素数去除n。(2)求最大公约数的方法min(a1,b1)min(a2,b2)min(an,bn)gcd(a,b)=p1p2pn3210360=23550900112545=2355090010gcd(2545,360)=235509=52.求487与468的最小公倍数。解：掌握两点：(1)如何进行素因子分解从最小素数2开始到不超过n的素数去
2、除n。(2)求最小公倍数的方法max(a1,b1)max(a2,b2)max(an,bn)lcm(a,b)=p1p2pnab=gcd(a,b)﹡lcm(a,b)487是质数，因此gcd(487,468)=1lcm(487,468)=(487*468)/1=487*468=2279163.设n是正整数，证明：6
3、n(n+1)(2n+1)证明：用数学归纳法：归纳基础：当n=1时，n(n+1)(2n+1)=1*2*3=6，6
4、6归纳假设：假设当n=m时，6
5、m(m+1)(2m+1)归纳推导：当n=m+1时，n(n+1)(2n+1)=(m+
6、1)(m+1+1)[2(m+1)+1]=(m+1)(m+2)(2m+3)=m(m+1)(2m+3)+2(m+1)(2m+3)=m(m+1)(2m+1+2)+2(m+1)(2m+3)=m(m+1)(2m+1)+2m(m+1)+2(m+1)(2m+3)=m(m+1)(2m+1)+2(m+1)(m+2m+3)=m(m+1)(2m+1)+2(m+1)(3m+3)2=m(m+1)(2m+1)+6(m+1)因为由假设6
7、m(m+1)(2m+1)成立。2而6
8、6(m+1)2所以6
9、m(m+1)(2m+1)+6(m+1)故当n=m+1时，命题亦成立
10、。所以6
11、n(n+1)(2n+1)5-21已知6x≡7(mod23),下列式子成立的是(D):A.x≡7(mod23)B.x≡8(mod23)C.x≡6(mod23)D.x≡5(mod23)2如果a≡b(modm),c是任意整数，则（A）：1A.ac≡bc(modm)B.a=bC.acbc(modm)D.a≠b3解同余方程31x≡5（mod17）。解：(1)由于gcd(17,31)=1,由定理3知存在31模17的逆。求31和17的线性组合（欧几里得逆过程）31=1·17+1417=1·14+314=4·3+23=1·2+12=1·2
12、+0（结束）因此，-6·31+11·17=1，-6是31模17的逆(2)-6×31x≡-6×5（mod17）x≡-30mod17≡4mod17满足同余式的解有：…-47,-30,-13及4,21,38,…4用RSA密码系统为数字85加密，求加密信息并验证解密信息的正确性。其中p=11，q=13，e=7。解：(1)设想需要发送信息M=85。利用(n,e)=(143,7)计算出加密值：e7C=Mmodn=85mod143=123(2)接下来求d：①ed≡1mod((p-1)(q-1))-1d=emod((p-1)(q-1))-1=7mo
13、d120②由于gcd(7,120)=1,由定理3知存在7模120的逆。求7和120的线性组合（欧几里得逆过程）120=17·7+17=7·1+0（结束）-17·7+1·120=1因此，d=-17+120=103d103(3)M=C(modn)=123mod143=856-11.设集合A={1,2,3,…，10}，问下面定义的二元运算∗关于集合A是否封闭？a)x∗y=max(x,y)封闭b)x∗y=min(x,y)封闭c)x∗y=gcd(x,y)封闭d)x∗y=lcm(x,y)不封闭，例lcm(3,7)=21e)x∗y=质数p的个数，
14、使得x≤p≤y不封闭，例6∗6=02.设代数系统,其中A={a,b,c},∗是A上的一个二元运算。对于由以下几个表所确定的运算，试分别讨论他们的交换性、等幂性以及在A中关于∗运算是否有幺元。如果有幺元，那么A中的每个元素是否有逆元。2a)b)∗abc∗abcaabcaabcbbcabbacccabccccc)d)∗abc∗abcaabcaabcbabcbbbccabccccb解：a)可交换，不等幂，a为幺元，a以自身为逆元，b、c互为逆元。b)可交换，不等幂，a为幺元，a、b以自身为逆元，c没有逆元。c)不可交换，等幂，没
15、有幺元。d)可交换，不等幂，a为幺元，a以自身为逆元，b、c没有逆元。b3.定义I+上的两个二元运算为：a∗b=a,a△b=a·b,a,b∈I+。试证明∗对△是不可分配的。证明：由于bc⋅a∗=(bc+i)a∗(bc)=abcbcb+
