《高二数学竞赛讲义欧拉、威尔逊定理.pdf》由会员分享，可在线阅读，更多相关《高二数学竞赛讲义欧拉、威尔逊定理.pdf（5页珍藏版）》请在三一文库上搜索。
1、数学 高二数学竞赛班二试讲义 第 2 讲欧拉定理、威尔逊定理 班级姓名 一、知识点金 1算术基本定理：任何一个正整数n，都可以唯一分解成素因数乘积的形式， 其中 12 12 k k nppp。12,kppp均为素数，12,k为非负整数。 记( )n是n的正约数的个数，( )n是n的正约数的和，则 1 ( )(1)(1) k n， 1 1 +1+1 1 11 1 11 ( )(1)(1) 11 k k k kk k pp npppp pp 2n为平方数的充分必要条件是( )n为奇数 3 完系和缩系： 在模m的m个剩余类中各任取一个数作为代表，这样的m个数称为模m的 一个完全剩余系，简称完系。如果
2、i和m互素，则易知同余类 i M中所有数都和m互素，这 样的同余类称为模m缩同余类，我们将模m缩同余类的个数记作()m，称为欧拉函数。 在()m个缩同余类中各任取一个数作为代表，这样的()m个数称为模m的一个缩剩 余系，简称缩系（也称简系）。 4设( ,)1a m，b是任意整数。 （i）,2,3 ,(1) ,aaama ma是模m的完系。a叫做模m的生成元。 （ii ）若 12 , m c cc是模m的完系，则 12 , m acb acbacb也是模 m的完系。 （iii ）若 12() , m r rr是模m的缩系，则12() , m ar arar也是模 m的缩系。 证明：( ,)1a
3、m， （i）假设(mod)iajam，ji，则|m iaja，因为( ,)1a m，所以|m ij，矛盾！ （ii ）假设(mod) ij acbacbm，ji，则| ()ijm a cc，所以|ijm cc，矛盾！ （iii ）(,)1,(,)1 ij ar mar m，假设(mod) ij ararm，ji，则|ijm rr，矛盾！ 5欧拉函数( )n，它表示不大于n且与n互素的正整数的个数，设 12 12 k aaa k np pp， 12 , k p pp均为素数，则 1 1 ( )(1) k i i nn p 。 因此，若(, )1m n，则()() ( )mnmn 证明：由容斥原理
4、 11112 1 ( )( 1)(1) kk k iijkiiijki nnn nnn pp pp ppp 因为(, )1m n，则,m n没有相同素因子，由公式易得()() ( )mnmn 6欧拉定理： 设( ,)1a m，则 () 1(mod) m am 证明：当( ,)1a m时，若 12() , m r rr是模m的缩系， 则 12() , m ar arar也是模m的缩系。 所以12()12()mm arararrrr ，即 () 1 2() |(1) m m m rrra，所以 () |1 m m a 费尔马小定理：p为素数，且|p n，则 1 | (1) p pn。 即p为素数，
5、且1),(np，)(mod1 1 pn p 证明：当p为素数，且|p n时，(, )1p n，( )1pp， 由欧拉定理得 1 1(mod ) p nn 费尔马小定理的推论： p为素数，对任意正整数n，都有 |() p pnn。 数学 7威尔逊定理：设p为素数，则(1)!1(mod)pp 证明：若( ,)1a m，则由 4（iii ）可知，存在x使得1(mod)axm。我们称x为a关于模 m的逆，记作 1 a或 1 a 。 当2p时结论显然成立。 如3p， 由上述结论知， 对每个a，11ap， 有唯一的 1 a， 使得 1 1(mod)aap 当 1 (mod)aap 时，等价于 2 1(mo
6、d)ap ，则 1 1(mod)aap 所以3p个数2,3,2p可配为 3 2 p 对，每对 1 ,a a 满足 1 1(mod)aap。 因此，(1)!1 2(2)(1)1 (1)1(mod)ppppp 二、例题分析 例 1 （1）证明：完全平方数模4 同余于 0 或 1 （2）证明：奇数的平方模8 同余于 1 （3）证明：完全立方数模9 同余于 0，1 例 2设a是奇数，n为正整数，证明： 21 1(mod2) n n a 例 3设,p q是不同的奇素数， 1 | 21 pq pq，则 11 | 21,|21 qp pq，反之亦然。 数学 例 4若正整数n满足( )2nn，则称n为完全数。
7、证明：偶数n为完全数的充分必要条 件是 1 2(21) kk n，且21 k 是素数。 三、同步检测 1设21 p p M，p是素数。证明：若|pq，则(,)1 pq MM。 2证明：有无穷多个41k形式的素数，也有无穷多个61k形式的素数（k为正整数）。 3设n是给定的正整数。证明：存在连续n个正整数，其中每一个都不是素数。 数学 4 设n是偶数，12,na aa与12,nb bb都是模n的完系。证明：1122,nnab abab 不是模n的完系。 5设3p是素数， 121 , p a aa与 121 , p b bb都是模p的缩系。 证明： 1 12211 , pp a b a bab不是
8、模p的缩系。 6设p是一个素数，k为正整数，则 （1）| k p p C，对1,2,1kp成立。 （2） 1 ( 1) (mod) kk p Cp，对1,2,1kp成立。 数学 第 2 讲欧拉定理、威尔逊定理 例 1证明略 例 2对n归纳。1n时易证。假设1n时结论成立，即 1 21 12 n n ax，两边平方， 则 1 222 ()12 n n ax，所以 21 1(mod2) n n a 例 3 1(1)11 21(21) 221 pqpqqq ， 1 | 21 pq pq知 1 | 21 pq p， 所以 (1)11 |(21) 221 pqqq p，由费尔马小定理， 1 21(mod
9、) p p，所以 1 |21 q p 同理 1 |21 p q 例 4设 1 2 k nm，其中2,2 |km。由公式得出 21 22() 21 k k mnm ，故 () 21 k m mm，但m及 21 k m 都是m的约数， 而()m为m的所有正约数之和，故m 只有这两个约数，即m为素数，且1 21 k m 1由带余除法得 (, ) (,)(21,21)21 pqp q pq MM 2设形如41k的素数只有有限多个，设为12,np pp，考虑奇数N1241np pp， 易知1N，故N有素数因子。如果这些素数因子都是41k形式，则它们的积也是这 种形式。但N是4 1k 的形式，从而必有一个
10、素数因子形如 41k ，又显然不同于 12,np pp，矛盾。 3可取(1)! 2,(1)! 3,(1)!1nnnn 4反证法：假设有一组 12 , n a aa与 12 , n b bb使 1122 , nn ab abab是模n的完 系，则 1122 12()()()2 (12) ( m o d) nn nabababnn 即 (1) | 2 n n n。因为n是偶数，这不能成立。 5由威尔逊定理，模p的任一缩系的乘积(1)!1(mod)pp 6 （ 1）因 1 1 kk pp kCpC，故| k p p kC，但显然( ,)1k p，所以| k p p C。 （ 2）因 1 11 kkk ppp CCC，故 1 11 0(mod ) kk pp CCp，对k归纳得出证明。