数论中的基础概念

1、1 群、环、域概念A1:加法的封闭性：如果 a和b属于G,那么a+b也属于GA2 :加法结合律：对 G中的任意元素a,b,c,a+(b+c)=(a+b)+cA3:加法单位元：G中存在一个元素0，使得对于G中的任意元素a，有a+0=0+aA4:加法逆元：对于G中的任意元素a，G中一定存在一个元素a,使得a+(-a)=(-a)+a=0A5:加法交换律：对于 G中的任意元素a和b，有a+b=b+aM1 ：乘法的封闭性：如果a和b属于G，那么ab也属于GM2 :乘法结合律：对于 G中的任意元素a,b,c有a(bc)=(ab)cM3 :乘法分配了 ：对于 G中的任意元素a,b,c,有a(b+c)=ab+

2、ac和(a+b)c=ac+bcM4 :乘法交换律：对于 G中的任意元素a,b有ab=baM5 :乘法单位元：对于G中的任意元素a,在G中存在一个元素1，使得a仁1a=aM6 :无零因子：对于 G中的元素a,b,假设ab=O,那么必有a=0或b=0M7 :乘法逆元：如果a属于G,且a不为0,那么G中存在一个元素a 1，使得aa 1 a 1a 1满足 A1-A4 称为群满足 A1-A5 称为可交换群 满足 A1-M3 称为环满足 A1-M4 称为可交换换满足 A1-M6 称为整环 满足 A1-M7 称为域2循环群：如果群中的每一个元素都是一个固定元素 a(a G)的幕ak k为整数， 那么称群G是

3、循环群。我们认为元素a生成了群G,或者说a是群G的 生成元。循环群总是交换群3 模运算(amodn) (bmodn)那么称整数 a和b是模n同余的，可以表示为：a b(modn)假设b整除a。那么用符号：b|a表示。其性质可表示如下： 如果a|1,那么a=-1或1。 如果 a|b ，且 b|a ，那么 a=b 或 a=-b 任何不等于零的数整除 0 如果b|g且b|h，那么对任意整数 m,n都有b| mg+nh证明性质：如果 b|g ，那么 g b g1,g 为整数。如果 b|h ，那么 h b h1，h 为整数。于是： mg nh mbg1 nbh1 b (mg1 nh1) 因此 b 整除

4、mg+nh.同余的性质：1 如果 n| a-b ，那么 a b modn2a b modn 隐含 b a modn3a b modn ，b c modn 隐含 a cmodn性质 1 证明：如果n|(a b),那么k , k为整数。使得a b kn , 那么有 a b kn (a mod n) b kn modn bmodn 即得 a b modn 。性质 2 证明：由 a b mod n 得：(a mod n) (bmod n)即 k1, k2 ,r Z，满足a kin r b k2n r由可推出b a (k2 kjn,由性质1可知b a modn成立 那么得证。性质 3 证明：由性质 2证

5、明过程知：k1,k2,k3,r Z 满足：b a (k2 k1)n c b (k3 k2)n由可以推出a c (k1 k2)n，由性质1可知a cmodn模算术运算有如下性质：1 amod n bmod n modn a b modn2amodnb mod nmod na- b modn3amodnbmodnmodna b mod n性质 1 证明：设 a mod nra ， bmod nrb 那么 j, kaZ ，使得 abra jn rb kn那么有：a b mod nrajn rbkn mod nra rb jk n modnra rb mod na modn bmod n mod n即

6、得证。性质 2 证明：由性质 1 证明过程知 j ,k Z 使得ra jn rb kn那么有：a-b modn ra jn-rb -kn modn ra - rb j - k n mod n ra - rb modna modn - b modn modn性质 3 证明：前半段证明如上，2a b mod n rarb rb jn rakn jkn mod n2rarb rbj rakn jkn modnra rb mod na mod n bmod n mod n定义比 n 小的非负整数集合为 Zn0,1, , n 1 。这个集合称为 剩余类集 ，或模 n 的剩余类。Zn中每一个整数都代表一个

7、剩余类，我们可以将模 n的剩余类表示为：0,1,2,n 1，其中r a:a是一个整数，a r mod n。如果 a b a c modn ，那么 b c modn假设 a 与 n 互素，如果 a b a c modn ，那么 b c modnZn中整数模运算性质:交换律：w x modn (x w)modn w x modn (x w)modn结合律：w x y modn (x w y )modnw x y modn (w x y)modn分配律：w x y modn (w y) x y ) modn单位元：w 0 modn wmodnw 1 modn wmodn加法逆元-W：对于Zn中的任意

