pn choose pk and n choose k are congruent mod p

Show that \binom{pn}{pk} \equiv \binom{n}{k} mod p.


Note that (1+x)^{pn} = \sum_{t=0}^{pn} \binom{pn}{t}x^t by the binomial theorem. The coefficient of x^{pk} is \binom{pn}{pk}. Over \mathbb{F}_p, we have (1+x)^{pn} = ((1+x)^p)^n = (1+x^p)^n = \sum_{t=0}^n \binom{n}{t}(x^p)^t, and now the coefficient of x^{pk} is \binom{n}{k}. In particular, we have \binom{pn}{pk} \equiv \binom{n}{k} mod p.

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: