As my most recent question still does not have any answers and it appears to be a difficult problem, I propose the following problem (that seems easier), but which I still could not manage to solve:
Is it true that for every $k \in \mathbb{N}$ there exists distinct natural numbers $x_1, \cdots, x_k$ such that $\phi(x_1)=\phi(x_2)=\cdots=\phi(x_k)$, where $\phi$ is the Euler's totient function?
Any ideas? Thank you!
Let $N(x)$ be the number of different values of $\phi(n)$ that are $\le x$. Pillai (Bull. Amer. Math. Soc. Volume 35, Number 6 (1929), 832-836) showed that $N(x) = O(x/(\log x)^t)$ where $t = \log(2)/e$. In particular, $N(x)/x \to 0$ as $x \to \infty$. If you take $x$ large enough that $N(x)/x < 1/k$, then by the Pigeonhole Principle some $k$ natural numbers $\le x$ must have the same value of $\phi$.