Upper bound for Euler's totient function on composite numbers I've seen before the general bound $\phi(n) \leq n - n^{1/2}$ for composite $n$. Can this bound be improved at least for those $n$ when we don't have equality above? Say could we possibly have at least $\phi(n) \leq n - kn^{1/2}$ for some $k > 1$?
 A: We have the formula
$$
\phi(n)=n\prod_{\substack{p\mid n\\p\text{ prime}}}\left(1-\frac1p\right)\tag{1}
$$
For a composite $n$, the smallest prime $p_0\mid n$ is at most $\sqrt{n}$, so $(1)$ implies
$$
\begin{align}
\phi(n)
&\le n\left(1-\frac1{p_0}\right)\\
&\le n\left(1-\frac1{\sqrt{n}}\right)\\
&=n-\sqrt{n}\tag{2}
\end{align}
$$
Furthermore, for $n=p^2$,
$$
\phi(p^2)=p^2-p\tag{3}
$$
Thus, we can find an arbitrarily large composite $n$ so that $\phi(n)=n-\sqrt{n}$.
If we don't have equality as in $(3)$, we have either $n=p^k$ or $n$ has two distinct prime factors.
$$
\phi(p^k)=p^k-p^{k-1}\tag{4}
$$
Thus, for $k\ge3$
$$
\frac{n-\phi(n)}{\sqrt{n}}=\frac{p^{k-1}}{p^{k/2}}=p^{k/2-1}=n^{1/2-1/k}\ge n^{1/6}\tag{5}
$$
so if we are looking for the smallest $\frac{n-\phi(n)}{\sqrt{n}}$, we need to look at $n=pq$. We get
$$
\frac{pq-\phi(pq)}{\sqrt{pq}}=\frac{p+q-1}{\sqrt{pq}}=\frac{\sqrt{p}}{\sqrt{q}}+\frac{\sqrt{q}}{\sqrt{p}}-\frac1{\sqrt{pq}}\tag{6}
$$
Since $x+\frac1x=2+\left(\sqrt{x}-\frac1{\sqrt{x}}\right)^2\ge2$, with equality only when $x=1$, we have that if $n$ has two distinct prime factors,
$$
\frac{n-\phi(n)}{\sqrt{n}}\gt2-\frac1{\sqrt{n}}\implies\phi(n)\lt n-2\sqrt{n}+1\tag{7}
$$
Furthermore, inequality $(5)$ guarantees that inequality $(7)$ holds if $n\ge39$ and $n$ is not a prime or the square of a prime.

Checking the integers less than $39$, we see that if $n$ is not a prime or the square of a prime and $n\ne8$ and $n\ne27$, then $(7)$ holds.
A: Let $n=p^2$. Then $\varphi(n)=p^2-p=n-\sqrt{n}$. So we have equality for infinitely many $n$. 
If $n=p^e$ where $e\gt 2$, then $\varphi(n)=p^e-p^{e-1}=n-n^{1-1/e}$. Worst case is $e=3$, $p=2$. In this case we have  $n^{2/3}\ge kn^{1/2}$ where $k=2^{1/6}$. Thus $\varphi(n)\le n-2^{1/6}n^{1/2}$. 
If $n=ab$ where $a$ and $b$ are greater than $1$ and relatively prime, then $\varphi(n)=\varphi(ab)\le (a-1)(b-1)=n-(a+b)+1$. Note that $a+b\gt 2\sqrt{n}$, so we get $\varphi(n)\le n-2\sqrt{n}+1$ in this case. 
