網(wǎng)絡(luò)近期復(fù)習(xí)常見(jiàn)問(wèn)題問(wèn)題9

1、整除和因子整除和因子 素?cái)?shù)互為素?cái)?shù)ab互素，如果它們之間沒(méi)有共同的素?cái)?shù)因子（。例如，815互素，因?yàn)? 8 15 僅有的公因子（8 的因1，2，4 815 的因子1，3，5 158 15 的公因子是 1模運(yùn)算 0 r q= a =qn+ an是一個(gè)正整數(shù)，則amodn a n的余數(shù)注意：a mod n = 0n a 一個(gè)因子。數(shù)集合0,1.n1)。這個(gè)整數(shù)集合又稱為n的Zn。因此余數(shù)集合Zn = 0, 1. , (n 顯然，a b mod n 等價(jià)于 b a mod n。例如，734mod23mod23一定不能省略不寫(xiě)。abmodnn能夠整除(ab)n|(ab)模運(yùn)算的一些性質(zhì)(amodn)+

2、 (bmodn)modn=(a+b)mod (amod n)(bmodn)modn=(ab)mod(amod n)(bmodn)modn=(ab)mod例如：11mod 815mod 8 = (11 mod 8)+(15 mod8) mod 8=3+7mod 8 =10mod 8 =(11+ 15)mod 8 =26 mod8= (11 mod8) (15mod8)mod 8= 3 7mod 8= 4(11 mod8) (15mod8)mod 8= 3 7mod 8= 4mod 8=(11 15)mod 8= 4mod8=(11 mod 8) (15 mod8)mod 8 =3 7mod8 =

3、21 mod 8 =(1115)mod 8 =165 mod8 =1723mod551716+4+2+1mod=(171617417217)mod =(1716mod55)(174mod55) (172mod55) (17mod55)mod 172mod 55 =289mod 55 =174mod55=(172mod 55)(172mod55)mod =14 14 mod 55=196 mod55 =1716mod55=(174mod55)(174mod 55)(174mod55)(174mod55)mod =31 31 31 31 mod=923521mod = 16791 55 + 16

4、mod= 1723mod5516311417mod=118048mod =2146 55+ 18 mod = (abmodnacmodnbmodncmod例如，(5 3)mod 815 mod 87 mod(5 11) mod8= 55mod 87 mod 3mod 811mod不互素，則上述結(jié)論不能成立。例如，63 18 2 mod 86 7= 42 2 mod3 7 8費(fèi)馬定理an互素 1 mod 1, 2,., (p amod p,2amodp,., (p1)a mod公式(8)中的(p1)個(gè)數(shù)恰好是某種次序的1,2,.,p 1)。例如，a5,p5mod 8,10mod 8,15 mod

5、8,20 mod8,25 mod 8,30mod 8,35 mod 也就是5,2,7,4,1,6,3。（要從一般意義上證明這一點(diǎn)也很容易。這只需要證明公式(8)中的任意兩個(gè)數(shù)的模 p 都是不同的數(shù)即可，讀者可自行證明。）將公式(8)中的(p1)個(gè)數(shù)相乘應(yīng)當(dāng)?shù)扔诠揭簿褪?,2,7,4,1,6,3。（要從一般意義上證明這一點(diǎn)也很容易。這只需要證明公式(8)中的任意兩個(gè)數(shù)的模 p 都是不同的數(shù)即可，讀者可自行證明。）將公式(8)中的(p1)個(gè)數(shù)相乘應(yīng)當(dāng)?shù)扔诠?7)中的(p1)個(gè)數(shù)相乘： (a mod p) (2a mod p) . ( (p 1)a mod p) = (p 1)!(amodp)(

6、2amodp).(p1)amod p)modp=(p1)!mod(ap1)(p1)!modp= (p 1)! mod p= 1 (p1)! mod利用公式(5)，因?yàn)?p1)!p互素，因此可以從等式兩端消去(p1)!ap1modp=1 mod 或ap11mod函數(shù)函數(shù)(Eulerstotient function)記為(n)，(n)nn互素的正整數(shù)個(gè)數(shù)(p) = p 例如，p11時(shí)，(p101111互素的正整數(shù)個(gè)數(shù)10 (n) = (pq) = (p) (q) = (p 1) (q 7,1421,11,2233,等都去除。因此下面就按照這樣的思路證明公式(10)(n)= (pq1)(p1) (

7、q1)=pqp q+1 =(p1) (q 1)=(p) 1, 2, 3, 4, 5, 6, 8, 9. 10, 12, 13, 15, 16, 17, 18, 19, 20, 23, 24, 25, 26, 27, 29, 30, 31, 32, 36, 37, 38, 39, 40, 41, 43, 45, 46, 47, 48, 50, 51, 52, 53, 54, 57, 58, 59, 60, 61, 62, 64, 65, 67, 69,7172,7374, 75, 76定理 1 mod a3, n10, (n(10) = 34811mod10a2,n11, (n(11)10, 21010241mod11證明 如果 n 為任意整數(shù)，則如果 n 為任意整數(shù)，則的正整數(shù)個(gè)數(shù)。設(shè)這樣的整數(shù)集合為 R：R=x1,x2, S=ax1modn,ax2 modn,ax(n)modn S中不存在重復(fù)的整數(shù)。因?yàn)楦鶕?jù)公式(5)aximodnaxjmodnxixj。因此，集合 S 中所有的數(shù)的乘積應(yīng)當(dāng)?shù)扔诩?R 中所有的數(shù)的乘積：(ax1modn)(ax2modn)(ax(n)modn)=(x1)(x2)(ax1modn)(ax2modn)(ax(n)modn)modn=(x1)(x2)(x(n)mod (ax1)(ax2) (ax(n)mod n=(x1)(x2) (x(n)mod