注:文章内容来源于网络,真实性有待确认,请自行甄别。
什么是欧拉函数?
发表于:2024-10-24 00:00:00浏览:5次
问题描述:什么是欧拉函数?
φ(1) = 1(小于等于1的正整数中唯一和1互质的数就是1本身)。
若n是质数p的k次幂,φ(n) = φ(pk) = pk − pk − 1 = (p − 1)pk − 1,因为除了p的倍数外,其他数都跟n互质。
欧拉函数是积性函数,即是说若m,n互质,φ(mn) = φ(m)φ(n)。证明:设A, B, C是跟m, n, mn互质的数的集,据中国剩余定理,和C可建立双射(一一对应)的关系。因此φ(n)的值使用算术基本定理便知,
若
则。
例如
猜你喜欢
栏目分类全部>