# g.c.d. and Euler's totient function

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.

 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.

• Did you try any experiments? Nov 19, 2012 at 14:16
• Nice question. Did you try some numerical experiment?
– Joël
Nov 19, 2012 at 14:16
• 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$. Nov 19, 2012 at 15:56
• 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$ Nov 19, 2012 at 16:07
• I think the right assumption to make on the polynomial is that it be irreducible over $\mathbb{Z}.$ Nov 19, 2012 at 21:41

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.

• 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$. Dec 4, 2012 at 15:55
• 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) Dec 4, 2012 at 17:33
• 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$. Dec 4, 2012 at 17:39
• 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. Dec 4, 2012 at 17:40
• Thanks Joel (sorry: I cannot type the umlaut). The computations look very promising. 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)$

• 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. Nov 19, 2012 at 21:32
• Of course, it is not known whether there exists an infinite collection of Sophie Germain primes :( Nov 19, 2012 at 21:33
• 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. Nov 20, 2012 at 2:30