数论基础（四）数论函数¶
章节概述¶
数论函数是定义在正整数上的函数，在数论研究中占有重要地位。本章将介绍两个最重要的数论函数：欧拉函数 φ(n) 和莫比乌斯函数 μ(n)，以及它们的计算方法和应用。
学习目标¶
- 理解欧拉函数的定义和性质
- 掌握欧拉函数的计算方法（筛法）
- 理解莫比乌斯函数的定义和性质
- 掌握莫比乌斯函数的计算方法
- 了解数论函数在组合数学和算法中的应用
- 掌握欧拉定理和费马小定理
（一）欧拉函数¶
欧拉函数的定义¶
欧拉函数 φ(n) 定义为：小于等于 n 的正整数中与 n 互质的数的个数。
数学表达式：
基本性质¶
性质1：质数的欧拉函数¶
如果 p 是质数，则：
原因：质数 p 与所有小于 p 的正整数都互质。
性质2：质数幂的欧拉函数¶
如果 p 是质数，k ≥ 1，则：
原因：在 1 到 pᵏ 中，只有 p 的倍数（p, 2p, 3p, ..., pᵏ⁻¹p）与 pᵏ 不互质，共有 pᵏ⁻¹ 个。
性质3：积性函数¶
如果 gcd(m, n) = 1，则：
性质4：欧拉函数的值¶
对于任意 n ≥ 3，φ(n) 是偶数。
性质5：欧拉函数的求和¶
计算欧拉函数¶
方法一：分解质因数法¶
原理：利用欧拉函数的积性性质
如果 n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ，则：
def euler_phi(n):
"""
计算欧拉函数 φ(n)（分解质因数法）
参数:
n: 正整数
返回:
int: φ(n) 的值
时间复杂度: O(√n)
示例:
>>> euler_phi(1)
1
>>> euler_phi(7)
6
>>> euler_phi(12)
4 # 1, 5, 7, 11
>>> euler_phi(100)
40
"""
if n == 0:
return 0
result = n
p = 2
while p * p <= n:
if n % p == 0:
# p 是 n 的质因数
while n % p == 0:
n = n // p
result = result // p * (p - 1)
p += 1
# 如果剩下的 n 是质数
if n > 1:
result = result // n * (n - 1)
return result
方法二：筛法（预处理）¶
应用场景：需要计算多个数的欧拉函数
def euler_phi_sieve(n):
"""
筛法求 1 到 n 的欧拉函数
参数:
n: 正整数
返回:
list: phi[i] 表示 φ(i)
时间复杂度: O(n log log n)
空间复杂度: O(n)
示例:
>>> phi = euler_phi_sieve(20)
>>> print(phi)
[0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8]
"""
phi = list(range(n + 1))
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, n + 1):
if is_prime[i]:
# i 是质数，更新所有 i 的倍数
for j in range(i, n + 1, i):
is_prime[j] = (j == i)
phi[j] = phi[j] // i * (i - 1)
return phi
方法三：线性筛法（欧拉筛）¶
def euler_phi_linear(n):
"""
线性筛法求 1 到 n 的欧拉函数
参数:
n: 正整数
返回:
list: phi[i] 表示 φ(i)
时间复杂度: O(n)
空间复杂度: O(n)
示例:
>>> phi = euler_phi_linear(20)
>>> print(phi)
[0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8]
"""
phi = [0] * (n + 1)
primes = []
is_composite = [False] * (n + 1)
phi[1] = 1
for i in range(2, n + 1):
if not is_composite[i]:
primes.append(i)
phi[i] = i - 1
for p in primes:
if i * p > n:
break
is_composite[i * p] = True
if i % p == 0:
# p 是 i 的质因数
phi[i * p] = phi[i] * p
break
else:
# i 和 p 互质
phi[i * p] = phi[i] * phi[p]
return phi
欧拉定理¶
定理：如果 gcd(a, n) = 1，则：
证明：利用群论或构造性证明
应用： - 求模逆元 - RSA 加密算法 - 简化幂运算
def euler_theorem(a, n):
"""
验证欧拉定理
参数:
a, n: 整数，gcd(a, n) = 1
返回:
bool: 如果 a^φ(n) ≡ 1 (mod n) 返回 True
"""
if gcd(a, n) != 1:
return False
phi = euler_phi(n)
return mod_pow(a, phi, n) == 1
费马小定理¶
定理：如果 p 是质数，且 gcd(a, p) = 1，则：
推论：
注意：这是欧拉定理在 n = p（质数）时的特例。
欧拉函数的应用¶
应用1：求模逆元¶
def mod_inverse_using_euler(a, n):
"""
使用欧拉定理求模逆元
参数:
a: 整数
n: 正整数
返回:
int: a 模 n 的逆元
如果逆元不存在返回 None
"""
if gcd(a, n) != 1:
return None
phi = euler_phi(n)
return mod_pow(a, phi - 1, n)
应用2：简分数计数¶
问题：分母为 n 的真分数（分子分母互质）有多少个？
def count_reduced_fractions(n):
"""
计算分母为 n 的真分数个数
参数:
n: 分母
返回:
int: 真分数的个数
"""
return euler_phi(n)
（二）莫比乌斯函数¶
莫比乌斯函数的定义¶
莫比乌斯函数 μ(n) 定义为：
规则： - μ(1) = 1 - 如果 n 有平方因子（即存在质数 p，使 p² | n），则 μ(n) = 0 - 如果 n 是 k 个不同质数的乘积，则 μ(n) = (-1)^k
基本性质¶
性质1：积性函数¶
如果 gcd(m, n) = 1，则：
性质2：莫比乌斯函数的求和¶
性质3：与欧拉函数的关系¶
计算莫比乌斯函数¶
def mobius(n):
"""
计算莫比乌斯函数 μ(n)
参数:
n: 正整数
返回:
int: μ(n) 的值（-1, 0, 或 1）
时间复杂度: O(√n)
示例:
>>> mobius(1)
1
>>> mobius(2)
-1
>>> mobius(4)
0
>>> mobius(6)
1
>>> mobius(30)
-1
"""
if n == 1:
return 1
prime_factors = set()
temp = n
# 分解质因数
for i in range(2, int(n**0.5) + 1):
if temp % i == 0:
count = 0
while temp % i == 0:
count += 1
temp = temp // i
if count > 1:
return 0 # 有平方因子
prime_factors.add(i)
if temp > 1:
prime_factors.add(temp)
return (-1) ** len(prime_factors)
筛法求莫比乌斯函数¶
def mobius_sieve(n):
"""
筛法求 1 到 n 的莫比乌斯函数
参数:
n: 正整数
返回:
list: mu[i] 表示 μ(i)
时间复杂度: O(n log log n)
空间复杂度: O(n)
示例:
>>> mu = mobius_sieve(20)
>>> print(mu)
[0, 1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, 0]
"""
mu = [0] * (n + 1)
mu[1] = 1
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, n + 1):
if is_prime[i]:
# i 是质数
for j in range(i, n + 1, i):
is_prime[j] = (j == i)
mu[j] *= -1
mu[j * i] = 0
return mu
莫比乌斯反演¶
定理：如果
则应用：简化求和问题
def mobius_inversion(f, n):
"""
莫比乌斯反演
参数:
f: 函数 f
n: 正整数
返回:
int: g(n) 的值
假设 f(n) = Σ[d|n] g(d)
"""
result = 0
for d in range(1, n + 1):
if n % d == 0:
result += mobius(d) * f(n // d)
return result
莫比乌斯函数的应用¶
应用1：计算互质数对¶
问题：求 1 ≤ i, j ≤ n 且 gcd(i, j) = 1 的数对 (i, j) 的个数
def count_coprime_pairs(n):
"""
计算 1 ≤ i, j ≤ n 且 gcd(i, j) = 1 的数对个数
参数:
n: 正整数
返回:
int: 互质数对的个数
时间复杂度: O(n log n)
"""
phi = euler_phi_sieve(n)
# 互质数对个数 = 2 × Σ(φ(i)) - 1
return 2 * sum(phi) - 1
应用2：容斥原理¶
莫比乌斯函数可以看作是容斥原理的数学表达。
（三）其他重要数论函数¶
约数函数 d(n)¶
定义：n 的正约数的个数
性质：如果 n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ，则：
def divisor_count(n):
"""
计算 n 的约数个数
参数:
n: 正整数
返回:
int: 约数的个数
示例:
>>> divisor_count(12)
6 # 1, 2, 3, 4, 6, 12
"""
factors = prime_factorization(n)
count = 1
for exp in factors.values():
count *= (exp + 1)
return count
约数和函数 σ(n)¶
定义：n 的所有正约数的和
性质：如果 n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ，则：
def divisor_sum(n):
"""
计算 n 的所有约数的和
参数:
n: 正整数
返回:
int: 所有约数的和
示例:
>>> divisor_sum(12)
28 # 1 + 2 + 3 + 4 + 6 + 12 = 28
"""
factors = prime_factorization(n)
total = 1
for p, exp in factors.items():
total *= (p**(exp + 1) - 1) // (p - 1)
return total
（四）实战应用¶
应用1：计算循环群的阶¶
问题：在模 n 下，与 n 互质的数构成一个乘法群，求这个群的阶。
def multiplicative_group_order(n):
"""
计算模 n 乘法群的阶
参数:
n: 正整数
返回:
int: 群的阶（即 φ(n)）
"""
return euler_phi(n)
应用2：计算原根¶
问题：判断 g 是否是模 p 的原根
def is_primitive_root(g, p):
"""
判断 g 是否是模 p 的原根
参数:
g: 候选原根
p: 奇质数
返回:
bool: 如果是原根返回 True
原根定义：g 模 p 的阶为 φ(p) = p-1
"""
if g % p == 0:
return False
# 检查 g^((p-1)/q) ≠ 1 (mod p) 对所有 p-1 的质因数 q
phi = p - 1
factors = prime_factorization(phi)
for q in factors.keys():
if mod_pow(g, phi // q, p) == 1:
return False
return True
实战练习¶
练习1：计算多个数的欧拉函数¶
任务：使用筛法计算 1 到 100 的所有欧拉函数值
def exercise_1():
"""
计算 1 到 100 的欧拉函数值
"""
phi = euler_phi_sieve(100)
for i in range(1, 101):
print(f"φ({i}) = {phi[i]}")
练习2：验证欧拉函数的积性¶
任务：验证如果 gcd(m, n) = 1，则 φ(m × n) = φ(m) × φ(n)
def exercise_2():
"""
验证欧拉函数的积性
"""
for m in range(1, 50):
for n in range(1, 50):
if gcd(m, n) == 1:
assert euler_phi(m * n) == euler_phi(m) * euler_phi(n)
print("✓ 欧拉函数的积性验证通过")
练习3：计算互质概率¶
任务：随机选择两个正整数，求它们互质的概率
def estimate_coprime_probability(trials=10000):
"""
估计两个随机整数互质的概率
参数:
trials: 试验次数
返回:
float: 估计的概率
理论值：6/π² ≈ 0.6079
"""
import random
count = 0
for _ in range(trials):
a = random.randint(1, 1000)
b = random.randint(1, 1000)
if gcd(a, b) == 1:
count += 1
return count / trials
# 运行
print(estimate_coprime_probability())
章节小结¶
本章介绍了重要的数论函数：
- 欧拉函数：理解定义、性质和计算方法（筛法、线性筛法）
- 莫比乌斯函数：理解定义、性质和计算方法
- 欧拉定理和费马小定理：掌握其应用
- 其他数论函数：了解约数函数和约数和函数
- 莫比乌斯反演：理解其在求和问题中的应用
数论函数在组合数学、解析数论和算法设计中都有重要应用。
下一步¶
继续学习第五章：数论算法，学习质因数分解、勒让德符号、离散对数等高级算法。
重点提醒： - 欧拉函数是积性函数，可以用筛法高效计算 - 莫比乌斯函数用于容斥原理和莫比乌斯反演 - 欧拉定理和费马小定理是模运算的重要工具 - 线性筛法可以在 O(n) 时间内计算所有欧拉函数值