Note
这篇文章涉及几个欧拉函数的性质
暂时没有证明,大概寒假的时候会补一下证明
完结撒花!我居然在寒假第一天就把这证明补完了...
如果下方的证明有哪里有问题的话,请在下方评论区指出,以提醒作者修改。
定义
(phi(n))表示在1~n中与n互质的数
计算式及计算方法
[egin{aligned}
&若n根据算术基本定理分解为n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}\
&则phi(n)=nprod_{i=1}^{m}left(1-frac{1}{p}
ight)\
&也可以变式为phi(n)=nprod_{i=1}^mleft(frac{p-1}{p}
ight)\
&本质是一样的
end{aligned}
]
(upd):(O(frac{sqrt{n}}{log n}))计算一个数的欧拉函数
分解质因数,由性质4可以顺便算出每个(varphi(p^k)),然后因为(varphi)是个积性函数,所以直接把每个值相乘即得到该数的(varphi)。
直接分解质因数是(O(sqrt{n}))的,但是只要预处理出根号内的质数就可以(O(frac{sqrt{n}}{log n}))计算一个数的欧拉函数了。
性质1
[egin{aligned}
&phi是积性函数,但不是完全积性函数\
&当n,m互质时,满足:\
&phi(nm)=phi(n)*phi(m)\
&那么显然,当n根据算术基本定理分解为n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}时\
&phi(n)=prod_{i=1}^m{phi(p_i^{c_i})}
end{aligned}
]
证明:
[egin{aligned}
&若n与m互质,则n与m没有相同的质因子\
&设n的质因子个数为cnt_n,m的质因子个数为cnt_m,则\
&phi(n)*phi(m)\
&=n*prod_{i=1}^{cnt_n}(1-p_i)*m*prod_{i=1}^{cnt_m}(1-p_i)\
&=n*m*prod_{i=1}^{cnt_n+cnt_m}(1-p_i)\
&=phi(nm)
end{aligned}
]
证毕。
性质2
对于质数(p),它的欧拉函数值(phi(p)=p-1)
证明:
因为(p)为质数,所以比它小的数都和它互质,即在1~p中共有p-1个数和它互质。
证毕。
性质3
[当n为奇数时,phi(2*n)=phi(n)
]
证明:
[egin{aligned}
&当n为奇数时,n与2互质\
&由欧拉函数是积性函数可知,n与2互质时,phi(2n)=phi(2)*phi(n)\
&又因为phi(2)=1\
&所以phi(2n)=phi(n)
end{aligned}
]
证毕。
性质4
[当n=p^k时,phi(n)=p^k-p^{k-1}
]
证明:
[因为n=p^k,所以n只有p一个质因数,则由欧拉函数的计算式可得\
phi(n)=p^k*(1-frac{1}{p})=p^k-p^{k-1}
]
性质5
[egin{aligned}
&n中与n互质的数的和为phi(n)/2*n(n>1)\
&phi(n)(n>2)为偶数
end{aligned}
]
证明:
需要知道的一个基本事实是(gcd(n,x)=gcd(n,n-x)(n>x))
关于这个,可以了解一下更相减损术
因为(gcd(n,x)=gcd(n,n-x)(n>x)),所以与n互质的数都是成对出现的
每一对的和都为(n)。所以他们的和为(phi(n)/2*n)。
至于(phi(n)(n>2))为偶数。因为与n互质的数都是成对出现的,所以显然与n互质的数为偶数,即(phi(n))为偶数。
证毕。
性质6
[egin{aligned}
&若p|n且p^2|n,则phi(n)=phi(frac{n}{p})*p\
&若p|n且p^2
ot|spacespace n,则phi(n)=phi(frac{n}{p})*(p-1)
end{aligned}
]
证明:
对于第一点
[egin{aligned}
&若p|n且p^2|n,则证明n和frac{n}{p}有相同的质因子,只是p这一项的指数不同\
&那么我们可以将其按照欧拉函数的计算式展开,并相除,可得:\
&frac{nprod_{i=1}^m(1-frac{1}{p_i})}{frac{n}{p}prod_{i=1}^{m}(1-frac{1}{p_i})}=frac{n}{frac{n}{p}}=p\
end{aligned}
]
对于第二点
[egin{aligned}
&若p|n且p^2
ot|spacespace n,则说明p与frac{n}{p}互质(因为p为素数)\
&那么根据欧拉函数为积性函数的这个性质即可证得phi(n)=phi(frac{n}{p})*phi(p)=phi(frac{n}{p})*(p-1)
end{aligned}
]
证毕。
这个性质广泛用于递推求欧拉函数
性质7
[sum_{d|n}phi(d)=n
]
证明:
[设f(n)=sum_{d|n}phi(d)\
]
则f(n)为一个积性函数(当n,m互质时)
证明:
(设n,m互质)
[egin{aligned}
&f(n)*f(m)\
&=sum_{i|n}phi(i)*sum_{j|m}phi(m)\
&=sum_{i|n}sum_{j|m}phi(i)*phi(j)\
&=sum_{i|n}sum_{j|m}phi(i*j)\
&=sum_{d|nm}phi(d)\
&=f(nm)
end{aligned}\
egin{aligned}
&可以发现的是sum_{i|n}sum_{j|m}phi(i*j)涵盖了所有nm的因数的欧拉函数,即为f(n)*f(m)\
&所以f是一个积性函数
end{aligned}
]
那么则有
[egin{aligned}
&若n根据算数基本定理可以分解为p_1^{c_1}p_2^{c_2}...p_k^{c_k}\
&则由f是一个积性函数可知,f(n)=f(p_1^{c_1})*f(p_2^{c_2})*...*f(p_k^{c_k})\
&所以f(p^c)=phi(1)+phi(p)+phi(p^2)+...+phi(p^k)=1+(p-1)+(p^2-p)+...+(p^k-p^{k-1})=p^k\
&则f(n)=f(p_1^{c_1})*f(p_2^{c_2})*...*f(p_k^{c_k})=p_1^{c_1}*p_2^{c_2}*...*p_k^{c_k}=n\
&即sum_{d|n}phi(d)=n
end{aligned}
]
证毕。
性质8
[phi(n)=sum_{d|n}frac{mu(d)}{d}
]
证明
我们将性质7用狄利克雷卷积形式表示出来
[egin{aligned}
&phi*1=id\
&两边卷上mu\
&phi*1*mu=id*mu\
&phi*(1*mu)=id*mu\
&phi*e=id*mu
end{aligned}
]
最后一个式子写出来就是
[phi(n)=sum_{d|n}frac{mu(d)}{d}
]
证毕。