1 2 3 4 5 6 7 8 3 4 1 1 1 1 1 4 0 1 -4 5 -9 14 -23 37 1 -3 13 -16 29 -45 74 -119 550 119 74 45 29 16 13 3 1 -4 5 -9 14 -23 37 -171 -3 13 -16 29 -45 74 -119 550 119 74 45 29 16 13 3 1 根据扩展欧几里德算法逆元是550
2.9、用快速指数模运算方法计算200837 mod 77和319971 mod 77
解：由于gcd(2008,77)?1,且77?7?11，?(7)?6,?(11)?10,[?(7),?(11)]?3037?7mod30,由欧拉定理可知200837?20087mod77，设a为指数，计算过程如下：a?6时，2008?6mod77a?3时，20082?36mod77a?2时，6?36?216?62mod77a?1时，362?64mod77a?0时，64?62?3968?41mod77，所以200837?20087mod77?41mod77解：由于gcd(3,77)?1,且77?7?11，?(7)?6,?(11)?10,[?(7),?(11)]?3019971?21mod30,由欧拉定理知319971?321mod77，由21??10101?2得32?9， 31?90?3(mod77)9?4,3?4?12(mod77)42?16，12?160?12(mod77)162?25,12?251?69(mod77).即319971?69mod77
2.10、用费马定理求3201 (mod 11)
21
解：由于gcd(3,11)?1,那么由费马定理得310=311-1?1mod11,那么3201?3?3200mod11?3?(310mod11)?(310mod11)?........(310mod11)mod11
???????????????????共20个?3mod11?3
2.11、计算下面欧拉函数；
(1) ?(41) 、?(27)、?(231) 、?(440)
解：（?41）=41-1=40?(27)=?(33)=33?32?18
?(231)??(3?7?11)??(3)??(7)??(11)?(3?1)?(7?1)?(11?1)?120?(440)??(23?5?11)?(23?22)?(5?1)?(11?1)?160
5
(2) φ(2)φ(6)和φ(3)φ(4)，哪一个等于φ(12)。
解：?(2)?(6)??(2)??(2)??(3)?1?1?2?2?(3)?(4)??(3)?(22)?2?(22?2)?4?(12)??(3?2)??(3)?(2)?2?(2?2)?4显然?(3)?(4)??(12)222
2.12、求解下列一次同余方程 (1)3x≡10(mod 29)
解 因为(3，29)＝1，所以方程有惟一解。利用辗转相除法求得使3x＋29y＝1成立的x、y为x＝10，y＝－1。于是3·10＋29·(－1)＝1，3·100＋29·(－10)＝10，所以x≡100≡13(mod 29)。 (2)40x≡191(mod 6191)
解 因为(40，6191)＝1，所以方程有惟一解。利用辗转相除法求得使40x＋6191y＝1成立的x、y为x＝1393，y＝－9。于是40·1393＋6191·(－9)＝1，40·1393·191＋6191·(－9·191)＝191，所以x≡1393·191≡6041(mod 6191) (3)258x≡131(mod 348)
解 因为(258， 348)＝6，而6 131，所以方程无解。
2.13、证明下面结论
设a、b、c、d为整数，m为正整数，若a≡b(mod m)，c≡d(mod m)，则： (1)ax＋cy≡bx＋dy(mod m)，x、y为任意整数； (2)ac≡bd(mod m)；
(3)an≡bn(mod m)，n＞0；
(4)f(a)≡f(b)(mod m)，f(x)为任一整系数多项式。
证明 (1)因为a≡b(mod m)，c≡d(mod m)，所以m|(a－b)，m|(c－d)，于是m|((a－b)x＋(c－d)y)，即m|((ax＋cy)－(bx＋dy))，故ax＋cy≡bx＋dy(mod m)。
(2)因为a≡b(mod m)，c≡d(mod m)，所以m|(a－b)，m|(c－d)，于是m|((a－b)c＋(c－d)b)，即m|(ac－bd)，故ac≡bd(mod m)。
(3)因为a≡b(mod m)，则存在整数q使得a－b＝mq。于是：
an－bn＝(b＋mq)n－bn＝(bn＋bn-1(mq)1＋…＋b1(mq)n-1＋(mq)n)－bn＝mp，其中p是一整数。
所以an≡bn(mod m)。 (4)由(1)和(3)可证。
2.14、求满足下面同余方程的解
x≡1(mod 5)，x≡5(mod 6)，x≡4(mod 7)，x≡10(mod 11)
解：令m1＝5，m2＝6，m3＝7，m4＝11，b1＝1，b2＝5，b3＝4，b4＝10。则m＝2310，M1＝462，M2＝385，M3＝330，M4＝210。
利用辗转相除法求得M1?＝－2，M2?＝1，M3?＝1，M4?＝1。 所以，x≡1·(－2)·462＋5·1·385＋ 4·1·330＋10·1·210≡4421≡2111(mod 2310)
2.15、求Z5中各非零元素的乘法逆元。 解：1-1=1,2-1=3,3-1=2,4-1=4
6
2.16、类似于表2.2，用表列出有限域GF(5)中的加法和乘法运算 解：表如下： 0 1 2 加法 0 1 2 3 4 乘法 0 1 2 3 4 a 0 1 2 3 4 -a 0 4 3 2 1 a-1 -- 1 3 2 4 0 1 2 3 4 0 0 0 0 0 0 1 2 3 4 0 1 0 1 2 3 4 2 0 2 4 1 3 2 3 4 0 1 3 3 4 0 1 2 3 0 3 1 4 2 4 4 0 1 2 3 4 0 4 3 2 1 2.17、对于系数在Z10上的取值的多项式运算，分别计算
a?、x+2)-(x2+5)=-x2+7x-3mod(10x2+10x+10)=9x2+7x+7
b、(6x2?x?3)?(5x2?2)?(30x4?5x3?27x2?2x?6)mod(10x4?5x3?27x2?2x?6)?5x3?7x2?2x?6
2.18、假设f(x)=x3+x+1在GF(2n)中是一个不可约多项式，a(x)=2x2+x+2,b(x)=2x2+2x+2,求a(x)b(x)
解：a(x)?b(x)=a(x)b(x)modf(x)?(2x2+x+2)(2x2+2x+2)mod（x3+x+1）=6x+6x+2x+432
2.19、编程实现模n的快速指数运算。 #include \#include
int main(int argc, char* argv[]) { int m,e,n; printf(\ cin>>e;
7
printf(\ cin>>m; printf(\ cin>>n; int a=e,b=m,c=1; for(a=e;a>0; ) { if(a%2==1) { a-=1; c=(c*b)%n; if(a==0) cout< 2.20、编写实现扩展欧几里德算法求最大公因子和乘法逆元。#include \#include int main(int argc, char* argv[]) { int m,d; cout<<\ first number:\ cin>>m; cout<<\ cin>>d; int a[3]={1,0,m},b[3]={0,1,d}; int Q; if(b[2]%a[2]>=0) { Q=b[2]/a[2]; for(int i=0;i<=2;i++) { int t[3]; t[i]=a[i]-Q*b[i]; a[i]=b[i]; b[i]=t[i]; 8