《朱震--初等数论.doc》由会员分享，可在线阅读，更多相关《朱震--初等数论.doc（13页珍藏版）》请在金锄头文库上搜索。
1、整除、同余、不定方程整除、同余、不定方程【大纲要求】全国联赛加试中对初等数论部分的考试要求：同余，欧几里得除法，裴蜀定理，完全剩余类，二次剩余，不定方程和方程组，高斯函数x，费马小定理，格点及其性质，无穷递降法，欧拉定理*，孙子定理*(带*的在加试中不考)【基本知识】一关于奇数和偶数的常用性质1奇数+奇数=偶数；奇数+偶数=奇数；偶数+偶数=偶数2若干个整数之和为奇数，这些数中必有奇数，且奇数的个数为奇数个；若干个整数之和为偶数，且这些数中有奇数，则奇数的个数为偶数个3奇数奇数=奇数；奇数偶数=偶数；偶数偶数=偶数4若干个整数之积为奇数，则这些数必为奇数；若干个整数之积为偶数，则这些数中必有偶
2、数5若a为整数，则|a|与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是整数，则裴蜀定理 若，则存在整数有且必存在自然数，有，其中推论 当时，存在，且，有三整数的整除性定义设a、b是整数，且，如果存在整数c使得a=bc，则称b整除a，或称a能被b整除记作否则称b不整除a，记作显然，1能整除任何整数；
3、0能被任何整数整除质因数分解定理 每一个大于1的整数n都能分解成质因数的乘积，并且不考虑因数的次序时，分解的方式是惟一的，即n可惟一表示成，其中是不同的质数，性质1设a、b、c是整数(1)a|a； (2)若a|b，b|c，则a|c； (3)若a|b，a|c，则对任意整数m、n，有a|(bm+cn)性质2若等式中除某项外，其余各项都能被c整除，则这一项也能被c整除性质3(1)若(a，b)=1，且a|bc，则a|c； (2)若(a，b)=1，且a|c，b|c，则ab|c；(3)p是质数，若p|ab，则p|a或p|b四同余的性质定义1设m是大于1的整数，a、b是整数，如果m|(a-b)，则称a、b关
4、于m同余，记作，读作a同余b模m当m(a-b)时，则称a、b关于m不同余，记作显然(1)若，则m|a； (2)若，则a、b分别用m表示的余数相同定理1设a、b、c、m(m1)是整数，则有(1)反身性：； (2)对称性：若，则；(3)传递性：若，则；定理2设，则(1)；(2)推论1若，则(1)；(2)推论2若，则定理3若，且，则推论若，且，则定理4若，且，则定理5若，且，则五剩余类、完全剩余系、费马小定理定义1设m是正整数，以m为模，则任何整数必与之一同余把同余数归为一类，不同余数的整数必在不在同一类中，则全体整数可分为m类，称每一类为模m的剩余类余数为的剩余类记作，则，是一个以m为公差的等差数
5、列我们有以下性质：(1)； (2)；(3)对任一整数n，有惟一的，使得；(4)对任意整数a、b，a、b定义2设是以m为模的所有剩余类，由每一个中任意取一个数，则这m个数组成一组数，称之为模m的一个完全剩余系定理1 m是整数，是m的一个完全剩余系当时，定理2设m、a是正整数，b是任意整数，如果是m的一个完全剩余系，那么也是m的一个完全剩余系定理3(费马小定理)设p是质数，a是整数，且，则定理4(威尔逊定理)若p为质数，则六数论函数(一)高斯函数设，则表示不超过x的最大整数，则成为高斯函数函数的定义域为R，值域为Z性质1 ，且性质2 ，性质3，则有 性质4，都有性质5，都有性质6若，则 性质7 ，
6、都有性质8 ，有性质9 x为正实数，n为正整数，则不超过x的所有正实数中，是n的倍数的数共有个性质10在的质因数分解中，质数p的指数是(二)与设n的质因数分解式为则正整数n的正因数个数显然，为奇数当且仅当n是完全平方数正整数n的正因数的和性质 与都是积性函数，即，(三)欧拉函数设n为正整数，表示不大于n并且与n互质的自然数个数设n的质因数分解式为，则欧拉定理如果，那么七不定方程整系数方程称为二元一次不定方程定理1方程有整数解的充要条件是定理2若，且时方程的一组解(通常称其为特解)，则方程的全部解(通常称为通解)为定理3（勾股方程）的正整数解为，其中a、b是满足，且一奇一偶的任意整数无穷递降法
7、证明模式大致为：首先假定原方程有解，然后构造某个无穷递降的过程，并且从方程本身看，这个过程应该是有限的，从而导出矛盾其理论依据是“最小数原理”【例题选讲】例1 已知n为奇数，是的一个排列证明：是偶数例2 把1,2,3,1024这1024个数任意排列为算出,，再将这512个数任意排列为，算出,，如此继续下去，最后得到一个数x，试判断x是奇数还是偶数例3 设正整数d不等于2,5,13，证明集合中可以找到两个数a、b，使得不是完全平方数例4 (1)设n是正整数，证明：；(2)若m、n是正整数，且，求证：例5 证明3个连续正整数的积不是平方数例6 设n是正整数，求证：例7 证明：存在无穷多个正整数n，
8、使得，例8 证明：数列11，111，1111，中没有平方数例9 设a和b都是正整数，使得求证：可被1979整除例10 已知如果整数a和b满足关系式：，求证：和都是整数的平方例11 求的末尾两位数例12 的各位数字之和为A，A的各位数字之和为B，求B的各位数字之和例13 称形如的数是费马数(1)求证：，都有；(2)求证：，都有例14 求证：(1) ；(2)例15 证明：存在无穷多个正偶数k，使得对每个质数p，均有为合数例16 求例17 证明方程没有实数解例18 证明存在一个有理数，其中，能使对于都成立例19 将属于之间分母不超过99的既约分数从小到大排列，求与相邻的两个数例20 试求不定方程的整
9、数解例21 求最小的正整数n，使得不定方程例22 证明：不定方程的全部正整数解是例23 已知x，y是质数，求不定方程的解例24 求不定方程的正整数解 例25 试证不定方程无非零整数解例26(2009江苏复赛) 求满足下列条件的所有正整数x、y：(1)x与互素； (2)例27(2010江苏复赛) 设p是一个素数，设x、y是整数，满足求证：存在整数，使得例28(2011江苏复赛) 设整数a、b、c满足，且，求所有的三元组例29(2010西部奥林匹克) 求所有的整数k，使得存在正整数a和b，满足例30 (2009西部奥林匹克) 设数列满足及当时试确定的末两位数字的所有可能的值例31(2010东南奥林
10、匹克) 设正整数a、b满足，若存在正整数k，使得，则称数对是“好的”求所有“好的”数对的个数例32(1990)设，且G具有下列性质：(1)对任何，(2)试证：G中的奇数的个数是4的倍数，且G中所有数的平方和是一定数例33(2003) 设三角形的三边长分别是整数l、m、n，且lmn已知 求这个三角形周长的最小值例34(2009) 设k、l是给定的两个正整数，证明：有无穷多个正整数，使得与l互素例35(2010) 设k是给定的正整数，记，证明：存在正整数m，使得为一个整数例36(2011) 证明：对任意整数，存在一个n次多项式具有如下性质：(1)均为正整数；(2)对任意正整数m及任意k个互不相同的
11、正整数，均有例37 (IMO12) 试确定具有下述性质的所有正整数n集合可以分成两个不相交的非空子集，使得一个子集中所有元素的积等于另一个子集的所有元素的积例38 (IMO39) 试确定使的全部正整数对例39 (IMO46) 数列的通项公式为，求与此数列每一项都互质的所有正整数例40(IMO52) 对任意4个不同正整数组成的集合，记，设是满足整除的数对的个数求所有由4个不同正整数组成的集合A，使得达到最大值【课后练习】1有n个数，它们中的每一个数要么是1，要么若，求证2设p是大于5的奇素数，求证：3证明：对任意，是既约分数4求最大的正整数x，使得对每一个正整数y，都有x能整除5一个八位数能被1
12、983整除，求这个八位数6设a、b、c是三个整数，证明下面三个数，中至少有一个是24的倍数7是否存在自然数n使得存在大于1 的自然数a和b，有？若存在，求出满足条件的n；若不存在，请说明理由（2011苏州一模）8设集合被分成999个彼此不交的二元子集，并且对，均有，求证：的末尾数是99设p是大于5的素数，求证在1,11,111，中有无穷多项是p的倍数10已知，证明11证明：当为质数时，n一定是2的整数幂12已知三个相邻自然数的立方和是一个自然数的立方证明：这三个相邻自然数中间那个数是4的倍数13证明：对任意整数n1，总可以找到n个连续的合数14已知p是奇质数，试求不定方程的正整数解15(2011甘肃预赛)设是一正整数，由不大于n的连续10个正整数的和组成集合A，由不大于n的连续11个正整数的和组成集合B若的元素个数是181，求n的最大值和最小值16(2009女子奥林匹克)求证：方程只有有限组正整数解
