30th Turkish Mathematical Olympiad

For the solution we will show that if $$\varphi (k)<(n-1)!\text{ then }k<n!$$ Let $k=q_1^{{\alpha }_1}\dots q_s^{{\alpha }_s}$ with $q_1<q_2<\cdots <q_s$. It suffices to show that $$\frac{\varphi (k)}{k}\ge \frac{1}{n}.$$ Since $$\frac{\varphi (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})\ge \frac{1}{n}.$$ Since $q_t\ge t+1$ for each $t\ge 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 $$\varphi (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.