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
    ! can you give little bit more clarification?2012-08-04
  • 0
    Can you explain the same please..2012-08-04
  • 1
    @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".2012-08-04
  • 0
    ! 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 much2012-08-04
  • 0
    ! 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..2012-08-05
  • 0
    @BMSA I am having trouble understanding any part of your question. Maybe you should post it as a new question and try to clarify exactly what you are asking.2012-08-06
  • 0
    ! Sir, as per your guidance, I posted question very clearly in the new post.Please look at the new post titled Lucas theorem and facts. Please.. kindly answer.2012-08-06
  • 0
    ! kindly answer my new post.2012-08-07