信息安全第2章-同余习题解答

第二章同余习题解答

1.(1)写出模9的一个完全剩余系，它的每个数是奇数。

(2)写出模9的一个完全剩余系，它的每个数是偶数。

(3)(1)和(2)中的要求对模10的完全剩余系能实现吗？解模9的最小非负完全剩余系为：

0,1,2,3,4,5,6,7,8(1)模9的每个数都是奇数的一个完全剩余系：

9,1,11,3,13,5,15,7,17(2)模9的每个数都是偶数的一个完全剩余系：

0,10,2,12,4,14,6,16,8模9的不同剩余类：m

＝9

C0＝

C1＝

C2＝

C3＝

C4＝

C5＝

{c|c∈Z,0≡c(mod9)}＝{…,-18,-9,0,9,18,…}

{c|c∈Z,1≡c(mod9)}＝{…,-17,-8,1,10,19,…}

{c|c∈Z,2≡c(mod9)}＝{…,-16,-7,2,11,20,…}

{c|c∈Z,4≡c(mod9)}＝{…,-14,-5,4,13,22,…}

{c|c∈Z,5≡c(mod9)}＝{…,-13,-4,5,14,23,…}

{c|c∈Z,3≡c(mod9)}＝{…,-15,-6,3,12,21,…}模9的不同剩余类：m

＝9

C6＝

C7＝

C8＝

{c|c∈Z,6≡c(mod9)}＝{…,-12,-3,6,15,24,…}

{c|c∈Z,7≡c(mod9)}＝{…,-11,-2,7,16,25,…}

{c|c∈Z,8≡c(mod9)}＝{…,-10,-1,8,17,26,…}模10的不同剩余类：m

＝10

C0＝

C1＝

C2＝

C3＝

C4＝

C5＝

{c|c∈Z,0≡c(mod10)}＝{…,-20,-10,0,10,20,…}

{c|c∈Z,1≡c(mod10)}＝{…,-19,-9,1,11,21,…}

{c|c∈Z,2≡c(mod10)}＝{…,-18,-8,2,12,22,…}

{c|c∈Z,4≡c(mod10)}＝{…,-16,-6,4,14,24,…}

{c|c∈Z,5≡c(mod10)}＝{…,-15,-5,5,15,25,…}

{c|c∈Z,3≡c(mod10)}＝{…,-17,-7,3,13,23,…}模10的不同剩余类：m

＝10

C6＝

C7＝

C8＝

C9＝

{c|c∈Z,6≡c(mod10)}＝{…,-14,-4,6,16,26,…}

{c|c∈Z,7≡c(mod10)}＝{…,-13,-3,7,17,27,…}

{c|c∈Z,8≡c(mod10)}＝{…,-12,-2,8,18,28,…}

{c|c∈Z,8≡c(mod10)}＝{…,-11,-1,9,19,29,…}由模10的不同剩余类可以看出，一个剩余类中的数或全为偶数或全为奇数。所以对模10来说不存在满足(1)或(2)的完全剩余系。2.证明：当m>2时，02,12,…,(m－1)2一定不是模m

的完全剩余系。证明：由(m－1)2

－12

＝m(m－2)≡0

(modm)，知(m－1)2≡12(modm)所以，结论成立。

