《初等数论知识点汇总》由会员分享,可在线阅读,更多相关《初等数论知识点汇总(19页珍藏版)》请在金锄头文库上搜索。
1、第一节整数的p进位制及其应用正整数有无穷多个,为了用有限个数字符号表示出无限多个正整数,人们发明了进位制,这是一种位值记数法。进位制的创立体现了有限与无限的对立统一关系,近几年来,国内与国际竞赛中关于“整数的进位制”有较多的体现,比如处理数字问题、处理整除问题及处理数列问题等等。在本节,我们着重介绍进位制及其广泛的应用。基础知识给定一个m位的正整数A,其各位上的数字分别记为,则此数可以简记为:(其中)。由于我们所研究的整数通常是十进制的,因此A可以表示成10的次多项式,即,其中且,像这种10的多项式表示的数常常简记为。在我们的日常生活中,通常将下标10省略不写,并且连括号也不用,记作,以后我们
2、所讲述的数字,若没有指明记数式的基,我们都认为它是十进制的数字。但是随着计算机的普及,整数的表示除了用十进制外,还常常用二进制、八进制甚至十六进制来表示。特别是现代社会人们越来越显示出对二进制的兴趣,究其原因,主要是二进制只使用0与1这两种数学符号,可以分别表示两种对立状态、或对立的性质、或对立的判断,所以二进制除了是一种记数方法以外,它还是一种十分有效的数学工具,可以用来解决许多数学问题。为了具备一般性,我们给出正整数A的p进制表示:,其中且。而仍然为十进制数字,简记为。第二节 整数的性质及其应用(1)基础知识整数的性质有很多,这里我们着重讨论整数的整除性、整数的奇偶性,质数与合数、完全平方
3、数及整数的尾数等几个方面的应用。1整除的概念及其性质在高中数学竞赛中如果不加特殊说明,我们所涉及的数都是整数,所采用的字母也表示整数。定义:设是给定的数,若存在整数,使得则称整除,记作,并称是的一个约数(因子),称是的一个倍数,如果不存在上述,则称不能整除记作 。由整除的定义,容易推出以下性质:(1)若且,则(传递性质);(2)若且,则即为某一整数倍数的整数之集关于加、减运算封闭。若反复运用这一性质,易知及,则对于任意的整数有。更一般,若都是的倍数,则。或着,则其中;(3)若,则或者,或者,因此若且,则;(4)互质,若,则;(5)是质数,若,则能整除中的某一个;特别地,若是质数,若,则;(6)
4、(带余除法)设为整数,则存在整数和,使得,其中,并且和由上述条件唯一确定;整数被称为被除得的(不完全)商,数称为被除得的余数。注意:共有种可能的取值:0,1,。若,即为被整除的情形;易知,带余除法中的商实际上为(不超过的最大整数),而带余除法的核心是关于余数的不等式:。证明的基本手法是将分解为与一个整数之积,在较为初级的问题中,这种数的分解常通过在一些代数式的分解中取特殊值而产生,下面两个分解式在这类论证中应用很多,见例1、例2。若是正整数,则;若是正奇数,则;(在上式中用代)(7)如果在等式中取去某一项外,其余各项均为的倍数,则这一项也是的倍数;(8)n个连续整数中,有且只有一个是n的倍数;
5、(9)任何n个连续的整数之积一定是n!的倍数,特别地,三个连续的正整数之积能被6整除;2奇数、偶数有如下性质:(1)奇数奇数=偶数,偶数偶数偶数,奇数偶数奇数,偶数偶数偶数,奇数偶数偶数,奇数奇数奇数;即任意多个偶数的和、差、积仍为偶数,奇数个奇数的和、差仍为奇数,偶数个奇数的和、差为偶数,奇数与偶数的和为奇数,和为偶数;(2)奇数的平方都可以表示成的形式,偶数的平方可以表示为或的形式;(3)任何一个正整数,都可以写成的形式,其中为负整数,为奇数。(4)若有限个整数之积为奇数,则其中每个整数都是奇数;若有限个整数之积为偶数,则这些整数中至少有一个是偶数;两个整数的和与差具有相同的奇偶性;偶数的
6、平方根若是整数,它必为偶数。3完全平方数及其性质能表示为某整数的平方的数称为完全平方数,简称平方数。平方数有以下性质与结论:(1)平方数的个位数字只可能是0,1,4,5,6,9;(2)偶数的平方数是4的倍数,奇数的平方数被8除余1,即任何平方数被4除的余数只有可能是0或1;(3)奇数平方的十位数字是偶数;(4)十位数字是奇数的平方数的个位数一定是6;(5)不能被3整除的数的平方被3除余1,能被3整数的数的平方能被3整除。因而,平方数被9也合乎的余数为0,1,4,7,且此平方数的各位数字的和被9除的余数也只能是0,1,4,7;(6)平方数的约数的个数为奇数;(7)任何四个连续整数的乘积加1,必定
7、是一个平方数。(8)设正整数之积是一个正整数的次方幂(),若()1,则都是整数的次方幂。一般地,设正整数之积是一个正整数的次方幂(),若两两互素,则都是正整数的k次方幂。4整数的尾数及其性质整数的个位数也称为整数的尾数,并记为。也称为尾数函数,尾数函数具有以下性质:(1);(2);(3);(4);(5)若,则;(6);(7);(8)5整数整除性的一些数码特征(即常见结论)(1)若一个整数的未位数字能被2(或5)整除,则这个数能被2(或5)整除,否则不能;(2)一个整数的数码之和能被3(或9)整除,则这个数能被3(或9)整除,否则不能;(3)若一个整数的未两位数字能被4(或25)整除,则这个数能
8、被4(或25)整除,否则不能;(4)若一个整数的未三位数字能被8(或125)整除,则这个数能被8(或125)整除,否则不能;(5)若一个整数的奇位上的数码之和与偶位上的数码之和的差是11的倍数,则这个数能被11整除,否则不能。6质数与合数及其性质1正整数分为三类:(1)单位数1;(2)质数(素数):一个大于1的正整数,如果它的因数只有1和它本身,则称为质(素)数;(3)如果一个自然数包含有大于1而小于其本身的因子,则称这个自然数为合数。2有关质(素)数的一些性质(1)若,则的除1以外的最小正因数是一个质(素)数。如果,则;(2)若是质(素)数,为任一整数,则必有或()1;(3)设为个整数,为质
9、(素)数,且,则必整除某个();(4)(算术基本定理)任何一个大于1的正整数,能唯一地表示成质(素)因数的乘积(不计较因数的排列顺序);(5)任何大于1的整数能唯一地写成的形式,其中为质(素)数()。上式叫做整数的标准分解式;(6)若的标准分解式为,的正因数的个数记为,则。第三节整数的性质及其应用(2)基础知识最大公约数与最小公倍数是数论中的一个重要的概念,这里我们主要讨论两个整数互素、最大公约数、最小公倍数等基本概念与性质。定义1.(最大公约数)设不全为零,同时整除的整数(如)称为它们的公约数。因为不全为零,故只有有限多个,我们将其中最大一个称为的最大公约数,用符号()表示。显然,最大公约数
10、是一个正整数。当()1(即的公约数只有)时,我们称与互素(互质)。这是数论中的非常重要的一个概念。同样,如果对于多个(不全为零)的整数,可类似地定义它们的最大公约数()。若()1,则称互素。请注意,此时不能推出两两互素;但反过来,若()两两互素,则显然有()1。由最大公约数的定义,我们不难得出最大公约数的一些简单性质:例如任意改变的符号,不改变()的值,即;()可以交换,()();()作为的函数,以为周期,即对于任意的实数,有()()等等。为了更详细地介绍最大公约数,我们给出一些常用的一些性质:(1)设是不全为0的整数,则存在整数,使得;(2)(裴蜀定理)两个整数互素的充要条件是存在整数,使得
11、;事实上,条件的必要性是性质(1)的一个特例。反过来,若有使等式成立,不妨设,则,故及,于是,即,从而。(3)若,则,即的任何一个公约数都是它们的最大公约数的约数;(4)若,则;(5)若,则,因此两个不互素的整数,可以自然地产生一对互素的整数;(6)若,则,也就是说,与一个固定整数互素的整数集关于乘法封闭。并由此可以推出:若,对于有,进而有对有。(7)设,若,则;(8)设正整数之积是一个正整数的次方幂(),若()1,则都是整数的次方幂。一般地,设正整数之积是一个正整数的次方幂(),若两两互素,则都是正整数的次方幂。定义2.设是两个非零整数,一个同时为倍数的数称为它们的公倍数,的公倍数有无穷多个
12、,这其中最小的一个称为的最小公倍数,记作,对于多个非零实数,可类似地定义它们的最小公倍数。最小公倍数主要有以下几条性质:(1)与的任一公倍数都是的倍数,对于多于两个数的情形,类似结论也成立;(2)两个整数的最大公约数与最小公倍满足:(但请注意,这只限于两个整数的情形,对于多于两个整数的情形,类似结论不成立);(3)若两两互素,则;(4)若,且两两互素,则。第四节同余同余式性质应用非常广泛,在处理某些整除性、进位制、对整数分类、解不定方程等方面的问题中有着不可替代的功能,与之密切相关的的数论定理有欧拉定理、费尔马定理和中国剩余定理。基础知识三个数论函数对于任何正整数均有定义的函数,称为数论函数。
13、在初等数论中,所能用到的无非也就有三个,分别为:高斯(Gauss)取整函数x及其性质,除数函数d(n)和欧拉(Euler)函数和它的计算公式。1 高斯(Gauss)取整函数设是实数,不大于的最大整数称为的整数部分,记为;称为的小数部分,记为。例如:0.50,等等。由的定义可得如下性质:性质1.;性质2.;性质3.设,则;性质4.;性质5.;性质6.对于任意的正整数,都有如下的埃米特恒等式成立:;为了描述性质7,我们给出如下记号:若,且,则称为恰好整除,记为。例如:我们有等等,其实,由整数唯一分解定理:任何大于1的整数能唯一地写成的形式,其中为质(素)数()。我们还可以得到:。性质7.若,则请注
14、意,此式虽然被写成了无限的形式,但实际上对于固定的,必存在正整数,使得,因而,故,而且对于时,都有。因此,上式实际上是有限项的和。另外,此式也指出了乘数的标准分解式中,素因数的指数的计算方法。2除数函数d(n)正整数的正因数的个数称为除数函数,记为d(n)。这里给出d(n)的计算公式:d(n),为素数唯一分解定理中的指数。为了叙述地更加明确,我们组出素数唯一分解定理。算术基本定理(素数唯一分解定理):任何一大于1的整数均可以分解为素数的乘积,若不考虑素数乘积的先后顺序,则分解式是唯一的。例如:。当一个整数分解成素数的乘积时,其中有些素数可以重复出现。例如在上面的分解式中,2出现了三次。把分解式
15、中相同的素数的积写成幂的形式,我们就可以把大于1的正整数写成(1)此式称为的标准分解式。这样,算术基本定理也可以描述为大于1的整数的标准分解式是唯一的(不考虑乘积的先后顺序)。推论1.若的标准分解式是(1)式,则是的正因数的充要条件是:(2)应说明(2)不能称为是的标准分解式,其原因是其中的某些可能取零值(也有可能不含有某个素因数,因而)推论2.设,且,若是整数的次方,则也是整数的次方。特别地,若是整数的平方,则也是整数的平方。3. 欧拉(Euler)函数设正整数0,1,中与互素的个数,称之为的欧拉函数,并记为。若的标准分解式是,则的计算公式是:例如:; .以下我们讲述同余的概念:同余的概念是高斯(Gauss)在1800年左右给出的。设是正整数,若用去除整数,所得的余数相同,则称为与关于模同余,记作,否则,称为与关于模不同余。定义1.(同余)设,若,则称和对模同余,记作;若不然,则称和对模不同余,记作。例如:,等等。当时,则称是对模的最小非负剩余。由带余除法可知,和对模同余的充要条件是与被