8、w，存在一个z使得w z Omodn加法逆元：对每一个Zn，存在一个u,使得w+u=0 mod n，记为u=-w,显然在模n 下， -w=n-w。如果 a bmodn,c dmodn ，那么有a c b d modn ，特例 a c b cmodn ，更一般式： ax cy bx dy modn， x,y Zac bdmodn特例： ac bcmodnfa f b modn其中f(x)为任意给定的一个整系数多项式最大公约数：gcd(a,b) max k,满足k|a和k | b欧几里得算法：对于任意非负整数a和任意正整数b有gcd(a,b) gcd(b,amodb)算法描述如下：设整数 a b

9、O,EUCLID(a,b)1X a;Y b ；2如果Y=0，返回X=gcd(a,b)，否那么继续;3R=XmodY4X Y ；5 YR;6返回2扩展的欧几里得算法描述如下：Extended EUCLID(a,n)1 X1,X2,X31,0,n ； Y1,Y2,Y30,1,a ；2如果丫3 0，返回X3 gcd(a, n)，无逆元；否那么继续；3如果 丫3 1，返回 丫3 gcd(a, n) ; 丫2 a 1 mod n ；4QX3y3 ；5T1,T2,T3X1 Q¥,X2 QY2,X3 QY3 ；6X1,X2,X3丫1,丫2,丫3 ；7丫1,丫2,丫3T1,T2,T3 ；8返回2。有

10、限域GF(P):阶为pn的有限域一般记为GF Pn，GF代表伽罗瓦域。给定一个素数p，元素个数为p的有限域GF(p)被定义为整数0,1，p-1的集合Zp，其运算为模p的算术运算。乘法逆元-1 :任意 Zp，0，存在z Zp使得 z 1modp求最大公因式：我们可以通过定义最大公因式来扩展域上的多项式和整数运算之间的类比 如果：1.c(x)能同时整除a(x)和b(x)。2. a(x)和b(x)的任何因式都是c(x)的因式。就称多项式c(x)为a(x)和b(x)的最大公因式。此定义等价定义与：gcda(x),b(x)是能同时整数a(x)和b(x)的多项式中次数最 高的一个。多项式模运算：如果定义了

11、适宜的运算，那么每一个这样的集合 S 都是一个有限域。定义由 如下几条组成：1. 该运算遵循根本代数规那么中的普通多项式运算规那么2系数运算以P为模，即遵循有限域Zp上的运算规那么3. 如果乘法运算结果是次数大于 n-1 的多项式，那么必须将其除以某个次数为 n 的既约多项式m(x)并取余式。对于多项式f(x)，这个余式可表示为r(x)=f(x) mod m(x)素数任意整数a 1都可以惟一地因子分解为：a p1 p22 Pt t，其中pi,p2, pt均为素数， p1 p2pt 且指数皆为正整数。费马定理：p是素数，a是与p互素的正整数，那么a p 1 1mod p 或者 ap amod p

12、显然有 ak a kmod( p 1) modp,k Z欧拉函数：欧拉函数 n 是一个定义在正整数集上的函数， n 的值等于小于 n 且与 n 互素的正整数的个数。欧拉函数有性质如下：1. 如果 n 是素数，那么 n n-12. 如果 n p q ， p 和 q 是素数，且 p 不等于 q 那么n p q p q p 1 q 1欧拉定理：对任何互素的两个整数 a和n，有a n 1 modn。 欧拉定理有如下推论。1. n 为素数时，有 a n an 1 1modn ，即费马定理。2. 由欧拉定理，有a n 1 amodn进一步有ak n 1 amodn， k Z3. 假设n=pq，p和q是素数

13、，p不等于q，那么有a n 1 a(p 1)(q 1) 1 amodn。4.假设n=pq，p和q是素数，p不等于q，而gcd(a, n) p或q，仍有an1amodn中国剩余定理：设正整数mi,m2, ,m两两互素，记Mmi，贝U同余在模M同余的意义下，有唯一解Mi ,1 mi如果a,n 1，那么至少有一个整数b mod m1 b2 mod m2 g modm3bk mod mkkbi M i yi mod Mi 11i r; yi Mi modmi,1其中:m即m n丨满足am 1 modn。满足上式的最小正整数 m为模n下a的阶又称次数。本原根：如果a的阶等于n，那么称a为n的本原根又称素

14、根性质：如果a是n的本原根，贝V a,a2,a3,a n在模n下互不相同，且均与 n互素。注意：模n下的本原根并不具备唯一性，且并非所有的整数n都有本原根，只有 以下形式的整数才有本原根：2,4, pa,2pa，其中a为整数，p为奇素数。离散对数：设p为以素数，a是p的本原根，那么在模p下a,a2,a3, ,ap1产生1到p-1之间的所 有值，且每一个值仅出现一次。因此：对于任意b 1, ,p 1，都存在唯一的正整数 k1 k p 1，使得b ak mod p这样，模p下a的方幕运算为：y ax mod p， 1 x p 1称x为模p下以a为底y的对数，记为：x ind a,p y ，1 y p 1以上运算定义在模 p有限域上的，所以称为离散对数运算。性质：1.in da,p 1