Turkish Mathematical Olympiad

For the solution we will show that if
$$\phi(k) < (n-1)! \text{ then } k < n!$$
Let $k = q_1^{\alpha_1} \dots q_s^{\alpha_s}$ with $q_1 < q_2 < \dots < q_s$. It suffices to show that
$$\frac{\phi(k)}{k} \geq \frac{1}{n}.$$
Since
$$\frac{\phi(k)}{k} = (1 - \frac{1}{q_1}) \dots (1 - \frac{1}{q_s}),$$
the required inequality has the following form
$$(1 - \frac{1}{q_1}) \dots (1 - \frac{1}{q_s}) \geq \frac{1}{n}.$$
Since $q_t \geq t+1$ for each $t \geq 1$ we get
$$(1 - \frac{1}{q_1}) \dots (1 - \frac{1}{q_s}) \ge (1 - \frac{1}{2}) \dots (1 - \frac{1}{s+1}) = \frac{1}{s+1}$$
Thus, if
$$\frac{1}{s+1} \ge \frac{1}{n}$$
we are done. Otherwise, $s > n - 1$. Then $k$ has at least $n$ distinct prime divisors and we get
$$\phi(k) \ge (q_1 - 1) \dots (q_n - 1) \ge 1 \cdot 2 \dots (n - 1) = (n - 1)!$$
which contradicts to the assumption at the beginning of the solution. We are done.