信息安全第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節(jié)定理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節(jié)定理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節(jié)定理1,有

a1＋a2＋…＋ak

≡

b1＋b2＋…＋bk(modm)。證：由題設,根據2.1節(jié)定理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