华东师范大学离散数学章炯民课后习题第2章答案_离散数学课后答案详细

华东师范大学离散数学章炯民课后习题第2章答案由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学课后答案详细”。

P32

11*2设n>1是奇数，证明n整除(1+++)(n-1)!2n-1证明：

11++)(n-1)!=[(11)(11)(11)](n1)!2n-11n12n2

nnn)(n1)!n1n1n12(n2)

111](n1)!n1n1n1n2(1+=(=n[

4求方程963x+657y=(963,657)的所有整数解。

解：

（1）

由辗转相除法可得到方程的一个解：x0 =-15，y0=22

设(x,y)也是一个解，则963x+657y=(963,657)

于是963(x-x0)+657(y-y0)=0，从而107(x-x0)=-73(y-y0)，所以10773(y-y0)。又因为(107,73)=1,所以107(y-y0)

设(y-y0)=107k，则(x-x0)=-73k，从而x=x0-73k，y=y0+107k

容易验证，对于任意整数k，(x0+73k,y0+107k)满足原方程。

所以，原方程有无穷多个解：x=-15-73k

y=22+107k

其中k=…,-2,-1,0,1,2,…

（2）

963x+657y=(963,657) 963x-9=-657y

x,yZ，963x-9=-657y  xZ，963x≡9(mod 657)

5．设a、b、c、d是正整数，满足ab=cd。证明：a4+b4+c4+d4不是素数。证明：设11)(n-1)!∴n整除(1+++2n-1adp，其中p和q是互素的正整数 cbq

aq=cp  paq  pa（∵p和q互素）

于是，uN，使a=pu  c=qu

同理vN，使d=pv  b=qv

从而，a4+b4+c4+d4=(p4+q4)(u4+v4) a4+b4+c4+d4不是素数

7团体操表演过程中，要求队伍在变换成10行、15行、18行、24行时均能成长方形，问需要多少人？

解：

由题意，所求之数为10,15,18,24的倍数，[10,15,18,24]＝360，故需360k(k>0)人。

10证明：如果p,p+2,p+4都是素数，则p=3。

证明：用反证法，假设p≠3。

p,p+1,p+2是3个连续的整数，其中有且仅有一个为3的倍数。

p,p+2是素数，且p≠3  p+1是3的倍数

不妨设p+1=3k(kN)。

于是，p+4=3(k+1)必为合数，与条件矛盾。

所以，p=3

11计算2400 mod 319。

解：

φ(n)=319*(1-1／11)(1-1／29)=280

2400 mod 319=2280·2120mod 319=2120mod 319=(210)12mod 319)=(3*319+67)12 mod 319=(672)6 mod 319=((23)2)3 mod 319=(210)3 mod 319=111

14(2)解同余方程：56x≡88(mod 96)。

解：

（1）(a,m)=(56,96)=8，8|96，方程有解

（2）a=56/8=7，b=88/8=11，m=96/8=12

（3）由辗转相除法可求得p和q满足pa+qm=1，p=-5，q=3

特解x0=pb=-511

（4）解为x-511+t12(mod 96)，t=0,1,,7 即x≡5,17,29,41,53,65,77,89(mod 96)

16(1)解同余方程组：x3(mod5)x7(mod9)

解：

m1=5，m2=9，M=45，M1=9，M2=5

9x≡1(mod 5),5x≡1(mod 9),的特解：c1=-1,c2=2原方程组的解：x≡-1×3×9+2×7×5≡43(mod 45)

5x7(mod 12)16(2)解同余方程组7x1(mod 10)

解：

5x≡7(mod 12) 12(5x-7) 4(5x-7)且3(5x-7) 5x≡7(mod 4)且5x≡7(mod 3)∴同余方程5x≡7(mod 12)与同余方程组5x7(mod 4)同解

5x7(mod 3)

x3(mod 4)后者可规约为 x2(mod 3)

类似地，同余方程7x≡1(mod 10)可规约为同余方程组

x1(mod 2)x3(mod 5)

x2(mod 3)x2(mod 3)x3(mod 4)x3(mod 4)∴原同余方程组可规约为，它与同余方程组同解 x3(mod 5)x1(mod 2)

x3(mod 5)

x2(mod 3)x3(mod 4)求解同余方程组： x3(mod 5)

m1=3，m2=4，m3=5，M=60，M1=20，M2=15，M3=12

20x≡1(mod 3),15x≡1(mod 4),12x≡1(mod 5)的特解：c1=2,c2=3,c3=3

原同余方程组的解：x≡2×2×20+3×3×15+3×3×12≡80+135+108≡23(mod 60)

*17解同余方程组：

x≡3(mod 8)，x≡11(mod 20)，x≡1(mod 15)。

解：

x3(mod 8)x3(mod8)x11(mod 4)x1(mod 3)原同余方程组与同余方程组x11(mod 5)同解，后者可规约为x1(mod 5)x1(mod 5)x1(mod 3)

x3(mod8)x1(mod 3)： 求解同余方程组x1(mod 5)

m1=8，m2=3，m3=5，M=120，M1=15，M2=40，M3=24

15x≡1(mod 8),40x≡1(mod 3),24x≡1(mod 5)的特解：

c1=7,c2=1,c3=4

原同余方程组的解：x≡7×3×15+1×1×40+4×1×24≡351+40+96≡91(mod 120)

19．*设m1和m2是正整数，b1和b2是整数。证明一次同余方程组

x≡b1(mod m1)，x≡b2(mod m2)

有解的充分必要条件是(m1,m2)|(b1-b2)；并且，当此条件成立时，该同余方程组的解可表示为x≡c(mod [m1,m2])，其中0

证明：用反证法，假设p≠3。

（1）

有解  可设x为一个解  m1x-b1，m2x-b2  k1,k2Z，使x-b1=k1m1, x-b2=k2m2  b2-b1=k1m1-k2m2

(m1,m2)|m1,(m1,m2)|m 2 (m1,m2)| k1m1-k2m2=(b1-b2)

（2）

(m1,m2)|(b1-b2) k,s,tN，使(b1-b2)=k(m1,m2)=k(sm1+tm2)

容易验证，x=b1-ksm1是同余方程组的解  有解

（3）容易验证，解x，kZ，x+k[m1,m2]也是解  结论

补充：编写一程序实现Miller-Rabin素性测试算法。已知RSA密码体制的公钥(e,n)=(5,35)，（1）请按本小节例题所示的方式将明文信息“rsa”加密；

（2）请破解出私钥。

解：

（1）

明文信息由26个小写字母构成，数字化编码为字母的序号：a01，r18，s19，明文“rsa”181901

取段长为2，明文” 181901”分为3段：m1=18，m2=19，m3=01

用公钥(5,35)加密得到3个密文：

c1=m1e mod n =185 mod 35=23

c2=m2e mod n =195 mod 35=24

c3=m3e mod n =015 mod 35=01

组合得到密文串：232401

（2）

由公钥：KU=(e,n)=(5,35)得到n=35的两个素因数p=5,q=7，(n)=(p-1)(q-1)=24，e=5(5,24)=1，解同余方程5d≡1(mod 24)，得到唯一解d=5

私钥： KR=(d,n)=(5,35)

请编写一个高效的指数取模运算算法

/*

exp_mod.c

handle the Modexp calculation((a^p)%m)using Montgomery algorithm(O(logn))*/

#include

int expmod(int a, int p, int m){

int r;

int k;

if(p==0)return 1;

r=a%m;

k=1;

while(p>1){

if((p&1)!=0)

k=(k*r)%m;

r=(r*r)%m;

p>>=1;

}

return(r*k)%m;

}

void main()

{

int a,b,c,r;

scanf(“%d%d%d”,&a,&b,&c);

r=expmod(a,b,c);

printf(“(%d^%d)%%%d=%dn”,a,b,c,r);

//getch();

}

编写一程序实现Miller-Rabin素性测试算法

#include

#include

int powmod(int i,int d,int n)//模n的大数幂乘快速算法

{

int c = 1;//c为余数，保存每次模后的数

while(d == 0)

{

if(d % 2 == 0){d = d / 2;i =(i * i)% n;}//d是偶数，就先求i平方的模

else {d--;c =(c * i)% n;}//d是奇数，就与上一次的模相乘后在求模

}

return c;//d为0，只能通过d--，所以返回的必是c

}

void main()

{

int i = 2,d,n;

d = n1){printf(“是素数”);break;} //如果模为n-1也结束，因为只有当模为1时才能不断地把d折半

}

else {printf(“ 不是素数”);printf(“%d”,powmod(i,d,n));break;}//如果在d折半的过程中出现的powmod不是1或n-1的话就结束

}

if(d == 1)printf(“是素数”);//如果d一直都能折半到1，也为素数

//getch();

}