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?

Does the theorem assume that we're considering irreducibility mod $q$? Does this change anything? Also, what does "e" on p. 200 (after Theorem 4.1) refers to? There was no mention of it earlier in the paper and I don't see why it should be the constant $e$.

Note: This is cross-posted from math.SE (and slightly edited): https://math.stackexchange.com/questions/459173/if-fa-1-ldots-a-k-0-whenever-a-1-ldots-a-k-are-integers-such-that-fx

  • $\begingroup$ He means take primes $p,q$, polynomials $f_p,f_q$ such that $f_p$ is arbitrary modulo $p$ and $f_q$ is irreducible modulo $q$, then find $f$ which is $f_p \pmod p, f_q \pmod q$ by CRT. Then $f$ is irreducible (a factorization of $f$ gives a factorization of $f_q$) so $F=0$ and thus $F$ vanishes identically $\pmod p$ and (as $p$ is arbitrary) $F$ vanishes identically. This should have been answered in MSE... $\endgroup$ Aug 7, 2013 at 3:14
  • $\begingroup$ Thanks for the clarification! I thought so too, but there weren't any answers on MSE even a while after the question was posted. $\endgroup$
    – modnar
    Aug 7, 2013 at 3:42

1 Answer 1


Pick two distinct primes $p$ and $q$. Now choose any monic irreducible polynomial $f_q$ of degree $k$ modulo $q$ (i.e. in ${\bf F}_q$); these exist. Also choose $a_1, \dots, a_k$ arbitrary mod $p$ and let $f_p = x^k - a_1 x^{k-1} + \dots + (-1)^k a_k$. Then by CRT, there is a common lift $f(x) \in {\bf Z}[x]$ which agrees with $f_p$ mod $p$ and with $f_q$ mod $q$. Since $f_q$ is irred, so is $f$. So $F(a_1, \dots, a_k) = 0$ for every such choice, and so $F \equiv 0 \pmod p$ etc.

Aso for your second question, I'm not sure, but it looks like you pick $h$ to be one of the $h_i$ from equation (4.3) and then $e$ is the associated $e_i$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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