In this paper, the author stated that we can use Lucas theorem to prove that $$\binom{ap^f+r}{m}\equiv \binom{r}{m}\ (\text{mod}\ p)$$

where $0\le r, m < p^f$, $a\ge 0$.

I don't know how to use Lucas theorem to deduce that.

My idea is follows

Let $a=a_0+a_1p+...+a_wp^w$, $r=r_0+r_1p+...+r_up^u$, $m=m_0+m_1p+...+m_vp^v$ be the p-nary representation of $a, r, m$ respectively, then $ap^f+r=r_0+r_1p+...+r_up^u+a_0p^f+...+a_wp^{f+w}$.

Applying Lucas theorem, we have $$ \binom{ap^f+r}{m}\equiv \binom{r_0}{m_0}\binom{r_1}{m_1}...\binom{r_v}{m_v}.\binom{r_{v+1}}{0}...\binom{r_u}{0}.\binom{a_0}{0}...\binom{a_w}{0}=\binom{r_0}{m_0}\binom{r_1}{m_1}...\binom{r_v}{m_v}$$

But note that by Lucas theorem again, we have $$\binom{r}{m}\equiv \binom{r_0}{m_0}\binom{r_1}{m_1}...\binom{r_v}{m_v} \ (\text{mod}\ p) $$

Therefore, $\binom{ap^f+r}{m}\equiv \binom{r}{m}\ (\text{mod}\ p)$

I see that it's too obvious. Am I wrong? If i'm wrong please point out my mistake and provide a proof using Lucas theorem.

Please help me.


  • $\begingroup$ Why "too obvious"? Obvious is a good thing, when it's true. $\endgroup$ – Robert Israel Mar 1 '16 at 5:42
  • $\begingroup$ Looks okay to me; some things really are easy. $\endgroup$ – Brian M. Scott Mar 1 '16 at 5:48
  • 1
    $\begingroup$ It looks from the way you stated the assumptions that it's a valid case to consider. You're right that $\binom{r}{m} = 0$ in this case, but then you want to argue that the left side is also $0$ mod $p$. $\endgroup$ – Michael Harrison Mar 1 '16 at 6:13
  • 1
    $\begingroup$ @Arsenaler For example, it allows you to say things such as: $3$ divides $\binom{11}{4}$. ($r=2$, $m=4$, $p=3$, $f=2$, $a=1$), This seems like a reasonable application of this result. $\endgroup$ – Michael Harrison Mar 1 '16 at 6:38
  • 1
    $\begingroup$ @Arsenaler I think your proof is fine. Atleast you wrote it out once, so now you see everything that cancels. If $r<m$ then for some $t$, you'll have $m_t > r_t$, which makes $\binom{r_t}{m_t} = 0$, which makes the whole product $0$ (mod $p$). $\endgroup$ – Michael Harrison Mar 1 '16 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.