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?

  • 2
    $\begingroup$ What do you (or what does the book) mean by "for some $p$ irreducible mod $q$"? $\endgroup$
    – Eric Auld
    Aug 4, 2013 at 0:19
  • $\begingroup$ It might help if we could see the source of the proof. $\endgroup$ Aug 4, 2013 at 0:29
  • $\begingroup$ @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". $\endgroup$
    – modnar
    Aug 4, 2013 at 1:59
  • $\begingroup$ 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. $\endgroup$
    – user88908
    Aug 4, 2013 at 5:32

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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