Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 6 down vote accepted

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.

share|improve this answer
! 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
show 3 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.