离散数学作业及答案

1、2011-2012 学年第一学期离散数学作业及参考答案学年第一学期离散数学作业及参考答案-信息安全信息安全 10 级级 5-1 1.利用素因子分解法求 2545 与 360 的最大公约数。 解：掌握两点：(1) 如何进行素因子分解 从最小素数2开始到不超过 的素数去除n。 n (2) 求最大公约数的方法 gcd(a,b) = p1min(a1,b1) p2min(a2,b2) pnmin(an,bn) 360=2332515090 2545=2030515091 gcd(2545,360) =2030515090=5 2.求 487 与 468 的最小公倍数。 解：掌握两点：(1) 如何进行素

2、因子分解 从最小素数2开始到不超过 的素数去除n。 n (2) 求最小公倍数的方法 lcm(a,b) = p1max(a1,b1) p2max(a2,b2) pnmax(an,bn) ab=gcd(a, b) lcm (a, b) 487 是质数，因此 gcd(487,468)=1 lcm(487,468)= (487*468)/1=487*468=227916 3.设 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=

3、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)

4、2 故当 n=m+1 时，命题亦成立。 所以 6| n(n + 1)(2n + 1) 5-2 1 已知 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 ） ： 1 A. acbc (mod m) B. a=b C. ac bc (mod m) D. a b 3 解同余方程 31 x 5（mod 17） 。 解： (1) 由于 gcd(17,31)=1,由定理 3 知存在 31 模 17 的逆。 求

5、 31 和 17 的线性组合（欧几里得逆过程） 31=117+14 17=114+3 14=43+2 3=12+1 2=12+0（结束） 因此，-631+1117=1 ，-6 是 31 模 17 的逆 (2) -631x -65（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=Me mod n=857 mod 14

6、3=123 (2) 接下来求 d： ed1 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=177+1 7=71+0 （结束） -177+1120=1 因此，d=-17+120=103 (3) M=Cd (mod n)=123103 mod 143=85 6-1 1. 设集合 A=1,2,3,，10，问下面定义的二元运算关于集合 A 是否封闭？ a) xy=max(x,y) 封闭 b) xy=min(x,y)

7、封闭 c) xy=gcd(x,y) 封闭 d) xy=lcm(x,y) 不封闭，例 lcm(3,7)=21 e) xy=质数 p 的个数，使得 xpy 不封闭，例 66=0 2.设代数系统,其中 A=a,b,c, 是 A 上的一个二元运算。对于由以下几个 表所确定的运算，试分别讨论他们的交换性、等幂性以及在 A 中关于运算是否 有幺元。如果有幺元，那么 A 中的每个元素是否有逆元。 2 a) b) c) d) a b c a b c a b c b a c c c c a b c a b c a b c b c a c a b a b c a b c a b c a b c a b c a b

8、 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+上的两个二元运算为：ab=ab, ab=ab, a,bI+。试证明对是不可 分配的。 a ()() () ()() () b+c b c bcbcb c b cab ca a ba caaa aa b c + = = ?i ?i i? 证明：由于 而不一定等于，所以 对 是不可

9、分配的。 6-2 1.证明：如果 f 是由到的同态映射，g 是由到的同 态映射，那么 g。f 是由到的同态映射。 ( * )( )( ) B()( )( ), ( * )( ( * )( ( )( ) = ( ( )( ( ) abAf a bf af b cdg c dg cg d abA gf a bg f a bg f af b g f ag f bg = = = = ? ? ? ? 证明： 因为对于任意的 ，有， 而对于任意的 ，有 所以对于任意的 ，有： ( ) ( ) f agf b gf ? ?因此，是由到的同态映射。 2. 与同构吗？ 3 -0a( ), ( )(0)(0)(

10、)(0) ( )(0)( )(0)(0) (0)(0)=1. (2) -0c(c)-1, ()( )( )(-1) (-1)1, =00 f RRf f ccf cf c ccc = += += 中的幺元。即应有 对于 1必存在使得有： 由于是同构映射， 所以必有唯一的元素0与1对应，所以， (0)-1 f= 由此导致的矛盾。 因此，与不可能同构。 3.证明：一个集合上任意两个同余关系的交也是一个同余关系。 12 11 12 12 1 , , , RR a bc dRR a bc dRa bc dR RR a c b dRa c 所以 因此，一个集合上任意两个同余关系的交仍是一个同余关系。 4

11、.考察代数系统,以下定义在 I 上的二元关系 R 是同余关系吗？ a) R,当且仅当(x0y0)(x0y0) b) R,当且仅当|x-y|10 c)R,当且仅当(x=y=0)(x0y0) d) R,当且仅当 xy )R-2,-2 , 1,4 -2+1,-2+4=-1,2 )R )-4,6 ,6, 6 -4+6,6-6=2,0 aR RR b cR 解： 首先证明 是等价关系，但存在着而 ， 所以 不是同余关系。 传递性不成立，不是等价关系，更不是同余关系。 而 )R RR d ， 所以 不是同余关系。 对称性不成立，不是等价关系，更不是同余关系。 以上只是该题的简略答案，实际解题时应该一步步进

