In this answer: https://math.stackexchange.com/a/652909

Ted equates mod $p$ the coefficients of $$\sum_{n=0}^{pa} \binom{pa}{n} x^n$$ and $$\sum_{i=0}^{a} \binom{a}{i} x^{pi}$$ to get that $$\binom{pa}{pb} \equiv \binom{a}{b} \mod p$$

But one of the summations has $pa$ terms, and the other summation has $a$ terms, so what does it mean to equate the coefficients mod $p$? Shouldn't it be that several different elements of $\sum \binom{pa}{n} x^n$ will collapse into one element of $\sum \binom{a}{i} x^{pi}$ since $x^{pb} \equiv x^{p^kb} \mod p$ so that after modding by $p$, the coefficients of each $x^{p^kb}$ will contribute to the coefficient of $x^{pb}$ i.e. $$\binom{pa}{b} + \binom{pa}{pb} + \binom{pa}{p^2b} \dots \equiv \binom{a}{b} \mod p$$

Is Ted's proof complete? And if not, what would a complete proof look like?


In the original post, this was not my proof, but clark's. I merely edited some typos in it. But I can address your concerns.

First, you cannot write something like $x^{pb} \equiv x^{p^k b} \mod{p}$. Not sure how you got that, so I'll just say this: When working with polynomials mod $p$, the exponents do not reduce modulo $p$. The exponents are ordinary (nonnegative) integers. You can only equate powers that are exactly equal as integers (you cannot reduce them modulo $p$). Only the coefficients can be reduced modulo $p$.

So what do we get when we equate coefficients of equal powers of $x$? On the right side (the second sum in your question above), the term $i=b$ gives $\binom{a}{b}$ as the coefficient of $x^{pb}$. This corresponds to the term $n=pb$ in the first sum, which has coefficient $\binom{pa}{pb}$. These can be equated modulo $p$, giving $\binom{pa}{pb} \equiv \binom{a}{b} \mod p$.

To address your concern that the first sum has $pa$ terms and the second sum only $a$ terms, what's happening is that most of the terms in the first sum are 0. If $n$ is not divisible by $p$, then $\binom{pa}{n}$ is divisible by $p$ and therefore becomes 0 when working modulo $p$. The argument in the previous paragraph is a proof of this (since the second sum obviously has no terms that are not multiples of $p$), but you can also prove it directly.


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.