高二数学竞赛班二试数论讲义-欧拉、威尔逊定理-2

高二数学竞赛班二试讲义 第2讲 欧拉定理、威尔逊定理 班级 姓名 一、知识点金 1．算术基本定理：任何一个正整数 ，都可以唯一分解成素因数乘积的形式， 其中 。 均为素数， 为非负整数。 记 是 的正约数的个数， 是 的正约数的和，则 ， 2． 为平方数的充分必要条件是 为奇数 3．完系和缩系：在模 的 个剩余类中各任取一个数作为代表，这样的 个数称为模 的一个完全剩余系，简称完系。如果 和 互素，则易知同余类 中所有数都和 互素，这样的同余类称为模 缩同余类，我们将模 缩同余类的个数记作 ，称为欧拉函数。 在 个缩同余类中各任取一个数作为代表，这样的 个数称为模 的一个缩剩余系，简称缩系（也称简系）。 4．设 ， 是任意整数。 （i） 是模 的完系。 叫做模 的生成元。 （ii）若 是模 的完系，则 也是模 的完系。 （iii）若 是模 的缩系，则 也是模 的缩系。 证明： ， （i）假设 ， ，则 ，因为 ，所以 ，矛盾！ （ii）假设 ， ，则 ，所以 ，矛盾！ （iii） ，假设 ， ，则 ，矛盾！ 5．欧拉函数 ，它表示不大于 且与 互素的正整数的个数，设 ， 均为素数，则 。 因此，若 ，则 证明：由容斥原理 因为 ，则 没有相同素因子，由公式易得 6．欧拉定理：设 ，则 证明：当 时，若 是模 的缩系， 则 也是模 的缩系。 所以 ，即 ，所以 费尔马小定理： 为素数，且 ，则 。 即 为素数，且 ， 证明：当 为素数，且 时， ， ，由欧拉定理得 费尔马小定理的推论： 为素数，对任意正整数 ，都有 。 7．威尔逊定理：设 为素数，则 证明：若 ，则由4（iii）可知，存在 使得 。我们称 为 关于模 的逆，记作 或 。 当 时结论显然成立。如 ，由上述结论知，对每个 ， ，有唯一的 ，使得 当 时，等价于 ，则 所以 个数 可配为 对，每对 满足 。 因此， 二、例题分析 例1．（1）证明：完全平方数模4同余于0或1 （2）证明：奇数的平方模8同余于1 （3）证明：完全立方数模9同余于0， 1 例2．设 是奇数， 为正整数，证明： 例3．设 是不同的奇素数， ，则 ，反之亦然。 例4．若正整数 满足 ，则称 为完全数。证明：偶数 为完全数的