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

2024年4月5日发(作者：英朗xt两厢)

高二暑假南理工夏令营

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

1、欧拉函数：

φ

(

m

)是1, 2, …,

m

中与

m

互质的个数，称为欧拉函数.

?

n

1

?

2

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

m

＝

p

?

1

p

2

…

p

n

, 则

φ

(

m

)＝

m

(1－

1

p

1

)(1－

1

p

2

)…(1－

1

p

n

)

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

?

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

1

2

1

3

1

5

kk?1

?

(p)?p?1,

?

(p)?p(p?1),

若

p

为合数，则

?

(p)?p?2,

②若

p

为素数，则

1

n

?

(n)

③不超过

n

且与

n

互质的所有正整数的和为

2

；

④若

(a,b)?1?

?

(ab)?

?

(a)

?

(b),

若

ab?

?

(a)

?

(b)

n

d

， ⑤设

d

为

n

的正约数，则不大于

n

且与

n

有最大公因数

d

的正整数个数为

?

()

同时

dn

?

?

(d)?

?

?

()?n

dn

n

d

；

例1、证明：

φ

(

n

)＝

n

不可能成立.

4

1

第 1 页 共 13页

高二暑假南理工夏令营

【练习】证明：

?

(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)是欧拉函数，由欧拉定理有：

?

?

(u

k

)

2

?

(u

1

u

2

?

u

k

)

＝2

?

(u

1

）

?

(u

2

）

?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

n

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

，由(

a

n

，105)＝1，可得(

r

，105)＝1，即

r?{a

1

,a

2

,,a

48

}

.

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

q

,

r?{a

1

,a

2

,,a

48

}

有(105

q

＋

r

，105)＝1，于是105

q

＋

r

都是数列的项，

第 2 页 共 13页