高二数学竞赛班二试讲义
第2讲 欧拉定理、威尔逊定理
班级 姓名
一、知识点金
1．算术基本定理：任何一个正整数n ，都可以唯一分解成素因数乘积的形式， 其中n =p 11p 22⋅⋅⋅p k k 。p 1, p 2, ⋅⋅⋅, p k 均为素数，α1, α2, ⋅⋅⋅, αk 为非负整数。
记τ(n ) 是n 的正约数的个数，σ(n ) 是n 的正约数的和，则τ(n ) =(α1+1) ⋅⋅⋅(αk +1) ，
αk +1α1+1
-1p 1-1p k
σ(n ) =(1+p 1+⋅⋅⋅+p 1) ⋅⋅⋅(1+p k +⋅⋅⋅+p k ) =⋅⋅⋅
p 1-1p k -1
2．n 为平方数的充分必要条件是τ(n ) 为奇数 3．完系和缩系：在模m 的m 个剩余类中各任取一个数作为代表，这样的m 个数称为模m 的一个完全剩余系，简称完系。如果i 和m 互素，则易知同余类M i 中所有数都和m 互素，这样的同余类称为模m 缩同余类，我们将模m 缩同余类的个数记作ϕ(m ) ，称为欧拉函数。 在ϕ(m ) 个缩同余类中各任取一个数作为代表，这样的ϕ(m ) 个数称为模m 的一个缩剩
α1
αk
α
α
α
余系，简称缩系（也称简系）。 4．设(a , m ) =1，b 是任意整数。
（i ）a ,2a ,3a , ⋅⋅⋅,(m -1) a , ma 是模m 的完系。a 叫做模m 的生成元。
（ii ）若c 1, c 2, ⋅⋅⋅, c m 是模m 的完系，则ac 1+b , ac 2+b , ⋅⋅⋅, ac m +b 也是模m 的完系。 （iii ）若r 1, r 2, ⋅⋅⋅, r ϕ(m ) 是模m 的缩系，则ar 1, ar 2, ⋅⋅⋅, ar ϕ(m ) 也是模m 的缩系。 证明：(a , m ) =1，
（i ）假设ia ≡ja (modm ) ，i ≠j ，则m |ia -ja ，因为(a , m ) =1，所以m |i -j ，矛盾！ （ii ）假设ac i +b ≡ac j +b (modm ) ，i ≠j ，则m |a (c i -c j ) ，所以m |c i -c j ，矛盾！ （iii ）(ar i , m ) =1,(ar j , m ) =1，假设ar i ≡ar j (modm ) ，i ≠j ，则m |r i -r j ，矛盾！ 5．欧拉函数ϕ(n ) ，它表示不大于n 且与n 互素的正整数的个数，设n =p 11p 22⋅⋅⋅p k k ，
a
a
a
p 1, p 2, ⋅⋅⋅, p k 均为素数，则ϕ(n ) =n ∏(1-
i =1
k
1
) 。 p i
因此，若(m , n ) =1，则ϕ(mn ) =ϕ(m ) ϕ(n ) 证明：由容斥原理ϕ(n ) =n -
∑
i =1
k
k
n n n 1k
+∑-⋅⋅⋅+(-1) =n ∏(1-) p i 1≤i
因为(m , n ) =1，则m , n 没有相同素因子，由公式易得ϕ(mn ) =ϕ(m ) ϕ(n ) 6．欧拉定理：设(a , m ) =1，则a
≡1(modm )
证明：当(a , m ) =1时，若r 1, r 2, ⋅⋅⋅, r ϕ(m ) 是模m 的缩系，
则ar 1, ar 2, ⋅⋅⋅, ar ϕ(m ) 也是模m 的缩系。
所以ar 1⋅ar 2⋅⋅⋅⋅⋅ar ϕ(m ) =r 1⋅r 2⋅⋅⋅⋅⋅r ϕ(m ) ，即m |r 1r 2⋅⋅⋅r ϕ(m ) (a ϕ(m ) -1) ，所以m |a ϕ(m ) -1 费尔马小定理：p 为素数，且p n ，则p |(n 即p 为素数，且(p , n ) =1，n
p -1
p -1
ϕ(m )
-1) 。
p -1
≡1(modp )
≡1(modn )
p
ϕ(p ) =p -1， 证明：当p 为素数，且p 时，(p , n ) =1，由欧拉定理得n
费尔马小定理的推论：p 为素数，对任意正整数n ，都有p |(n -n ) 。
7．威尔逊定理：设p 为素数，则(p -1)! ≡-1(modp )
证明：若(a , m ) =1，则由4（iii ）可知，存在x 使得ax ≡1(modm ) 。我们称x 为a 关于模
m 的逆，记作a -1或
-1-1
1。 a
-1
当p =2时结论显然成立。如p ≥3，由上述结论知，对每个a ，有唯一的a ，1≤a ≤p -1，使得aa
≡1(modp )
2
-1
当a ≡a (modp ) 时，等价于a ≡1(modp ) ，则a ≡a 所以p -3个数{2,3, ⋅⋅⋅, p -2}可配为
=±1(modp )
p -3-1
对，每对a , a -1满足aa ≡1(modp ) 。 2
因此，(p -1)! ≡1⋅2⋅⋅⋅⋅⋅(p -2)(p -1) ≡1⋅(p -1) ≡-1(modp ) 二、例题分析
{}
例1．（1）证明：完全平方数模4同余于0或1 （2）证明：奇数的平方模8同余于1
（3）证明：完全立方数模9同余于0，±1
例2．设a 是奇数，n 为正整数，证明：a ≡1(mod2)
pq -1
-1，则p |2q -1-1, q |2p -1-1，反之亦然。 例3．设p , q 是不同的奇素数，pq |2
2n
n +1
例4．若正整数n 满足σ(n ) =2n ，则称n 为完全数。证明：偶数n 为完全数的充分必要条件是n =2
k -1
(2k -1) ，且2k -1是素数。
三、同步检测
p
1．设M p =2-1，p 是素数。证明：若p /|q ，则(M p , M q ) =1。
2．证明：有无穷多个4k -1形式的素数，也有无穷多个6k -1形式的素数（k 为正整数）。
3．设n 是给定的正整数。证明：存在连续n 个正整数，其中每一个都不是素数。
a 1, a 2, ⋅⋅⋅, a n 与b 1, b 2, ⋅⋅⋅, b n 都是模n 的完系。a 1+b 1, a 2+b 2, ⋅⋅⋅, a n +b n 4．设n 是偶数，证明：
不是模n 的完系。
5．设p ≥3是素数，a 1, a 2, ⋅⋅⋅, a p -1与b 1, b 2, ⋅⋅⋅, b p -1都是模p 的缩系。 证明：a 1b 1, a 2b 2, ⋅⋅⋅, a p -1b p -1不是模p 的缩系。
6．设p 是一个素数，k 为正整数，则
k
（1）p |C p ，对k =1,2, ⋅⋅⋅, p -1成立。
（2）C p -1≡(-1) (modp ) ，对k =1,2, ⋅⋅⋅, p -1成立。
k k
第2讲 欧拉定理、威尔逊定理
例1．证明略
例2．对n 归纳。n =1时易证。假设n =1时结论成立，即a 则(a
2n -12
2n -1
=1+2n +1x ，两边平方，
) =1+2n +2x '，所以a 2≡1(mod2n +1)
pq -1
n
例3．2
-1=(2(p -1) q -1) ⋅2q -1+2q -1-1，pq |2pq -1-1知p |2pq -1-1，
-1) ⋅2q -1+2q -1-1，由费尔马小定理，2p -1≡1(modp ) ，所以p |2q -1-1 -1
k -1
k
所以p |(2同理q |2
(p -1) q
p -1
2k -1
σ(m ) ，故 例4．设n =2m ，其中k ≥2,2/|m 。由公式得出2m =2n =
2-1
m m
，但m 及k 都是m 的约数，而σ(m ) 为m 的所有正约数之和，故m σ(m ) =m +k
2-12-1
m
只有这两个约数，即m 为素数，且k =1
2-1p q (p , q )
=1 1．由带余除法得(M p , M q ) =(2-1, 2-1) =2
2．设形如4k -1的素数只有有限多个，设为p 1, p 2, ⋅⋅⋅, p n ，考虑奇数N =4p 1p 2⋅⋅⋅p n -1，易知N >1，故N 有素数因子。如果这些素数因子都是4k +1形式，则它们的积也是这
种形式。但N 是4k -1的形式，从而必有一个素数因子形如4k -1，又显然不同于p 1, p 2, ⋅⋅⋅, p n ，矛盾。
3．可取(n +1)! +2,(n +1)! +3, ⋅⋅⋅,(n +1)! +n +1
4．反证法：假设有一组a 1, a 2, ⋅⋅⋅, a n 与b 1, b 2, ⋅⋅⋅, b n 使a 1+b 1, a 2+b 2, ⋅⋅⋅, a n +b n 是模n 的完系，则
(1+b 1+) a (2+b 2+) ⋅⋅⋅+a n (+b n ≡) +2(+1⋅⋅⋅+2n 1+2+⋅⋅⋅+n ≡a
即n |
n ) ( m o d )
n (n +1)
。因为n 是偶数，这不能成立。 2
5．由威尔逊定理，模p 的任一缩系的乘积≡(p -1)! ≡-1(modp )
k k k k -1
6．（1）因kC p =pC p -1，故p |kC p ，但显然(k , p ) =1，所以p |C p 。
（2）因C p =C p -1+C p -1，故C p -1+C p -1≡0(modp ) ，对k 归纳得出证明。
k k -1k k -1k