费马定理、欧拉定理、威尔逊定理(讲稿)(优.选)

2024年4月5日发(作者：宝马5系优惠多少)

高二暑假南理工夏令营

欧拉定理、费马定理、威尔逊定理

1、欧拉函数：φ(m)是1, 2, …, m中与m互质的个数，称为欧拉函数.

111

?

n1

?

2

①欧拉函数值的计算公式：若m＝p

?

p…p, 则φ(m)＝m (1－)(1－)…(1－)

12n

p

1

p

2

p

n

111

235

kk?1

②若p为素数，则

?

(p)?p?1,

?

(p)?p(p?1),

若p为合数，则

?

(p)?p?2,

1

③不超过n且与n互质的所有正整数的和为

n

?

(n)

；

2

④若

(a,b)?1?

?

(ab)?

?

(a)

?

(b),

若

ab?

?

(a)

?

(b)

例如，30＝2·3·5，则

?

(30)?30(1?)(1?)(1?)?8.

⑤设d为n的正约数，则不大于n且与n有最大公因数d的正整数个数为

?

()

，

同时

n

d

?

?

(d)?

?

?

()?n

；

dndn

n

d

1

例1、证明：φ(n)＝n不可能成立.

4

【练习】证明：

?

(4)?

证：若

?

(4)?

1

n不可能成立；

4

1

n成立，则4|n

4

?

k

?

1

?

2

设n?2

?

p

1

p

2

?

p

k

,(

?

?2),p

1

,p

2

,

?

p

k

为奇质数，则：

?

(n)?

p?1

1

?

?

1

?

2

?

k

?

k

p

1

?1p

2

?1

?

1

?

2

2p

1

p

2

?

p

k

?2

?

p

1

p

2

?

p

k

()()

?

(

k

)

4p

1

p

2

p

k

?

k

?

k

?1

?

1

?

2

?

1

?1

?

2

?1

即：2

?

?2

p

1

p

2

?

p

k

?2

?

p

1

p

2

?

p

k

(p

1

?1)(p

2

?1)

?

(p

k

?1)

即：p

1

p

2

?

p

k

?4(p

1

?1)(p

2

?1)

?

(p

k

?1)

又

?

上式右边是一个偶数，左边是一个奇数，?上式不成立，?假设不成立

?

?

(4)?

1

n不可能成立

4

例2、证明：数列{2

n

－3}中有一个无穷子数列，其中任意两项互质.

例2、证明：数列{2

n

?3}中有一个无穷子数列，其中任意两项互素；

证明：设数列{2

n

?3}中已有k项是两两互素的，记为u

1

,u

2

,

?

,u

k

,

作u

k?1

?2

?

(u

1

u

2

?

u

k

)?1

?3

其中

?

(x)是欧拉函数，由欧拉定理有：

2

?

(u

1

u

2

?

u

k

)

＝2

?

(u

1

）

?

(u

2

）

?

?

(u

k

)

?1(modu

i

),1?i?k

?2

?

(u

1

u

2

?

u

k

)?1

?3??1(modu

i

),1?i?k

?数列u

1

,u

2

,

?

,u

k

、u

k?1

是k?1项两两互素的子数列，依此方法一直下去

数列{2

n

?3}中一定有一个任意两项互素的无穷子数列{u

i

}

例3、已知p为质数，在1, 2, …, p

α

中有多少个数与p

α

互质？并求φ(p

α

). 直接用性质②

例4 将与105互素的所有正整数从小到大排成数列，求出这个数列的第2010项.

解：1~105的所有正整数中共有

?

(105)?

?

(3)

?

(5)

?

(7)?48

个与105互素，他们从小到排列为：

a

1

?1,a

2

?2,a

3

?4,a

4

?8,a

5

?11,,a

48

?104

. 对于任一的

a

n

，由带余除法存在唯一的q, r使得

,a

48

}

.

,a

48

}

有(105q＋r，105)＝1，于是105q＋r 都是数列的项，

,48)

的数由小到大排列而成的.

a

n

?105q?r,q?0,0?r?105

，由(a

n

，105)＝1，可得(r，105)＝1，即

