初等数论复习 (1)

1、初等数论复习,完全数,6全部因数(除本身)1,2,36=1+2+328全部因数(除本身)1,2,4,7,1428=1+2+4+7+14,一个数若等于它的全部因数之和(不包括自身)，就叫做完全数,亲和数,亲和数的定义是：对于自然致m和n，若m的全部因数(不包括自身)之和恰好等于n而n的全部因数(不包括自身)之和又恰好等于m，则m和n是一对亲和数,例如，220的全部因数之和1+2+4+5+10+11+20+22+44+55+110=284而248的全部因数之和1+2+4+71+142220，所以220和284是一对亲和数,费马数,也叫费马质数.当年费马发现F1=2(21)+1=5F2=2(22)+

2、1=17F3=2(23)+1=257F4=2(24)+1=65537F5=2(25)+1=4294967297前4个是质数,因为第5个数实在太大了,费马认为是质数,并提出(费马没给出证明),梅森数马林梅森（MarinMersenne,15881648）是17世纪法国著名的数学家和修道士,形如2p1的正整数，其中p是素数，常记为Mp。若Mp是素数，则称为梅森素数。p2，3，5，7时，Mp都是素数，但M1120472389不是素数。已发现的最大梅森素数是p24036583的情形，此时Mp是一个7235733位数。是否有无穷多个梅森素数是数论中未解决的难题之一。,任何一个大于2的偶数都是两个素数之和

3、。中国的陈景润证明了1+2“质因数个数较少的数称为殆质数,哥德巴赫猜想,1.1奇数与偶数,整数中能被2整除的整数称为偶数，一般表示为k整数中不能被2整除的整数称为奇数。一般表示为k+1偶数集：0,2,4,6奇数集：1,3,50是偶数而且0是任何整数的倍数,基本性质1.1,（1）偶数偶数=偶数（2）奇数奇数=偶数（3）偶数奇数=奇数奇数个奇数的和是奇数;偶数个奇数的和是偶数；任意正整数个偶数的和是偶数,基本性质1.2,（1）奇数奇数=奇数（2）奇数偶数=偶数（3）偶数偶数=偶数任意多个奇数的积是奇数;至少有一个乘数是偶数的积是偶数,基本性质1.3,（1）如果一个偶数能被奇数整除，那么商必是偶数.

4、（2）两个连续整数的积n(n+1)是偶数.,1.2.1带余除法,(带余数除法)设a与b是两个整数，b0，则存在唯一的两个整数q和r，使得a=bqr，0rr2，所以式(1)中只包含有限个等式。,1.2.3裴蜀恒等式,(a,b)=ua+vb其中u,v是两个整数,rn2=rn1qnrn,(a,b)=rn=rn2rn1qn,rn-1=rn3rn2qn-1,代入上式得(a,b)=u1rn2v1rn3,可得:(a,b)=ua+vb,对于任意的正整数a1,a2,an，存在整数k1,k2,kn,使得k1a1+k2a2+knan=(a1,a2,an),当a,b互质时，就有整数u,v，满足,1=ua-vb1ub，

5、0va,例用辗转相除法求(125,17)，以及x，y，使得125x17y=(125,17)。解做辗转相除法：125=7176，q1=7，r1=6，17=265，q2=2，r2=5，6=151，q3=1，r3=1，5=51，q4=5。(125,17)=r3=1。,125317(22)=(125,17)=1,1.3质因数分解定理,正整数分类1质数(素数)合数,定理1(算术基本定理)任何大于1的整数n可以唯一地表示成n=，(2)其中p1,p2,pk是素数，p1p2pk，1,2,k是正整数。,定义使用定理1中的记号，称n=是n的标准分解式，其中pi（1ik）是素数，p1p22，则由an1=(a1)(a

6、n1an21)可知an1是合数。所以a=2。若n是合数，则n=xy，x1，y1，于是由2xy1=(2x1)(2x(y1)2x(y2)1)以及2x11可知2n1是合数，所以2n1是素数时，n必是素数。,注：若n是素数，则称2n1是Mersenne数,第二章同余,2.1基本性质2.2同余的应用2.3费马小定理2.4中国剩余定理,定义:给定正整数m，如果整数a与b之差被m整除，(存在q使得a-b=qm)则称a与b对于模m同余，或称a与b同余，模m，记为ab(modm)，此时也称b是a对模m的同余。如果整数a与b之差不能被m整除，则称a与b对于模m不同余，或称a与b不同余，模m，记为ab(modm)。

