Given a prime $p$ and some $k,t\in\Bbb{Z}^{+}$, when does the congruence equation $${x \choose k} \equiv t\pmod {p}$$ have an integer solution?

Is there some necessary and sufficient condition about $p,k,t$?

  • $\begingroup$ @JCAA I changed my question. Thank you. $\endgroup$ – MathEric Jun 30 at 17:58

By Lucas's theorem, $${x \choose k} \equiv \prod_j {x_j \choose k_j} \mod p$$ where the base-$p$ representations of $x$ and $k$ have digits $x_j$ and $k_j$ respectively, (with extra $0$'s as needed in $k_j$ when $k$ has fewer digits than $x$). If all $k_j = 0$ or $p-1$, for example, ${x_j \choose k_j} \equiv 0$ or $1 \mod p$, and then${x \choose k} \equiv 0$ or $1 \mod p$.

So for a given $k$ and $p$, with $[k_d, \ldots, k_0]$ the base $p$ representation of $k$, the possible nonzero values $t$ are the products $t = \prod_{j=0}^d t_j \mod p$ where $t_j \in \{{0 \choose k_j} \mod p, \ldots, {p-1 \choose k_j} \mod p\}$.

For example, with $p=5$ and $k = 123 = 443_5$, ${x \choose 4} \equiv 0$ or $1 \mod 5$, and ${x \choose 3} \equiv 0, 1$ or $4 \mod 5$, so the possibilities for ${x \choose 123}$ are $0, 1$ and $4 \mod 5$.

| cite | improve this answer | |

Your Answer

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

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