第1讲 初等数论中的同余问题 复旦大学附属中学 万军

2011年协作体夏令营系列讲座(一) 初等数论中的同余问题 复旦附中  万军 同余的概念和性质： 设为非零整数，如果整数满足，则称和对模同余，记为；否则称和对模不同余，记为． 注意到，，故，所以我们总是可以假定为正整数． 对于固定的模，同余有很多性质： 1）同余是一种等价关系，即有 ①自反性：； ②对称性：若，则； ③传递性：若，，则． 2）加法、减法、乘法和乘方运算： 若，， 则， ，． 3）除法运算： ，则． 特别地，若，则． 4）同余组： 同时成立的充要条件是 剩余类与完全剩余系： 设为一个给定的正整数，则全体整数可以分成个集，记为， 其中，则称为模的剩余类． 模的剩余类有下列性质： 1）每个整数必属于且仅属于模的一个剩余类中； 2）两个整数同在一个剩余类中的充要条件是这两个整数模同余． 事实上，，0≤≤，有 如果个整数中不存在两个数属于同一剩余类，则称为模的一个完全剩余系（或称完系）． 最常用的剩余系称为模的非负最小完全剩余系． 此外也常用到绝对值最小完全剩余系，它们是： 当为奇数时， 当为偶数时，或 完全剩余系有下列性质： 1）个整数作为模的一个完全剩余系的充要条件是它们两两模不同余； 2）若是模的一个完全剩余系，， 那么也是模的一个完全剩余系； 也常这样描述：设是正整数，，若通过模的一个完全剩余系， 则也通过模的一个完全剩余系． 3）若是互质的两个正整数，而分别通过的一个完全剩余系， 则通过的一个完全剩余系． 如果一个模的剩余类里面的数与互质，就把它叫做一个与模互质的剩余类，在与模互质的全部剩余类中，从每一类各任取一个代表元所组成的数集，叫做模的一个简化剩余类系（或缩系）． 定理1：模的剩余类是模互质的剩余类的充要条件是此类中有一个数与互质．因此与模互质的剩余类的个数是，模的每一个简化剩余类系是由与互质的个对模不同余的整数组成的． 其中，（欧拉函数）是定义在正整数上的函数，它在正整数上的值是集合 中与互质的数的个数． 定理2：若是个与互质的数整，并且两两对模不同余， 则是模的一个简化剩余类系． 定理3：若，通过模的一个简化剩余系，则也通过模的一个完全剩余系． 定理4：若是互质的两个正整数，而分别通过的一个简化剩余系， 则通过的一个简化剩余系． 推论：若是互质的两个正整数，则． 下面的几个定理在处理数论问题时经常用到，并且它们本身的证明也是很好的例题． 1、（欧拉函数）是定义在正整数上的函数，它在正整数上的值是集合 中与互质的数的个数，求． 2、（欧拉定理）设是正整数，且，则． 3、（费尔马小定理）若是质数，是正整数，则． 4、（拉格朗日定理）设为素数，多项式 是一个模为次整系数多项式，则关于的同余方程（在模的意义下）至多有个不同的解． 5、（威尔逊定理）设为素数，则． 6、设为整数，为正整数，若存在，使得，则称为模的二次剩余，否则，称为模的二次非剩余． 7、已知斐波那契数列， 设为大于5的素数，证明： 8、求所有满足下面两式的三元组，其中为奇素数，为大于1的整数． ① ② 练习题： 1、设为素数，证明：存在无穷多个，使得． 2、对，如果对任意，只要，就有，那么就称具有性质．1）证明：每个素数都具有性质； 2）是否存在无穷多个合数具有性质？ 3、求所有满足的正整数和素数．（其中欧拉函数） 4、求不定方程的整数解为． （其中表示最接近整数的5的倍数） 5、对于正奇数，若存在正奇数，满足，求满足条件的正奇数的总和． 6、设，，正整数数组满足：， 如果不能将分为和相等的两组数，那么称数组为“优秀的”，求所有的“优秀的”数组． 讲座一                 参考答案                  2011-7-18 例题答案： 1.解：设，其中是质数，是正整数， 由定理4的推论得， 由欧拉函数的定义知等于减去集合中与不互质的元素个数， 也就是减去集合中与不互质的元素个数，又是质数， ∴ ∴ 另证：本定理也可以用容斥原理来证明． 设，其中是质数，是正整数， 记， ∴由容斥原理得 2.证明：设是模的一个简化剩余系， 则由定理3知，也是模的一个简化剩余系． ∴ 与且仅与中的一个数对模同余， ∴ 即  （*） 又是模的一个简化剩余系，故． ∴ ∴  由（*）知：． 3.证明：若，则，结论显然成立； 若，由欧拉定理知，即． 注：费尔马小定理的另一种形式：若是质数，是正整数，，则． 另证：对进行归纳， 当时，结论显然成立； 假设时，结论也成立，即 则 ． （其中用到了，当时，） ∴对任意，有． 4.证明：对进行归纳． 当时，由于，则无解，∴定理成立． 假设定理对所有次数小于的多项式都成立，现设存在一个次多项式，使得同余方程有个（在模的意义下）不同的解． 利用因式定理，可设，则在模的意义下是一个至多 次的多项式．由都是的解，知对≤≤，都有 ， 而，故，从而至少有根，与归纳假设矛盾，所以，定理对次整系数多项式也成立． 综上，定理成立． 5.证明：当时，显然成立； 当为奇素数时，考虑多项式 可以看到的最高次数为 又当时，，由费尔马小定理知， ∴ 由拉格朗日定理知，的展开式中各项系数都是的倍数， ∴ 又为奇素数，为偶数，∴，得证． 6.设为奇素数，且，证明：是模的二次剩余充要条件是；是模的二次非剩余充要条件是． 证明：若为模的二次剩余，即存在，使得． 由，可知，由费尔马小定理知，． 反过来，若，则是同余方程的解， 由拉格朗日定理知，该方程至多有个解，而都是该同余方程的解， ∴它们就是该方程的全部解， ∴存在，使得． 另一方面，若是模的二次非剩余，则 但由费尔马小定理，，即 ∴，即 反过来，，又是模的二次剩余，则 ∴与为奇素数矛盾． 7.证明：知斐波那契数列的通项公式（） 对大于5的素数，由费尔马小定理可知， ∴  ，又 ∴或 如果 （其中用到了，当时，，及费尔马小定理） ∴ 如果，类似计算可得，则 综上， 8.解：显然是①的解，代入②解得，∴都是方程的解． 另外，当或时，同样可以得出上述解． 下设≥5， 当时，由②知 而 ∴或 但是，∴上式不可能成立．∴≥3 由①知 同理可得， ∴ ∴    ③ 又 在≥4时，单调递增，∴≥ ∴③式≤≤矛盾． ∴ 由于 又，没有平方因数，∴ ∴≥7，≥11并且≤≤， ∴≤与③式矛盾． ∴本题的解只能是． 练习题答案： 1、设为素数，证明：存在无穷多个，使得． 证明：当时，只需要取为偶数即可； 当为奇素数时，由费尔马小定理知，， 此时令，则． 2、对，如果对任意，只要，就有，那么就称具有性质．1）证明：每个素数都具有性质； 2）是否存在无穷多个合数具有性质？ 证明：对任意素数，由，可知， 从而由费尔马小定理知， ∴，可得， ∴ ∴． 2）存在无穷多个合数具有性质．例如：对奇素数，数都具有性质． 事实上，，则为奇数，∴ 又，∴或 若，由1）知； 若，由费尔马小定理知，， 这时， ∴ 综上，总有，∴，即数都具有性质． 3、求所有满足的正整数和素数．（其中欧拉函数） 解：若时，， ∴为偶数，且中所有的奇数均与互质， ∴ 若为奇素数，设，其中是质数，是正整数，且 ∴，∴，又 ∴，但是，当时，，而 ∴  ，，∴  ∴  综上：时，；时，； 4、求不定方程的整数解为． （其中表示最接近整数的5的倍数） 解： 由， 若，  设， 则， 又 ， ∴ 解得； 若，设， 则， 又 ∴ 解得或． 5、对于正奇数，若存在正奇数，满足，求满足条件的正奇数的总和． 解：由为正奇数得： 又由为正奇数得： ∴ 另一方面：若，可以找到满足条件的正奇数 当时，则； 当时， ∴ 共个正奇数的平方和． 综上：，则其总和为． 6、设，，正整数数组满足：， 如果不能将分为和相等的两组数，那么称数组为“优秀的”，求所有的“优秀的”数组． 解：设数组为“优秀的”，对1≤≤，考虑下面的个数： ，其中 由于不能将分为和相等的两组数，即其中没有若干个数之和等于， ∴上面的个数中，除外，其余任意两项对模不同余，否则这两项之差等于． 另外，上面的个数中，必有两个数模同余， ∴对都成立 ∴  又 ∴ 综上：当为奇数时，中有一个是，其余都是1，或； 当为偶数时，中有一个是，其余都是1．