数论难题$若n为合数,则varphi(n)
2020-04-10
数论难题
$若n为合数,则varphi(n)<=n-sqrtn
$varphi是欧拉函数
优质解答
设$n=p_1^(a_1)p_2^(a_2)...p_k^(a_k)$
$varphi(n)=p_1^(a_1-1)p_2^(a_2-1)...p_k^(a_k-1)*(p_1-1)(p_2-1)...(p_k-1)$
$n-varphi(n)=p_1^(a_1-1)p_2^(a_2-1)...p_k^(a_k-1)*(p_1p_2...p_k-(p_1-1)(p_2-1)...(p_k-1))$
$>=p_1^(a_1/2)p_2^(a_2/2)...p_k^(a_k/2)=sqrt{n}$
设$n=p_1^(a_1)p_2^(a_2)...p_k^(a_k)$
$varphi(n)=p_1^(a_1-1)p_2^(a_2-1)...p_k^(a_k-1)*(p_1-1)(p_2-1)...(p_k-1)$
$n-varphi(n)=p_1^(a_1-1)p_2^(a_2-1)...p_k^(a_k-1)*(p_1p_2...p_k-(p_1-1)(p_2-1)...(p_k-1))$
$>=p_1^(a_1/2)p_2^(a_2/2)...p_k^(a_k/2)=sqrt{n}$