Let $\phi$ denote Euler's totient function and $f$ a non-constant univariate polynomial with integer coefficients such that $f(u) \in \mathbf N^+$ for all $u \in \mathbf N^+$ (assume $f$ is irreducible if useful/necessary).

Q1. Is it true that $\mathfrak i_f := \inf_{n \ge 1} \frac{1}{n}|\phi(f(u)) \bmod n: u \in \mathbf N^+\}| > 0$?

We have from [1] that if a residue class (modulo a fixed $n \in \mathbf N^+$) contains at least one multiple of 4 then it contains infinitely many totients (i.e., stuff in the image of $\phi$), which implies that the answer to Q1 is affirmative if $f$ is linear and monic. In fact, I would be already happy to hear about other particular cases. So let me add the following:

Q2. What about the case when $f$ is linear/quadratic?

My motivation (for those here who dislike random questions) is somehow related to the study of the "density" (whatever this means) of sets of totients.


[1] T. Dence and C. Pomerance, Euler's Function in Residue Classes, Ramanujan J. 2 (1998), 7-20 (click).

  • $\begingroup$ I doubt you can prove something like that unconditionally. $\endgroup$ – sergey Jul 19 '15 at 14:29
  • $\begingroup$ The answer, if positive, would resolve a "long standing" math.stack question math.stackexchange.com/questions/43020/… $\endgroup$ – sergey Jul 19 '15 at 14:37
  • $\begingroup$ I doubt it too, but special cases (I mean, cases corresponding to some specific choice of $f$) would already be interesting to me. E.g., what about the linear/quadratic case? (Btw, thanks for the link.) $\endgroup$ – Salvo Tringali Jul 19 '15 at 14:42

Your Answer

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

Browse other questions tagged or ask your own question.