# If $F(a_1,\ldots,a_k)=0$ whenever $a_1,\ldots,a_k$ are integers such that $f(x)=x^k-a_1x^{k-1}-\cdots-a_k$ is irreducible, then $F\equiv0$

I'm trying to understand a proof of the following theorem (from section II of Hall's paper An Isomorphism Between Linear Recurring Sequences and Algebraic Rings):

If $F(a_1, \ldots, a_k)$ is a polynomial in $a_1, \ldots, a_k$ with integer coefficients and $F = 0$ whenever $a_1, \ldots, a_k$ are integers such that $f(x) = x^k - a_1x^{k - 1} - \cdots - a_k$ is irreducible, then $F \equiv 0$.

The proof provided was that taking $f(x)$ modulo $p$ for some $p$ (prime?) irreducible mod $q$, we find that $F = 0$ (modulo $p$). Since $F \equiv 0$ (mod $p$) for any appropriate $a_1, \ldots, a_k$ for arbitrary $p$, we have that $F \equiv 0$.

I'm confused about the first part of the proof because irreducibility over integers doesn't imply irreducibility modulo $p$ for any prime $p$. Also, does it make sense to consider $q$ to be an arbitrary positive integer?

EDIT: Does the theorem assume that we're considering irreducibility mod $q$? Does this change anything?

• What do you (or what does the book) mean by "for some $p$ irreducible mod $q$"? Aug 4, 2013 at 0:19
• It might help if we could see the source of the proof. Aug 4, 2013 at 0:29
• @EricAuld The "irreducible mod $q$" describes $f$ considered mod $p$. The proof is contained in section II of Hall's paper "An Isomorphism Between Linear Recurring Sequences and Algebraic Rings". Aug 4, 2013 at 1:59
• This is just a comment . I hope it could help. Consider prime p, let the constant is p, and the other coefficients are multiple of p, then by Eisenstein criterion, f is irreducible, so F is zero on such kinds of coefficients. And we can switch the prime p arbitrary, see if those informations imply theresult. Aug 4, 2013 at 5:32

Let $$F$$ be as in the theorem.
Let $$(z_1,\ldots, z_k)\in\Bbb Z^k$$ be arbitrary.
Let $$p,q$$ be any two distinct primes. It is well-known that there exist irreducible polynomials $$\in\Bbb F_q[X]$$ of arbitrary degree, i.e., there is $$g(X)=x^k-b_1X^{k-1}-\ldots -b_k\in\Bbb Z[X]$$ such that $$g(X)\bmod q\in \Bbb F_q[X]$$ is irreducible. By the Chinese Remainder Theorem, we find $$a_1,\ldots, a_k\in\Bbb Z$$ such that $$\tag1a_i\equiv z_i\pmod p$$ and $$\tag2a_i\equiv b_i\pmod q.$$ From the $$(1)$$, we conclude that $$F(z_1,\ldots, z_k)\equiv F(a_1,\ldots, a_k)\pmod p$$, whereas $$(2)$$ tells us that $$X^k-a_1X^{k-1}-\ldots -a_k$$ is irreducible in $$\Bbb Z[X]$$. Therefore, $$F(a_1,\ldots, a_k)=0$$ and so $$F(z_1,\ldots, z_k)\equiv 0\pmod p.$$ As $$p$$ was an arbitrary prime, it follows that $$F(z_1,\ldots, z_k)=0.$$ As this holds for all $$z_1,\ldots ,z_k\in\Bbb Z$$, we ultimately conclude that $$F$$ is the zero polynomial.