第二讲数论中的存在性问题

初等数论（三）--数论中的存在性问题。重要工具：欧拉函数()n--介于1和n之间与n互质的自然数个数完全剩余系—设m为一个自然数，011,,...,maaa是m个自然数。如果这m个自然数中的任何两个关于m不同余，则称它们是一个完全剩余系。缩系---在()n个剩余类中各取一个元素，它们形成一个模n的缩系欧拉定理。设m是一个自然数，(,)=1am。证明：()1(mod)mam。这就是著名的欧拉定理。如果取mp为质数，那么就成为了费马小定理。其中()m是欧拉函数，计算{1,2,...,}m中与m互质的元素个数中国剩余定理设12,,...,kmmm是k个两两互质的正整数，12...,/(1,2,...,)kiiMmmmMMmik。12,,...,kbbb是任意k个自然数。则同余式方程1122mod;mod;........mod;kkxbmxbmxbm有唯一解***111222...kkkxMMbMMbMMb，其中*1(mod),1,2,...,.iiiMMmik它的通解是***111222...()kkkxMMbMMbMMbMllZ注意：从解的构造上看，关键在于求*,1,2,...,.iMik而且*iiMM具有双重意义：第一,在模运算下就是1：*1(mod),1,2,...,.iiiMMmik第二，每一项*iiMM中含有因子()jmji，使得*0(mod),.iijMMmji，因此，在模运算下，这个通解公式具有“识别”功能，即，当你要选择第i个方程时，(mod).iixmb例1.证明：有无穷多个正奇数n，使得2nn不是质数。例2.证明：有无穷多个自然数n使得2100(2)nn。例3.设p是一个质数，证明数列{2}(1)nnn中有无穷多个项被p整除。例4.证明：数列1,31,331,3331,...中有无穷多个合数。例5.证明：对于任意给定正整数n，总有n个连续自然数，其中每一个都有大于1的平方因子。例6.证明：对于任意给定正整数n，总有n个连续自然数，其中每一个都不是幂数。解答：我们证明：存在n个连续自然数，其中每一个都至少有一个质因子，在这个数的标准例7．证明：存在无穷多个正整数n使得21n有一个大于22nn的因子。例8.设A是正整数集的无限子集，1n是一个给定的整数。已知：对于任意一个不整除n的质数p，集合A中总存在无穷多个元素不被p整除。证明：对于任意整数1,(,)1,mmn集合A中均存在有限多个互不相同的元素，其和S满足1(mod),0(mod).SmSn例9.证明：对于1,2,3,i均有无穷多个正整数n使得,2,28nnn中恰好有i个可以表为三个自然数的立方和。例10.证明：对于不小于4的正整数n，数3n可以表示成为5个整数的立方和，并且每一个整数的绝对值都小于n。例11．方程[][2][4][8][16][32]12345xxxxxx是否有解？例12.证明：存在无穷多个质数p使得方程21xxpy有正整数解(,)xy。例13.设p为一个奇质数。证明：从任何21p个整数中可以找到p个数，它们的和是p的倍数。例14.我们称形如kn的正整数为幂数，这里,nkN，且1k。问：是否存在一个由1000个正整数组成的集合S，使得S的任意一个非空子集合的元素之和都是幂数？例15.求所有质数序列12...nppp满足1231111111...1npppp是一个整数。例16.证明：不定方程532ab唯一的正整数解为1.ab例17.设,ab为互质的自然数，m为任何一个正整数。证明：等差数列,,2,...,,...aababakb中一定有无穷多个数与m互质。例18.设,ab为互质的自然数。证明：等差数列,,2,...,,...aababakb中一定有一个无穷子列，其中任何两个数都互质。例19.证明：当正整数n充分大时，数列,1,2,...,9nnnn中有一个数，它的不同的质因数的个数不小于3.