Prove that if $p$ is a prime number, then p divides $\binom{n}{p} − \lfloor\frac{n}{p}\rfloor$, for all $n > p$.
(where the $\lfloor\frac{n}{p}\rfloor$ denotes the greatest integer less than or equal to $\frac np $, for any real number $\frac np $.)
Does this result generalise to a result about $p^{r}$ instead of $p$?, where $r = \frac np $
My only thought on approaching this is assuming that it is true and proving my contradiction, but am unsure on how to use the floor function as it can give the same result for many numbers, for example $4.1,4.2,4.4,4.4$ all output $4$.
Any help would be appreciated.
Answer
Lucas' theorem does the job. Write $n=\sum\limits_0^q p^kn_k$ where $n_k$'s are the digits in the base $p$-representation of $n$. Since $n\gt p$, we must have $q\geq 1$. Then, by Lucas' theorem,
$$\binom np\equiv\binom{n_1}1\binom{n_0}0\equiv n_1\pmod p$$
Also, $$\lfloor n/p\rfloor=\lfloor(\sum_0^q p^kn_k)/p\rfloor=\lfloor n_0/p\rfloor+n_1+p(\cdots)=0+n_1+p(\cdots)\equiv n_1\pmod p$$
Thus, $$\binom np\equiv\left\lfloor\frac np\right\rfloor\pmod p$$
I'm not sure if an analogous argument would work for modulo prime powers of $p$ because Lucas' theorem modulo prime powers is a bit different from the usual statement, but here's a (sort of) generalization:
$$\binom n{p^k}\equiv\left\lfloor\frac n{p^k}\right\rfloor\equiv n_k\pmod p$$
where $k$ goes from $1$ to $q$ (also the trivial case of $k=0$ holds)
No comments:
Post a Comment