Binomial Coefficient Modulo a Prime by Lucas’s Theorem

Compute C(n,k) modulo a prime from the base-prime digits of exact nonnegative decimal integers; the prime is capped at 10,000 for bounded work.

Description

Lucas’s theorem reduces a binomial coefficient modulo a prime to smaller binomial coefficients of base-prime digits.

Lucas’s theorem reduces a binomial coefficient modulo a prime to smaller binomial coefficients of base-prime digits. This allows large indexes without constructing the full binomial coefficient.^[1]

The tool returns residue. The indexing and output conventions below determine how to read these values.

When to use Binomial Coefficient Modulo a Prime by Lucas’s Theorem

Use this for the following task: Compute C(n,k) modulo a prime from the base-prime digits of exact nonnegative decimal integers; the prime is capped at 10,000 for bounded work. Use the input and output conventions below to reproduce the intended mathematical quantity.

How to use Binomial Coefficient Modulo a Prime by Lucas’s Theorem and understand its results

Choose the required indexes, integers or sequence entries. Preserve decimal-string encodings where the field table specifies strings.
Enter n, k, prime according to the field table, then run the tool.
Read residue. Use the stated units, indexing and interpretation of the numerical result.
Keep exact decimal strings for subsequent integer arithmetic; distinguish them from any explicitly approximate numeric result.

Input field	Meaning	Value type and bounds	Requirement
n	Nonnegative upper binomial index	string (integer/arbitrary); maximum text length 200; pattern ^(0\|[1-9][0-9]*)$	Required
k	Nonnegative lower binomial index	string (integer/arbitrary); maximum text length 200; pattern ^(0\|[1-9][0-9]*)$	Required
prime	Prime modulus (resource limit 10000)	integer; minimum 2; maximum 10000	Required

Parse nonnegative n and k as BigInt strings and require a prime modulus at most 10000. Multiply digit-level numerator products and modular inverses; return zero when a lower digit exceeds its upper digit.

C(n,k) mod p = Π C(nᵢ,kᵢ) mod p, for base-p digits

The symbols and boundary conditions refer to the supplied fields and the implementation described above.

Output field	Meaning	Value type
residue	Binomial coefficient modulo the prime	integer

json

{
  "input": {
    "n": "100",
    "k": "50",
    "prime": 7
  },
  "output": {
    "residue": 4
  }
}

Limitations and assumptions

The modulus must be prime. The output is a residue, not the full binomial coefficient, and both decimal indexes are limited to 200 characters.

Use the declared integer bounds and string formats. Large exact outputs remain decimal strings; numerical approximations use ordinary floating-point arithmetic. A rejected input is different from a valid zero count or false membership flag.

Alternative or Complementary methods

Choose q-Binomial Coefficient Polynomial when you need its operation: Return exact coefficients of the Gaussian binomial [n choose k]_q in ascending degree order, with zero for k>n and indices capped at 64. Choose Modular Inverse for the complementary operation: Find the least nonnegative inverse of a signed decimal integer modulo a decimal modulus of at least two, rejecting noncoprime pairs.

Background reference: Lucas’s Theorem.

References

Lucas’s Theorem — Harvey Mudd College Math Fun Facts

Similar or alternative tools

q-Binomial Coefficient Polynomial
Return exact coefficients of the Gaussian binomial [n choose k]_q in ascending degree order, with zero for k>n and indices capped at 64.
Modular Inverse
Find the least nonnegative inverse of a signed decimal integer modulo a decimal modulus of at least two, rejecting noncoprime pairs.