# Number Theory and combinatorial

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 Answer 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. - ! can you give little bit more clarification? – BMSA Aug 4 '12 at 5:12 Can you explain the same please.. – BMSA Aug 4 '12 at 6:28 @BMSA The point of Lucas's theorem is it is possible to compute the remainder of any binomial coefficient modulo$p$by just looking at the digits of both numbers in base$p$. In base$p$, the bottom number$p\$ is just "10". –  Erick Wong Aug 4 '12 at 6:41
! Thanks a lot. Let me work on this and I will post on tomorrow if I had any doubts and difficulties. Once again thank you so much –  BMSA Aug 4 '12 at 15:39
! I am very much inspired on your reply and I, myself more involved and I studied the Lucas theorem and then I found some facts. Please see my main post, which I just edited. Now, I am so excitedly waiting your reply on my new edited post. Kindly answer.. –  BMSA Aug 5 '12 at 14:14