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)! ) = pm f(m!). Similarly, f( (np)! ) = pn f(n!) and f( ((m-n)p)! ) = pm-n f( (m-n)! ). Hence f( mCn ) = f( (mp)C(np) ).
© John Scholes
jscholes@kalva.demon.co.uk
30 Nov 1999