11数论的几个重要定理.doc

11 数论的几个重要定理 欧拉定理、费马小定理、威尔逊定理及中国剩余定理是数论的四大定理，它们是解决数论问题的重要工具。下面介绍这几个定理在竞赛数学中的应用方法。 基本原理 定理1（欧拉定理） 设为大于1的整数，，为欧拉函数，则 . 证 设为模的一个简化剩余系，因为，所以 也是模的一个简化剩余系，从而有 ， 即 （1） 因为 ，所以由（1）得 . 定理2（费马小定理） 设是素数，，则 . 证 因为是素数，所以，由欧拉定理知 ， ∴ . 推论 设为素数，为整数，则 （2） 证 当时，（2）式显然成立.当不能整除时，因为为素数，所以.由定理2得 ， ∴ . 定理3（威尔逊定理） 若为素数，则 . 证 ，因为，所以也是模的简化剩余系，故存在唯一的，使得 （1） ∵ ，∴ ，.若，则 ∴ . ∴ , 这与矛盾.综上即知且. 将中的数按（1）式两两配对，得 ， ∴ . 定理4（中国剩余定理） 设是个两两互质的正整数，，，，则同余式组 （1） 有唯一解 （2） 其中，. 证 容易验证（2）是（1）的解.又若，均是（1）的解，则对于，有 ， 从而有 ，又因为两两互质，从而有 ， 即 ， 所以与是同余式组（1）的相同解. 设，，则由欧拉定理知，我们把满足条件 的最小正整数称为对模的阶，或称为对模的指数.关于对模的阶，我们有如下结论. 定理5 设，，对模的阶为，为正整数.若，则. 证 由带余除法知，存在非负整数及，使得 ，. 所以 ， 由于，由的最小性知，所以. 方法解读 用上述定理解题，除应掌握数论解题的基本方法外，还应对这几个定理的用途有一定的 认识.一般说来，欧拉定理与费马小定理提供了降幂与归1的工具.威尔逊定理提供了处理连续整数的积的方法.中国剩余定理提供了某些存在性问题的构造方法.定理5提供了由方幂的指数导出整除关系的途径. 求使为7的倍数的所有正整数. . 解 ∵ ，，， 所以2对模7的阶为3.又因为，所以由定理5知 ，即. 设整数，，满足，记，求证不是素 数. 证 ∵ ， ∴ 同理知 ，， ∴ ， ∴ . 又由费马小定理知，， ∴ ， 同理可证 ，， ∴ ， ∴ . 又∵ ，∴ ，所以不是素数. 证明：数列1,19,119,1119,11119，…中有无穷多个合数. 证 因为19是素数，，由费马小定理知 ，所以对于任 意的正整数，有 ， ∴ ， ∴ ， ∵ ， ∴ ，∴ ，即. 由于正整数有无穷多个，所以数列中有无穷多项被19整除，故数列中有无穷多项为合数. 例4（第47界IMO预选题） 已知，令，且的小数点后第位数字是的小数点后第位数字.证明：若为有理数，则也为有理数. 证 设， ， 则对于，有.因为为有理数，所以数列从某项开始为周期数列，为了说话方便，不妨设为周期数列，为它的一个周期，，其中为非负整数，为大于1的奇数（这是可以办到的，因为若为数列的周期，则也为周期）.现令，由欧拉定理知，，从而有 ， 即 ， 所以对于任意的正整数，有 ， 即 . ∵ 是的周期，从而有 ， 即. 综上知，对于任意的，都有，所以从第项开始为周期数列，因此为有理数. 例5设，求的末三位数. 解 令. ∵ ，∴ . 又因为 （1） 所以 . 由（1）式知 （2） ∵ ， （3） （4） 由（3）得 ，代入（4）得 ， 即 ， ∴ . ，所以 ， ∴ . 又∵ ，由欧拉定理知 ， ∴ （5） 又 （6） 由（5）得 ，代入（6）得 ， 即 ， ∴ . ∴ ，代入得 ， ∴ . 综上知，， 所以 ，故的末三位数为001. 例6求具有如下性质的素数的最大值：存在的两个排列（这两个排列可 以相同），使得被除所得的余数互不相同. 解 不妨设 .若，则存在 ，使得 ，从而有 ，，从而有 ，这与题设矛盾，因此有 . 因为 ，又被除所得的余数互不相同，所以 被除的余数构成的集合为，由有威尔逊定理，得 . 又 ， ∴ ，∴ ，∴ . 由于为素数，所以.容易验证满足要求.故所求的最大值为2. 例7设整数，满足，且不为某个质数的平方，试证： （1） 这里表示的这个数部分. 证 若为合数，因为不为质数的平方，所以存在大于1的整数，，，使得.因为，所以，，从而有，因此 . ∵ ，，， ∴ ， ∴ ，故结论成立. 若为质数，当，易知，从