4
$\begingroup$

Today, I took this observation from my note book. I am looking the strategy to deal this statement. The difference between $\binom{n}{p}$ and $\left\lfloor\frac{n}{p}\right\rfloor\,$ is divisible by p for a positive integer n and p is prime with >1. Here $\binom{n}{p}$ is the number of ways one can choose p out of n elements and $\left\lfloor{x}\right\rfloor\,$ is the greatest integers not exceeding the real number x. The above one is I found from the following problem.

5 divides the difference between $\binom{n}{5}$and$\left\lfloor\frac{n}{5}\right\rfloor\,$

Numerically we can solve. I would like to learn how to solve or prove the above cited statement mathematically?

Thank you.

I got good reply from one of the MATH STACK USER. I studied as per his guidance about the LUCAS Theorem, I encounter the following facts with doubts and difficulties.

If we express the p (not prime) in terms of $q^x$ k where q and k are relatively primes with q is prime,. Then my example given above fails. Of course x and k are not equal to 1 simultaneously. With reference to the above fact, how we generalize the above fact mathematically? Now, my second doubt/question is, why to solve my statement by Lucas Theorem? If we can do the same by Wilson’s theorem? This is I am just guessing. I am not sure how far I am correct. Kindly discuss, if I am wrong/correct? If Lucas Theorem only will solve my statement, how to encounter the fgollowing fact from Lucas theorem? For a and q are positive integers and greater than 1, such that $\binom{na}{ma}$ $\equiv 3\ $$\binom{n}{m}$ (mod p) For every pair of integers n greater than equal to m greater than equal to 0 with a & q are powers of the same prime p ? I am so exited to encounter the above facts during my study on Lucas theorem to complete my statement given above. Kindly discus and thank you so much for every replier.

1 Answers 1

6

This is a very pretty instance of Lucas's Theorem: http://en.wikipedia.org/wiki/Lucas%27_theorem

If you write out $n$ and $p$ in base $p$ you'll see that only the "tens" digit of $n$ contributes to the product, and this digit is equivalent to $\lfloor n/p \rfloor$ modulo $p$.

Here is a more elementary argument by induction: notice that $\lfloor n/p \rfloor - \lfloor (n-1)/p \rfloor$ is either $0$ or $1$ depending on whether $n$ is a multiple of $p$.

Therefore we want to show that the remainder of $\binom{n}{p}$ is exactly the same as $\binom{n-1}{p}$ if $n$ is not divisible by $p$, and that it is exactly $1$ higher in the case that $n$ is divisible by $p$. Expand out:

$\binom{n}{p}-\binom{n-1}{p} = \binom{n-1}{p-1} = \frac{(n-1)(n-2)\cdots (n-p+1)}{(p-1)(p-2)\cdots1}.$

If $n$ is not divisible by $p$, then the numerator has one term divisible by $p$, but the denominator doesn't, so $\binom{n}{p}-\binom{n-1}{p}$ is a multiple of $p$. This proves half of what we wanted to show.

If $n$ is divisible by $p$, then both the numerator and denominator are congruent to $(p-1)!$ mod $p$, so they cancel out to exactly $1$. This proves the other half.

  • 0
    ! kindl$y$ answer m$y$ new post.2012-08-07