(事实上(m－i)2

－i2

＝m(m－2i)≡0

(modm)

即

(m－i)2≡i2(modm)，i＝1,2,…,[m/2]抽屉原理：原理1

把n+k

(k≥1)个的物体放到n个抽屉里，则至少有一个抽屉里有2个或2个以上的物体。原理2把mn+k

(k≥1)个的物体放到n个抽屉里，则至少有一个抽屉里有m+1个或多于m+1个的物体。3.设有m个整数，它们都不属于剩余类0

(modm)。那么，其中必有两个数属于同一剩余类。证明：设m个不属于剩余类0

(modm)的整数分别为a1,a2,…,am。模m的除剩余类0

(modm)以外的剩余类为：C1,C2,…,Cm－1。共有m－1个(m个物品放在m－1个抽屉中)

。根据抽屉原理，m个整数a1,a2,…,am中必有两个数属于同一剩余类。4.在任意取定的对模m两两不同余的[m/2]＋1个整数中，必有两数之差属于剩余类1

(modm)，如何推广本题。证明：设取定的[m/2]＋1

个两两不同余的整数分别是a1,a2,…,a[m/2]＋1

，模m的剩余类为C0,C1,C2,…,Cm－1。由题意a1,a2,…,a[m/2]＋1两两不同余，所以他们分别属于不同的剩余类。又在模m的剩余类C0,C1,C2,…,Cm－1中，按照这样的顺序，两两互不相邻的剩余类最多有[m/2]个(有[m/2]个抽屉)

。根据抽屉原理，整数a1,a2,…,a[m/2]＋1

中必有两个数在相邻的两个剩余类中。设ai属于剩余类Ck

，aj属于剩余类Ck＋1，即ai≡k，aj≡k＋1(modm)。根据2.1节定理4，aj－ai≡1(modm)。即aj－ai属于剩余类1

(modm)。推广：在任意取定的对模m两两不同余的[m/2]＋i个整数中，必有两数之差属于剩余类i(modm)

。设m1

m。那么对任意r有Cr(modm)

Cr(modm1)等号成立当且仅当m1＝m。进一步，设d＝m/m1

则5.(i)把剩余类1

(mod5)写成模15的剩余类的并。解：根据公式取r＝1

，m1＝5，m＝15，d＝m/m1＝3，剩余类1

(mod5)写成模15的剩余类的并为：所以，C1

(mod5)＝C1

(mod15)∪C6

(mod15)∪C11

(mod15)

5.(ii)把剩余类6

(mod10)写成模120的剩余类的并。解：根据公式，取r＝6

，m1＝10，m＝120，d＝m/m1＝12，剩余类6

(mod10)写成模120的剩余类的并为：C6(mod10)＝C6＋10(mod120)∪C6＋20(mod120)∪C6＋30

(mod120)∪C6＋40(mod120)∪C6＋50(mod120)∪C6＋60

(mod120)∪C6＋70(mod120)∪C6＋80(mod120)∪C6＋90(mod120)∪C6＋100(mod120)∪C6＋110

(mod120)∪C6＋120

(mod120)即C6(mod10)＝C16(mod120)∪C26(mod120)∪C36

(mod120)∪C46(mod120)∪C56

(mod120)∪C66

(mod120)∪C76(mod120)∪C86

(mod120)∪C96

(mod120)∪C106(mod120)∪C116

(mod120)∪C6

(mod120)62003年5月9日是星期五,问第220080509天是星期几?

解因为

21≡2(mod7),22≡4(mod7),23=8≡1(mod7)

又20080509＝6693503×3,所以

220080509＝(23)6693503≡1(mod7)

故第22003天是星期六。7证明：如果ai≡bi

(modm)，1

i

k则(i)a1＋a2＋…＋ak

≡

b1＋b2＋…＋bk(modm)；

(ii)a1a2…ak

≡

b1b2…bk(modm)。证：由题设,根据2.1节定理1,分别存在整数

c1,c2,…,cn

使得

a1＝b1＋c1m,a2＝b2＋c2m,…,ak＝bk＋ckm

从而a1＋a2＋…＋ak

＝b1＋b2＋…＋bk

＋(c1＋c2＋…＋ck

)m因为c1＋c2＋…＋ck

是整数,

所以根据2.1节定理1,有

a1＋a2＋…＋ak

≡

b1＋b2＋…＋bk(modm)。证：由题设,根据2.1节定理1,分别存在整数

c1,c2,…,cn

使得

a1＝b1＋c1m,a2＝b2＋c2m,…,ak＝bk＋ckm

从而

a1a2…ak

＝b1b2…bk

＋gm

其

g＝

c1b2…bk＋b1c2…bk＋…＋c1c2…ck是整数,

所以根据定理1,有a1a2…ak

≡

b1b2…bk(modm)。14.证明：如果ak

≡

bk(modm)

，

ak＋1

≡

bk＋1(modm)

，a，b，k，m是整数，k>0，并且(a，m)

＝1，那么a≡

b(modm)

。如果去掉(a，m)

＝1这个条件，结果成立吗？证明：由ak

≡

bk(modm)

得bk

＝ak

＋cm。两边同时乘以b得bk＋1

＝(ak

＋cm)b

＝ak

b＋cmb

(1)由已知条件ak＋1

≡

bk＋1(modm)

得

bk＋1

＝ak＋1

＋dm(2)由(1)和(2)得ak＋1

＋dm＝ak

b＋cmb，即

ak＋1

－ak

b＝

cmb

－dm＝(cb

－d)m，

ak(a－b)＝

(cb

－d)m，

由(a，m)

＝1知(ak，m)

＝1，所以必有

m

(a－b)。即a≡

b(modm)

。当去掉(a，m)

＝1这个条件时，结果不成立。如15.当正整数n满足什么条件时，1＋2＋…＋(n－1)≡0(modn)13＋23＋…＋(n－1)3≡0(modn)一定成立(不计算等号左边的和式)。解：当n为奇数时，有

2(n-1)

1＋2＋…＋(n－1)

＝

(1＋(n－1))＋(2＋(n－2))＋

…＋((n－1)/2＋((n＋1)/2)

≡0(modn)当n为偶数时，有2

n

1＋2＋…＋(n－1)

＝

(1＋(n－1))＋(2＋(n－2))＋

…＋((n－2)/2＋((n＋2)/2)＋n/2

≡

n/2≡0(modn)当n是奇数，有

2(n-1)

13＋23＋…＋(n－1)3

＝

(13＋(n－1)3)＋(23＋(n－2)3)＋

…＋[((n－1)/2)3＋((n＋1)/2)3]

≡0(modn)当n为偶数时，有

2

n

13＋23＋…＋(n－1)3

＝

(13＋(n－1)3)＋(23＋(n－2)3)＋

…＋[((n－2)/2)3＋((n＋2)/2)3]＋(n/2)3

≡(n/2)3

≡0(modn)25.如果p是奇素数，那么

12·32·…·(p－4)2·(p－2)2

≡(－1)(p＋1)/2(modp)证明：由12·32·…·(p－4)2·(p－2)2

≡

1

·3

·…·(p－4)

·(p－2)·(－(p－1))

·(－(p－3))

·…·(－4)·(－2)

≡(－1)(p－1)/2

(p－1)！

(modp)

≡(－1)(p－1)/2＋1(modp)

≡(－1)(p＋1)/2(modp)所以12·32·…·(p－4)2·(p－2)2

＝

1

·3

·…·(p－4)

·(p－2)

·1

·3

·…·(p－4)

·(p－2)

≡

(－1)(p－1)/2

(

(p－1)

·(p－3)

·…·4

·2)

·1

·3

·…·(p－4)

·(p－2)(modp)

≡

(－1)(p－1)/2

(p－1)

！

(modp)

≡(－1)(p－1)/2＋1(modp)

≡(－1)(p＋1)/2(modp)26.证明：如果p是素数，并且p

≡3(mod4)，那么{(p－1)/2}！≡

1(modp)。证明：根据Wilson定理，(p－1)！≡－1(modp)，即(p－1)

·(p－2)

·…·(p－

(p－1)/2)·((p－1)/2)!

≡－1(modp)。又

p－1≡－1,p－2≡－2,…,(p－

(p－1)/2)≡－

(p－1)/2(modp)，所以，(p－1)！

≡(－1)(－2)…(－

(p－1)/2))(p－1)/2)!

≡(－1)(p－1)/2((p－1)/2)!((p－1)/2)!(modp)。由p

≡3(mod4)

知，p－1≡2(mod4)

即

(p－1)/2≡1(mod2)。所以(－1)(p－1)/2＝－1。由(p－1)！≡－1(modp)，得

[((p－1)/2)!]2≡1(modp)，即

[((p－1)/2)!]2－1≡0(modp)，([((p－1)/2)!]

+1)([((p－1)/2)!]

－1)≡0(modp)，

所以

{(p－1)/2}！≡

1(modp)。35.证明：如果p和q是不同的素数，则

pq－1＋q

p－1≡1(mod