数论中的基础概念.doc

1群、环、域概念

A1：加法的封闭性：如果a和b属于G，则a+b也属于G
A2：加法结合律：对G中的任意元素a,b,c,a+(b+c)=(a+b)+c
A3：加法单位元：G中存在一个元素0，使得对于G中的任意元素a，有a+0=0+a
A4：加法逆元：对于G中的任意元素a，G中一定存在一个元素a,使得
a+(-a)=(-a)+a=0
A5：加法交换律：对于G中的任意元素a和b，有a+b=b+a
M1：乘法的封闭性：如果a和b属于G，则ab也属于G
M2：乘法结合律：对于G中的任意元素a,b,c有a(bc)=(ab)c
M3：乘法分配了：对于G中的任意元素a,b,c，有a(b+c)=ab+ac和(a+b)c=ac+bc
M4：乘法交换律：对于G中的任意元素a,b有ab=ba
M5：乘法单位元：对于G中的任意元素a,在G中存在一个元素1，使得a1=1a=a
M6：无零因子：对于G中的元素a,b，若ab=0，则必有a=0或b=0
M7：乘法逆元：如果a属于G，且a不为0,则G中存在一个元素，使得

满足A1---A4称为群
满足A1---A5称为可交换群
满足A1---M3称为环
满足A1---M4称为可交换换
满足A1---M6称为整环
满足A1---M7称为域

2循环群：如果群中的每一个元素都是一个固定元素的幂（k为整数），
则称群G是循环群。我们认为元素a生成了群G，或者说a是群G的
生成元。
循环群总是交换群

3模运算

则称整数a和b是模n同余的，可以表示为：
若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|h，那么，h为整数。
于是：
因此b整除mg+nh.

同余的性质：
1如果n|（a-b），，那么
2隐含
3，隐含
性质2和性质3证明是我自己证的。

性质1证明：
如果，那么，为整数。使得，
则有
即得。

性质2证明：
由得：即，满足
……①
由①可推出,由性质1可知成立
则得证。

性质3证明：
由性质2证明过程知：满足：
……②
由②可以推出，由性质1可知

模算术运算有如下性质：
1
2
3
性质2性质2是我自己证明的。

性质1证明：
设，则，使得
那么有：

即得证。

性质2证明：
由性质1证明过程知使得
那么有：

性质3证明：
前半段证明如上，

定义比n小的非负整数集合为。这个集合称为剩余类集，或
模n的剩余类。
中每一个整数都代表一个剩余类，我们可以将模n的剩余类表示为：
，其中。

如果，那么
若a与n互素，如果，那么

中整数模运算性质：
交换律：

结合律：

分配律：

单位元：

加法逆元（-w）：对于中的任意w，存在一个z使得
以下部分摘自刘嘉勇编P231

加法逆元：对每一个，存在一个u,使得w+u=0 mod n，记为u=-w,显然在模
n下，-w=n-w。
如果，则有
，
特例，
更一般式：，

特例：
其中f(x)为任意给定的一个整系数多项式
以上部分摘自刘嘉勇P231

最大公约数：

欧几里得算法：对于任意非负整数a和任意正整数b有
算法描述如下：设整数
（1）；
（2）如果Y=0，返回X=gcd(a,b)，否则继续；
（3）R=XmodY
（4）；
（5）;
（6）返回（2）
扩展的欧几里得算法描述如下：Extended EUCLID(a,n)
（1）；；
（2）如果，返回，无逆元；否则继续；
（3）如果，返回；；
（4）；
（5）；
（6）；
（7）；
（8）返回（2）。

有限域GF(P):
阶为的有限域一般记为，GF代表伽罗瓦域。
给定一个素数p，元素个数为p的有限域GF(p)被定义为整数的集合，其运算为模p的算术运算。

乘法逆元：任意，，存在使得

求最大公因式：
我们可以通过定义最大公因式来扩展域上的多项式和整数运算之间的类比。如果：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为模，即遵循有限域上的运算规则
3. 如果乘法运算结果是次数大于n-1的多项式，那么必须将其除以某个次数为n的既约多项式m(x)并取余式。对于多项式f(x)，这个余式可表示为r(x)=f(x) mod m(x)

素数
任意整数都可以惟一地因子分解为：，其中均为素数，且指数皆为正整数。

费马定理：p是素数，a是与p互素的正整数，则
或者
显然有

欧拉函数：欧拉函数是一个定义在正整数集上的函数，的值等于小于n
且与n互素的正整数的个数。
欧拉函数有性质如下：
1.如果n是素数，则
2.如果，p和q是素数，且p不等于q则

欧拉定理：对任何互素的两个整数a和n，有。

欧拉定理有如下推论。
1. n为素数时，有，即费马定理。
2. 由欧拉定理，有进一步有，
3. 若n=pq，p和q是素数，p不等于q，则有。
4. 若n=pq，p和q是素数，p不等于q，而，仍有

中国剩余定理：设正整数两两互素，记，则同余

在模M同余的意义下，有唯一解，其中：

如果，则至少有一个整数m（即）满足。
满足上式的最小正整数m为模n下a的阶（又称次数）。

本原根：如果a的阶等于，则称a为n的本原根（又称素根）有些材料上称本原元

性质：如果a是n的本原根，则在模n下互不相同，且均与n互素。
注意：模n下的本原根并不具备唯一性，且并非所有的整数n都有本原根，只有以下形式的整数才有本原根：，其中a为整数，p为奇素数。

离散对数：
设p为以素数，a是p的本原根，则在模p下产生1到p-1之间的所有值，且每一个值仅出现一次。因此：
对于任意，都存在唯一的正整数，使得
这样，模p下a的方幂运算为：，
称x为模p下以a为底y的对数，记为：，
以上运算定义在模p有限域上的，所以称为离散对数运算。

性质：
1.
2.
3.
4.
5. 若，其中a,n互素，a是n的本原根，则有：。

平方剩余：
设p是一素数，a小于p，如果方程有解，称a是模p的平方剩余（也称二次剩余），否则称为非平方剩余。

设p是素数，a是一整数，a是p的平方剩余的充要条件是：
a是p的非平方剩余的充要条件是：