12、行等价关系验证， 然后再进行同余关系验证。 6-3 1.设是一个半群，aS，在 S 上定义一个二元运算，使得对于 S 中的任 意元素 x 和 y，都有 xy=xay，证明二元运算是可结合的。 4 ( ( )()() ()()() )() x yzx ayzx ayazx ay az xy zxy azx ay azx ay az x yzxy z = = = = = = = ? ? ? 证明：由于 所以 2.设是一个代数系统，是 R 上的一个二元运算，使得对于 R 中的任意元 素 a，b 都有 ab=a+b+ab，证明 0 是幺元且是独异点。 , 000, 000, 0=0=a ,+R R ,

13、 , ()() aR aaaa aaaaa a a bR a baba bR a b cR a bcaba bc =+= =+= =+ =+ i i i i i 证明：(1)对于任意的 所以 ，因此0是幺元. (2)对于任意的,由于 和 在 上封闭，所以， ，即 在 上封闭。 对于任意的有 ( ) ()() () aba bcaba b c abca ba cb ca b c ab cabcb c abcb ca bcb c =+ + =+ + =+ + =+ + + iii iiii i i iii ()(), iiii i 运算 是可结合的。 因此，是独异点。 3.设X=R-0,1，在X上

14、定义 6 个函数如下：对于任意xX，f1(x)=x; f2(x)=x-1; f3(x)=1-x; f4(x)=(1-x)-1; f5(x)=(x-1)x-1; f6(x)=x(x-1)-1 试证明是一个群。其中F=f1，f2，f3，f4，f5，f6， 。是函数的复合运算. 证明：由函数复合运算的定义 f。g(x)=f(g(x),可写出。在 F 上的运算表如下： 。 f1 f2 f3 f4 f5 f6 f1 f2 f3 f4 f5 f6 f1 f2 f3 f4 f5 f6 f2 f1 f4 f3 f6 f5 f3 f5 f1 f6 f2 f4 f4 f6 f2 f5 f1 f3 f5 f3 f6

15、 f1 f4 f2 f6 f4 f5 f2 f3 f1 由表可知，运算。在 F 上是封闭的， 运算。是可结合的， f1是运算的幺元， f1 f2 f3 f6均以自身为逆元， f4 f5互为逆元。 因此，是一个群。 4.设是一个半群， e 是幺元且对于每一个 xA, 存在x ? A， 使得x xe= ? 。 a)证明：对于任意的 a,b,cA，如果,ca ba cb=则。 b)通过证明 e 是 A 中的幺元，证明是群。 5 a()() = = = ? ? 证明：( )由可得到 由于是半群，满足结合律， 所以有： ( ， 是左幺元 ( )对于任意的 ()() (a)()ee ()() =x ? ?

16、 ? ? , 结合的结论有：，说明 也是右幺元，故 是幺元。 于是对于任意的, 所以，故有，说明任意 均有逆元 ，因此 是群。 5.设是群，对于任一 a G ,令 H=y|ya=ay, yG, 试证明是 的子群。 证明：根据 H 集合的定义知，任意的 yH, 一定有 yG，因此 HG。 由于是群，运算在 G 中满足结合律，在 H 中也满足结合律。 对于任意的 x,yH,以及任意的 a G，因为 -1-1-1-1 (xy) axy a=x ay=axy=a (xy) yHH * H* ()() x e aa eeH xx aa x xx axxaxx = = = = 所以，说明 关于 是封闭的。

17、 因为，所以。 对于任意的，由于，所以 -1-1-1 axxaxH=表明 综上所述，是的子群。 6.设是群，且|A|=2n，nI+。证明：在A中至少存在ae，使得aa=e。其中 e是幺元。 证明：对于任意的xA，均有它的逆元x -1A，使得-1-1 x xxxe=，由于 互为逆元的两个不相等的元素是成对出现的，而且群中有唯一的幺元e，因此， 至少有一个元素是以自身为逆元的。即必存在aA,ae,使得 a ae= 6-4 1. 设是一个独异点，并且对于任一 x G , 都有 xx=e，其中 e 是幺元， 证明是一个阿贝尔群。 2.证明任何阶数分别是 1,2,3,4 的群都是阿贝尔群。并举一个 6

18、阶群，它不是阿贝 尔群。 6 -1 111 , ; ,(), xGxxe e xx a bG a ba bbab a = = = 1.证明：对于任意的有是幺元，说明每个 元素都有逆元，且 对于任意的 因此，是阿贝尔群。 2.证明： (1)对于阶数为 1 的群，该群中仅有唯一的一个幺元 e，ee=e，显然是阿贝 尔群。 (2)对于阶数为 2 的群，该群中除幺元外，仅有一个与 e 不同的元素 a,且 ea=ae=a, 因为每个元素都要有逆元，因此有 aa=e，所有运算满足交换律，所 以是阿贝尔群。 (3)对于阶数为 3 的群。若ab=a，则有a-1ab= a-1a，导致b=e 的矛盾；同理，若ab

19、=b，则导致a=e的矛盾；所以必有ab=e。又因 ba= babb-1=beb-1=e，因此群是阿贝尔群。 (4)对于阶数为 4 的群, 1) 如果 a,b,c 中有两个元素互为逆元，不妨设它们是 a,b, 则 ab=ba=e。 于是必有 cc= e, ace( c 的唯一逆元是 c)， 所以 ac=b。 （ 假 设ac=a ， 代 入ab=ba ， 有acb=bac ， 就 有 acb=ec=c=a b，与 ab=e 矛盾。假设 ac=c，由 cc= e 有： cc=(ac)c=a(cc)=ae=a,推出矛盾。因此只能是 ac=b） 。同理可 证 ca=b，故 ac=ca。 同理可证 bc=

