欧拉函数##
欧拉函数，符号记作(varphi(n))，其值为小于(n)且与(n)互质的数的个数
性质##
①
对于质数(n)
[varphi(n) = n - 1
]
②
对于(n = p^k)
[varphi(n) = (p - 1) * p^{k - 1}
]
③
【积性函数】
对于(gcd(n,m) = 1)
[varphi(n*m) = varphi(n)*varphi(m)
]
④
【计算式】
对于(n = prod p_i^{k_i})
[varphi(n) = n * prod (1 - frac{1}{p_i})
]
⑤
【欧拉定理】
对于互质的(a,m)
[a^{varphi(m)} equiv 1 pmod {m}
]
⑥
小于(n)且与(n)互质的数的和：
[S = n * frac{varphi(n)}{2}
]
⑦
对于质数(p)
若(n mod p = 0)
[varphi(n * p) = varphi(n) * p
]
若(n mod p eq 0)
[varphi(n * p) = varphi(n) * (p - 1)
]
⑧
[sumlimits_{d|n} varphi(d) = n
]
[varphi(n) = sumlimits_{d|n} mu(d) * frac{n}{d}
]