数论中的基础概念

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+ac和(a+b)c=ac+bcM4：乘法交换律：对于G中的任意元素a,b有ab=baM5 :乘法单位元：对于G中的任意元素a,在G中存在一个元素1,使得a1=1a=aM6 :无零因子：对于G中的元素a,b,若ab=0,则必有a=0或b=0M7：乘法逆元：如果a届于G,且a不为0,则G中存在一个元素a1,使得aa 1a 1a 1满足A1---A4称为群满足A1---A5称为可交换群满足A1---M3称为环满足A1---M4称为可交换换满足A1---M6称为整环满足A1---M7称为域2循环群：如果群中的每一个元素都是一个固定元素a(a G)的籍a k(k为整数)，则称群G是循环群。

我们认为元素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 g i ,g为整数。

如果b|h，那么h b ^1 , h为整数。

于是：mg nh mbg i nbhi b (mg i nhi) 因此b整除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 (amodn) b kn modn bmodn即得 a b modn 。

性质2证明：由 a b modn 得：(amodn) (bmodn)即k〔,k2,r Z ,满足a kn r……①b k2n r1由①可推出b a (k2 k〔)n,由性质1可知b a modn成立则得证。

性质3证明：由性质2证明过程知：k1,k2,k3,r Z满足：b a (k2k1)nc b (k3k2)n由②可以推出a c (k1 k2)n，由性质1可知a c mod n模算术运算有如下性质:1 amod n bmod n modn a b modn2 amodn - bmodn modn a-b modn3 amodn bmodn modn a b modn性质1证明:那么有：a-b modn r a jn-r b -kn modn r a - r b j - k n mod n r a - r b modnamodn - bmodn modn性质3证明：前半段证明如上，a b mod n r a r b r b jn r a kn jkn 2 mod n2 r a r b r b j r a k n jkn mod nr a r b mod namod n b mod n mod n模n 的剩余类。

