Proving ${n choose p} equiv Bigl[frac{n}{p}Bigr] (text{mod} p)$












17












$begingroup$


This is an exercise from Apostol, which i have been struggling for a while.



Given a prime $p$, how does one show that $${n choose p} equiv biggl[frac{n}{p}biggr] (text{mod} p)$$ Note that $Bigl[frac{n}{p}Bigr]$ denotes the integral part of $frac{n}{p}$.



I would also like to know as to how does one try to solve this problem. Well, what we need is to show is whenever one divides ${n choose p}$ by a prime $p$ the remainder is the integral part of $frac{n}{p}$.



Now, $${ n choose p} = frac{n!}{p! cdot (n-p)!}$$ Now $n!$ can be written as $$n!= n cdot (n-1) cdot (n-2) cdots (n-p) cdots 2 cdot 1$$



But i am really struggling in getting the integral part.










share|cite|improve this question









$endgroup$












  • $begingroup$
    I think that this is trivialized with Lucas's theorem.
    $endgroup$
    – Mayank Pandey
    Oct 17 '13 at 2:41










  • $begingroup$
    Here's a cute proof for the case $p=2$: The sign of $begin{pmatrix}n&cdots&2&1end{pmatrix}$ is, on the one hand, $lfloorfrac n2rfloor$: change $1$ with $n$, $2$ with $n-1$, ... On the other hand we can first bring the $1$ in front, step by step; then bring the $2$ to the 2nd place, ... This takes $1+cdots+n-1=binom n2$ transpositions, so $lfloorfrac n2rfloorequivbinom n2pmod2$. I wonder if there's a way to generalise this to all $p$.
    $endgroup$
    – nbarto
    Dec 20 '15 at 19:09
















17












$begingroup$


This is an exercise from Apostol, which i have been struggling for a while.



Given a prime $p$, how does one show that $${n choose p} equiv biggl[frac{n}{p}biggr] (text{mod} p)$$ Note that $Bigl[frac{n}{p}Bigr]$ denotes the integral part of $frac{n}{p}$.



I would also like to know as to how does one try to solve this problem. Well, what we need is to show is whenever one divides ${n choose p}$ by a prime $p$ the remainder is the integral part of $frac{n}{p}$.



Now, $${ n choose p} = frac{n!}{p! cdot (n-p)!}$$ Now $n!$ can be written as $$n!= n cdot (n-1) cdot (n-2) cdots (n-p) cdots 2 cdot 1$$



But i am really struggling in getting the integral part.










share|cite|improve this question









$endgroup$












  • $begingroup$
    I think that this is trivialized with Lucas's theorem.
    $endgroup$
    – Mayank Pandey
    Oct 17 '13 at 2:41










  • $begingroup$
    Here's a cute proof for the case $p=2$: The sign of $begin{pmatrix}n&cdots&2&1end{pmatrix}$ is, on the one hand, $lfloorfrac n2rfloor$: change $1$ with $n$, $2$ with $n-1$, ... On the other hand we can first bring the $1$ in front, step by step; then bring the $2$ to the 2nd place, ... This takes $1+cdots+n-1=binom n2$ transpositions, so $lfloorfrac n2rfloorequivbinom n2pmod2$. I wonder if there's a way to generalise this to all $p$.
    $endgroup$
    – nbarto
    Dec 20 '15 at 19:09














17












17








17


18



$begingroup$


This is an exercise from Apostol, which i have been struggling for a while.



Given a prime $p$, how does one show that $${n choose p} equiv biggl[frac{n}{p}biggr] (text{mod} p)$$ Note that $Bigl[frac{n}{p}Bigr]$ denotes the integral part of $frac{n}{p}$.



I would also like to know as to how does one try to solve this problem. Well, what we need is to show is whenever one divides ${n choose p}$ by a prime $p$ the remainder is the integral part of $frac{n}{p}$.



Now, $${ n choose p} = frac{n!}{p! cdot (n-p)!}$$ Now $n!$ can be written as $$n!= n cdot (n-1) cdot (n-2) cdots (n-p) cdots 2 cdot 1$$



But i am really struggling in getting the integral part.










share|cite|improve this question









$endgroup$




This is an exercise from Apostol, which i have been struggling for a while.



Given a prime $p$, how does one show that $${n choose p} equiv biggl[frac{n}{p}biggr] (text{mod} p)$$ Note that $Bigl[frac{n}{p}Bigr]$ denotes the integral part of $frac{n}{p}$.



I would also like to know as to how does one try to solve this problem. Well, what we need is to show is whenever one divides ${n choose p}$ by a prime $p$ the remainder is the integral part of $frac{n}{p}$.



Now, $${ n choose p} = frac{n!}{p! cdot (n-p)!}$$ Now $n!$ can be written as $$n!= n cdot (n-1) cdot (n-2) cdots (n-p) cdots 2 cdot 1$$



But i am really struggling in getting the integral part.







number-theory






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Oct 1 '10 at 11:37







anonymous



















  • $begingroup$
    I think that this is trivialized with Lucas's theorem.
    $endgroup$
    – Mayank Pandey
    Oct 17 '13 at 2:41










  • $begingroup$
    Here's a cute proof for the case $p=2$: The sign of $begin{pmatrix}n&cdots&2&1end{pmatrix}$ is, on the one hand, $lfloorfrac n2rfloor$: change $1$ with $n$, $2$ with $n-1$, ... On the other hand we can first bring the $1$ in front, step by step; then bring the $2$ to the 2nd place, ... This takes $1+cdots+n-1=binom n2$ transpositions, so $lfloorfrac n2rfloorequivbinom n2pmod2$. I wonder if there's a way to generalise this to all $p$.
    $endgroup$
    – nbarto
    Dec 20 '15 at 19:09


















  • $begingroup$
    I think that this is trivialized with Lucas's theorem.
    $endgroup$
    – Mayank Pandey
    Oct 17 '13 at 2:41










  • $begingroup$
    Here's a cute proof for the case $p=2$: The sign of $begin{pmatrix}n&cdots&2&1end{pmatrix}$ is, on the one hand, $lfloorfrac n2rfloor$: change $1$ with $n$, $2$ with $n-1$, ... On the other hand we can first bring the $1$ in front, step by step; then bring the $2$ to the 2nd place, ... This takes $1+cdots+n-1=binom n2$ transpositions, so $lfloorfrac n2rfloorequivbinom n2pmod2$. I wonder if there's a way to generalise this to all $p$.
    $endgroup$
    – nbarto
    Dec 20 '15 at 19:09
















$begingroup$
I think that this is trivialized with Lucas's theorem.
$endgroup$
– Mayank Pandey
Oct 17 '13 at 2:41




$begingroup$
I think that this is trivialized with Lucas's theorem.
$endgroup$
– Mayank Pandey
Oct 17 '13 at 2:41












$begingroup$
Here's a cute proof for the case $p=2$: The sign of $begin{pmatrix}n&cdots&2&1end{pmatrix}$ is, on the one hand, $lfloorfrac n2rfloor$: change $1$ with $n$, $2$ with $n-1$, ... On the other hand we can first bring the $1$ in front, step by step; then bring the $2$ to the 2nd place, ... This takes $1+cdots+n-1=binom n2$ transpositions, so $lfloorfrac n2rfloorequivbinom n2pmod2$. I wonder if there's a way to generalise this to all $p$.
$endgroup$
– nbarto
Dec 20 '15 at 19:09




$begingroup$
Here's a cute proof for the case $p=2$: The sign of $begin{pmatrix}n&cdots&2&1end{pmatrix}$ is, on the one hand, $lfloorfrac n2rfloor$: change $1$ with $n$, $2$ with $n-1$, ... On the other hand we can first bring the $1$ in front, step by step; then bring the $2$ to the 2nd place, ... This takes $1+cdots+n-1=binom n2$ transpositions, so $lfloorfrac n2rfloorequivbinom n2pmod2$. I wonder if there's a way to generalise this to all $p$.
$endgroup$
– nbarto
Dec 20 '15 at 19:09










7 Answers
7






active

oldest

votes


















17












$begingroup$

Hint $ $ If $rm nequiv j : (mod p): $ and $rm: bigl[frac{n}{p}bigr] = k, : $ then pairing factors so that top $equiv$ bottom $rm:(mod p):$ in the binomial coefficient fractions below makes the result obvious. For example