7、如6248(mod7)1260(mod8),下面的三个叙述是等价的：()ab(modm)；()存在整数q，使得a=bqm；()存在整数q1，q2，使得a=q1mr，b=q2mr，0r0,有x=x+x-x=-x-x=-x+-x=-x-1,n!中质数p的次数,记n！中质数p出现的次数为vp(n!)vp(n!)=,3.2(n)与(n),(n)表示正整数n的因数个数,则n的因数为：,(n),(n)表示正整数n的所有因数的和,积性函数,定义：如果f(n)为数论函数，并且对于任何一对互质的自然数a，b，有f(ab)=f(a)f(b),(n)与(n)都是积性函数,(ab)=(a)(b),(ab)=(a)(b

8、),完全数,如果自然数n的因数的和是n的两倍，即(n)=2n，那么称n为完全数。6=1+2+328=1+2+4+7+14,(n),欧拉函数(n)设n为正整数，(n)表示不大于n并且与n互质的自然数个数，称(n)为欧拉函数(1)=1，(2)=1，(10)=4,(n),性质3.5对质数p，(p)=p-1.性质3.6对质数p及正整数k，(pk)=pk-1(p-1).性质3.7(n)是积性函数，也就是(a,b)=1,则(ab)=(a)(b),(n),性质3.8设则,第4章不定方程,4.1一次不定方程4.2费马方程,4.1一次不定方程,设a1,a2,an是非零整数，b是整数，称关于未知数x1,x2,xn

9、的方程a1x1a2x2anxn=b(1)是n元一次不定方程。若存在整数x10,x20,xn0满足方程(1)，则称(x10,x20,xn0)是方程(1)的解，或说x1=x10，x2=x20，xn=xn0是方程(1)的解。,定理1方程(1)有解的充要条件是(a1,a2,an)b。(2),定理1设a，b，c是整数，二元一次不定方程axby=c(3)有解的充要条件是(a,b)|c.,定理2设a，b，c是整数，方程axby=c(3)若有解(x0,y0)，则它的一切解具有,tZ(4),的形式，其中,解二元一次不定方程的一般步骤,（1）判断方程是否有解（2）如果方程有解，那么先求方程,的一组特解，从而得到方

10、程ax+by=c的一组特解。,（3）写出方程的通解,定理1和定理2说明了解方程(3)的步骤：()判断方程是否有解，即(a,b)c是否成立；()利用辗转相除法求出x0，y0，使得ax0by0=(a,b)；()写出方程(3)的解,无解,例求不定方程3x6y=15的解。,解(3,6)=315，所以方程有解。由辗转相除法（或直接观察），可知x=1，y=1是3x6y=3的解，所以x0=5，y0=5是原方程的一个解。由定理2，所求方程的解是,例求不定方程3x6y=15的解。,解(3,6)=315，所以方程有解。,比较,4.2费马方程,商高不定方程,容易看出，(x,y,z)=(0,0,0)，(0,a,a)以

11、及(a,0,a)都是方程(1)的解。若(x,y,z)是方程(1)的解，则对于任何整数k，(kx,ky,kz)也是方程(1)的解。此外，若(x,y)=k，则kz，(x,y,z)=k。因此，我们只需研究方程(1)的满足下述条件的解：x0，y0，z0，(x,y)=1。(2),定理1若(x,y,z)是方程(1)的满足条件(2)的解，则下面的结论成立：()x与y有不同的奇偶性；()x与y中有且仅有一个数被3整除；()x，y，z中有且仅有一个数被5整除。,定理2方程(1)的满足式(2)和2x的一切正整数解具有下面的形式：x=2ab，y=a2b2，z=a2b2，(8)其中ab0，(a,b)=1，a与b有不同的奇偶