朱震--初等数论.doc

《朱震--初等数论.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、整除、同余、不定方程整除、同余、不定方程【大纲要求】全国联赛加试中对初等数论部分的考试要求：同余，欧几里得除法，裴蜀定理，完全剩余类，二次剩余，不定方程和方程组，高斯函数[x]，费马小定理，格点及其性质，无穷递降法，欧拉定理*，孙子定理*(带*的在加试中不考)．【基本知识】一．关于奇数和偶数的常用性质1．奇数+奇数=偶数；奇数+偶数=奇数；偶数+偶数=偶数．2．若干个整数之和为奇数，这些数中必有奇数，且奇数的个数为奇数个；若干个整数之和为偶数，且这些数中有奇数，则奇数的个数为偶数个．3．奇数奇数=奇数；奇数偶数=偶数；偶数偶数=偶数．

2、4．若干个整数之积为奇数，则这些数必为奇数；若干个整数之积为偶数，则这些数中必有偶数．5．若a为整数，则

3、a

4、与a有相同的奇偶性．6．若a、b都是整数，则a+b与a-b有相同的奇偶性．二．最大公约数和最小公倍数定义1如果a是的约数，那么a称为的公约数．公约数中最大的一个称为最大公约数，记为．定义2如果b是的倍数，那么b称为的公倍数．公倍数中最小的一个称为最小公倍数，记为．性质1(1)a为整数，则；(2)若d是a的约数，则；(3)a，b是整数，则；(4)a，b是整数，则．裴蜀定理若，则存在整数有．且必存在自然数，有，其中．推论当时，存在

5、，且，有．三．整数的整除性定义设a、b是整数，且，如果存在整数c使得a=bc，则称b整除a，或称a能被b整除．记作．否则称b不整除a，记作．显然，1能整除任何整数；0能被任何整数整除．质因数分解定理每一个大于1的整数n都能分解成质因数的乘积，并且不考虑因数的次序时，分解的方式是惟一的，即n可惟一表示成，其中是不同的质数，．性质1设a、b、c是整数．(1)a

6、a；(2)若a

7、b，b

8、c，则a

9、c；(3)若a

10、b，a

11、c，则对任意整数m、n，有a

12、(bm+cn)．性质2若等式中除某项外，其余各项都能被c整除，则这一项也能被c整除．性质3(

13、1)若(a，b)=1，且a

14、bc，则a

15、c；(2)若(a，b)=1，且a

16、c，b

17、c，则ab

18、c；(3)p是质数，若p

19、ab，则p

20、a或p

21、b．13整除、同余、不定方程四．同余的性质定义1设m是大于1的整数，a、b是整数，如果m

22、(a-b)，则称a、b关于m同余，记作，读作a同余b模m．当m(a-b)时，则称a、b关于m不同余，记作．显然(1)若，则m

23、a；(2)若，则a、b分别用m表示的余数相同．定理1设a、b、c、m(m>1)是整数，则有(1)反身性：；(2)对称性：若，则；(3)传递性：若，，则；定理2设，，则(1)；(2)．推

24、论1若，，则(1)；(2)．推论2若，则．定理3若，，且，则．推论若，且，则．定理4若，且，，则．定理5若，，且，则．五．剩余类、完全剩余系、费马小定理定义1设m是正整数，以m为模，则任何整数必与之一同余．把同余数归为一类，不同余数的整数必在不在同一类中，则全体整数可分为m类，称每一类为模m的剩余类．余数为的剩余类记作，则，是一个以m为公差的等差数列．我们有以下性质：(1)；(2)；(3)对任一整数n，有惟一的，使得；(4)对任意整数a、b，a、b．定义2设是以m为模的所有剩余类，由每一个中任意取一个数，则这m个数组成一组数，称之为模

25、m的一个完全剩余系．定理1m是整数，是m的一个完全剩余系当时，．定理2设m、a是正整数，，b是任意整数，如果是m的一个完全剩余系，那么也是m的一个完全剩余系．定理3(费马小定理)设p是质数，a是整数，且，则．定理4(威尔逊定理)若p为质数，则．六．数论函数(一)高斯函数13整除、同余、不定方程设，则表示不超过x的最大整数，则成为高斯函数．函数的定义域为R，值域为Z．性质1，，且．性质2，．性质3，则有．性质4，都有．性质5，都有．性质6若，则．性质7，都有．性质8，有．性质9x为正实数，n为正整数，则不超过x的所有正实数中，是n的倍数

26、的数共有个．性质10在的质因数分解中，质数p的指数是．(二)与设n的质因数分解式为．则正整数n的正因数个数．显然，为奇数当且仅当n是完全平方数．正整数n的正因数的和．性质与都是积性函数，即，．(三)欧拉函数设n为正整数，表示不大于n并且与n互质的自然数个数．设n的质因数分解式为，则．欧拉定理如果，那么．七．不定方程整系数方程①称为二元一次不定方程．定理1方程①有整数解的充要条件是．定理2若，且时方程①的一组解(通常称其为特解)，则方程①的全部解(通常称为通解)为．13整除、同余、不定方程定理3（勾股方程）的正整数解为，其中a、b是满足

27、，且一奇一偶的任意整数．无穷递降法证明模式大致为：首先假定原方程有解，然后构造某个无穷递降的过程，并且从方程本身看，这个过程应该是有限的，从而导出矛盾．其理论依据是“最小数原理”．13整除、同余、不定方程【例题选讲】例1