基础知识——数论函数中同余.doc

《基础知识——数论函数中同余.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、同余同余式性质应用非常广泛，在处理某些整除性、进位制、对整数分类、解不定方程等方面的问题中有着不可替代的功能，与之密切相关的的数论定理有欧拉定理、费尔马定理和中国剩余定理。基础知识三个数论函数对于任何正整数均有定义的函数，称为数论函数。在初等数论中，所能用到的无非也就有三个，分别为：高斯(Gauss)取整函数［刃及其性质，除数函数和欧拉(Euler)函数°(兀)和它的计算公式。1.高斯(Gauss)収整函数［X］设兀是实数，不大于兀的最大整数称为X的整数部分，记为［x］;x-［x］称为兀的小数部分,记为{兀}。例如：［0.5］=0,［750］=7,［-3］=-3,［-^］=-4,{

2、^}=0.1415•{-0.3}=0.7等等。由［xl{x}的定义可得如下性质：性质1.x-[x]={x};0<{x}<1；性质2.X—1<[x]W兀V[兀]+1;性质3.设aeZ,则[a+x]=a+[x]；性质4.[兀+刃>[x]+[y];{x+y}<{x}+{y};性质5.[-x]=-[x]-kl-ixeZx电Z性质6.对于任意的正整数〃，都有如下的埃米特恒等式成立：

3、r

4、［兀］+H+丄］+［兀+兰］+…+［兀+"二］=［处］;nnn为了描述性质7,我们给岀如下记号：若baa.且〃网*则称为恰好整除d,记为baIR/o例如：我们有241

5、2000,531

6、2000等等，其实

7、，由整数唯一分解定理：任何大于1的整数d能唯一地写成a=p；'p?・・・p；k,i=2,,・・・,k的形式,其中p为质(素)数(Pi

8、

9、d,心1,2,…nnn性质7•若pa,则6^=[-]+[—]+[—].••PP请注意，此式虽然被写成了无限的形式，但实际上对于固定的斤，必存在正整数a?n使得pk>n,因而0v/「vl,故[^]=0，而且对于m>k时，都有[——]=0。因此，PP，n上式实际上是有限项的和。另外，此式也指出了乘数用的标准分解式中，素因数/?的指数Q的计算方法。2.除数函数〃(/?)正整数斤的正因数的个数称为除数函数，记为

10、6/(/7)o这里给出〃5)的计算公式：如=(0+1)@+1)・・・(％)，0S，…，％为素数唯一分解定理中的指数。为了叙述地更加明确，我们组出索数唯一分解定理。算术基本定理(素数唯一分解定理)：任何-•大于1的整数均可以分解为素数的乘积，若不考虑素数乘积的先后顺序，则分解式是唯一的。例如：24=2x2x2x3。当一个整数分解成索数的乘积时，其中有些素数可以重复出现。例如在上而的分解式中，2出现了三次。把分解式中相同的素数的积写成幕的形式，我们就可以把大于1的正整数。写成a==(1)此式称为a的标准分解式。这样，算术基本定理也可以描述为大于1的整数的标准分解式是唯一的(不考虑乘积的

11、先后顺序)。推论1.若。的标准分解式是(1)式，则〃是a的正因数的充要条件是：d=”什筒…卩化os0.vdJ=l,2,,・・・,R(2)应说明(2)不能称为是d的标准分解式，，其原因是其中的某些0,可能取零值(d也有可能不含有某个索因数门，因而0,=0)推论2.设。二be,且@,c)=l,若Q是整数的£次方，则b,c也是整数的£次方。特別地，若d是整数的平方，则b,c也是整数的平方。3.欧拉(Euler)函数(p(n)设斤正整数0,1,”-1中与〃互素的个数，称之为n的欧拉函数，并记为0(斤)。若刃的标准分解式是n=艸p?…P?,心12,,则(p(n)的计算公式是：处2)=矿円卩严

12、…P严(卩-1)(必-1)…(几-1),212,…伙例如:0(2000)=0(245彳)=2453(2-1)(5-1)=800；0(2001)=0(3x23x29)=(3-1)(23-1)(29-1)=1432.以下我们讲述同余的概念:同余的概念是高斯(Gauss)在1800年左右给出的。设加是正整数，若用m去除整数d",所得的余数相同，则称为Q与方关于模加同余，记作«=/?(modm),否则，称为g与方关于模加不同余°定义1.(同余)设加>0,若m

13、(a-h),则称a和b对模加同余，记作a=Z?(modm)；若不然，则称g和b对模血不同余，记作ab(mod”2)。例如：34=4(

14、mod⑸，1000=-l(mod7)等等。当0(modm)的充要条件是a=h+mt,teZ也即m(a-b)o性质2.同余关系满足以下规律：(1)(反身性)a=a(modm)；(2)(对称性)若a三/?(modm),则Z?三a(modm)；(3)(传递性)若a三