2024年4月5日发(作者：五菱宏光s5新款价格)
高二暑假南理工夏令营
欧拉定理、费马定理、威尔逊定理
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页
更多推荐
定理,欧拉,成立,宏光
发布评论