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

If $n$ is divisible by $m$, why is it the case that the $m$th primitive roots of unity are also roots of $\binom{n}{k}_q$ if and only if $m$ does not divide $k$?

I'm viewing $\binom{n}{k}_q$ as a polynomial in $q$, but I don't see why the divisibility relations gives this condition of the primitive roots being roots of the polynomial. Thanks.

share|cite|improve this question
up vote 4 down vote accepted

The complex $m$th roots of unity are roots of $x^m-1$, and form a regular $m$-gon on the unit circle in the complex plane with one vertex at $1$ (for $0 < m \in \mathbb{N}$). Primitive $m$th roots of unity are roots of the irreducible polynomial factors of $x^m-1$, called cyclotomic polynomials $\phi_d(x)$ and satisfying $$ x^m-1 = \prod_{0<d|m}\phi_d(x)\;, $$ which recursively defines them: $\phi_1(x)=x-1$, $\phi_2(x)=x+1$, $\phi_3(x)=x^2+x+1$, $\phi_4(x)=x^2+1$, $\phi_5(x)=x^4+x^3+x^2+x+1$, $\phi_6(x)=x^2-x+1$, etc. In particular, $\phi_d(x)$ has degree $\phi(d)$ and, as stated, its roots are precisely the primitive $m$th roots of unity.

(The polynomial factorization formula above can also be seen as providing a partition of the full set of $m$th roots of unity, which forms a multiplicative subgroup of $\mathbb{C}$ of order $m$, into subsets based on their order -- for which minimal $d$ do they satisfy $x^d=1$ -- comprised of $\phi(d)$ generators $\{e^{2\pi ij/d}|(j,d)=1\}$ of the subgroup of order $d$ for each positive divisor $d$ of $n$. It is worthwhile once to draw some examples of these partitions.)

Now since $$ [m]_q=\frac{q^m-1}{q-1}=\prod_{1<d|m}\phi_d(q)\;, $$ its roots are precisely the nontrivial $m$th roots of unity for $m>1$ (all primitive $d$th roots of unity where $d>1$ and $d \mid m$). So a root of $$ \binom{n}{k}_q =\prod_{j=1}^{k}\frac{[n-j+1]_q}{[j]_q} =\prod_{1<d \leq n}\phi_d(q)^{e_d} \qquad\text{for some }e_d\in\mathbb{Z} $$ must be a root of the numerator more times than of the denominator (counting multiplicity). It is actually pretty elementary to calculate the $e_d$ (no prime factorization is needed). We simply observe that we need to add one for each time that $d$ divides a number from $\{n, n-1, \dots, n-k+1\}$ and subtract one for each time it divides a number from $\{k, k-1, \dots, 1\}$. This can be expressed using the floor function, by similar reasoning as is used to count powers in the prime factorization of a factorial: $$ e_d =\left[\frac{n}{d}\right] -\left[\frac{n-k}{d}\right] -\left[\frac{k}{d}\right] $$ Observing that the each floor function is only taking away the residue or remainder modulo $d$ from the numerator of the fraction it contains, and grouping the two negative terms, we can see that $e_d\geq0$ is in fact positive iff $k$ has smaller (nonnegative) residue than $n$ modulo $d$. To see this, let $n=ud+r$ and $k=vd+s$ for $0 \leq r,s < d$ and note that $$ e_d = \left[u+\frac{r}{d}\right] -\left[u-v+\frac{r-s}{d}\right] -\left[v+\frac{s}{d}\right] =-\left[\frac{r-s}{d}\right] =\left\{\begin{matrix} 1 & r < s \\ 0 & r \geq s \end{matrix} \right. $$ since the floor function rounds down to $-\infty$ and $-d<r-s<d$.

In particular for $m=d \mid n$, we can see that the primitive $m$th roots of unity are roots of $\binom{n}{k}_q$ iff $$ \phi_m(q) \mid \binom{n}{k}_q \iff e_m = 1 \iff m \nmid{k} \iff m \nmid n-k \;. $$

share|cite|improve this answer
Thanks bgins. Do you mind explaining further the case when $m\mid k$ if you have the time? – Shea Dec 17 '11 at 7:13
Wow, amazing! Thanks again bgins. – Shea Dec 17 '11 at 17:33

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.