$\phi(n)$ being Euler's totient function.
Regarding effort put into the problem:
In the case that $n$ is a prime $p$, then it is given that $\phi(p) = p-1$. It is also given that $n\ne 2$, so the fact that $p-1 \ge \sqrt p$, or $(p-1)^2 \ge p$ is easy enough to prove in it of itself.
Considering the case were $n$ is some non-prime number, then $n$ may be written as its power prime factorization $n=p^{a_1}_1p^{a_2}_2 \ldots p^{a_k}_k$. It is given that $\phi$ is multiplicative, so applying this to the original problem we have $\phi(n)=\phi(p^{a_1}_1) \phi(p^{a_2}_2) \ldots \phi(p^{a_k}_k)$.
It is given that $\phi(p^{a_j}_j)=p^j_j-p^{a_j-1}_j=p^{a_j}_j(1-\frac{1}{p_j})$, so the above can be rewritten as
$\phi(n)=p^{a_1}_1p^{a_2}_2 \ldots p^{a_k}_k(1-\frac{1}{p_1})(1-\frac{1}{p_2}) \ldots (1-\frac{1}{p_k})=n(1-\frac{1}{p_1})(1-\frac{1}{p_2}) \ldots (1-\frac{1}{p_k})$.
Which is where I am stuck, as I don't quite see how to prove that the above product (or product squared) is greater than $\sqrt n$ (or $n$ in the product squared case). Is this the wrong angle to be approaching the problem from, or are one of my inferences altogether mistaken?
Best Answer
Sorry for this being very non-rigorous and not very elegant either.. as a high schooler I don't know many "high powered" tools that I could use to solve this.
Let's try to find $n$ which don't fit the statement.
Proposition: We'll get our best bet at falsifying the statement among primorials, i.e., those numbers of the form $\displaystyle \prod_{n = 1}^k p_n$
Consider when it is not a primorial.
Case 1: We add a $p_i$ to our primorial $p_k \#$ with $i < k$. In other words, $n$ has a repeated factor. Then $p_i \phi(n) = \phi (np_i)$. Thus, by doing this we increase the left hand side by $p_i$ while increasing our right hand side only by $\sqrt p_i$, so this is unproductive. Conclusion, we have at most of one of any prime factor in $n$.
Case 2: What if we didn't take the smallest primes. What if we changed a factor $p_i$ in $p_k \#$ into a $p_j$ with $i < k <j$? Then we would increase the left hand side by a factor of $(\frac{p_j}{p_i})(\frac{p_i}{p_i-1})(\frac{p_j-1}{p_j})$ while increasing the left hand side by a lesser factor of $\sqrt{\frac{p_j}{p_i}}$. Conclusion, we take the smallest primes we can.
Furthermore, once we find one primorial that works for the statement, all further primorials work as well. Consider if $p_i \#$ doesn't work, i.e. $\phi(p_i \#) \geq \sqrt{p_i \#}$. Then $\phi (p_{i+1} \#) = \phi(p_{i+1})\phi(p_i \#) \geq \sqrt{p_{i+1}} \sqrt{p_i \#}$, since $\phi(p_{i+1}) = p_{i+1} - 1 \geq \sqrt{p_{i+1}}$ for all $i \geq 1$
So, by inspection we find $n = 2, n = 6$ don't work. $n = 24$ works because $6 \geq \sqrt{24}$, so no further primorials work either.
To finish, we just need to do some inspection in $n =2$ and $n = 6$ to make sure that variations of them work. For $n = 2$, we check $2^2$, and find that $\phi (4) = 2 \geq 2$ works. For $n = 6$, we check $2^2 \times 3$ and $2 \times 3^2$, and find that both of them work. Thus, $n = 2, n = 6$ are the only integers $n$ which do not satisfy the statement.