The distribution of the binomial coefficients modulo \(p\) (Q1187808)

Let \(a\) be a primitive root modulo prime \(p\). The authors show that if \(R_ n(X)=\sum_{i=0}^{p-2} \#\{k\): \(0\leq k\leq n\), \({n \choose k} \equiv a^ i\mod p\}X^ i\) then \(R_ n(X)\equiv \prod_{j=0}^{p-1} R_ j(X)^{t_ j} \mod X^{p-1}-1\), where \(t_ j\) is the number of occurrences of the digit \(j\) in the base \(p\) expansion of \(n\). This makes it easy to decide, for instance, how the binomial coefficients \({1,000,000 \choose k}\) are distributed modulo 7. The authors use their result to show that there are an equal number of quadratic residues and non-residues modulo \(p\), amongst the binomial coefficients \({n \choose k}\), as \(k\) varies, if and only if there are amongst the \({m \choose k}\), for some digit \(m\) of \(n\) when written in base \(p\).