How can I show $q^k$ does not divide ${{n}\choose{q}}$ when $q$ is a prime factor of $n$ and $k$ is the largest integer such that $q^k$ divides $n$?

Question

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.

Answer 1

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$.

Answer 2

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$