高中竞赛数论专题

高中竞赛数论专题1.整除设如果存在使得那么就说可被整除(或整除),记做且称是的倍数,是的约数(也可称为除数、因数).不能被整除就记做.整除关系的基本性质(1)(2)对任意的有设是两个不全为零的整数,如果且那么就称为和的公约数,我们把和的公约数中的最大的称为和的最大公约数,记做若则称和是既约的,或是互素的.设是两个均不为零的整数,如果且那么就称为和的公倍数,我们把和的公倍数中的最小的称为和的最小公倍数,记做1.设是两个不全为零的整数,证明对任意整数,都有2.设证明(1)若则(2)若则3.(Bezout定理)设是不全为零的整数,证明的充要条件是存在整数使得4.证明对任意整数,能被整除.5.设是一个大于2正整数,若存在正整数使得.求的所有可能取值.6.证明：正整数是完全平方数的充要条件是对于任意正整数,中至少有一项可以被整除.7.已知整数满足且使得是整数,求证能被整除.8.证明：对于任何自然数和,数都不能分解成若干个连续的自然数之积.9.对于所有素数和所有正整数,证明：能被整除.10.(1)求所有的素数数列,使得是一个整数.(2)是否存在个大于1的不同正整数使得为整数?.11.设是正整数,证明12.任给,证明：存在个互不相同的正整数,其中任意两个的和整除这个数的积.高一竞赛数论专题1.整除解答设如果存在使得那么就说可被整除(或整除),记做且称是的倍数,是的约数(也可称为除数、因数).不能被整除就记做.整除关系的基本性质(1)(2)对任意的有设是两个不全为零的整数,如果且那么就称为和的公约数,我们把和的公约数中的最大的称为和的最大公约数,记做若则称和是既约的,或是互素的.设是两个均不为零的整数,如果且那么就称为和的公倍数,我们把和的公倍数中的最小的称为和的最小公倍数,记做1.设是两个不全为零的整数,证明对任意整数,都有证明：记.即于是所以,即于是所以所以命题得证.2.设证明(1)若则(2)若则证明则于是(1),则于是所以(2)则即3.(Bezout定理)设是不全为零的整数,证明的充要条件是存在整数使得证明：当中有一个为零时,结论是显然的.不妨设都不为零,且一方面若存在整数使得注意到.所以即所以.另一方面设为整数,若则辗转相除到此为止；否则继续.为整数,若则辗转相除到此为止；否则继续.为整数,若则辗转相除到此为止；否则继续.由于且均为自然数,所以经过有限步辗转相除可得即引理：设是两个整数且为整数.则证明：因为又所以回到原题：利用引理我们可得注意到所以由辗转相除的过程知道所以所以是的线性组合即存在整数使得即所以若则存在整数使得4.证明对任意整数,能被整除.证明：.所以能被整除.5.设是一个大于2正整数,若存在正整数使得.求的所有可能取值.解:因为,所以所以(若不然,则于是,即矛盾).因为,所以存在正整数使得.因为,所以.从而注意到所以于是即矛盾.所以不存在这样的6.证明：正整数是完全平方数的充要条件是对于任意正整数,中至少有一项可以被整除.证明：正整数是完全平方数,则.对于是连续个正整数,所以一定存在某个使得于是所以对于任意正整数,中至少有一项可以被整除.假设正整数不是完全平方数,则中一定有一个素因数,它的指数是奇数即存在正整数使得因为对于任意正整数,中至少有一项可以被整除.故取,对于一定存在某个使得注意到.所以(若不然,又于是矛盾).由于于是注意到.所以我们得到且.这与是完全平方数矛盾.所以假设错误.所以正整数是完全平方数.7.已知整数满足且使得是整数,求证能被整除.证明：设其中则是整数.即从而于是注意到所以又,所以因为所以是整数,结合所以于是,又,则又且所以也就是.即又.所以8.证明：对于任何自然数和,数都不能分解成若干个连续的自然数之积.证明:我们知道数能分解成个连续的自然数之积,则一定能被整除.所以只需要证明数不能被一个很小的自然数整除即可..所以也就是数不能分解成3个或3个以上的连续的自然数之积.下面再证明数不能分解成2个连续的自然数之积.由上可知.因此只需要证明无自然数解.当时,,故无解.当时,,故无解.当时,故无解.所以数不能分解成2个连续的自然数之积.于是我们证明了对于任何自然数和,数都不能分解成若干个连续的自然数之积.9.对于所有素数和所有正整数,证明：能被整除.证明：这连续个数有且仅有一个被整除,设这个数为则则且除以的余数不计次序为.于是.因为与互素,所以于是所以10.(1)求所有的素数数列,使得是一个整数.(2)是否存在个大于1的不同正整数使得为整数?.解(1)当时,故所以又所以于是矛盾.所以.当时,.当时,,又.所以于是所以综上,所求的数列只有一个(2)不存在.当时,设所以.所以不存在个大于1的不同正整数使得为整数.11.设是正整数,证明解：不妨设有带余除法得.我们有因为,所以注意到若则于是结论成立.若则作辗转相除.,.我们有因为,所以.若则继续处理,直到为止.由辗转相除法知至此,我们证得了结论.12.任给,证明：存在个互不相同的正整数,其中任意两个的和整除这个数的积.证明：我们任取个互不相同的正整数并选取一个正整数参数希望的积被任意两项的和整除,取互不相同,显然有高一竞赛数论专题2.同余设为正整数,若整数和被除的余数相同,则称和对模同余,记做设是一个给定的正整数,我们称为模的同余类(或剩余类).显然构成整数集的一个划分.在模的同余类中各取一数,这个数称为模的一个完全剩余系(简称完系).最常用的完系称为模的非负最小完全剩余系.如果一个模的同余类里面的数与互素,就把它叫做一个与模互素的同余类,在与模互素的全部同余类中,各取一数所组成的集叫做模的一个简系.模的一个简系的元素个数记为欧拉函数欧拉函数是一个定义在正整数集上的函数,的值等于中与互素的数的个数.1.证明(特别地若则若则)2.设是素数,证明3.(Euler定理)设证明：(Fermat小定理)设一个素数,对任意的整数,证明若则4.(Wilson定理)设是素数,是模的一个简系,证明特别地,有5.(Lucas定理)设是一个素数,将和写成进制数：其中.证明：6.已知正整数,为整数,且其中任何一个均不为的倍数.证明：存在不全为零的整数,使得为的倍数,其中7.已知素数证明：为整数,其中.8.设素数,证明高一竞赛数论专题2.同余解答设为正整数,若整数和被除的余数相同,则称和对模同余,记做设是一个给定的正整数,我们称为模的同余类(或剩余类).显然构成整数集的一个划分.在模的同余类中各取一数,这个数称为模的一个完全剩余系(简称完系).最常用的完系称为模的非负最小完全剩余系.如果一个模的同余类里面的数与互素,就把它叫做一个与模互素的同余类,在与模互素的全部同余类中,各取一数所组成的集叫做模的一个简系.模的一个简系的元素个数记为欧拉函数欧拉函数是一个定义在正整数集上的函数,的值等于中与互素的数的个数.1.证明(特别地若则若则)证明：因为所以即因为所以即2.设是素数,证明证明：等于满足以下条件的的个数：由于是素数,所以有显然因此就等于中不能被整除的数的个数,由于能被整除的数的个数有个.所以3.(Euler定理)设证明：(Fermat小定理)设一个素数,对任意的整数,证明若则证明：引理是模的一个简系,则也是模的一个简系.引理的证明：假设不是模的一个简系.则存在因为所以与是模的一个简系矛盾,所以引理得证.由引理知道由于是模的一个简系,所以于是即证得了Euler定理.令,若则于是若则,所以这就证明了Fermat小定理.4.(Wilson定理)设是素数,是模的一个简系,证明特别地,有证明：引理：对取定的一个简系中的每个必有唯一的一个使得引理的证明：因为,所以存在整数使得,则所以,所以一定存在简系中一个满足且,这就证明了存在性.下面证明唯一性,若还存在简系中一个使得则,因为,所以所以这就证明了唯一性.当时结论显然成立,可设.有引理知道对取定的一个简系中的每个必有唯一的一个使得又若且,则与矛盾.所以,不能同时成立.也即不能同时成立.同时也说明除之外,必有使得成立.不妨设.这样在,模的一个简系中除外恰好两两一对且满足于是所以特别地恰好是模的一个简系,所以5.(Lucas定理)设是一个素数,将和写成进制数：其中.证明：证明：引理1设是一个素数,当时,则其中.引理1的证明：因为因为是一个素数,所以所以即引理2设是一个素数,则引理2的证明：因为,由引理1得证.回到原题的证明,因为所以.即上式右边的通项为注意到若,由进制的表示唯一性知比较的系数得6.已知正整数,为整数,且其中任何一个均不为的倍数.证明：存在不全为零的整数,使得为的倍数,其中证明：设集合.对于令.(1)若存在不同的,满足,则令则不全为零且同时有(2)若所有的均模不同余,由于则模的余数分别为考虑多项式一方面模的余数分别为即所有的的一般形式为故可以考虑复数..另一方面.因为不为的倍数,所以都不是的倍数.所以当时,.于是.这样就产生了矛盾.所以所有的均模不同余是不可能发生的.所以命题得证.7.已知素数证明：为整数,其中.证明：由Fermat小定理知,则所以.又所以.即,于是,从而.即于是.下面只需要证明即可.引理：设是正整数,则回到原题,注意到且均为素数,所以于是.即为整数.8.设素数,证明证明：引理对于任给素数,多项式的所有系数都能被整除.引理的证明：设则是的个解.从而当然也是的个解.由Fermat小定理知是的个解.所以是的个解.又是次的多项式.则回到原题,由韦达定理知道令则一方面另一方面注意到.所以,因为由引理知所以.即高一竞赛数论专题3.整除与同余1.设和都是正整数,当时,证明.2.设证明：是一个正整数.3.设,证明其中为欧拉函数.4.设为素数,且其中证明：.5.如果是素数,证明：至少有个不同的素因数.6.设是奇素数,证明：7.设是素数,证明：8.已知是大于1的正整数,求满足的所有的值.9.设是大于3的素数,证明：至少含有一个不同于的素因数.10.设是大于3的素数,且其中证明：高一竞赛数论专题3.整除与同余解答1.设和都是正整数,当时,证明.证明：设,则,于是,这表明是的公因数,所以则,所以又,所以所以所以,于是是的公因数,所以所以因为所以即证得了.2.设证明：是一个正整数.证明：由Bezout定理知存在整数使得所以是整数.注意到所以是一个正整数.3.设,证明其中为欧拉函数.证明：设是小于且与互素的全部正整数,因为所以是大于且小于并且与互素的全部正整数.显然与不互素.于是是小于且与互素的全部正整数.并注意到.故4.设为素数,且其中证明：.证明：因为,所以,于是.即.另一方面,因为,所以于是即因为,所以.于是从而可设所以.且于是5.如果是素数,证明：至少有个不同的素因数.证明：设为非负整数,为正奇数.若,则,是的真因数,与素数矛盾.所以于是设.其中.注意到若,则这是因为.所以所以这个数两两互素.于是这个数各至少有一个不同的素因数.注意到,则所以至少有个不同的素因数.6.设是奇素数,证明：证明：因为是偶数,所以因为所以所以因为是奇素数,所以.由Fermat小定理知于是所以从而所以7.设是素数,证明：证明：方法1因为Wilson定理得所以即于是这就证明了所以方法2由Wilson定理得即所以存在整数使得于是又令则从而.于是又所以于是存在整数使得于是所以即故所以即因为,显然是整数.所以即证明了8.已知是大于1的正整数,求满足的所有的值.解：由Wilson定理知若是素数,则也就是说.若为合数,则其中于是必是中的某个数.若,则若,则当时,因为一定含有,所以当时,因为综上满足题意的为除4外的全体合数.注解：本题可以说明若则是素数.这就证明了Wilson定理是双向等价的.即是素数9.设是大于3的素数,证明：至少含有一个不同于的素因数.证明：方法1假设没有不同于的素因数.即注意到是大于3的素数,所以.且于是又所以于是注意到所以故矛盾.于是至少含有一个不同于的素因数.方法2先证明因为是大于3,所以即也就是令所以是减函数.是大于3,.所以即也就是于是所以.这就证明了注意到是素数,于是至少含有一个不同于的素因数.方法3：因为是大于3的素数,所以于是因为,所以所以存在整数使得因为,所以所以即存在正整数使得因为且,所以含有一个与互素的因数的素因数显然不同于所以至少含有一个不同于的素因数.10.设是大于3的素数,且其中证明：证明：引理设素数,则(2.同余第8题)由引理知道.于是从而从而.于是我们可以得到同时其中因为所以.但.也就是因为是素数,所以或若则(矛盾),故因为所以.若不然,从而(矛盾).故所以可是所以又所以高一竞赛数论专题5.素因数分解算术基本定理：设整数,那么其中是素数,在不计次序下唯一.把中相同的素数合并,则得到 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 素因数分解式正因数个数定理：设表示大于1的整数的所有正因数的个数,若,其中是素数,则正因数和定理：设表示大于1的整数的所有正因数之和,若,其中是素数,则1.设是非零的整数,证明：2.设是正整数,证明：的素因数分解式为其中是素数,3.求的十进制表示式中末尾的零的个数.4.设为正整数.证明：若的所有正因数之和为的整数次幂,则这些正因数的个数也为2的整数次幂.5.设整数,不超过的素数共有个.设为集合的子集,的元素个数小于且中任意一个数不是另一个数的倍数.证明存在集合的元子集使得中任意一个数也不是另一个数的倍数,且包含高一竞赛数论专题5.素因数分解解答算术基本定理：设整数,那么其中是素数,在不计次序下唯一.把中相同的素数合并,则得到标准素因数分解式正因数个数定理：设表示大于1的整数的所有正因数的个数,若,其中是素数,则正因数和定理：设表示大于1的整数的所有正因数之和,若,其中是素数,则1.设是非零的整数,证明：证明：设素因数分解式则2.设是正整数,证明：的素因数分解式为其中是素数,证明：一方面若素数则另一方面,任一素数,必有所以下面去确定设为整数的素因数的次方.因为必有整数满足所以设表示中能被整除的数的个数,则表示中恰能被整除的数的个数.则显然当时,及于是所以3.求的十进制表示式中末尾的零的个数.解：这就是要求正整数使得因为,实际上是求的最大方次与的最大方次的最小值.显然的最大方次大于的最大方次.所以就是求的最大方次注意到所以所以的十进制表示式中末尾的零的个数为502个.4.设为正整数.证明：若的所有正因数之和为的整数次幂,则这些正因数的个数也为2的整数次幂.证明：设为素数.则的所有正因数之和若为2的整数次幂,则的因数也是2的整数次幂.显然是奇数.若,则由于的素因数只有2,所以不含大于1的奇数因数.于是是奇数.所以.从而于是都是2的整数次幂,显然,于是因为,所以于是矛盾.因此的正因数的个数故的正因数的个数也是2的整数次幂.5.设整数,不超过的素数共有个.设为集合的子集,的元素个数小于且中任意一个数不是另一个数的倍数.证明存在集合的元子集使得中任意一个数也不是另一个数的倍数,且包含证明：引理：若则可在中找到一个数,其不整除集合中任意一个数,也不被集合中任意一个数整除.若引理得证,进而将数添入集合中,并重复这一过程,直到将扩充成一个元子集则集合满足要求.下面证明引理,对大于1的整数,设的标准素因数分解为定义由于则不同的素因子个数小于又不超过的素数共有个,因此,存在素数使得于是设则(若不然,将有,于是与矛盾).对任意若,则为的方幂.于是与矛盾.因此若因为所以故为不同于的素数,且从而矛盾.因此从而,不属于的元素不整除集合中任意一个数,也不被集合中任意一个数整除.法2将不超过的所有个素数从下到大记为对,取正整数满足对这个,取正整数满足其中,均唯一确定的,且令则为在中的约数全体,为在中的倍数全体.考虑个集合,注意到集合中的每个数均以为最大素因子,从而为的两两不相交的个子集.当时,必存在某个,使得即不整除集合中任意一个数,也不被集合中任意一个数整除.将添入集合重复这一过程,直到将扩充成一个元子集则集合满足要求.高一竞赛数论专题6.欧拉函数与Möbius函数欧拉函数是一个定义在正整数集上的函数,的值等于中与互素的数的个数.也等于模的一个简系的元素个数.Möbius函数定义为1.若跑遍模的简系,跑遍模的简系.证明：跑遍模的简系.2.若证明：3.设是正整数,(1)证明：(2)证明：(3)证明：4.已知正整数的素因数分解式其中素数,证明：5.设表示正整数的所有正因数的个数,表示模的一个简系的元素个数证明：6.证明：对任意的正整数都有7.设是正整数,证明：8.给定整数证明：至多存在有限个正整数同时满足下列条件：(1)；(2)高一竞赛数论专题6.欧拉函数与Möbius函数解答欧拉函数是一个定义在正整数集上的函数,的值等于中与互素的数的个数.也等于模的一个简系的元素个数.Möbius函数定义为1.若跑遍模的简系,跑遍模的简系.证明：跑遍模的简系.证明：我们知道跑遍模的完系,则跑过个数,跑遍模的完系,则跑过个数,于是跑过个数.假设,其中是模的完系中的数,是模的完系中的数.于是,因为所以所以这表明跑遍模的完系.若则由得于是所以反之,若则于是所以这就证明了所要的结论.2.若证明：证明：因为跑遍模的简系,跑遍模的简系.则跑遍模的简系.所以模的简系个数等于跑过的个数,跑过的个数为模的简系个数,跑过的个数为模的简系个数.于是跑过的个数为即3.设是正整数,(1)证明：(2)证明：(3)证明：证明(1)当时结论成立.当时,设的素因数分解式结论成立.(2)显然所以得证.(3)当时,显然成立.当素数,所以结论成立.当,为不含平方因数的整数,若则则,,结论成立.所以4.已知正整数的素因数分解式其中素数,证明：法1证明：法25.设表示正整数的所有正因数的个数,表示模的一个简系的元素个数证明：证明：当时,显然成立.当时,设正整数的素因数分解式其中素数,则因为,所以所以6.证明：对任意的正整数都有证明：方法1当时显然成立当时设正整数的素因数分解式其中素数,,所以,于是.注意到所以方法2我们把正整数按与的最大公约数分类.即与有相同的最大公约数的作为一类.这样,的正约数与这样的分类正整数之间建立了一个一一对应关系.记.首先每一个的正约数都对应一个,其次不同的的正约数对应不同的.所以这些分类就是的一个划分.因为,所以于是因为所以这样满足上式的就是模的简系,所以的个数为这就是说满足的元素个数为所以注意到.所以7.设是正整数,证明：证明：令则若,则,则于是从而所以若,则存在使得于是此时所以也就是说若时,若时,计算得恰好就是与互素的的个数.故8.给定整数证明：至多存在有限个正整数同时满足下列条件：(1)；(2)证明：设因为所以注意到所以设是的所有正约数中满足的那些.先证明引理引理的证明(反证法)假设即无平方因子.则于是.因为所以若是奇数,所以都是奇素数,于是从而但矛盾.若是偶数,所以都是奇素数,于是从而但矛盾.于是假设不成立,所以由引理知道回到原题,下面我们证明,所以这就证明了时结论成立.假设且对,均有为正有理数,通分约分后分母至多为,分子至少为1,所以从而于是.这就证明了特别地.这就证明满足要求的至多有有限多个.高一竞赛数论专题7.奇数偶数1.求所有的正整数使得对于任意的两个整数均有与同奇偶.2.在一个国家里,国王要建座城市,并且在它们之间建条道路,使得从每座城市可通往任何一座城市(每条道路连接两座城市,道路不相交,也不经过其他城市).国王要求：沿着道路网,两座城市之间的最短距离分别为1公里,2公里,3公里,,公里.(1)若；国王的要求能实现？(2)若；国王的要求能实现？3.设中的,现将矩阵中个两两既不同行也不同列的的数的乘积称为一个基本项,例如就是一个基本项.证明：矩阵的全部基本项的和总能被4整除.4.求所有使得的整数对高一竞赛数论专题7.奇数偶数解答1.求所有的正整数使得对于任意的两个整数均有与同奇偶.解：与同奇偶就是说是偶数,也就是同奇偶.注意到当时,对任意的正整数都有,所以的只能都是奇数.再注意到当时,对任意的正整数都有,所以一定是偶数.所以当为奇数时,为偶数,当为偶数时,为奇数,且是偶数.于是必为奇数.若为奇数,注意到时奇数,所以为奇数时,为偶数,当为偶数时,为奇数.从而我们证明了与同奇偶的充要条件是为奇数.若为奇数,则都是偶数,因为由任意性可取,因为,所以,则于是所以,于是于是.另一方面若,我们证明都是奇数.,与所含的的方幂相同,这是因为则,但因为,所以即所以都是奇数.法2：与同奇偶就是说是偶数,也就是同奇偶.注意到当时,对任意的正整数都有,所以的只能都是奇数.再注意到当时,对任意的正整数都有,所以一定是偶数.,因为一定是偶数,=1\*GB3①若是奇数,则由Lucas定理知道所以是奇数.满足条件.=2\*GB3②若是偶数,则若存在,则,于是由Lucas定理知道所以是偶数矛盾.所以对任意的都有取最大的,则此时的只能是此时由Lucas定理知道所以是奇数.满足条件.若则由Lucas定理是奇数.所以2.在一个国家里,国王要建座城市,并且在它们之间建条道路,使得从每座城市可通往任何一座城市(每条道路连接两座城市,道路不相交,也不经过其他城市).国王要求：沿着道路网,两座城市之间的最短距离分别为1公里,2公里,3公里,,公里.(1)若；国王的要求能实现？(2)若；国王的要求能实现？解：首先由要建座城市,并且在它们之间建条道路知道从任何一座城市到另外一座城市只有唯一的线路,若不然,一定存在某几座城市可以形成环线,不妨设座城市形成环线,这个环线至少需要条道路,每增加一座城市,至少需要建1条道路,所以增加座城市至少需要建条道路,从而总共至少要建条道路.矛盾.(1)设要建座城市为,最短距离为1公里的两座城市只能是直达道路,这6座城市的最短距离分别是1公里,2公里,3公里,,公里,又6座城市两两的距离至多有种可能,所以没有两座城市的最短距离相同.因为,所以6座城市不能是直线状的.因为最短距离为1公里的两座城市只能是直达道路,所以可以考虑所以国王的要求能实现.(2)设国王要建的座城市中的首都定义为“好”,则若到另外一座城市的距离为偶数时,则也称为“好”,若到另外一座城市的距离为奇数时,则也称为“坏”.当两座城市都是“好”,则两座城市的最短距离一定是偶数,这是因为这两座城市都距离首都的最短距离是偶数,若有直达道路,则到较远的城市一定要经过较近的城市,若不然就会形成环线,于是的直达道路为两偶数的差,是偶数.若没有直达道路,则到一定有一个距离最远的分叉点(有可能就是,到和到重叠的最长距离为于是到一定要经过分叉点.两座城市的最短距离为.因为都是偶数,所以同奇偶,所以两座城市的最短距离为是偶数.同理可说明当两座城市都是“坏”,则两座城市的最短距离一定是偶数.当两座城市一“好”一“坏”,则两座城市的最短距离一定是奇数.设“好”城市为座,“坏”城市为座.则则恰好为一“好”一“坏”城市对.因为国王要求：沿着道路网,两座城市之间的最短距离分别为1公里,2公里,3公里,,公里.于是对应最短距离的公里数为奇数.=1\*GB3①若是偶数,则.所以.=2\*GB3②若是奇数,则.所以所以这就是说能满足国王要求的当且仅当时完全平方数.都不是完全平方数,所以时,所以国王的要求不能实现.3.设中的,现将矩阵中个两两既不同行也不同列的的数的乘积称为一个基本项,例如就是一个基本项.证明：矩阵的全部基本项的和总能被4整除.证明：设每个基本项为,则的个数为个.对于含作为乘积项的基本项共有个,也就是每个都在所有的基本项被选用.所以.因为所以所以,于是我们证明了说明个基本项为的有偶数个,设为.于是有个为1的基本项.  因为所以即4.求所有使得的整数对解：当时,所以此时当时,,不存在当时,是奇数,所以是奇数.所以偶数中有且只有一个能被4整除,另一个不能被4整除,只能被2整除.于是且是奇数.从而即.也就是若因为为奇数,所以无解.若则,因为为奇数,解得所以从而所以使得的整数对.法2当时,所以此时当时,,不存在当时,是奇数,所以是奇数.显然若满足条件,则也满足条件,可设.即.因为一定是一奇数一偶数,所以,也就是所以所以即.所以也就是若是奇数,,也就是于是的可能取值为3,4.若,则此时的,于是,.若,则此时的,无解.若是偶数,,也就是于是的可能取值为2,3.若,则此时的,无解.若,则此时的,于是无解.所以从而所以使得的整数对.高一竞赛数论专题9.同余方程设整系数多项式同余式称为模的同余方程,若整数满足则称为同余方程的解,显然均为同余方程的解,这些解看做相同的,把它们算做同余方程的一个解.因此解同余方程只要在模的一组完全剩余系中解同余方程.满足同余方程的解的个数即为解数,模的同余方程的解数至多为若都是整系数多项式,则1.求同余方程的解.2.证明同余方程的解数为3.解同余方程4.若及其中称为对模的逆或数论倒数.整系数多项式证明：同余方程与同余方程等价.5.设正整数整系数多项式证明：同余方程有解的必要条件是同余方程有解.6.证明：当时,一元一次同余方程必有解,且其解数为1.7.证明一元一次同余方程有解的充要条件是其解数为若是其一解,则它的个解为8.设是素数,证明：是的解.9.(拉格朗日定理)设是素数,模意义下的次整系数多项式,证明：同余方程在模的意义下至多有个不同的解.10.证明对于任给素数,多项式的所有系数都能被整除.高一竞赛数论专题9.同余方程解答设整系数多项式同余式称为模的同余方程,若整数满足则称为同余方程的解,显然均为同余方程的解,这些解看做相同的,把它们算做同余方程的一个解.因此解同余方程只要在模的一组完全剩余系中解同余方程.满足同余方程的解的个数即为解数,模的同余方程的解数至多为若都是整系数多项式,则1.求同余方程的解.解：取模的绝对最小完全剩余系直接计算知道是同余方程的解,所以它的解式2.证明同余方程的解数为解：由Fermat小定理知道任意整数对任意整数都有.即.由Fermat小定理知道任意整数对任意的整数都有.即.因为所以对任意的整数都有.于是同余方程的解数为3.解同余方程解：因为对任意的整数都有,所以原同余方程等价于直接计算得解为所以原同余方程为4.若及其中称为对模的逆或数论倒数.整系数多项式证明：同余方程与同余方程等价.证明：若是的解,则于是即这就说明了的解都是的解.若是的解.则因为所以于是即也就是这就说明了的解都是的解.5.设正整数整系数多项式证明：同余方程有解的必要条件是同余方程有解.证明：若同余方程有解,则因为所以即.所以同余方程有解6.证明：当时,一元一次同余方程必有解,且其解数为1.证明：方法1当时,遍历模的一组完全剩余系时,也遍历模的一组完全剩余系.即若是模的完全剩余系,也是模的完全剩余系,因此有且仅有一个使得即一元一次同余方程必有解,且其解数为1.方法2当时,则由Bezout定理知道存在使得取则这就证明了有解.若还有解使得则因为所以这就证明了解数为1.注意到当时有Euler定理所以于是也就是说的解为7.证明一元一次同余方程有解的充要条件是其解数为若是其一解,则它的个解为证明：当时,显然成立.当时,若有解,则也就是,又所以.若则满足的的值与的的值相同.因为所以有解.所以同余方程有解.若是的解,则也的解.于是的所有的值是于是的所有的值也是即也就是8.设是素数,证明：是的解.证明：所以所以.9.(拉格朗日定理)设是素数,模意义下的次整系数多项式,证明：同余方程在模的意义下至多有个不同的解.证明：若,显然在模至多有个不同的解.若,下面用数学归纳法证明.当时,显然成立.假设当时,结论成立.当时,结论不成立,则至少有个解.设为.考虑多项式令,则的解至少有有个解因为,所以是次多项式,由归纳假设知道至多有个解,矛盾.所以当时,结论成立.所以结论成立.10.证明对于任给素数,多项式的所有系数都能被整除.证明：设则是的个解.从而当然也是的个解.由Fermat小定理知是的个解.所以是的个解.又至多是次的多项式.则若不然,则必存在使得于是,由拉格朗日定理知道解数至多个,于是解数至多个.矛盾.高一竞赛数论专题10.中国剩余定理1.(中国剩余定理)设是个两两互素的正整数,证明对任意整数,一次同余方程组必有解,在模的意义下解唯一.其中是关于模的数论倒数即2.解同余方程组.3.设证明：存在使得同余方程在模的意义下至少有个根.(请对比拉格朗日定理).4.证明：对任意给定的正整数,均有连续个正整数,其中每一个都有大于1的平方因子.5.证明：对任意正整数,存在个连续正整数,它们中每一个数都不是素数的幂.6.证明：存在任意长的由不同正整数组成的等差数列,它的项都是正整数的幂,幂指数是大于1的整数.7.设是自然数,满足对任意自然数.证明存在某个整数使得高一竞赛数论专题10.中国剩余定理解答1.(中国剩余定理)设是个两两互素的正整数,证明对任意整数,一次同余方程组必有解,在模的意义下解唯一.其中是关于模的数论倒数即证明：因为所以由Bezout定理知道存在整数使得取于是另一方面,所以于是即是一次同余方程组的解.若是是一次同余方程组的两个解.则于是即.因为所以,即所以中国剩余定理的得证.2.解同余方程组.解：两两互素,则由中国剩余定理知道有唯一解.取取取所以3.设证明：存在使得同余方程在模的意义下至少有个根.(请对比拉格朗日定理).证明：对于任意的素数,同余方程可化为.所以恰好有两个不同的解.现在任取个不同的奇素数,这里的满足令.考虑个不同的数组,其中.由中国剩余定理方程组有唯一解(在模的意义下).此解满足,也就是满足若两个不同的数组,则必存在使得不妨设于是与不同解.于是.从而.这就证明了至少有个解.所以存在存在使得同余方程在模的意义下至少有个根.4.证明：对任意给定的正整数,均有连续个正整数,其中每一个都有大于1的平方因子.证明：由于素数有无穷多个,我们可取出个互不相同的素数,考虑同余方程组.因为显然两两互素,故由中国剩余定理知上述同余方程组有正整数解于是连续个数分别被平方数整除.命题得证.5.证明：对任意正整数,存在个连续正整数,它们中每一个数都不是素数的幂.证明：若能找到个连续正整数,它们中的每一个数都有两个不同的素因子,则命题得证.为此取个不同的素数考虑同余方程组因为显然两两互素,故由中国剩余定理知上述同余方程组有正整数解于是连续个数中每一个数都有两个不同的素因子.命题得证.6.证明：存在任意长的由不同正整数组成的等差数列,它的项都是正整数的幂,幂指数是大于1的整数.证明：设是任意正整数,由于素数有无穷多个,设表示第个素数,对任意的正整数,显然,由中国剩余定理知同余方程组有正整数解.于是存在正整数满足.令.则组成了一个项的递增的等差数列.注意到,其中由可知当时,于是所以是正整数的幂,幂指数是大于1的整数.命题得证.7.设是自然数,满足对任意自然数.证明存在某个整数使得证明：设其中为非负整数,且为证明结论,只需要证明即可.若,考虑同余方程组因为故由中国剩余定理知上述同余方程组有正整数解于是于是与矛盾.若,考虑同余方程组因为故由中国剩余定理知上述同余方程组有正整数解于是于是与矛盾.所以.于是命题得证.高一竞赛数论专题11.模为素数的二次剩余设素数是整数,如果同余方程有解,则称是模的二次剩余,若无解,则称是模的二次非剩余.注意到则同余方程,则其有且只有一解若且则同余方程为有且只有一解1.设素数,证明在模的一个既约剩余系中,恰有个模的二次剩余,个模的二次非剩余.此外,若是模的二次剩余,则同余方程的解数为2.2.(Euler判别法)设素数那么,是模的二次剩余的充要条件是是模的二次非剩余的充要条件是3.若素数证明：是模的二次剩余的充要条件是当时,4.设是奇素数,证明：中全体模的二次剩余之和由此可以证明当时,高一竞赛数论专题11.模为素数的二次剩余解答设素数是整数,如果同余方程有解,则称是模的二次剩余,若无解,则称是模的二次非剩余.注意到则同余方程,则其有且只有一解若且则同余方程为有且只有一解1.设素数,证明在模的一个既约剩余系中,恰有个模的二次剩余,个模的二次非剩余.此外,若是模的二次剩余,则同余方程的解数为2.证明：取模的绝对最小既约剩余系是模的二次剩余当且仅当由于所以是模的二次剩余当且仅当当时,所以给出了模的全部二次剩余,共有个.由于模的既约剩余系(简系)有个数,所以另外的个必为模的二次非剩余.当是模的二次剩余时,必存在唯一的使得是同余方程的解,于是在模的绝对最小既约剩余系中有且仅有是同余方程的解,所以解数为2.2.(Euler判别法)设素数那么,是模的二次剩余的充要条件是是模的二次非剩余的充要条件是证明：首先来证明对任一有且仅有一个成立.由Euler定理知道因此由于素数即所以对任一有且仅有一个成立.下面来证明是模的二次剩余的充要条件是先证必要性若是模的二次剩余,则必有使得因此有由于所以由Euler定理知道,所以再证充分性,若则考虑一次同余方程对模的绝对最小既约剩余系中的每个,当时,必有唯一的属于模的绝对最小既约剩余系,使得若不是模的二次剩余,则必有这样模的绝对最小既约剩余系中的个数就可按作为一对,两两配完.因此有由Wilson定理知,所以这与矛盾.是模的二次剩余的充要条件是与对任一有且仅有一个成立.可以推得是模的二次非剩余的充要条件是3.若素数证明：是模的二次剩余的充要条件是当时,证明：由Euler判别法知道是模的二次剩余的充要条件是又,所以即由Wilson定理,当时,4.设是奇素数,证明：中全体模的二次剩余之和由此可以证明当时,证明：因为是模的二次剩余当且仅当设,则于是若,则因为,由Euler判别法知道与同为二次剩余或非二次剩余.又在模的一个既约剩余系中,恰好有个模的二次剩余,所以于是高一竞赛数论专题12.Legendre符号设素数是整数,如果同余方程有解,则称是模的二次剩余,若无解,则称是模的二次非剩余.设素数定义整变数的函数(Legendre符号)Legendre符号的性质(1)(2)(3)(4)当时,(5)(6)(7)二次互反律1.计算.2.设是奇素数,求的值.3.证明有无穷多个形如的素数.注解:狄利克莱定理:若则包含无穷多个素数.4.设是素数,证明：是素数的充要条件是5.设且是素数,证明：梅森数是合数.6.证明对任意正整数,高一竞赛数论专题12.Legendre符号设素数是整数,如果同余方程有解,则称是模的二次剩余,若无解,则称是模的二次非剩余.设素数定义整变数的函数(Legendre符号)Legendre符号的性质(1)(2)(3)(4)当时,(5)(6)(7)二次互反律1.计算.解：所以所以2.设是奇素数,求的值.解：是奇素数,所以,所以必存在一个整数使得,则显然.于是我们容易证明在模的简系中不同的对应的不同,若不然,若,则即矛盾.其实在模的意义下唯一.当跑遍模的简系,也跑遍模的简系.注意到,于是,所以当取时,也恰好取.于是也恰好取所以3.证明有无穷多个形如的素数.注解:狄利克莱定理:若则包含无穷多个素数.证明：假设形如的素数只有有限多个,设它们的全部为.考虑数,显然是形如,且数均大于素数,于是不是素数.设是数的素因子,则显然是奇素数,且即于是是模的二次剩余,即,所以,即具有的形式,也就是存在,,于是,从而矛盾.所以形如的素数有无穷多个.4.设是素数,证明：是素数的充要条件是证明必要性：若是素数,又所以这里的原因是所以,于是2是模的二次剩余,由柯西判别法知道即充分性若设是使得成立的最小整数,则因为是素数,所以又由欧拉定理所以所以或,由于,所以这就证明了是素数.5.设且是素数,证明：梅森数是合数.证明：设,则因为,所以2是模的二次剩余,于是存在使得于是即下面证明是的真因子.所以梅森数是合数.6.证明对任意正整数,证明：若且是奇素数.则.令则.于是,注意到这表明是模的二次剩余,即因为所以又所以于是也就是是模3的二次剩余,所以,即.而所以对任意正整数,高一竞赛数论专题13.指数与原根(一)1.设证明(1)存在正整数使得(2)设是满足(1)的最小正整数那么的充要条件是我们记为称为对模的指数.则2.设证明的充要条件是且对模两两不同余.特别地,时,是模的一组简系.设,使得成立的最小正整数称为对模的指数(或阶).记做当时,称是模的原根,简称的原根.当时,所有整数的指数均为1,且均为原根.注解：模有原根的充要条件是其中是奇素数,3.求模7的原根.4.证明指数的基本性质(1)若则(2)若则(3)设是对模的逆,则(4)设是非负整数,证明：在模的一个简系中,至少有个数对模的指数等于(5)(6)若则.(7)若则(8)设那么,对任意的,必有使得(9)对任意的,一定存在使得5.当,证明：对任意的必有高一竞赛数论专题13.指数与原根(一)1.设证明(1)存在正整数使得(2)设是满足(1)的最小正整数那么的充要条件是我们记为称为对模的指数.则证明：(1)由于知从而显然于是这样个余数仅有个取值.其中必有两个相等.即于是取即证明了(1).(2)显然.设因为所以由的最小性.可得于是2.设证明的充要条件是且对模两两不同余.特别地,时,是模的一组简系.证明：若,则是显然的,若不都对模两两不同余.则存在使得.因为所以,,这与的最小性矛盾.所以得证.因为对模两两不同余,所以,又这就是证明了.设,使得成立的最小正整数称为对模的指数(或阶).记做当时,称是模的原根,简称的原根.当时,所有整数的指数均为1,且均为原根.3.求模7的原根.解：模7的指数表362136原根为4.证明下列指数的基本性质(1)若则证明：因为所以于是同理可证明所以(2)若则证明：不妨设因为所以所以于是也就是(3)设是对模的逆,则证明：所以同理可证所以(4)设是非负整数,证明：在模的一个简系中,至少有个数对模的指数等于证明：所以因为所以于是所以当时,这时的指数所以至少有个数对模的指数等于(5)证明：所以因为所以同理可证又于是另一方面.于是所以.我们有所以.另一方面.所以因为,所以又所以(6)若则.证明：即因为所以即.所以.(7)若则证明：注意到所以于是另一方面显然有又所以所以所以(8)设那么,对任意的,必有使得证明：考虑同余方程组由中国剩余定理知道这同余方程组有唯一解.注意到所以同理于是(9)对任意的,一定存在使得证明：由素因数分解及最小公倍数知可设其中于是取即可.5.当,证明：对任意的必有证明：设下面用数学归纳法证明当时,假设当时,结论成立.即当时,所以当结论成立.所以对任意的必有高一竞赛数论专题14.指数与原根(二)1.设为大于1的正整数,证明：用指数解题的套路：先求出指数,再利用Fermat-Euler定理,最后利用指数的性质,得到整除关系式.2.设证明：3.设第个Fermat数.证明(1)(2)若素数则(3)的素因子(4)若是素数,则2一定不是的原根.(5)若是素数,则模的任意一个二次非剩余必为的原根.(6)若是素数,则都是原根.(7)的素因子4.设证明是素数的充要条件是高一竞赛数论专题14.指数与原根(二)解答1.设为大于1的正整数,证明：证明：因为所以是满足的最小正整数,即由Euler定理知道所以即用指数解题的套路：先求出指数,再利用Fermat-Euler定理,最后利用指数的性质,得到整除关系式.2.设证明：证明：显然是奇数,设是的最小素因子,则我们证明从而因为所以即,于是由是大于2的素数,所以由Euler定理知道设对模的指数为则于是因为是奇数,是偶数,所以若奇素数则从知道又,这与是的最小素因子矛盾.所以因为所以因为所以即.于是3.设第个Fermat数.证明(1)(2)若素数则(3)的素因子(4)若是素数,则2一定不是的原根.(5)若是素数,则模的任意一个二次非剩余必为的原根.(6)若是素数,则都是原根.(7)的素因子证明：(1)所以即注意到所以因为,所以.所以(2)所以设.即若,则,因此,即,这与Fermat数两两互素矛盾.所以即(3)的素因子满足又即于是(4)因为但,所以所以2一定不是素数的原根.(5)若是模的二次非剩余,则由欧拉判别法知道假设不是的原根,则.又于是即设,则(矛盾).所以是的原根.(6)当是偶数时,当是奇数时,所以都是模的二次非剩余,所以都是原根.(7)的素因子令则推广(3)得引理：设为数的奇素因子,则引理证明：由已知知道即于是又所以所以由Euler定理知道,所以于是由引理知道4.设证明是素数的充要条件是证明：(必要性)若是素数,则若不然一定存在奇素数于是是合数矛盾.于是是Fermat数,又是素数,所以是模的原根,于是是模的二次非剩余,于是(充分性)若即于是于是又所以所以是素数.