《整数的整除性与同余分析》由会员分享，可在线阅读，更多相关《整数的整除性与同余分析（38页珍藏版）》请在金锄头文库上搜索。
1、整数的整除性,与同余分析,第四节,数论是研究整数规律和性质的数学分支,它是既古老又活跃着的数学分支,一般地说,数论分为初等数论、解析数论、代数数论.,初等上数论基础知识较为简单, 但处理问题的方法技巧性很强,在培养思维能力方面起着重要作用,因此在国内外数学竞赛中中占有重要地位.,一、整数的整除性,整数的整除性有如下基本性质:,1.设,是整数,则,1),若,2),则,3),若,则对任意整数,有,2.若在,中,除某一项外,其余各项都能,被,整除,则这一项也能被,整除.,3.若,且,则,4.若,且,且,则,则,5.若,为素数,或,分析,将,与,的倍数即可.,的线性组合表示为17,证明,消去,得,由,
2、用整除性质易知结论成立.,注：,若消去,同理可证,记,证明,因为2与5互素,只要证给定的三个数至少,有一个同时能被2和5整除.,显然,都能被2整除.,都是偶数,若,中至少有一个能被5整除,结论成立.,若,都不能被5整除,则,数只能是1、4、6、9,的个位,枚举知,中至少一个能被5整除,由,则易知,知,综上,结论成立.,整除.,中至少有一个能被5,注：上述证明先利用整除性质简化问题, 再根据给定数的特征, 采用分类讨论、考察完全平方数的特征性质等方法, 使整除性逐步暴露出来.本题如果用余数分析法则比较方便(见后面同余分析).,故,不是3的倍数,大于5的素数,是大于5的素数,证明,首先,为奇数,又
3、,是两个相邻偶数,数,另一个必是4的倍数,有,故其中一个是2的倍,于是,其次,有,从而,最后,对大于5的素数,同上知,或,前者有,后者有,故总有,综上,注: 本题用到了余数分析,综上,对一切正整数,有,证明,(用数学归纳法),设,则,命题成立.,则,因,只要证,再用归纳法证明:,记,则,假设,则有,假设知,从而,得证.,由归纳,设,证明,与1979有关？！,于是,即,故,( 是整数),而1979是素数,证明,由条件得,若,设,是集合,中使,最小的元素,(不妨设 ),则存在正,整数k使,于是,a是方程,的解,即,的解.,设c为方程的另一个根,由韦达定理,又由根的定义,有,由,的最小性知,故,又,
4、所以,由此可得,这显然是矛盾的.,有,二.奇偶性分析与同余分析,性质1 奇数+奇数=偶数;,奇数+偶数=奇数;,偶数+偶数=偶数.,性质2 若干个整数的和为是奇数,则这些数,中必有奇数,且奇数的个数为奇数个;,若干个整数的和为是偶数,则这些数,中若有奇数,奇数的个数必为偶数个.,性质3 奇数奇数=奇数;奇数偶数=偶数;,偶数偶数=偶数.,性质4 若干个整数的积为是奇数,则这些数,必有奇数;,若干个数的积为是偶数,则这些数中至,少有一个为偶数.,性质5 若,为整数,则,与,有相同的奇偶性.,性质4 若干个整数的积为是奇数,则这些数,必有奇数;,由定义不难证明如下性质:,定理1(等价性),反身性,
5、对称性,传递性,定理,(加减法与乘法),特别地,一般地,有消去律,定理,(除法),定理,定理(费尔马定理),设,为素数,则有,亦即,解,由于,与,有相同的奇偶性,的数任意添加正号或负号得到的代数和与,为奇数.,的奇偶性相同,(其中有奇数项为奇数),故对给定,证明,(反证法),若该乘积为奇数,则,而,都是奇数,为奇数,故,为奇数.,另一方面,由于,为,排列,故,的任意一,为偶数.,矛盾.,综上,为偶数.,解,为便于思考,将1号厅涂成红色,再把与其相邻的两个厅涂成蓝色,继而对相邻展览厅采取红、蓝相,间的方法涂色.,显然,参观者从红厅出来只能进入相邻的蓝,厅,从蓝厅出来只能进入相邻的红厅,并且从1,
6、号展厅出来,其间经过25次移动,最后再回到1号厅.,考察参观者的移动:,移动奇数,次时所在展厅的涂色颜色改变,而移动偶数次时所在展厅的涂色,颜色不变.,来,其间经过25次移动,注意到25是奇数,因此从1号展厅出,最后不可能再回到1号,厅,即参观者的愿望不能够实现.,为自然数,求证,能被1985整除.(1985年,匈牙利),证明,1985=5397,(5，397)=1.,所以,1985整除,被37除的余数.,解,所以,被37除得到的余数为26.,证一,按,及,分类讨论.,(略),证二,由费尔马定理,因此,所以,得证.,解,323=1719,当 为偶数时,当 为奇数时,综上，选().,解一,由条件
7、知,故,下证：对任意正整数,首先,为偶数,有,其次,预算知,故对任意正整数,分类讨论如下:,时,时,时,又,(2,9)=1,故,即所求,好!,解二,(数学归纳法),由条件,故 为,18的约数,对任意正整数,有,时,结论成立.,则,时,由,及归纳假设知,故,即所求,下证:,分析,记,但在同,余观点下,的局部虽然不确定,的局部却是稳定的:,这便于解决问题.,解,于是,的末位数字为4或9.,设集合,成999个彼此不交的二元子集,被分,且对所有,1i999,均有,1或6,求证:和数,的末位数字为9.(1998年,美国),于是,的末位数字为4或9.,解,由于,与,有相同的奇偶性,又,的代数和为奇数,故,中有奇数个(999个)奇数,所以它们,这,说明,的末位数字不能为4,只能为9.,证毕.,24=38,解,设,由,知,枚举知,为奇数,枚举知,为奇数,于是,即3、8都整除,而3与8互素,故24整除,于是,由,得,从而,相应的,有5个,选().,注:该题原证法是用整数的整除性知识,过程如下:,具体,故,因为,而,故,为奇数,又,由上知,是3个连续的整数,必有一个是3的倍,数,于是,由,得,从而相应的,有5,个,选().,比如:,将,改为,就无能为力了.,等形式时,原解法,但同余分析仍然可行.,读者不妨,试一试.,作业,谢谢！,
