Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Given the ring of polynomials $\mathbb{Z}_n[X]$, consider $$\mathbb{P}_n = \{a_0 +a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}| a_i \in \mathbb{Z}_n\},$$ i.e. $\mathbb{P}_n$ is the set of all polynomials in $\mathbb{Z}_n[X]$ with exponents in $\mathbb{Z}_n$.

So, $\mathbb{P}_2 = \{0,1,x,1+x\},$

$$\mathbb{P}_3 = \{0, x^2, 2x^2, x, x+x^2, x+2x^2, 2x, 2x+x^2, 2x+2x^2, 1, 1+x^2, 1+2x^2, 1+x \} \cup $$

$$ \{ 1+x+x^2, 1+x+2x^2, 1+2x, 1+2x+2x^2, 2, 2+x^2, 2+2x^2, 2+x, 2+x+x^2 \} \cup $$

$$ \{ 2+x+2x^2, 2+2x, 2+2x+x^2, 2+2x+2x^2\}$$

The above ordering of the elements is based on the coefficient coordinates pattern: $(0,0,0), (0,0,1),(0,0,2), (0,1,0), (0,1,1), (0,1,2), \cdots, (2,2,0), (2,2,1), (2,2,2).$

Clearly, $\mathbb{P}_n$ has $n^n$ elements. I am counting the number of polynomials in $\mathbb{P}_n$ that vanish in $\mathbb{Z}_n$. Let's denote the count for $\mathbb{P}_n$ by $r_n$ ($r$ loosely stands for 'reducible'). Then, $r_2 = 3, r_3 = 19, \cdots$ It is very early to guess the growth of $r_n$ or its primality but I would like to know if there is any theorem that would help to count or reduce the number of polynomials I should check.

Some work:

  1. Since $\mathbb{Z}_n \subset \mathbb{Z}_n[X]$, $r_n \leq n^n - (n-1)$. (there are $n-1$ nonzero elements)
  2. There are $(n-1)^{n-1}$ polynomials with zero constant term and there are $n-1$ polynomials of degree $1$ with nonzero constant term all of which vanish for some $x$ in $\mathbb{Z}_n$. Hence $(n-1)^{n-1} + (n-1) \leq r_n$. This is not a good bound as it is far less than $n^n$ for large $n$.
share|cite|improve this question

Let $n=p$ be a prime (otherwise I'm clueless). Let $q_k$ be the number of monic polynomials of deg $k$ having no root. The number of deg $m$ monic polynomials that split into linear factors is $C(p-1+k,k)$ (here $C(n,k)=n!/(k!(n-k)!)$). The number of all monic deg $n$ polys is $p^n$. Hence $$p^n=\sum_k C(p-1+k,k)q_{n-k}$$ (as any polynomial can be written as a product of those two types). Let $q(x)=\sum_{k=0}^{\infty}q_k x^k$. We get $$\sum p^n x^n=\sum_{k,m} C(p-1+k,k) x^k q_{m}x^m$$ i.e. $$1/(1-px)=(1-x)^{-p} q(x).$$ Hence $q(x)=(1-x)^p/(1-px)$. The number of all (nut just monic) polynomials of degree $\leq p-1$ having no root is therefore the coefficient of $x^{p-1}$ of $$(p-1)(1-x)^{p-1}/(1-px)$$ (expand $1/(1-px)$ to geometrical series to get a formula for the coefficient).

share|cite|improve this answer
Thank you very much. I am trying to understand the proof. – Chulumba Mar 27 '11 at 15: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.