### 38th Putnam 1977

**Problem A5**

p is a prime and m ≥ n are non-negative integers. Show that (pm)C(pn) = mCn (mod p), where mCn is the binomial coefficient.

**Solution**

*Easy.*

Let f(n) be the highest power of p dividing n. The multiples of p in (mp)! are mp, (m-1)p, ... , 2p, p. Hence f( (mp)! ) = p^{m} f(m!). Similarly, f( (np)! ) = p^{n} f(n!) and f( ((m-n)p)! ) = p^{m-n} f( (m-n)! ). Hence f( mCn ) = f( (mp)C(np) ).

38th Putnam 1977

© John Scholes

jscholes@kalva.demon.co.uk

30 Nov 1999