Suppose that $n \in \mathbb{N}$ is composite and has a prime factor $q$. If $k \in \mathbb{Z}$ is the greatest number for which $q^k$ divides $n$, how can I show that $q^k$ does not divide ${{n}\choose{q}}$?

Clearly, since $$ {{n}\choose{q}} = \frac{n!}{(n-q)!q!} = \frac{n(n-1)(n-2) \dots (n-q+1)}{q!} $$ So it suffices to show that, no element of the set $$ \left\{ n-1, n-2, \dots, n-q+1 \right\} $$ is divisible by $q$, which is clearly true, but I am unsure of how to show this rigourously.


If $q$ divides $n$, then one can conclude that:

$n$ and $n-q$ are consecutive multiples of $q$,

so there is no other multiple between $n-1$ and $n-q+1$, so none of these numbers are divisible by $q$. As you have mentioned none of these elements $$ \left\{ n-1, n-2, \dots, n-q+1 \right\} $$ are divisible by $q$.

Now suppose that $q$ is a prime number, then the numerator of $$ {{n}\choose{q}} = \frac{n!}{(n-q)!q!} = \frac{n(n-1)(n-2) \dots (n-q+1)}{q!} $$ is divisible by $q^k$, but not by $q^{k+1}$. Also the denominator is divisible by $q$, so one can conclude that ${{n}\choose{q}}$ is not divisible by $q^k$.


We can also use Kummer's Theorem (https://en.m.wikipedia.org/wiki/Kummer%27s_theorem) since it was designed for this kind of problems

Is it possible that when adding n-q and q we get k carry-overs?

First we must notice a couple of things

1) Since $q|n$, the last digit of $n$ in $q$'s expansion MUST be 0 (can see why?)

2)Notice that $q = (10)_q$

So now let's add $(n-q)$ + $(q)$ and use Kummer's Theorem. Since $q = (10)_q$, we can only have carryovers at the second position (from right to left) onwards to the the left

If we were to have k carry-overs, we'd then have them at the second position (for $q^1$), third position (for $q^2$) all the way to the $k+1$th position (for $q^k$)

But getting a carry in all these positions must mean that $n = Aq^{k + 1+r}+ Bq^{k+r} + \dots + Cq^{k+1}$

This means that n is now a number which, when written in base q, has its last nonzero digit at the position for $q^{k+1}$. From this position it's all zeros to the right

This means that n must be divisible by $q^{k+1}$. But this is an absurd that contradicts the fact that q^k is the largest power of q that divides n

This absurd was caused by our assumption that we could have k carry-overs when adding $q + (n-q)$

Since it is impossible for this happen, we now know that the $q$-adic valuation of ${n \choose q}$ must be strictly less than $k$


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.