20、cb。 2) 若 a,b,c 中的每一个元素都以自身为逆元，则必有 ab=ba=c， ac=ca=b，bc=cb=a。 因此，不论哪种情况，都表明是阿贝尔群。 (5) 定义在集合 S=a,b,c上的所有双射函数为： f0：f0(a)=a, f0(b)=b, f0(c)=c; f1：f1(a)=a, f1(b)=c, f1(c)=b; f2：f2(a)=b, f2(b)=a, f2(c)=c; f3：f3(a)=b, f3(b)=c, f3(c)=a; f4：f4(a)=c, f4(b)=a, f4(c)=b; f5：f5(a)=c, f5(b)=b, f5(c)=a; 于是集合F=f1，f2，

21、f3，f4，f5，f6关于函数的复合运算。构成群，群的阶 数为 6，其运算如下表所示。显然，它不是阿贝尔群。 。 f0 f1 f2 f3 f4 f5 f0 f1 f2 f3 f4 f5 f0 f1 f2 f3 f4 f5 f1 f0 f4 f5 f2 f3 f2 f3 f0 f1 f5 f4 f3 f2 f5 f4 f0 f1 f4 f5 f1 f0 f3 f2 f5 f4 f3 f2 f1 f0 第 5 页习题 3 中的 6 阶群也不是阿贝尔群，也可以该习题 3 为例来证明该题目。 7 6-5 1.设是一个代数系统，其中+, 为普通的加法和乘法运算，A 为下列集合： a) A=x|x=2n,nI 不是，没有乘法幺元 b) A=x|x=2n+1,nI 不是，对于加法不封闭 c) A=x|x0,且 xI 不是，对于任意 x0，不存在加法逆元 d) 4 A=x|x=a+b 5, a,bR 是整环 e) A=x|x=a+b 3, a,bR 是整环 问是整环吗？为什么？ 是整环的题目，要有验证过程。是整环的题目，要有验证过程。 2. 设是一个环，并且对于任意的 aA 都有 aa=a，