Elementary totient-ratio lower bound
= Elementary totient-ratio lower bound
{title2=$\varphi(r)/r\geq1/(1+\log_2r)$}
List the $k$ distinct prime divisors of $r$ in increasing order. The $j$th is at least $j+1$, and $k\leq\log_2r$. The <Euler totient function> product formula gives $\varphi(r)/r\geq\prod_{j=1}^k j/(j+1)=1/(k+1)$. This elementary bound is sufficient to show inverse-polynomial success probability for coprime phase labels in <quantum order finding>.