r?{a

1

,a

2

,

反之，对于任意固定非负整数q,

r?{a

1

,a

2

,

从而存在正整数n，使得

a

n

?105q?r

. 因此数列

{a

n

}

仅由

105q?a

n

(n?1,2,

1 / 7word.

高二暑假南理工夏令营

因为2010＝48*41＋42，所以有

a

2010

?105?41?a

42

,而由a

48

?104,求得a

42

?89,所以a

2010

?4394

.

2、(欧拉定理) 若(a, m)＝1，则a

φ

(

m

)

≡1(mod m).

证明：设r

1

，r

2

，…，r

φ(m)

是模m的简化剩余系，又∵(a, m)＝1，∴a·r

1

，a·r

2

，…，a·r

φ(m)

是模m的简化剩余系，

∴a·r

1

×a·r

2

×…×a·r

φ(m)

≡r

1

×r

2

×…×r

φ(m)

(mod m)，又∵(r

1

·r

2

·…·r

φ(m)

, m)＝1，∴a

φ

(

m

)

≡1(mod m).

注：这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题.

应用：设(a, m)＝1, c是使得a

c

≡1(mod m)的最小正整数, 则c|φ(m).

2、(定义1) 设m＞1是一个固定的整数, a是与m互质的整数，则存在整数k (1≤k≤m)，使a

k

≡1(mod m)，

我们称具有这一性质的最小正整数(仍记为k)称为a模m的阶，由a模m的阶的定义，可得如下性质：

⑴ 设(a, m)＝1，k是a模m的阶，u, v是任意整数，则a

u

≡a

v

(mod m)的充要条件是u≡v (mod k)，

特别地，a

u

≡1 (mod m)的充要条件是k|u

证明：充分性显然.

必要性：设

u?

?

,l?u?

?

，由

a?a(modm)

及

(a,m)?1

知

a?1(modm)

.

用带余除法，

l?kq?r,0?r?k,

故

a?a?1(modm)

，∴

a?1(modm)

，

由

k

的定义知，必须

r?0

，所以

u?v(modk).

＋

⑵ 设(a, m)＝1，k是a模m的阶，则数列a, a

2

, …, a

k

, a

k

1

,…是模m的周期数列，最小正周期为k，

而k个数a, a

2

,…, a

k

模m互不同余.

⑶ 设(a, m)＝1，k是a模m的阶，则k|φ(m)，特别地，若m是素数p，则a模p的阶整除p－1.

(4) 设(a, p)＝1, 则d

0

是a对于模p的阶?

a

0

≡1(mod p), 且1, a, …, a

do

?1

对模p两两不同余.

特别地, d

o

＝φ(p)

?

1, a,…, a

φ

(

p

)?1

构成模p的一个简化剩余系.

定理：若

l

为

a

对模

m

的阶，

s

为某一正整数，满足

a?1(modm)

，则

s

必为

l

的倍数.

例5、设a和m都是正整数，a＞1. 证明：

m|

?

(a?1).

证明：实上，显然

a与a?1

互素，且

a模a?1

的阶是m，所以由模阶的性质③导出

m|

?

(a?1).

例6：设m, a, b都是正整数，m＞1，则(

m?1,m?1)?m

证明：记

d?(m?1,m?1).

由于(a, b)|a及(a, b)|b，易知

m

故

m

(a,b)

ab

ab(a,b)

(a,b)

m

s

kqrr

u

?

l

d

mm

m

?1.

?1|m

a

?1

及

m

(a,b)

?1|m

b

?1

，

?1|d

， 另一方面设m模d的阶是k，则由

m

a

?1(modd),m

b

?1(modd)

(a,b)

推出，k|a及k|b，故k|(a，b). 因此

m

综合两方面可知，

d?m

(a,b)

?1(modd),即d|m

(a,b)

?1.

?1.

证毕.

p

3、(费尔马小定理) 若p是素数，则a

p

≡a(mod p) 若另上条件(a，p)＝1，则a

p

?1

≡1(mod p)

证明：设

p

为质数，若

a

是

p

的倍数，则

a?0?a(modp)

.若

a

不是

p

的倍数，则

(a,p)?1

由欧拉定理得：

?

(p)?p?1,a

?

(p)

?1(modp)

，

?a

p?1

?1(modp),a

p

?a(modp)

，由此即得.

4、(威尔逊定理) p为质数

?

(p－1)!≡－1 (mod p)

证明：充分性：若p为质数，当p＝2，3时成立，当p＞3时，

令x∈{1, 2, 3, …, p?1}，则

(x,p)?1

，在

x,2x,?,(p?1)x

中，必然有一个数除以

p

余1，

这是因为

x,2x,?,(p?1)x

则好是

p

的一个剩余系去0.

从而对

?x?{1,2,?p?1},?y?{1,2,?,p?1}

，使得

xy?1(modp)

；

若

xy

1

?xy

2

(modp)

，

(x,p)?1

，则

x(y

1

?y

2

)?0(modp)

，

p|(y

1

?y

2

)

，这不可能.

故对于不同的

y

1

,y

2

?{1,2,?,p?1}

，有

xy

1

／≡

xy

2

(modp)

.即对于不同的

x

对应于不同的

y

，

即

1,2,?,p?1

中数可两两配对，其积除以

p

余1，然后有

x

，使

x?1(modp)

，即与它自己配对，

这时

x?1?0(modp)

，

(x?1)(x?1)?0(modp)

，∴

x?p?1

或

x?1

.

除

x?1,p?1

外，别的数可两两配对，积除以

p

余1.故

(p?1)!?(p?1)?1??1(modp)

.

必要性：若(p－1)!≡－1 (mod p)，假设p不是质数，则p有真约数d＞1，故(p－1)!≡－1 (mod d)，

另一方面，d＜p，故d|(p－1)!，从而(p－1)!≡0 (mod d)，矛盾！ ∴p为质数.

5、算术基本定理：任何一个大于1的整数都可以分解成质数的乘积. 如果不考虑这些质因子的次序，

?

k1

?

2

则这种分解法是唯一的. 即对任一整数n＞1，有n＝p

?

1

p

2

…p

k

，其中p

1

＜p

2

＜…＜p

k

均为素数，

?

1

、?

2

、…、?

k

都是正整数.

2 / 7word.

2

2