MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hello everyone,

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

[Edit} I should have added the link

share|cite|improve this question
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
up vote 6 down vote accepted

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.

share|cite|improve this answer
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)$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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