There is this really nice paper by J.P.Serre on the congruence subgroup property for $SL_2$ for $S$-arithmetic groups (https://www.jstor.org/stable/1970630). If one looks at the proof of Proposition 3 there, Serre in fact proves the following result.

Let $a,b \in {\mathbb N}$ be two co-prime integers, and $\phi$ be Euler's totient function. For each $x\in {\mathbb N}$ we may consider $\phi (ax+b)$. Now consider the g.c.d. of the infinite set of numbers
$$N(a,b)= g.c.d. \{ \phi (ax+b): x=1,2,3,\cdots \}.$$ Now $N(a,b)$ seemingly depends on $a,b$ but it does not much: $N(a,b)$ divides $8$.

The proof of this uses Dirichlet's theorem on infinitude of primes.

If ${\mathbb Q}$ is replaced by a number field $K$, and $a,b$ are co-prime integers, define $\phi (ax+b)$ to be the number of units in the quotient ring $O_K/(ax+b)$, then the analogous g.c.d. divides $2\mu _K^2$ where $\mu _K$ is the number of roots of unity in $K$.

My question is : if I replace the linear polynomial $ax+b$ by any polynomial $P(x)=a_0+ a_1x+\cdots+ a_nx^n$, with the numbers $a_0,a_1, \cdots, a_n$ co-prime and $a_n\neq 0$, then does the corresponding g.c.d. $$g.c.d \{\phi (P(x)):x=0,1,2,..\}$$ depend (i.e. is bounded by a constant dependent) only on the degree $n$ and not on the polynomial?

The question came up in a question on discrete groups, which could be resolved, but THIS question remained. I do not have any applications for this, but I thought it was interesting on its own.

[Edit] I should have added the link https://arxiv.org/abs/math/0409377.

[Edit] The following paper https://arxiv.org/abs/1909.10808 answers this affirmatively (unconditionally for $n=2$ and modulo a well known conjecture in the general case). So the answer is Yes.

  • $\begingroup$ Did you try any experiments? $\endgroup$
    – Igor Rivin
    Nov 19, 2012 at 14:16
  • $\begingroup$ Nice question. Did you try some numerical experiment? $\endgroup$
    – Joël
    Nov 19, 2012 at 14:16
  • 1
    $\begingroup$ It can still depend on a,b even though it only takes values +/- 0,1,2,4,8. Think of Mobius function $\mu(n) = 0, \pm 1$. $\endgroup$ Nov 19, 2012 at 15:56
  • 1
    $\begingroup$ Yes, but not in a serious way; as I have said, I am interested in an upper bound on the g.c.d. independent of $a,b$ $\endgroup$ Nov 19, 2012 at 16:07
  • 1
    $\begingroup$ I think the right assumption to make on the polynomial is that it be irreducible over $\mathbb{Z}.$ $\endgroup$
    – Igor Rivin
    Nov 19, 2012 at 21:41

2 Answers 2


I have made some computations which seem to corroborate the OP's conjecture, namely that for any $n$ there exists a $N$, such that for every polynomial $P$ of degree $n$, with positive integral coefficients and content 1, the quantity $$g(P):= g.c.d(\phi(P(x)),x \geq 1)$$ divides $N$.

For $n=1$, as the OP says, one can take $N=8$ as proved by Serre.

For $n=2$, it seems that one can take $N=2^4 3^2 = 144$. It seems even more that one cannot do better, because for $P(x)=16x^2+32x+17$, I get experimentally $g(P)=16$ (this must not be hard to prove but I haven't tried), and for $P(x)=27 x^2 + 9x+1$, I get $g(P)=18$. So $144 | N$. On the other hand I have need been able to find any $P$ such that $g(P)$ was not a divisor of $144$.

For $n=3$ or $n=4$, I have failed to find any $P$ with $g(P)\geq 2$. This suggests $N=2$ in these cases.

  • 1
    $\begingroup$ If $P(x) | Q(x)$ then $g(P) | g(Q)$. So $(x+1)(16 x^2 + 32 x + 17)$ will achieve $144$. (By one of Gauss's many lemmas, the product of polynomials with content $1$ have content $1$.) As Igor Rivin suggests, this makes it seem natural to only study $g$ for irreducible $P$. $\endgroup$ Dec 4, 2012 at 15:55
  • $\begingroup$ Let $P(x)=x^4+x^3+x^2+x+1$ and $Q(x) = P(x+1)$. I claim that $5 | g(Q)$. (In fact, $g(Q)=10$.) More precisely, I'll show that any prime dividing $P(x)$ is either $1 \mod 5$ or equal to $5$. So we either have $P(x)=1$, $P(x)=5$ or $5 | \phi(P(x))$. The $+1$ makes $Q(x)$ large enough to exclude the first two. (continued) $\endgroup$ Dec 4, 2012 at 17:33
  • $\begingroup$ Proof of claim: If $p | x^4+x^3+x^2+x+1$ then $x$ is a $5$-th root of unity modulo $p$. Except when $p=5$, the polynomials $x-1$ and $x^4+x^3+x^x+x+1$ are relatively prime mod $p$, so $x$ is a primitive $5$-th root of unity mod $p$. This implies $p \equiv 1 \mod 5$. $\endgroup$ Dec 4, 2012 at 17:39
  • 1
    $\begingroup$ My intuition is that this sort of cyclotomic field trickery is basically the only way to force $g(P)$ to be large, and this trickery can clearly only get a finite amount for fixed $\deg P$. But I have no idea how to prove, or even rigorously formulate, this guess. $\endgroup$ Dec 4, 2012 at 17:40
  • $\begingroup$ Thanks Joel (sorry: I cannot type the umlaut). The computations look very promising. $\endgroup$ Dec 9, 2012 at 0:05

[I assume that by "$a_i$ coprime" you mean that the $a_i$ have no common divisor, and not that they are pairwise coprime. That would make things tricky.]

Given a collection of Sophie Germain primes ($p_i$ such that $2p_i+1$ is a prime), we can construct families where the gcd grows exponentially in $n$, with $n$ the sum of the larger primes in each pair.

First, Fermat's little theorem tells us that $2p+1$ divides $x^{2p+1} - x$ for any integer $x$. Take $x^{2p+1} + (p-1)x$ if you want to use only natural numbers. Then $\phi(2p+1) = 2p$ divides $\phi(x^{2p+1} - x)$ for all $x$. From here, we let $P(x) = \Pi(x^{2p_i+1} - x)$ for some collection of Sophie Germain primes $p_i$. Then $\Pi p_i$ divides the gcd, and the degree is $\Sigma(2p_i + 1)$

  • $\begingroup$ Your observation is compatible with the possibility that the gcd of the $\varphi$-values is bounded by a constant depending only on the degree of the polynomial. $\endgroup$
    – KConrad
    Nov 19, 2012 at 21:32
  • $\begingroup$ Of course, it is not known whether there exists an infinite collection of Sophie Germain primes :( $\endgroup$
    – Igor Rivin
    Nov 19, 2012 at 21:33
  • $\begingroup$ Yes, I do mean that $a_0{\mathbb Z}+\cdots+a_n{\mathbb Z}={\mathbb Z}$. In other words, the coefficients of $P$ do not have a common factor. $\endgroup$ Nov 20, 2012 at 2:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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