The formula for \(\phi(n)\) (derived here) is:
\[ \phi(n) =n \prod_{p|n, \ p \text{ is prime}} \left( 1 - \frac{1}{p} \right) \]
Let \(n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} \). We can rewrite the above as:
\[ \phi(n) = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} \prod_{i=1}^k \left( 1 - \frac{1}{p_i} \right) \]
Since \(p_i^{a_i} = p_i^{a_i - 1} * p_i\):
\[ \phi(n) = p_1^{a_1-1} p_2^{a_2-1} \cdots p_k^{a_k-1} \prod_{i=1}^k ( p_i - 1 ) \]
Squaring both sides:
\[ \phi(n)^2 = (p_1^{a_1-1} p_2^{a_2-1} \cdots p_k^{a_k-1})^2 \prod_{i=1}^k ( p_i - 1 )^2 \]
If we divide both sides by \(n\):
\[ \frac{\phi(n)^2}{n} = \frac{(p_1^{a_1-1} p_2^{a_2-1} \cdots p_k^{a_k-1})^2}{p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}} \prod_{i=1}^k ( p_i - 1 )^2 \]
Since \(\frac{1}{p_i} = \frac{p_i ^{a_i - 1}}{p_i ^ {a_i}}\):
\[\begin{align} \frac{\phi(n)^2}{n} &= \frac{p_1^{a_1-1} p_2^{a_2-1} \cdots p_k^{a_k-1}}{p_1 p_2 \cdots p_k} \prod_{i=1}^k ( p_i - 1 )^2 \\ &= \prod_{i=1}^k \frac{p_i ^ {a_i - 1}}{p_i} ( p_i - 1 )^2 \end{align}\]
Since \(a_i - 1 \ge 0\), then \(p_i^{a_i - 1} \ge 1\):
\[\begin{align} \frac{\phi(n)^2}{n} &= \prod_{i=1}^k \frac{p_i ^ {a_i - 1} ( p_i - 1 )^2}{p_i} \\ &\ge \frac{( p_i - 1 )^2}{p_i} \end{align}\]
If \(p_i \ge 3\), then \(\frac{(p_i-1)^2}{p_i} \ge \frac{4}{3}\). That means if \(p_i \ge 3\):
\[\frac{\phi(n)^2}{n} \ge \frac{( p_i - 1 )^2}{p_i} \ge \frac{4}{3}\]
What about if \(p_i = 2\)? Consider the case when \(a_i = 1\):
\[\begin{align} \frac{\phi(n)^2}{n} &= \prod_{i=1}^k \frac{p_i ^ {a_i - 1} ( p_i - 1 )^2}{p_i} \\ &= \frac{1}{2} \end{align}\]
If \(a_i \gt 1\), then \(p_i ^ {a_i - 1} \gt 1\):
\[\begin{align} \frac{\phi(n)^2}{n} &= \prod_{i=1}^k \frac{p_i ^ {a_i - 1} ( p_i - 1 )^2}{p_i} \\ &\gt \frac{1}{2} \end{align}\]
This mean we found a lower bound for \(\frac{\phi(n)^2}{n}\):
\[ \frac{\phi(n)^2}{n} \ge \frac{1}{2}\]
Rearranging:
\[\begin{gather} \phi(n)^2 \ge \frac{n}{2} \\ \phi(n) \ge \sqrt{\frac{n}{2}} \end{gather}\]