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

Hello everyone,

There is this really nice paper by J.P.Serre on the congruence subgroup property for SL_2 for $S$-arithmetic groups (http://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 $\phi$ 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: $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.

-
Did you try any experiments? – Igor Rivin Nov 19 '12 at 14:16
Nice question. Did you try some numerical experiment? – Joël Nov 19 '12 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$. – john mangual Nov 19 '12 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$ – Venkataramana Nov 19 '12 at 16:07
I think the right assumption to make on the polynomial is that it be irreducible over $\mathbb{Z}.$ – Igor Rivin Nov 19 '12 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$. – David Speyer Dec 4 '12 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) – David Speyer Dec 4 '12 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$. – David Speyer Dec 4 '12 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. – David Speyer Dec 4 '12 at 17:40
Thanks Joel (sorry: I cannot type the umlaut). The computations look very promising. – Venkataramana Dec 9 '12 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. – KConrad Nov 19 '12 at 21:32
Of course, it is not known whether there exists an infinite collection of Sophie Germain primes :( – Igor Rivin Nov 19 '12 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. – Venkataramana Nov 20 '12 at 2:30