Kummer’s Theorem on binomial coefficients

The Kummer’s theorem is a beautiful result concerning the divisibility of binomial coefficients(and so it is in a sense a connection between counting and number theory!). Binomial coefficients pop up everywhere. This may be because counting is one of those operations that human instinct can so very easily grasp.

Though a binomial coefficient can have different meanings in different contexts, one of the basic meanings it has is the following. Suppose you have 10 friends and you want to call 7 of them for a party, then the number of ways to send in these(much coveted?) invitations is precisely \binom{10}{7} . They are many surprising properties of the  binomial coefficients (for example, the Hockey-stick theorem is really pretty).

The first time I saw the Kummer’s theorem, I was bewildered. The theorem states that :

Given a prime number p and positive integers n \geq m \geq 0 , the highest power of p that divides \binom{n}{m} is equal to the number of “carries” that occur when m is addded to n-m in base p.

They were two things in the theorem which at first didn’t make sense. The first of these was that how is the number of “carries” encountered while adding two numbers related to divisibility?  Next, how does “base p” come into the picture? I started with binary first. It required some experimentation and then it started making sense. The algorithm for converting a given decimal number to binary held the key.

After I had proved the theorem for the case when p was 2, I tried to generalize the theorem for all primes. However, I soon realized that the generalization of my proof to include all primes would not be possible. This was simply because 2 has only two elements in its residue class, i.e., any number divided by 2 leaves either 0 or 1 as the remainder. On the other hand, other primes have more elements in their residue classes. It will become clear from my proof that why this fact affects the generalization of my proof.

Below is my proof for the case when p =2.

screen-shot-2016-11-18-at-3-24-51-pm
screen-shot-2016-11-18-at-3-26-54-pm

Screen Shot 2016-11-18 at 3.32.07 PM.png

 

Advertisements

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