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

1 P32 *2 设n>1 是奇数，证明n 整除 证明： = 111111[()()()](n 1)!n 1n 11n 12n 222 =nnn()(n 1)!n 1n 1n 12(n 2)22 =111n[](n 1)!n 1n 1n 1n 222 ∴ 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 不是素数。 证明：设qpbdca，其中p和 q是互素的正整数 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)人。 11(1+++)(n - 1)!2n - 111(1+++)(n -1)!2n -111(1+++)(n -1)!2n -12 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...