# Does $c(f) = \gcd(\{ f(n) | n \in \mathbb{Z} \})$?

Consider $\sum_{i = 0}^n a_i x^i \in \mathbb{Z}[x]$. Recall that the content of a polynomial is the gcd of its coefficients. I'm wondering whether the content is equal to $\gcd ( \{ \sum_{i = 0}^n a_i k^i | k \in \mathbb{Z} \} )$.

Context: I thought of the question when trying to think of a proof of Gauss's lemma, in which it is shown that c(fg) = c(f)c(g) for any two polynomials f and g. Of course the question above is true for degree 1 polynomials and constant polynomials, and so it seemed natural that it would hold for all degrees (and so I never thought to look for counterexamples in higher degrees as described below).

• Welcome to math.SE: since you are new, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are; this will prevent people from telling you things you already know, and help them give their answers at the right level. – Luiz Cordeiro May 13 '16 at 23:45
• Thanks. I suppose that's the reason for the down vote. – Dean Young May 13 '16 at 23:52
• Consider the polynomial $x+x^2$, values always divisible by $2$ Or $x^3-x$, values always divisible by $6$. Or many others. – André Nicolas May 13 '16 at 23:54
• Thanks. So it's much simpler than I thought then. – Dean Young May 13 '16 at 23:57
• You are welcome. In each of the examples, the content is $1$ but the gcd of the values is greater than $1$. If you look at the plynomial $(x+1)(x+2)\cdot (x+n)$ the content is $1$ but the gcd of the values is $n!$. – André Nicolas May 13 '16 at 23:59

## 1 Answer

Let $f(X)\in\mathbb{Q}[X]$ be integer-valued (i.e., $f(k)\in\mathbb{Z}$ for all $k\in\mathbb{Z}$). If $f(X)$ is of degree $n$, then $f(X)=\sum_{i=0}^n\,A_i\,\binom{X}{i}$ for some $A_0,A_1,\ldots,A_n\in\mathbb{Z}$. If the modified content $\tilde{C}(f)$ of $f$ is defined to be the gcd of all the $A_i$'s, then $\tilde{C}(f)$ is precisely the gcd of all $f(k)$ for $k\in\mathbb{Z}$.

In Andre Nicolas's first example, $X^2+X=0\binom{X}{0}+2\binom{X}{1}+2\binom{X}{2}$ so that $\gcd(0,2,2)=2$ is the gcd of all $k^2+k$ with $k\in\mathbb{Z}$. For the second one, $X^3-X=0\binom{X}{0}+0\binom{X}{1}+6\binom{x}{2}+6\binom{X}{3}$ so that $\gcd(0,0,6,6)=6$ is the gcd of all $k^3-k$ with $k\in\mathbb{Z}$.

I believe that this is also true. Let $S$ be an infinite subset of $\mathbb{Z}$ such that, for every prime $p\in\mathbb{N}$, integer $r>0$, and $j\in\left\{0,1,2,\ldots,p^r-1\right\}$, there exists $s\in S$ such that $s\equiv j\pmod{p^r}$. Then, $\tilde{C}(f)$ is also the gcd of all $f(k)$ for $k\in S$.

Why do I need the ridiculous requirement on $S$? First, it is clear that $S$ should be infinite for the gcd to be established for every integer-valued polynomial in $\mathbb{Q}[X]$. Then, it follows that, for any $j\in\mathbb{Z}$, $\gcd(S-j)=1$, otherwise $f(X)=X-j$ is a counterexample. This implies that $\gcd(S-S)=1$. However, this is still not enough (originally, I thought $\gcd(S-S)=1$ would be sufficient as mentioned in some of the comments below). If there exist a prime $p\in\mathbb{N}$, an integer $r>0$, and $j\in\left\{0,1,2,\ldots,p^r-1\right\}$ such that $s\not\equiv j\pmod{p^r}$ for all $s\in S$, then we may assume that $j=p^r-1$ and consider $f(X)=\binom{X}{p^r-1}$. In this case, $\tilde{C}(f)=1$ but it is easily seen by Lucas's Theorem that $p$ divides $f(k)$ for all $k\in S$. Hence, $s\equiv j\pmod{p^r}$ must have a solution $s\in S$ in order to satisfy the condition that $\tilde{C}(f)$ is the gcd of $f(k)$ for $k\in S$.

• great ! and by induction it is easy showing that every polynomial of $\mathbb{Z}[X]$ can be decomposed in this form. the algorithm : find $A_n$ first, substract the polynomial $A_n {X \choose n}$, then find $A_{n-1}$, etc. – reuns May 14 '16 at 0:18
• (and I don't see why you start with $\mathbb{Q}[X]$ and not $\mathbb{Z}[X]$) – reuns May 14 '16 at 0:30
• I am allowing polynomials, for example, of the form $f(X)=\frac{X^p-X}{p}$, where $p\in\mathbb{N}$ is prime, which takes integer values for $X\in \mathbb{Z}$. – Batominovski May 14 '16 at 0:32
• right, I didn't notice those kind of weird polynomials – reuns May 14 '16 at 0:32
• and why do you consider the set of differences $a-b$ ? what is the prototypal example of such a set ? – reuns May 14 '16 at 0:34