Z n 中每一个整数都代表一个剩余类，我们可以将模 n 的剩余类表示为：[0],[1],[2], ,[n 1],其中[r] (a : a 是-一个整数，a r mod n ｝。

如果 a b a c modn ，那么 b c modn设 amodn r a , bmodnr b 则j,k Z ，使得: b r a jn r b kn那么有：a b modn r a jn r b kn modn r a r b j k nmodn r a r b mod n amodn bmodnmodn即得证性质2证明:由性质1证明过程知j,k Z 使得 r a jnr b kn若a与n互素,如果 a b a c mod n，那么b c mod n交换律：wwx modn (xx modn (xw) mod nw)mod n结合律：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 mod n wmodn加法逆元（-w）:对于Z n中的任意w,存在一个z使得w z 0modn加法逆元：对每一个Z n,存在一个u,使得w+u=0 mod n,记为u=-w，显然在模n 下,-w=n-w o如果 a bmod n, c d modn ,贝U有a cb d modn ,特例J a c b cmodn ,更一般式：ax cy bx dy mod n , x,y Zac bd modn特例：ac bcmodnf a f b modn其中f(x)为任意给定的一个整系数多项式最大公约数:gcd(a,b) max[k,满足k | a^ k | b]欧几里得算法：对丁任意非负整数a和任意正整数b有gcd(a,b) gcd(b,amodb)算法描述如下：设整数 a b 0,EUCLID(a,b)(1) X a;Y b;(2) 如果Y=0，返回X=gcd(a,b),否则继续；(3) R=XmodY(4) X Y ；(5) Y R；(6) 返回(2)扩展的欧几里得算法描述如下：Extended EUCLID(a,n)(1) X I,X2,X31,0,n ； Y1,Y2,Y3 0,1,a ;(2) 如果Y3 0 ,返回X3 gcd(a,n),无逆元；否则继续；(3) 如果丫3 1 ,返回Y3 gcd(a,n);方 a 1 mod n ；(4) Q X% ；(5) T1,T2,T3 X1 QY,X2 QY2,X3 QY3 ；(6) X1,X2,X3 Y1,Y2,Y3 ;(7) Y1,Y2,Y3 T1,T2,T3 ；(8) 返回(2)。

有限域GF(P):阶为p n的有限域一般记为GF p n , GF代表伽罗瓦域。

给定一个素数p,元素个数为p的有限域GF(p)被定义为整数0,1, , p-1的集合Zp,其运算为模p的算术运算。

没有落日般的瑰丽，没有流云般的飘逸，但可以有水晶般的清纯与透明。

没有大山般的巍峨，没有湖水般的轻柔，但可以有岩石般的坚毅与稳重。

没有大海般的浩瀚，没有瀑布般的飞泻，但可以有泥土般的朴素与随和。

乘法逆元-1:任意Z p , 0 ,存在z Z p使得z Imodp求最大公因式：我们可以通过定义最大公因式来扩展域上的多项式和整数运算之间的类比。

如果：1.c(x)能同时整除a(x)和b(x)。

2. a(x)和b(x)的任何因式都是c(x)的因式。

就称多项式c(x)为a(x)和b(x)的最大公因式。

此定义等价定义与：gcd[a(x),b(x)]是能同时整数a(x)和b(x)的多项式中次数最高的一个。

多项式模运算：如果定义了合适的运算，那么每一个这样的集合S都是一个有限域。

定义由如下几条组成：1. 该运算遵循基本代数规则中的普通多项式运算规则2. 系数运算以P为模，即遵循有限域Z p上的运算规则3. 如果乘法运算结果是次数大于n-1的多项式，那么必须将其除以某个次数为n 的既约多项式m(x)并取余式。

对于多项式f(x),这个余式可表示为r(x)=f(x) mod m(x)素数任意整数a 1都可以惟一地因子分解为：a p/p22?七，，其中a,p2, p t均为素数，P I p2 p t且指数皆为正整数。

费马定理：p是素数，a是与p互素的正整数，则a p 1 1 mod p 或者a p a mod p显然有a k a kmod(p1) mod p, 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 n1modn。

欧拉定理有如下推论。

1. n为素数时，有a n a n 11 modn ,即费马定理。

2. 由欧拉定理，有a n 1amodn进一步有a k n 1amodn , k Z3. 若n=pq, p 和q 是素数，p 不等丁q,则有 a n 1a(p 1)(q1) 1amodn。

4. 若n=pq, p和q是素数,p不等丁q,而gcd(a,n) p或q，仍有a n 1amodn中国剩余定理：设正整数m1,m2, , m k两两互素，记M m i ,贝U同余i 1x 访mod m1 x b2 mod m2 x b s mod m3x b k mod m kk在模M同余的意义下，有唯一解xb i M i y i mod M ,其中:i 1M i一,1 i r; y i M i1modm i ,1 i km i如果a,n 1 ,则至少有一个整数m (即m n )满足a m1 modn 满足上式的最小正整数m为模n下a的阶(乂称次数)。

本原根：如果a的阶等丁n,则称a为n的本原根(乂称素根)性质：如果a是n的本原根，贝U a,a2,a3, ,a n在模n下互不相同，且均与n互素。

注意：模n下的本原根并不具备唯一性，且并非所有的整数n都有本原根，只有以下形式的整数才有本原根：2,4, p a,2p a，其中a为整数，p为奇素数。

离散对数：设p为以素数，a是p的本原根，则在模p下a,a2,a3, ,a p1产生1到p-1之间的所有值，且每一个值仅出现一次。

因此：这样，模p下a的方藉运算为：y a x mod p , 1 x p 1称x为模p下以a为底y的对数，记为：x ind a,p y , 1 y p 1以上运算定义在模p有限域上的，所以称为离散对数运算。

性质：1.ind a,p1 p 12.ind a,p a 13.ind a,p xy ind a,p x ind a,p y mod p4. ind a,p x y y ind a,p x mod p5. 若a x a y modn，其中a,n互素，a是n的本原根，则有：x y mod n 。