4
$\begingroup$

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!

$\endgroup$
4
  • 2
    $\begingroup$ This is true, but far from trivial. See math.uiuc.edu/~ford/wwwpapers/sierp.pdf $\endgroup$ Jul 9, 2015 at 22:44
  • 1
    $\begingroup$ Ford's statement is stronger than the one stated here: vieisci is asking for at least $k$ solutions to $\phi(x) = y$ for some $y$, but Ford wants exactly $k$. $\endgroup$ Jul 9, 2015 at 22:48
  • $\begingroup$ @Servaes, thank you for your answer. Any hope that might exist an easier argument if one only asks for at least $k$ solutions? $\endgroup$
    – u1571372
    Jul 9, 2015 at 22:51
  • $\begingroup$ @ElliotG, sorry, I meant distinct natural numbers, I've edited the question. $\endgroup$
    – u1571372
    Jul 9, 2015 at 22:51

1 Answer 1

6
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.