2011-2012学年第一学期离散数学作业及参考答案---信息安全10级5-11.利用素因子分解法求2545与360的最大公约数。
解：掌握两点：(1) 如何进行素因子分解从最小素数2的素数去除n。
(2) 求最大公约数的方法gcd(a,b) = p1min(a1,b1)p2min(a2,b2)pn min(an,bn)360=23325150902545=2030515091gcd(2545,360) =2030515090=52.求487与468的最小公倍数。
解：掌握两点：(1) 如何进行素因子分解从最小素数2的素数去除n。
(2) 求最小公倍数的方法lcm(a,b) = p1max(a1,b1)p2max(a2,b2)pn max(an,bn)ab=gcd(a, b)﹡lcm (a, b)487是质数，因此gcd(487,468)=1lcm(487,468)= (487*468)/1=487*468=2279163.设n是正整数，证明：6|n(n+1)(2n+1)证明：用数学归纳法：归纳基础：当n=1时，n(n+1)(2n+1)=1*2*3=6，6|6归纳假设：假设当n=m时，6|m(m+1)(2m+1)归纳推导：当n=m+1时，n(n+1)(2n+1)=(m+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)+2 m(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)= m(m+1)(2m+1)+ 6(m+1)2因为由假设6|m(m+1)(2m+1)成立。
而6|6(m+1)2所以6|m(m+1)(2m+1)+ 6(m+1)2故当n=m+1时，命题亦成立。
所以6| n(n + 1)(2n + 1)5-21 已知 6x ≡7 (mod 23),下列式子成立的是( D ):A. x ≡7 (mod 23)B. x ≡8 (mod 23)C. x ≡6 (mod 23)D. x ≡5 (mod 23)2 如果a ≡b (mod m) , c是任意整数，则（A ）：A. ac≡bc (mod m)B. a=bC. ac bc (mod m)D. a ≠b3 解同余方程 31 x ≡5（mod 17）。
解：(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+0（结束）因此，-6·31+11·17=1 ，-6是31模17的逆(2)-6×31x ≡ -6×5（mod 17）x≡-30 mod 17≡4 mod 17满足同余式的解有：…-47,-30, -13及4, 21,38, …4用RSA密码系统为数字85加密，求加密信息并验证解密信息的正确性。
其中p=11，q=13，e=7。
解： (1)设想需要发送信息M=85。
利用(n,e)=(143,7)计算出加密值：C=M e mod n=857 mod 143=123(2) 接下来求d：①ed≡1 mod ((p-1)(q-1))d=e-1 mod ((p-1)(q-1))= 7-1 mod 120②由于gcd(7,120)=1,由定理3知存在7模120的逆。
求7和120的线性组合（欧几里得逆过程）120=17·7+17=7·1+0 （结束）-17·7+1·120=1因此，d=-17+120=103(3) M=C d (mod n)=123103 mod 143=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的个数，使得x≤p≤y 不封闭，例6∗6=02.设代数系统<A,∗> 其中A={a,b,c}, ∗是A上的一个二元运算。
对于由以下几个表所确定的运算，试分别讨论他们的交换性、等幂性以及在A中关于∗运算是否有幺元。
如果有幺元，那么A中的每个元素是否有逆元。
a) b) c) d) ∗ a b c a b c a b c b a c c c c ∗a b c abca b c b c a c a b ∗a b c abc a b c a b c a b c ∗ a b c a b c a b c b b c c c b解：a) 可交换，不等幂，a 为幺元，a 以自身为逆元，b 、c 互为逆元。
b) 可交换，不等幂，a 为幺元，a 、b 以自身为逆元，c 没有逆元。
c) 不可交换，等幂，没有幺元。
d) 可交换，不等幂，a 为幺元，a 以自身为逆元，b 、c 没有逆元。
3. 定义I +上的两个二元运算为：a ∗b=a b , a △b=a·b, a,b ∈I +。
试证明∗对△是不可分配的。
a ()() ()()()() b+cb cb c b c b c b c a b c a a b a c a a a a a b c ⋅+∗=∗=∗∗===∗ i i i 证明：由于而不一定等于，所以对是不可分配的。
6-21.证明：如果f 是由<A, ∗>到<B, △>的同态映射，g 是由<B, △>到<C, □>的同态映射，那么g。
f 是由<A, ∗>到<C, □>的同态映射。
(*)()()B ()()(),(*)((*))(()())=(())(())a b A f a b f a f b c d g c d g c g d a b A g f a b g f a b g f a f b g f a g f b g ∈=∈=∈=== 证明： 因为对于任意的，，有，而对于任意的，，有所以对于任意的，有：() ()<A, ><C, >f ag f b g f ∗ 因此，是由到的同态映射。
2. <R-{0},×>与<R,+>同构吗？<R, +><R-{0}, >-{0}a (),()(0)(0)()(0) ()(0)()(0)(0)(0)<R-f b R R f a b b f a f a f f a f bb f a f a f a f b f f ×∈∈===+=×=×==+=×=×证明： 设是到的同构映射，于是(1)对于任意的，必存在使得有：所以是{0}, >(0)=1. (2) --{0}c (c)-1, ()()()(-1)(-1)1,=00 f R R f f c c f c f c c c c ×∈∈=+=×=×=+=中的幺元。
即应有对于 1必存在使得有：由于是同构映射，所以必有唯一的元素0与1对应，所以，，(0)-1 <R, +><R-{0}, >f =×由此导致的矛盾。
因此，与不可能同构。
3.证明：一个集合上任意两个同余关系的交也是一个同余关系。
121112121<A, >,,, ,,,,,, ,,R R a b c d R R a b c d R a b c d R R R a c b d R a c ∗<><>∈∩<><>∈<><>∈<∗∗>∈<∗证明： 设上的任意两个同余关系为和,于是对于任意的，有且由于和为同余关系，所以且112, b d R a c b d R R ∗>∈<∗∗>∈∩所以因此，一个集合上任意两个同余关系的交仍是一个同余关系。
4.考察代数系统<I,+>,以下定义在I 上的二元关系R 是同余关系吗？a) <x,y>∈R,当且仅当(x<0∧y<0)∨(x ≥0∧y ≥0)b) <x,y>∈R,当且仅当|x-y|<10c)<x,y>∈R,当且仅当(x=y=0)∨(x ≠0∧y ≠0)d) <x,y>∈R,当且仅当x ≥y )R -2,-2,1,4 -2+1,-2+4=<-1,2 )R )-4,6,6,6 -4+6,6-6=<2,0a R R R b c R <><>∈<>>∉<><−>∈<>解： 首先证明是等价关系，但存在着而，所以不是同余关系。
传递性不成立，不是等价关系，更不是同余关系。
而)RR R d >∉，所以不是同余关系。
对称性不成立，不是等价关系，更不是同余关系。
以上只是该题的简略答案，实际解题时应该一步步进行等价关系验证， 然后再进行同余关系验证。
6-31.设<S, ∗>是一个半群，a ∈S ，在S 上定义一个二元运算□，使得对于S 中的任意元素x 和y ，都有x □y=x ∗a ∗y ，证明二元运算是可结合的。
(( )()() ()()())()x y z x a y z x a y a z x a y a zx y z x y a z x a y a z x a y a zx y z x y z =∗∗=∗∗∗∗=∗∗∗∗=∗∗=∗∗∗∗=∗∗∗∗= 证明：由于所以 2.设<R, ∗>是一个代数系统，∗是R 上的一个二元运算，使得对于R 中的任意元素a ，b 都有a ∗b=a+b+a ⋅b ，证明0是幺元且<R, ∗>是独异点。
,000,000, 0=0=a ,+R R ,,, ()() a R a a a a a a a a a a a b R a b a b a b R a b c R a b c a b a b c∈∗=++=∗=++=∗∗∈∗=++∈∗∈∗∗=++∗i i i i i 证明：(1)对于任意的所以 ，因此0是幺元.(2)对于任意的,由于和在上封闭，所以，，即在上封闭。
对于任意的有( ) ()()()a b a b c a b a b ca b c a b a c b c a b ca b c a b c b c a b c b c a b c b c =++++++=++++++∗∗=∗++=++++++i i i i i i i i i i i i ()(), <R,a b c a b a c b c a b ca b c a b c =++++++∗∗=∗∗∗∗>i i i i i 运算是可结合的。