$${17choose 7} = frac{17}3 frac{16}2 frac{15}1 color{#c00}{frac{14}7}frac{13}6frac{12}5frac{11}4,equiv, color{#c00}2, =, leftlfloorfrac{17}7rightrfloorpmod 7qquadqquad $$



since all of the fractions with bottom $rmne p,$ are $,rmequiv 1pmod p,$ by top $equiv$ bottom, and the red term with the bottom = $rm ,p = 7,$ is just $rm,color{#c00}{kp/p = k}.,$ Generally we have



$$begin{eqnarray}rm {n choose p} &=&rm frac{n:(n-1):cdots:(n-p+1)}{p:(p-1):cdots: 1} \
\
&=& rm frac{n}{j} frac{n-1}{j-1}cdotsfrac{kp+1}{1} color{#c00}{frac{kp}p} frac{kp-1}{p-1}:cdotsfrac{n-p+2}{j+2} frac{n-p+1}{j+1}end{eqnarray}$$



This is a very special case of much more general arithmetical results on binomial coefficients. For example, see Andrew Granville's very interesting survey The Arithmetic Properties of Binomial Coefficients



Remark The above proof is a special case of a very simple purely arithmetical proof that I devised to show that binomial coefficients are integral. Namely, the same idea of exploiting the innate symmetry by aligning the numerators and denominators $rm:(mod p):$ extends to yield a simple algorithm that, given a binomial coefficient and a prime $rm p$, rewrites the binomial coefficient as a product of fractions whose denominators are all coprime to $rm p$. This implies that no prime divides the lowest-terms denominator, so that we may therefore conclude that the binomial coefficient is integral. For an example and further discussion see my post here.






share|cite|improve this answer











$endgroup$





















    9












    $begingroup$

    A useful result in such problems is Lucas's Theorem which states that



    If $p$ is a prime and if $a = sum_{i=0}^{k} a_{i} p^{i}, 0 le a_i < p $ i.e. the $a_i$ are digits of $a$ in base $p$ and similarly $b = sum_{i=0}^{k} b_{i}p^{i}$ (pad with zeroes if required) then



    $${a choose b} = prod_{i=0}^{k} {a_i choose b_i} mod p$$



    In our case $n=a$ and $b=p$. Since $b = p$ we have $b_1 = 1$ and rest of the $b_i = 0$.



    Thus



    $${a choose p} = {a_1 choose 1} = a_1 mod p$$



    It is easy to see that $a_1 = [frac{a}{p}] mod p$.






    share|cite|improve this answer









    $endgroup$





















      8












      $begingroup$

      Here's another way to look at it. Suppose $n=kp+j,$ for $0 le j le p-1.$ Then



      $$ (p-1)! {n choose p} = frac{n(n-1) cdots (n-p+1)}{p} = left( {n-j over p} right)
      prod_{i=0,ine j }^{p-1} (n-i)$$
      $$ equiv k(p-1)! (textrm{ mod } p). $$
      Since the product runs through a complete set of non-zero residues mod p.






      share|cite|improve this answer











      $endgroup$













      • $begingroup$
        @Moron Thanks, fixed.
        $endgroup$
        – Derek Jennings
        Oct 1 '10 at 17:40










      • $begingroup$
        That's equivalent to what I wrote.
        $endgroup$
        – Bill Dubuque
        Oct 1 '10 at 17:50






      • 7




        $begingroup$
        @Bill I did not copy your proof and I resent the suggestion.
        $endgroup$
        – Derek Jennings
        Oct 1 '10 at 18:10






      • 1




        $begingroup$
        @Bill. No problem. I used my approach as I recalled that my LHS was sometimes given as a hint. See for example problem 22 on page 51 of tar.hu/gergo73/nathanson.pdf . Anyway, I'm not into polemic, so I've just upvoted your answer.
        $endgroup$
        – Derek Jennings
        Oct 1 '10 at 20:40






      • 1




        $begingroup$
        @Derek: Thanks for the link. Initially I misunderstood and thought that you explicitly reformulated my proof because you thought there was some advantage to doing so (this happens occasionally here, usually due to my expository gaps, e.g. see math.stackexchange.com/questions/4150). Hopefully with my remark and the link you can see my motivation for presenting it in that form. Apologies for the misunderstanding.
        $endgroup$
        – Bill Dubuque
        Oct 1 '10 at 21:06



















      5












      $begingroup$

      The binomial theorem together with the identity $(x+y)^p = x^p + y^p mod p$ is useful for this type of problem.



      Here we want the the $x^p$ coefficient of $(1+x)^{Ap+B} = (1+x^p)^A (1+x)^B = (1 + Ax^p + dots)(1+X)^B$ where $0 leq B < p$. This coefficient comes only from multiplication of $(Ax^p)$ by $(1)$. So the result mod p is $A$.



      Another solution is to use combinatorics. Partition the set of integers from 1 to $n$ into $A$ blocks of size $p$ and a (perhaps empty) remainder of size $B$, as above. Any subset is either a complete block or it contains a proper nonempty subset of at least one block. Rotating the elements in the first partially filled block organizes the $binom{n}{p}$ p-subsets into collections of size $p$, plus a "remainder" consisting of complete $p$-blocks, and there are $A$ of the those.






      share|cite|improve this answer









      $endgroup$













      • $begingroup$
        REMARK The above generating function approach is mentioned in section 6 of the Granville survey that I mentioned, where he credits its application to Lucas's theorem to Fine (1947). See my other posts here for a sketch of the simple proof (from one of my old sci.math posts).
        $endgroup$
        – Bill Dubuque
        Oct 2 '10 at 1:24



















      1












      $begingroup$

      Consider ${n choose p}$ as $(n)(n-1)...(p+2)(p+1)/(n-p)!$. That can be written as $(n)/(n-p) cdot (n-1)/(n-p-1) cdot cdots cdot (p+1)/(1)$. Notice that these are all of the form $(x+p)/x$. Thus, terms where $x$ is not divisible by $p$ can be reduced modulo $p$ to $x/x=1$. The rest of the terms are going to be
      $(p [n/p])/((p [n/p]-1))) cdot cdots cdot (3p)/(2p) cdot (2p)/(p)$. This product telescopes to $(p [n/p])/p = [n/p]$.






      share|cite|improve this answer











      $endgroup$









      • 6




        $begingroup$
        Please TeX it so that viewers can understand your answer clearly.
        $endgroup$
        – anonymous
        Oct 1 '10 at 12:15






      • 8




        $begingroup$
        TeX is not a requirement for answers, but one way that users with high extraction rate (question to answer ratio) can contribute is to add TeX to answers that lack it. Questioners can also provide this courtesy to those who answer, and this is a reasonable division of labor. If somebody answers with correct mathematics and proper typography, that is purely a bonus.
        $endgroup$
        – T..
        Oct 1 '10 at 12:54












      • $begingroup$
        @Muad: Thanks a lot.
        $endgroup$
        – anonymous
        Oct 1 '10 at 17:46






      • 1




        $begingroup$
        @T: See, it was just a request, now don't make a big issue out of it.
        $endgroup$
        – anonymous
        Oct 1 '10 at 17:47






      • 4




        $begingroup$
        Requesting, in the form of a command, further volunteering from a helper, is bad form. Anyone troubled by the lack of TeX can simply add it. If you wish to educate the helper about site operations, lead by example rather than demanding corrections.
        $endgroup$
        – T..
        Oct 1 '10 at 19:54





















      1












      $begingroup$

      You can see the solution for the case $p=7$ here: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1775313.






      share|cite|improve this answer









      $endgroup$





















        1












        $begingroup$

        Below is a sketch of a generating-function-based proof of Lucas's theorem (mentioned in passing in a number of other answers). The original problem is just a special linear case.



        $rmquadquadquadquad! (1 + X)^{large a + b P + c P^2} (mod P)quadquad$ with $rmquadquad 0 le a,: b,: c < P$



        $rmquadquad = : (1 + X)^{large a}, (1 + X^P)^{large b} , (1 + X^{P^{large 2}})^{large c} (mod P)quadquad$



        $rmquadquad = : (1 + binom{:a:}1 X ,+ binom{:a:}2 X^2 + binom{a}3 X^3 , + :cdots: + X^{a} )$
        $rmquadquad * (1 + binom{b}1 X^P + binom{b}2: X^{2P} : + binom{b}3 X^{3P} +: cdots: + X^{bP}) $
        $rmquadquad * (1 + binom{:c:}1 X^{P^2}! + binom{:c:}2 X^{2P^2} + binom{c}3 X^{3P^2}! +: cdots: + X^{cP^2}) quad (mod P)$



        $rmquadquad = sum binom{a}A binom{b}B binom{c}C X^{: A + BP + CP^2}quad (mod P)$



        Therefore $rmquad binom{a}A binom{b}B binom{c}C = binom{a + bP + cP^2}{A + BP + CP^2} (mod P)$



        $rmquad Rightarrowquad b = binom{b}1 quad : =quad binom{a+bp}p $ for $rm B = 1, A = C = c = 0, P = p$



        the result sought with $rm n = a+bp Rightarrow [n/p] = b:$.



        For other proofs see Granville's delightful survey The Arithmetic Properties of Binomial Coefficients






        share|cite|improve this answer











        $endgroup$













          Your Answer





          StackExchange.ifUsing("editor", function () {
          return StackExchange.using("mathjaxEditing", function () {
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          });
          });
          }, "mathjax-editing");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "69"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: true,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });














          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f5818%2fproving-n-choose-p-equiv-bigl-fracnp-bigr-textmod-p%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown
























          7 Answers
          7






          active

          oldest

          votes








          7 Answers
          7






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          17












          $begingroup$

          Hint $ $ If $rm nequiv j : (mod p): $ and $rm: bigl[frac{n}{p}bigr] = k, : $ then pairing factors so that top $equiv$ bottom $rm:(mod p):$ in the binomial coefficient fractions below makes the result obvious. For example



          $${17choose 7} = frac{17}3 frac{16}2 frac{15}1 color{#c00}{frac{14}7}frac{13}6frac{12}5frac{11}4,equiv, color{#c00}2, =, leftlfloorfrac{17}7rightrfloorpmod 7qquadqquad $$



          since all of the fractions with bottom $rmne p,$ are $,rmequiv 1pmod p,$ by top $equiv$ bottom, and the red term with the bottom = $rm ,p = 7,$ is just $rm,color{#c00}{kp/p = k}.,$ Generally we have



          $$begin{eqnarray}rm {n choose p} &=&rm frac{n:(n-1):cdots:(n-p+1)}{p:(p-1):cdots: 1} \
          \
          &=& rm frac{n}{j} frac{n-1}{j-1}cdotsfrac{kp+1}{1} color{#c00}{frac{kp}p} frac{kp-1}{p-1}:cdotsfrac{n-p+2}{j+2} frac{n-p+1}{j+1}end{eqnarray}$$



          This is a very special case of much more general arithmetical results on binomial coefficients. For example, see Andrew Granville's very interesting survey The Arithmetic Properties of Binomial Coefficients



          Remark The above proof is a special case of a very simple purely arithmetical proof that I devised to show that binomial coefficients are integral. Namely, the same idea of exploiting the innate symmetry by aligning the numerators and denominators $rm:(mod p):$ extends to yield a simple algorithm that, given a binomial coefficient and a prime $rm p$, rewrites the binomial coefficient as a product of fractions whose denominators are all coprime to $rm p$. This implies that no prime divides the lowest-terms denominator, so that we may therefore conclude that the binomial coefficient is integral. For an example and further discussion see my post here.






          share|cite|improve this answer











          $endgroup$


















            17












            $begingroup$

            Hint $ $ If $rm nequiv j : (mod p): $ and $rm: bigl[frac{n}{p}bigr] = k, : $ then pairing factors so that top $equiv$ bottom $rm:(mod p):$ in the binomial coefficient fractions below makes the result obvious. For example



            $${17choose 7} = frac{17}3 frac{16}2 frac{15}1 color{#c00}{frac{14}7}frac{13}6frac{12}5frac{11}4,equiv, color{#c00}2, =, leftlfloorfrac{17}7rightrfloorpmod 7qquadqquad $$



            since all of the fractions with bottom $rmne p,$ are $,rmequiv 1pmod p,$ by top $equiv$ bottom, and the red term with the bottom = $rm ,p = 7,$ is just $rm,color{#c00}{kp/p = k}.,$ Generally we have



            $$begin{eqnarray}rm {n choose p} &=&rm frac{n:(n-1):cdots:(n-p+1)}{p:(p-1):cdots: 1} \
            \
            &=& rm frac{n}{j} frac{n-1}{j-1}cdotsfrac{kp+1}{1} color{#c00}{frac{kp}p} frac{kp-1}{p-1}:cdotsfrac{n-p+2}{j+2} frac{n-p+1}{j+1}end{eqnarray}$$



            This is a very special case of much more general arithmetical results on binomial coefficients. For example, see Andrew Granville's very interesting survey The Arithmetic Properties of Binomial Coefficients



            Remark The above proof is a special case of a very simple purely arithmetical proof that I devised to show that binomial coefficients are integral. Namely, the same idea of exploiting the innate symmetry by aligning the numerators and denominators $rm:(mod p):$ extends to yield a simple algorithm that, given a binomial coefficient and a prime $rm p$, rewrites the binomial coefficient as a product of fractions whose denominators are all coprime to $rm p$. This implies that no prime divides the lowest-terms denominator, so that we may therefore conclude that the binomial coefficient is integral. For an example and further discussion see my post here.






            share|cite|improve this answer











            $endgroup$
















              17












              17








              17





              $begingroup$

              Hint $ $ If $rm nequiv j : (mod p): $ and $rm: bigl[frac{n}{p}bigr] = k, : $ then pairing factors so that top $equiv$ bottom $rm:(mod p):$ in the binomial coefficient fractions below makes the result obvious. For example



              $${17choose 7} = frac{17}3 frac{16}2 frac{15}1 color{#c00}{frac{14}7}frac{13}6frac{12}5frac{11}4,equiv, color{#c00}2, =, leftlfloorfrac{17}7rightrfloorpmod 7qquadqquad $$



              since all of the fractions with bottom $rmne p,$ are $,rmequiv 1pmod p,$ by top $equiv$ bottom, and the red term with the bottom = $rm ,p = 7,$ is just $rm,color{#c00}{kp/p = k}.,$ Generally we have



              $$begin{eqnarray}rm {n choose p} &=&rm frac{n:(n-1):cdots:(n-p+1)}{p:(p-1):cdots: 1} \
              \
              &=& rm frac{n}{j} frac{n-1}{j-1}cdotsfrac{kp+1}{1} color{#c00}{frac{kp}p} frac{kp-1}{p-1}:cdotsfrac{n-p+2}{j+2} frac{n-p+1}{j+1}end{eqnarray}$$



              This is a very special case of much more general arithmetical results on binomial coefficients. For example, see Andrew Granville's very interesting survey The Arithmetic Properties of Binomial Coefficients



              Remark The above proof is a special case of a very simple purely arithmetical proof that I devised to show that binomial coefficients are integral. Namely, the same idea of exploiting the innate symmetry by aligning the numerators and denominators $rm:(mod p):$ extends to yield a simple algorithm that, given a binomial coefficient and a prime $rm p$, rewrites the binomial coefficient as a product of fractions whose denominators are all coprime to $rm p$. This implies that no prime divides the lowest-terms denominator, so that we may therefore conclude that the binomial coefficient is integral. For an example and further discussion see my post here.






              share|cite|improve this answer











              $endgroup$



              Hint $ $ If $rm nequiv j : (mod p): $ and $rm: bigl[frac{n}{p}bigr] = k, : $ then pairing factors so that top $equiv$ bottom $rm:(mod p):$ in the binomial coefficient fractions below makes the result obvious. For example



              $${17choose 7} = frac{17}3 frac{16}2 frac{15}1 color{#c00}{frac{14}7}frac{13}6frac{12}5frac{11}4,equiv, color{#c00}2, =, leftlfloorfrac{17}7rightrfloorpmod 7qquadqquad $$



              since all of the fractions with bottom $rmne p,$ are $,rmequiv 1pmod p,$ by top $equiv$ bottom, and the red term with the bottom = $rm ,p = 7,$ is just $rm,color{#c00}{kp/p = k}.,$ Generally we have



              $$begin{eqnarray}rm {n choose p} &=&rm frac{n:(n-1):cdots:(n-p+1)}{p:(p-1):cdots: 1} \
              \
              &=& rm frac{n}{j} frac{n-1}{j-1}cdotsfrac{kp+1}{1} color{#c00}{frac{kp}p} frac{kp-1}{p-1}:cdotsfrac{n-p+2}{j+2} frac{n-p+1}{j+1}end{eqnarray}$$



              This is a very special case of much more general arithmetical results on binomial coefficients. For example, see Andrew Granville's very interesting survey The Arithmetic Properties of Binomial Coefficients



              Remark The above proof is a special case of a very simple purely arithmetical proof that I devised to show that binomial coefficients are integral. Namely, the same idea of exploiting the innate symmetry by aligning the numerators and denominators $rm:(mod p):$ extends to yield a simple algorithm that, given a binomial coefficient and a prime $rm p$, rewrites the binomial coefficient as a product of fractions whose denominators are all coprime to $rm p$. This implies that no prime divides the lowest-terms denominator, so that we may therefore conclude that the binomial coefficient is integral. For an example and further discussion see my post here.







              share|cite|improve this answer














              share|cite|improve this answer



              share|cite|improve this answer








              edited Apr 13 '17 at 12:21









              Community

              1




              1










              answered Oct 1 '10 at 16:18









              Bill DubuqueBill Dubuque

              211k29193646




              211k29193646























                  9












                  $begingroup$

                  A useful result in such problems is Lucas's Theorem which states that



                  If $p$ is a prime and if $a = sum_{i=0}^{k} a_{i} p^{i}, 0 le a_i < p $ i.e. the $a_i$ are digits of $a$ in base $p$ and similarly $b = sum_{i=0}^{k} b_{i}p^{i}$ (pad with zeroes if required) then



                  $${a choose b} = prod_{i=0}^{k} {a_i choose b_i} mod p$$



                  In our case $n=a$ and $b=p$. Since $b = p$ we have $b_1 = 1$ and rest of the $b_i = 0$.



                  Thus



                  $${a choose p} = {a_1 choose 1} = a_1 mod p$$



                  It is easy to see that $a_1 = [frac{a}{p}] mod p$.






                  share|cite|improve this answer









                  $endgroup$


















                    9












                    $begingroup$

                    A useful result in such problems is Lucas's Theorem which states that



                    If $p$ is a prime and if $a = sum_{i=0}^{k} a_{i} p^{i}, 0 le a_i < p $ i.e. the $a_i$ are digits of $a$ in base $p$ and similarly $b = sum_{i=0}^{k} b_{i}p^{i}$ (pad with zeroes if required) then



                    $${a choose b} = prod_{i=0}^{k} {a_i choose b_i} mod p$$



                    In our case $n=a$ and $b=p$. Since $b = p$ we have $b_1 = 1$ and rest of the $b_i = 0$.



                    Thus



                    $${a choose p} = {a_1 choose 1} = a_1 mod p$$



                    It is easy to see that $a_1 = [frac{a}{p}] mod p$.






                    share|cite|improve this answer









                    $endgroup$
















                      9












                      9








                      9





                      $begingroup$

                      A useful result in such problems is Lucas's Theorem which states that



                      If $p$ is a prime and if $a = sum_{i=0}^{k} a_{i} p^{i}, 0 le a_i < p $ i.e. the $a_i$ are digits of $a$ in base $p$ and similarly $b = sum_{i=0}^{k} b_{i}p^{i}$ (pad with zeroes if required) then



                      $${a choose b} = prod_{i=0}^{k} {a_i choose b_i} mod p$$



                      In our case $n=a$ and $b=p$. Since $b = p$ we have $b_1 = 1$ and rest of the $b_i = 0$.



                      Thus



                      $${a choose p} = {a_1 choose 1} = a_1 mod p$$



                      It is easy to see that $a_1 = [frac{a}{p}] mod p$.






                      share|cite|improve this answer









                      $endgroup$



                      A useful result in such problems is Lucas's Theorem which states that



                      If $p$ is a prime and if $a = sum_{i=0}^{k} a_{i} p^{i}, 0 le a_i < p $ i.e. the $a_i$ are digits of $a$ in base $p$ and similarly $b = sum_{i=0}^{k} b_{i}p^{i}$ (pad with zeroes if required) then



                      $${a choose b} = prod_{i=0}^{k} {a_i choose b_i} mod p$$



                      In our case $n=a$ and $b=p$. Since $b = p$ we have $b_1 = 1$ and rest of the $b_i = 0$.



                      Thus



                      $${a choose p} = {a_1 choose 1} = a_1 mod p$$



                      It is easy to see that $a_1 = [frac{a}{p}] mod p$.







                      share|cite|improve this answer












                      share|cite|improve this answer



                      share|cite|improve this answer










                      answered Oct 1 '10 at 16:56









                      AryabhataAryabhata

                      70k6156246




                      70k6156246























                          8












                          $begingroup$

                          Here's another way to look at it. Suppose $n=kp+j,$ for $0 le j le p-1.$ Then



                          $$ (p-1)! {n choose p} = frac{n(n-1) cdots (n-p+1)}{p} = left( {n-j over p} right)
                          prod_{i=0,ine j }^{p-1} (n-i)$$
                          $$ equiv k(p-1)! (textrm{ mod } p). $$
                          Since the product runs through a complete set of non-zero residues mod p.






                          share|cite|improve this answer











                          $endgroup$













                          • $begingroup$
                            @Moron Thanks, fixed.
                            $endgroup$
                            – Derek Jennings
                            Oct 1 '10 at 17:40










                          • $begingroup$
                            That's equivalent to what I wrote.
                            $endgroup$
                            – Bill Dubuque
                            Oct 1 '10 at 17:50






                          • 7




                            $begingroup$
                            @Bill I did not copy your proof and I resent the suggestion.
                            $endgroup$
                            – Derek Jennings
                            Oct 1 '10 at 18:10






                          • 1




                            $begingroup$
                            @Bill. No problem. I used my approach as I recalled that my LHS was sometimes given as a hint. See for example problem 22 on page 51 of tar.hu/gergo73/nathanson.pdf . Anyway, I'm not into polemic, so I've just upvoted your answer.
                            $endgroup$
                            – Derek Jennings
                            Oct 1 '10 at 20:40






                          • 1




                            $begingroup$
                            @Derek: Thanks for the link. Initially I misunderstood and thought that you explicitly reformulated my proof because you thought there was some advantage to doing so (this happens occasionally here, usually due to my expository gaps, e.g. see math.stackexchange.com/questions/4150). Hopefully with my remark and the link you can see my motivation for presenting it in that form. Apologies for the misunderstanding.
                            $endgroup$
                            – Bill Dubuque
                            Oct 1 '10 at 21:06
















                          8












                          $begingroup$

                          Here's another way to look at it. Suppose $n=kp+j,$ for $0 le j le p-1.$ Then



                          $$ (p-1)! {n choose p} = frac{n(n-1) cdots (n-p+1)}{p} = left( {n-j over p} right)
                          prod_{i=0,ine j }^{p-1} (n-i)$$
                          $$ equiv k(p-1)! (textrm{ mod } p). $$
                          Since the product runs through a complete set of non-zero residues mod p.






                          share|cite|improve this answer











                          $endgroup$













                          • $begingroup$
                            @Moron Thanks, fixed.
                            $endgroup$
                            – Derek Jennings
                            Oct 1 '10 at 17:40










                          • $begingroup$
                            That's equivalent to what I wrote.
                            $endgroup$
                            – Bill Dubuque
                            Oct 1 '10 at 17:50






                          • 7




                            $begingroup$
                            @Bill I did not copy your proof and I resent the suggestion.
                            $endgroup$
                            – Derek Jennings
                            Oct 1 '10 at 18:10






                          • 1




                            $begingroup$
                            @Bill. No problem. I used my approach as I recalled that my LHS was sometimes given as a hint. See for example problem 22 on page 51 of tar.hu/gergo73/nathanson.pdf . Anyway, I'm not into polemic, so I've just upvoted your answer.
                            $endgroup$
                            – Derek Jennings
                            Oct 1 '10 at 20:40






                          • 1




                            $begingroup$
                            @Derek: Thanks for the link. Initially I misunderstood and thought that you explicitly reformulated my proof because you thought there was some advantage to doing so (this happens occasionally here, usually due to my expository gaps, e.g. see math.stackexchange.com/questions/4150). Hopefully with my remark and the link you can see my motivation for presenting it in that form. Apologies for the misunderstanding.
                            $endgroup$
                            – Bill Dubuque
                            Oct 1 '10 at 21:06














                          8












                          8








                          8





                          $begingroup$

                          Here's another way to look at it. Suppose $n=kp+j,$ for $0 le j le p-1.$ Then



                          $$ (p-1)! {n choose p} = frac{n(n-1) cdots (n-p+1)}{p} = left( {n-j over p} right)
                          prod_{i=0,ine j }^{p-1} (n-i)$$
                          $$ equiv k(p-1)! (textrm{ mod } p). $$
                          Since the product runs through a complete set of non-zero residues mod p.






                          share|cite|improve this answer











                          $endgroup$



                          Here's another way to look at it. Suppose $n=kp+j,$ for $0 le j le p-1.$ Then



                          $$ (p-1)! {n choose p} = frac{n(n-1) cdots (n-p+1)}{p} = left( {n-j over p} right)
                          prod_{i=0,ine j }^{p-1} (n-i)$$
                          $$ equiv k(p-1)! (textrm{ mod } p). $$
                          Since the product runs through a complete set of non-zero residues mod p.







                          share|cite|improve this answer














                          share|cite|improve this answer



                          share|cite|improve this answer








                          edited Oct 1 '10 at 17:39

























                          answered Oct 1 '10 at 17:28









                          Derek JenningsDerek Jennings

                          12k3054




                          12k3054












                          • $begingroup$
                            @Moron Thanks, fixed.
                            $endgroup$
                            – Derek Jennings
                            Oct 1 '10 at 17:40










                          • $begingroup$
                            That's equivalent to what I wrote.
                            $endgroup$
                            – Bill Dubuque
                            Oct 1 '10 at 17:50






                          • 7




                            $begingroup$
                            @Bill I did not copy your proof and I resent the suggestion.
                            $endgroup$
                            – Derek Jennings
                            Oct 1 '10 at 18:10






                          • 1




                            $begingroup$
                            @Bill. No problem. I used my approach as I recalled that my LHS was sometimes given as a hint. See for example problem 22 on page 51 of tar.hu/gergo73/nathanson.pdf . Anyway, I'm not into polemic, so I've just upvoted your answer.
                            $endgroup$
                            – Derek Jennings
                            Oct 1 '10 at 20:40






                          • 1




                            $begingroup$
                            @Derek: Thanks for the link. Initially I misunderstood and thought that you explicitly reformulated my proof because you thought there was some advantage to doing so (this happens occasionally here, usually due to my expository gaps, e.g. see math.stackexchange.com/questions/4150). Hopefully with my remark and the link you can see my motivation for presenting it in that form. Apologies for the misunderstanding.
                            $endgroup$
                            – Bill Dubuque
                            Oct 1 '10 at 21:06


















                          • $begingroup$
                            @Moron Thanks, fixed.
                            $endgroup$
                            – Derek Jennings
                            Oct 1 '10 at 17:40










                          • $begingroup$
                            That's equivalent to what I wrote.
                            $endgroup$
                            – Bill Dubuque
                            Oct 1 '10 at 17:50






                          • 7




                            $begingroup$
                            @Bill I did not copy your proof and I resent the suggestion.
                            $endgroup$
                            – Derek Jennings
                            Oct 1 '10 at 18:10






                          • 1




                            $begingroup$
                            @Bill. No problem. I used my approach as I recalled that my LHS was sometimes given as a hint. See for example problem 22 on page 51 of tar.hu/gergo73/nathanson.pdf . Anyway, I'm not into polemic, so I've just upvoted your answer.
                            $endgroup$
                            – Derek Jennings
                            Oct 1 '10 at 20:40






                          • 1




                            $begingroup$
                            @Derek: Thanks for the link. Initially I misunderstood and thought that you explicitly reformulated my proof because you thought there was some advantage to doing so (this happens occasionally here, usually due to my expository gaps, e.g. see math.stackexchange.com/questions/4150). Hopefully with my remark and the link you can see my motivation for presenting it in that form. Apologies for the misunderstanding.
                            $endgroup$
                            – Bill Dubuque
                            Oct 1 '10 at 21:06
















                          $begingroup$
                          @Moron Thanks, fixed.
                          $endgroup$
                          – Derek Jennings
                          Oct 1 '10 at 17:40




                          $begingroup$
                          @Moron Thanks, fixed.
                          $endgroup$
                          – Derek Jennings
                          Oct 1 '10 at 17:40












                          $begingroup$
                          That's equivalent to what I wrote.
                          $endgroup$
                          – Bill Dubuque
                          Oct 1 '10 at 17:50




                          $begingroup$
                          That's equivalent to what I wrote.
                          $endgroup$
                          – Bill Dubuque
                          Oct 1 '10 at 17:50




                          7




                          7




                          $begingroup$
                          @Bill I did not copy your proof and I resent the suggestion.
                          $endgroup$
                          – Derek Jennings
                          Oct 1 '10 at 18:10




                          $begingroup$
                          @Bill I did not copy your proof and I resent the suggestion.
                          $endgroup$
                          – Derek Jennings
                          Oct 1 '10 at 18:10




                          1




                          1




                          $begingroup$
                          @Bill. No problem. I used my approach as I recalled that my LHS was sometimes given as a hint. See for example problem 22 on page 51 of tar.hu/gergo73/nathanson.pdf . Anyway, I'm not into polemic, so I've just upvoted your answer.
                          $endgroup$
                          – Derek Jennings
                          Oct 1 '10 at 20:40




                          $begingroup$
                          @Bill. No problem. I used my approach as I recalled that my LHS was sometimes given as a hint. See for example problem 22 on page 51 of tar.hu/gergo73/nathanson.pdf . Anyway, I'm not into polemic, so I've just upvoted your answer.
                          $endgroup$
                          – Derek Jennings
                          Oct 1 '10 at 20:40




                          1




                          1




                          $begingroup$
                          @Derek: Thanks for the link. Initially I misunderstood and thought that you explicitly reformulated my proof because you thought there was some advantage to doing so (this happens occasionally here, usually due to my expository gaps, e.g. see math.stackexchange.com/questions/4150). Hopefully with my remark and the link you can see my motivation for presenting it in that form. Apologies for the misunderstanding.
                          $endgroup$
                          – Bill Dubuque
                          Oct 1 '10 at 21:06




                          $begingroup$
                          @Derek: Thanks for the link. Initially I misunderstood and thought that you explicitly reformulated my proof because you thought there was some advantage to doing so (this happens occasionally here, usually due to my expository gaps, e.g. see math.stackexchange.com/questions/4150). Hopefully with my remark and the link you can see my motivation for presenting it in that form. Apologies for the misunderstanding.
                          $endgroup$
                          – Bill Dubuque
                          Oct 1 '10 at 21:06











                          5












                          $begingroup$

                          The binomial theorem together with the identity $(x+y)^p = x^p + y^p mod p$ is useful for this type of problem.



                          Here we want the the $x^p$ coefficient of $(1+x)^{Ap+B} = (1+x^p)^A (1+x)^B = (1 + Ax^p + dots)(1+X)^B$ where $0 leq B < p$. This coefficient comes only from multiplication of $(Ax^p)$ by $(1)$. So the result mod p is $A$.



                          Another solution is to use combinatorics. Partition the set of integers from 1 to $n$ into $A$ blocks of size $p$ and a (perhaps empty) remainder of size $B$, as above. Any subset is either a complete block or it contains a proper nonempty subset of at least one block. Rotating the elements in the first partially filled block organizes the $binom{n}{p}$ p-subsets into collections of size $p$, plus a "remainder" consisting of complete $p$-blocks, and there are $A$ of the those.






                          share|cite|improve this answer









                          $endgroup$













                          • $begingroup$
                            REMARK The above generating function approach is mentioned in section 6 of the Granville survey that I mentioned, where he credits its application to Lucas's theorem to Fine (1947). See my other posts here for a sketch of the simple proof (from one of my old sci.math posts).
                            $endgroup$
                            – Bill Dubuque
                            Oct 2 '10 at 1:24
















                          5












                          $begingroup$

                          The binomial theorem together with the identity $(x+y)^p = x^p + y^p mod p$ is useful for this type of problem.



                          Here we want the the $x^p$ coefficient of $(1+x)^{Ap+B} = (1+x^p)^A (1+x)^B = (1 + Ax^p + dots)(1+X)^B$ where $0 leq B < p$. This coefficient comes only from multiplication of $(Ax^p)$ by $(1)$. So the result mod p is $A$.



                          Another solution is to use combinatorics. Partition the set of integers from 1 to $n$ into $A$ blocks of size $p$ and a (perhaps empty) remainder of size $B$, as above. Any subset is either a complete block or it contains a proper nonempty subset of at least one block. Rotating the elements in the first partially filled block organizes the $binom{n}{p}$ p-subsets into collections of size $p$, plus a "remainder" consisting of complete $p$-blocks, and there are $A$ of the those.






                          share|cite|improve this answer









                          $endgroup$













                          • $begingroup$
                            REMARK The above generating function approach is mentioned in section 6 of the Granville survey that I mentioned, where he credits its application to Lucas's theorem to Fine (1947). See my other posts here for a sketch of the simple proof (from one of my old sci.math posts).
                            $endgroup$
                            – Bill Dubuque
                            Oct 2 '10 at 1:24














                          5












                          5








                          5





                          $begingroup$

                          The binomial theorem together with the identity $(x+y)^p = x^p + y^p mod p$ is useful for this type of problem.



                          Here we want the the $x^p$ coefficient of $(1+x)^{Ap+B} = (1+x^p)^A (1+x)^B = (1 + Ax^p + dots)(1+X)^B$ where $0 leq B < p$. This coefficient comes only from multiplication of $(Ax^p)$ by $(1)$. So the result mod p is $A$.



                          Another solution is to use combinatorics. Partition the set of integers from 1 to $n$ into $A$ blocks of size $p$ and a (perhaps empty) remainder of size $B$, as above. Any subset is either a complete block or it contains a proper nonempty subset of at least one block. Rotating the elements in the first partially filled block organizes the $binom{n}{p}$ p-subsets into collections of size $p$, plus a "remainder" consisting of complete $p$-blocks, and there are $A$ of the those.






                          share|cite|improve this answer









                          $endgroup$



                          The binomial theorem together with the identity $(x+y)^p = x^p + y^p mod p$ is useful for this type of problem.



                          Here we want the the $x^p$ coefficient of $(1+x)^{Ap+B} = (1+x^p)^A (1+x)^B = (1 + Ax^p + dots)(1+X)^B$ where $0 leq B < p$. This coefficient comes only from multiplication of $(Ax^p)$ by $(1)$. So the result mod p is $A$.



                          Another solution is to use combinatorics. Partition the set of integers from 1 to $n$ into $A$ blocks of size $p$ and a (perhaps empty) remainder of size $B$, as above. Any subset is either a complete block or it contains a proper nonempty subset of at least one block. Rotating the elements in the first partially filled block organizes the $binom{n}{p}$ p-subsets into collections of size $p$, plus a "remainder" consisting of complete $p$-blocks, and there are $A$ of the those.







                          share|cite|improve this answer












                          share|cite|improve this answer



                          share|cite|improve this answer










                          answered Oct 1 '10 at 20:32









                          T..T..

                          10.4k23446




                          10.4k23446












                          • $begingroup$
                            REMARK The above generating function approach is mentioned in section 6 of the Granville survey that I mentioned, where he credits its application to Lucas's theorem to Fine (1947). See my other posts here for a sketch of the simple proof (from one of my old sci.math posts).
                            $endgroup$
                            – Bill Dubuque
                            Oct 2 '10 at 1:24


















                          • $begingroup$
                            REMARK The above generating function approach is mentioned in section 6 of the Granville survey that I mentioned, where he credits its application to Lucas's theorem to Fine (1947). See my other posts here for a sketch of the simple proof (from one of my old sci.math posts).
                            $endgroup$
                            – Bill Dubuque
                            Oct 2 '10 at 1:24
















                          $begingroup$
                          REMARK The above generating function approach is mentioned in section 6 of the Granville survey that I mentioned, where he credits its application to Lucas's theorem to Fine (1947). See my other posts here for a sketch of the simple proof (from one of my old sci.math posts).
                          $endgroup$
                          – Bill Dubuque
                          Oct 2 '10 at 1:24




                          $begingroup$
                          REMARK The above generating function approach is mentioned in section 6 of the Granville survey that I mentioned, where he credits its application to Lucas's theorem to Fine (1947). See my other posts here for a sketch of the simple proof (from one of my old sci.math posts).
                          $endgroup$
                          – Bill Dubuque
                          Oct 2 '10 at 1:24











                          1












                          $begingroup$

                          Consider ${n choose p}$ as $(n)(n-1)...(p+2)(p+1)/(n-p)!$. That can be written as $(n)/(n-p) cdot (n-1)/(n-p-1) cdot cdots cdot (p+1)/(1)$. Notice that these are all of the form $(x+p)/x$. Thus, terms where $x$ is not divisible by $p$ can be reduced modulo $p$ to $x/x=1$. The rest of the terms are going to be
                          $(p [n/p])/((p [n/p]-1))) cdot cdots cdot (3p)/(2p) cdot (2p)/(p)$. This product telescopes to $(p [n/p])/p = [n/p]$.






                          share|cite|improve this answer











                          $endgroup$









                          • 6




                            $begingroup$
                            Please TeX it so that viewers can understand your answer clearly.
                            $endgroup$
                            – anonymous
                            Oct 1 '10 at 12:15






                          • 8




                            $begingroup$
                            TeX is not a requirement for answers, but one way that users with high extraction rate (question to answer ratio) can contribute is to add TeX to answers that lack it. Questioners can also provide this courtesy to those who answer, and this is a reasonable division of labor. If somebody answers with correct mathematics and proper typography, that is purely a bonus.
                            $endgroup$
                            – T..
                            Oct 1 '10 at 12:54












                          • $begingroup$
                            @Muad: Thanks a lot.
                            $endgroup$
                            – anonymous
                            Oct 1 '10 at 17:46






                          • 1




                            $begingroup$
                            @T: See, it was just a request, now don't make a big issue out of it.
                            $endgroup$
                            – anonymous
                            Oct 1 '10 at 17:47






                          • 4




                            $begingroup$
                            Requesting, in the form of a command, further volunteering from a helper, is bad form. Anyone troubled by the lack of TeX can simply add it. If you wish to educate the helper about site operations, lead by example rather than demanding corrections.
                            $endgroup$
                            – T..
                            Oct 1 '10 at 19:54


















                          1












                          $begingroup$

                          Consider ${n choose p}$ as $(n)(n-1)...(p+2)(p+1)/(n-p)!$. That can be written as $(n)/(n-p) cdot (n-1)/(n-p-1) cdot cdots cdot (p+1)/(1)$. Notice that these are all of the form $(x+p)/x$. Thus, terms where $x$ is not divisible by $p$ can be reduced modulo $p$ to $x/x=1$. The rest of the terms are going to be
                          $(p [n/p])/((p [n/p]-1))) cdot cdots cdot (3p)/(2p) cdot (2p)/(p)$. This product telescopes to $(p [n/p])/p = [n/p]$.






                          share|cite|improve this answer











                          $endgroup$









                          • 6




                            $begingroup$
                            Please TeX it so that viewers can understand your answer clearly.
                            $endgroup$
                            – anonymous
                            Oct 1 '10 at 12:15






                          • 8




                            $begingroup$
                            TeX is not a requirement for answers, but one way that users with high extraction rate (question to answer ratio) can contribute is to add TeX to answers that lack it. Questioners can also provide this courtesy to those who answer, and this is a reasonable division of labor. If somebody answers with correct mathematics and proper typography, that is purely a bonus.
                            $endgroup$
                            – T..
                            Oct 1 '10 at 12:54












                          • $begingroup$
                            @Muad: Thanks a lot.
                            $endgroup$
                            – anonymous
                            Oct 1 '10 at 17:46






                          • 1




                            $begingroup$
                            @T: See, it was just a request, now don't make a big issue out of it.
                            $endgroup$
                            – anonymous
                            Oct 1 '10 at 17:47






                          • 4




                            $begingroup$
                            Requesting, in the form of a command, further volunteering from a helper, is bad form. Anyone troubled by the lack of TeX can simply add it. If you wish to educate the helper about site operations, lead by example rather than demanding corrections.
                            $endgroup$
                            – T..
                            Oct 1 '10 at 19:54
















                          1












                          1








                          1





                          $begingroup$

                          Consider ${n choose p}$ as $(n)(n-1)...(p+2)(p+1)/(n-p)!$. That can be written as $(n)/(n-p) cdot (n-1)/(n-p-1) cdot cdots cdot (p+1)/(1)$. Notice that these are all of the form $(x+p)/x$. Thus, terms where $x$ is not divisible by $p$ can be reduced modulo $p$ to $x/x=1$. The rest of the terms are going to be
                          $(p [n/p])/((p [n/p]-1))) cdot cdots cdot (3p)/(2p) cdot (2p)/(p)$. This product telescopes to $(p [n/p])/p = [n/p]$.






                          share|cite|improve this answer











                          $endgroup$



                          Consider ${n choose p}$ as $(n)(n-1)...(p+2)(p+1)/(n-p)!$. That can be written as $(n)/(n-p) cdot (n-1)/(n-p-1) cdot cdots cdot (p+1)/(1)$. Notice that these are all of the form $(x+p)/x$. Thus, terms where $x$ is not divisible by $p$ can be reduced modulo $p$ to $x/x=1$. The rest of the terms are going to be
                          $(p [n/p])/((p [n/p]-1))) cdot cdots cdot (3p)/(2p) cdot (2p)/(p)$. This product telescopes to $(p [n/p])/p = [n/p]$.







                          share|cite|improve this answer














                          share|cite|improve this answer



                          share|cite|improve this answer








                          edited Oct 1 '10 at 16:04







                          anon

















                          answered Oct 1 '10 at 12:09









                          yrudoyyrudoy

                          1,2381220




                          1,2381220








                          • 6




                            $begingroup$
                            Please TeX it so that viewers can understand your answer clearly.
                            $endgroup$
                            – anonymous
                            Oct 1 '10 at 12:15






                          • 8




                            $begingroup$
                            TeX is not a requirement for answers, but one way that users with high extraction rate (question to answer ratio) can contribute is to add TeX to answers that lack it. Questioners can also provide this courtesy to those who answer, and this is a reasonable division of labor. If somebody answers with correct mathematics and proper typography, that is purely a bonus.
                            $endgroup$
                            – T..
                            Oct 1 '10 at 12:54












                          • $begingroup$
                            @Muad: Thanks a lot.
                            $endgroup$
                            – anonymous
                            Oct 1 '10 at 17:46






                          • 1




                            $begingroup$
                            @T: See, it was just a request, now don't make a big issue out of it.
                            $endgroup$
                            – anonymous
                            Oct 1 '10 at 17:47






                          • 4




                            $begingroup$
                            Requesting, in the form of a command, further volunteering from a helper, is bad form. Anyone troubled by the lack of TeX can simply add it. If you wish to educate the helper about site operations, lead by example rather than demanding corrections.
                            $endgroup$
                            – T..
                            Oct 1 '10 at 19:54
















                          • 6




                            $begingroup$
                            Please TeX it so that viewers can understand your answer clearly.
                            $endgroup$
                            – anonymous
                            Oct 1 '10 at 12:15






                          • 8




                            $begingroup$
                            TeX is not a requirement for answers, but one way that users with high extraction rate (question to answer ratio) can contribute is to add TeX to answers that lack it. Questioners can also provide this courtesy to those who answer, and this is a reasonable division of labor. If somebody answers with correct mathematics and proper typography, that is purely a bonus.
                            $endgroup$
                            – T..
                            Oct 1 '10 at 12:54












                          • $begingroup$
                            @Muad: Thanks a lot.
                            $endgroup$
                            – anonymous
                            Oct 1 '10 at 17:46






                          • 1




                            $begingroup$
                            @T: See, it was just a request, now don't make a big issue out of it.
                            $endgroup$
                            – anonymous
                            Oct 1 '10 at 17:47






                          • 4




                            $begingroup$
                            Requesting, in the form of a command, further volunteering from a helper, is bad form. Anyone troubled by the lack of TeX can simply add it. If you wish to educate the helper about site operations, lead by example rather than demanding corrections.
                            $endgroup$
                            – T..
                            Oct 1 '10 at 19:54










                          6




                          6




                          $begingroup$
                          Please TeX it so that viewers can understand your answer clearly.
                          $endgroup$
                          – anonymous
                          Oct 1 '10 at 12:15




                          $begingroup$
                          Please TeX it so that viewers can understand your answer clearly.
                          $endgroup$
                          – anonymous
                          Oct 1 '10 at 12:15




                          8




                          8




                          $begingroup$
                          TeX is not a requirement for answers, but one way that users with high extraction rate (question to answer ratio) can contribute is to add TeX to answers that lack it. Questioners can also provide this courtesy to those who answer, and this is a reasonable division of labor. If somebody answers with correct mathematics and proper typography, that is purely a bonus.
                          $endgroup$
                          – T..
                          Oct 1 '10 at 12:54






                          $begingroup$
                          TeX is not a requirement for answers, but one way that users with high extraction rate (question to answer ratio) can contribute is to add TeX to answers that lack it. Questioners can also provide this courtesy to those who answer, and this is a reasonable division of labor. If somebody answers with correct mathematics and proper typography, that is purely a bonus.
                          $endgroup$
                          – T..
                          Oct 1 '10 at 12:54














                          $begingroup$
                          @Muad: Thanks a lot.
                          $endgroup$
                          – anonymous
                          Oct 1 '10 at 17:46




                          $begingroup$
                          @Muad: Thanks a lot.
                          $endgroup$
                          – anonymous
                          Oct 1 '10 at 17:46




                          1




                          1




                          $begingroup$
                          @T: See, it was just a request, now don't make a big issue out of it.
                          $endgroup$
                          – anonymous
                          Oct 1 '10 at 17:47




                          $begingroup$
                          @T: See, it was just a request, now don't make a big issue out of it.
                          $endgroup$
                          – anonymous
                          Oct 1 '10 at 17:47




                          4




                          4




                          $begingroup$
                          Requesting, in the form of a command, further volunteering from a helper, is bad form. Anyone troubled by the lack of TeX can simply add it. If you wish to educate the helper about site operations, lead by example rather than demanding corrections.
                          $endgroup$
                          – T..
                          Oct 1 '10 at 19:54






                          $begingroup$
                          Requesting, in the form of a command, further volunteering from a helper, is bad form. Anyone troubled by the lack of TeX can simply add it. If you wish to educate the helper about site operations, lead by example rather than demanding corrections.
                          $endgroup$
                          – T..
                          Oct 1 '10 at 19:54













                          1












                          $begingroup$

                          You can see the solution for the case $p=7$ here: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1775313.






                          share|cite|improve this answer









                          $endgroup$


















                            1












                            $begingroup$

                            You can see the solution for the case $p=7$ here: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1775313.






                            share|cite|improve this answer









                            $endgroup$
















                              1












                              1








                              1





                              $begingroup$

                              You can see the solution for the case $p=7$ here: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1775313.






                              share|cite|improve this answer









                              $endgroup$



                              You can see the solution for the case $p=7$ here: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1775313.







                              share|cite|improve this answer












                              share|cite|improve this answer



                              share|cite|improve this answer










                              answered Mar 31 '11 at 7:00









                              Amir HosseinAmir Hossein

                              2,38111750




                              2,38111750























                                  1












                                  $begingroup$

                                  Below is a sketch of a generating-function-based proof of Lucas's theorem (mentioned in passing in a number of other answers). The original problem is just a special linear case.



                                  $rmquadquadquadquad! (1 + X)^{large a + b P + c P^2} (mod P)quadquad$ with $rmquadquad 0 le a,: b,: c < P$



                                  $rmquadquad = : (1 + X)^{large a}, (1 + X^P)^{large b} , (1 + X^{P^{large 2}})^{large c} (mod P)quadquad$



                                  $rmquadquad = : (1 + binom{:a:}1 X ,+ binom{:a:}2 X^2 + binom{a}3 X^3 , + :cdots: + X^{a} )$
                                  $rmquadquad * (1 + binom{b}1 X^P + binom{b}2: X^{2P} : + binom{b}3 X^{3P} +: cdots: + X^{bP}) $
                                  $rmquadquad * (1 + binom{:c:}1 X^{P^2}! + binom{:c:}2 X^{2P^2} + binom{c}3 X^{3P^2}! +: cdots: + X^{cP^2}) quad (mod P)$



                                  $rmquadquad = sum binom{a}A binom{b}B binom{c}C X^{: A + BP + CP^2}quad (mod P)$



                                  Therefore $rmquad binom{a}A binom{b}B binom{c}C = binom{a + bP + cP^2}{A + BP + CP^2} (mod P)$



                                  $rmquad Rightarrowquad b = binom{b}1 quad : =quad binom{a+bp}p $ for $rm B = 1, A = C = c = 0, P = p$



                                  the result sought with $rm n = a+bp Rightarrow [n/p] = b:$.



                                  For other proofs see Granville's delightful survey The Arithmetic Properties of Binomial Coefficients






                                  share|cite|improve this answer











                                  $endgroup$


















                                    1












                                    $begingroup$

                                    Below is a sketch of a generating-function-based proof of Lucas's theorem (mentioned in passing in a number of other answers). The original problem is just a special linear case.



                                    $rmquadquadquadquad! (1 + X)^{large a + b P + c P^2} (mod P)quadquad$ with $rmquadquad 0 le a,: b,: c < P$



                                    $rmquadquad = : (1 + X)^{large a}, (1 + X^P)^{large b} , (1 + X^{P^{large 2}})^{large c} (mod P)quadquad$



                                    $rmquadquad = : (1 + binom{:a:}1 X ,+ binom{:a:}2 X^2 + binom{a}3 X^3 , + :cdots: + X^{a} )$
                                    $rmquadquad * (1 + binom{b}1 X^P + binom{b}2: X^{2P} : + binom{b}3 X^{3P} +: cdots: + X^{bP}) $
                                    $rmquadquad * (1 + binom{:c:}1 X^{P^2}! + binom{:c:}2 X^{2P^2} + binom{c}3 X^{3P^2}! +: cdots: + X^{cP^2}) quad (mod P)$



                                    $rmquadquad = sum binom{a}A binom{b}B binom{c}C X^{: A + BP + CP^2}quad (mod P)$



                                    Therefore $rmquad binom{a}A binom{b}B binom{c}C = binom{a + bP + cP^2}{A + BP + CP^2} (mod P)$



                                    $rmquad Rightarrowquad b = binom{b}1 quad : =quad binom{a+bp}p $ for $rm B = 1, A = C = c = 0, P = p$



                                    the result sought with $rm n = a+bp Rightarrow [n/p] = b:$.



                                    For other proofs see Granville's delightful survey The Arithmetic Properties of Binomial Coefficients






                                    share|cite|improve this answer











                                    $endgroup$
















                                      1












                                      1








                                      1





                                      $begingroup$

                                      Below is a sketch of a generating-function-based proof of Lucas's theorem (mentioned in passing in a number of other answers). The original problem is just a special linear case.



                                      $rmquadquadquadquad! (1 + X)^{large a + b P + c P^2} (mod P)quadquad$ with $rmquadquad 0 le a,: b,: c < P$



                                      $rmquadquad = : (1 + X)^{large a}, (1 + X^P)^{large b} , (1 + X^{P^{large 2}})^{large c} (mod P)quadquad$



                                      $rmquadquad = : (1 + binom{:a:}1 X ,+ binom{:a:}2 X^2 + binom{a}3 X^3 , + :cdots: + X^{a} )$
                                      $rmquadquad * (1 + binom{b}1 X^P + binom{b}2: X^{2P} : + binom{b}3 X^{3P} +: cdots: + X^{bP}) $
                                      $rmquadquad * (1 + binom{:c:}1 X^{P^2}! + binom{:c:}2 X^{2P^2} + binom{c}3 X^{3P^2}! +: cdots: + X^{cP^2}) quad (mod P)$



                                      $rmquadquad = sum binom{a}A binom{b}B binom{c}C X^{: A + BP + CP^2}quad (mod P)$



                                      Therefore $rmquad binom{a}A binom{b}B binom{c}C = binom{a + bP + cP^2}{A + BP + CP^2} (mod P)$



                                      $rmquad Rightarrowquad b = binom{b}1 quad : =quad binom{a+bp}p $ for $rm B = 1, A = C = c = 0, P = p$



                                      the result sought with $rm n = a+bp Rightarrow [n/p] = b:$.



                                      For other proofs see Granville's delightful survey The Arithmetic Properties of Binomial Coefficients






                                      share|cite|improve this answer











                                      $endgroup$



                                      Below is a sketch of a generating-function-based proof of Lucas's theorem (mentioned in passing in a number of other answers). The original problem is just a special linear case.



                                      $rmquadquadquadquad! (1 + X)^{large a + b P + c P^2} (mod P)quadquad$ with $rmquadquad 0 le a,: b,: c < P$



                                      $rmquadquad = : (1 + X)^{large a}, (1 + X^P)^{large b} , (1 + X^{P^{large 2}})^{large c} (mod P)quadquad$



                                      $rmquadquad = : (1 + binom{:a:}1 X ,+ binom{:a:}2 X^2 + binom{a}3 X^3 , + :cdots: + X^{a} )$
                                      $rmquadquad * (1 + binom{b}1 X^P + binom{b}2: X^{2P} : + binom{b}3 X^{3P} +: cdots: + X^{bP}) $
                                      $rmquadquad * (1 + binom{:c:}1 X^{P^2}! + binom{:c:}2 X^{2P^2} + binom{c}3 X^{3P^2}! +: cdots: + X^{cP^2}) quad (mod P)$



                                      $rmquadquad = sum binom{a}A binom{b}B binom{c}C X^{: A + BP + CP^2}quad (mod P)$



                                      Therefore $rmquad binom{a}A binom{b}B binom{c}C = binom{a + bP + cP^2}{A + BP + CP^2} (mod P)$



                                      $rmquad Rightarrowquad b = binom{b}1 quad : =quad binom{a+bp}p $ for $rm B = 1, A = C = c = 0, P = p$



                                      the result sought with $rm n = a+bp Rightarrow [n/p] = b:$.



                                      For other proofs see Granville's delightful survey The Arithmetic Properties of Binomial Coefficients







                                      share|cite|improve this answer














                                      share|cite|improve this answer



                                      share|cite|improve this answer








                                      edited Dec 23 '18 at 21:16

























                                      answered Oct 1 '10 at 22:26









                                      Bill DubuqueBill Dubuque

                                      211k29193646




                                      211k29193646






























                                          draft saved

                                          draft discarded




















































                                          Thanks for contributing an answer to Mathematics Stack Exchange!


                                          • Please be sure to answer the question. Provide details and share your research!

                                          But avoid



                                          • Asking for help, clarification, or responding to other answers.

                                          • Making statements based on opinion; back them up with references or personal experience.


                                          Use MathJax to format equations. MathJax reference.


                                          To learn more, see our tips on writing great answers.




                                          draft saved


                                          draft discarded














                                          StackExchange.ready(
                                          function () {
                                          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f5818%2fproving-n-choose-p-equiv-bigl-fracnp-bigr-textmod-p%23new-answer', 'question_page');
                                          }
                                          );

                                          Post as a guest















                                          Required, but never shown





















































                                          Required, but never shown














                                          Required, but never shown












                                          Required, but never shown







                                          Required, but never shown

































                                          Required, but never shown














                                          Required, but never shown












                                          Required, but never shown







                                          Required, but never shown







                                          Popular posts from this blog

                                          Ellipse (mathématiques)

                                          Quarter-circle Tiles

                                          Mont Emei