Lucas theorem calculator
Get C(n, k) modulo a prime without huge factorials: C(1000, 200) modulo 7 is 1, found by writing both numbers in base 7 and multiplying small digit binomials. The digits are listed so you can check every step. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- N
- 1,000
- K
- 200
- Power (W)
- 7
- Result
- 1
- N digits
- 6, 2, 6, 2
- K digits
- 4, 0, 4, 0
Lucas' theorem is the standard way to evaluate a binomial coefficient modulo a prime when n is large enough that n factorial is impractical. The product is exactly C(n, k) mod p; if any lower digit exceeds the matching upper digit, the whole value is zero. Contest programming, combinatorial number theory, and cryptography homework all need this reduction when direct factorials overflow or cost too much.
What Lucas' theorem states and when you need it
In elementary combinatorics the binomial coefficient C(n, k) counts k-subsets of an n-set and equals n factorial divided by k factorial times (n minus k) factorial. That closed form is useless as soon as n grows past a few thousand if you only need the answer modulo a small prime: the intermediate factorials explode, and floating-point approximations lose the exact residue. Lucas' theorem, named after Édouard Lucas, solves exactly this modular problem.
Each factor uses arguments smaller than p, so it can be computed with a short multiplicative loop and modular inverses that exist because p is prime and every denominator is smaller than p. questions without computing a full product. The theorem requires p to be prime; for composite moduli the same digit product is not valid in general, and this capacity deliberately refuses non-prime p rather than silently returning a wrong residue.
Students meeting the theorem in olympiad material, developers wiring competitive-programming libraries, and instructors preparing modular-arithmetic labs all benefit from a single deterministic function that both enforces the prime hypothesis and exposes the digit expansions used in the proof.
How this calculator applies Lucas' theorem step by step
Call the capability with integer fields n, k, and p. Both n and k must be non-negative integers at most one trillion; p must be a prime between two and one million three inclusive. The implementation validates types and bounds first, then runs a deterministic trial-division primality test on p.
When p is accepted, the solver walks the base-p digits of n and k from least significant to most significant. Each small binomial uses the multiplicative formula with modular inverses via Fermat’s little theorem (a to the power p minus two modulo p), implemented with exact BigInt intermediate products so no precision is lost inside the published bounds.
Edge cases are stable and documented: when k is zero or equals n the result is one modulo p (or zero only if p equals one, which is rejected); when k exceeds n the result is zero; when n and k are both zero the digit arrays are the single digit zero and the result is one modulo p.
What you can do with it
Contest programming and olympiad practice
Competitive programmers can verify C(n, k) mod p for large n against sample cases and see an explicit error when a modulus is accidentally composite.
Number-theory and combinatorics teaching labs
Instructors and students can inspect base-p digits alongside the modular product while learning Lucas' theorem and the prime-divisibility zero test.
FAQ
What happens if p is not prime?
The message states that p must be a prime (for example when p is composite or equal to 1). Failed validation is not charged.
Which algorithm computes the modular binomial?
Small digit binomials use the multiplicative formula with modular inverses.
Is the Lucas theorem binomial calculator free?
The browser tool runs free on your device.
What ranges of n, k, and p are accepted?
n and k must be non-negative integers at most 1,000,000,000,000. p must be a prime from 2 through 1,000,003. Values outside those limits, or composite p, are rejected.
How can I tell if C(n, k) is divisible by a prime?
Write n and k in base p and compare them digit by digit. If any digit of k is larger than the matching digit of n, the result is 0, which means p divides the binomial coefficient.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your stack
curl -X POST https://api.kit.forhosting.com/numth/lucas-theorem-binomial \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":1000,"k":200,"p":7}'const res = await fetch("https://api.kit.forhosting.com/numth/lucas-theorem-binomial", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 1000,
"k": 200,
"p": 7
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/lucas-theorem-binomial",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 1000,
"k": 200,
"p": 7
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/lucas-theorem-binomial", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":1000,"k":200,"p":7}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":1000,"k":200,"p":7}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/lucas-theorem-binomial", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Example request
{
"n": 1000,
"k": 200,
"p": 7
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.lucas_theorem_binomial",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
Given non-negative integers n and k and a prime modulus p, the theorem expands n and k in base p and multiplies the small digit binomials C(n_i, k_i) modulo p. This calculator accepts n, k, and p, rejects composite moduli with a clear invalid_input error, runs a deterministic Lucas walk, and returns the modular result together with the base-p digits so you can audit every step without re-deriving the expansion by hand.
What Lucas' theorem states and when you need it
Write n and k in base p as sequences of digits n_i and k_i, each digit strictly less than p. Then C(n, k) is congruent modulo p to the product over i of C(n_i, k_i). A crucial corollary is the zero test: if for any position the lower digit k_i is greater than n_i, that digit binomial is zero and therefore C(n, k) is divisible by p. This zero test alone answers many “is the binomial divisible by this prime?”
How this calculator applies Lucas' theorem step by step
Composite values, one, zero, and negatives all fail with invalid_input and a message that names p; those failures are not charged. For every pair (n_i, k_i) it either short-circuits to zero if k_i exceeds n_i, or multiplies the running product by C(n_i, k_i) mod p. The response returns n, k, p, result (the residue in zero through p minus one), is_zero, the arrays n_digits and k_digits in least-significant-first order, and method set to the string lucas.
Practical use, limits, pricing, and delivery
Use the browser tool when you want a quick Lucas check while reading a number-theory note, verifying a contest sample, or debugging a modular-combinatorics routine. Accepted inputs are non-negative integers n and k up to one trillion and primes p from two through one million three. If you need the unrestricted integer C(n, k), a binomial row for all k, or modular binomials for composite moduli via Chinese Remainder Theorem, use a dedicated capacity; this tool deliberately stops at Lucas for a verified prime p so the contract stays simple and auditable. Use the API when a grader, teaching platform, or script needs many C(n, k) mod p evaluations without embedding a prime gate and a digit walk. Each successful request is one billable item at $0.002; validation failures and non-prime moduli do not consume balance. Results are deterministic: the same triple always yields the same residue, the same digit arrays, and the same is_zero flag. Wire the endpoint into olympiad helpers, competitive-programming sandboxes, cryptography teaching demos that touch binomial coefficients modulo small primes, or any integer pipeline that already prefers exact modular arithmetic over approximate libraries. Because the unit is a single item and the engine is pure parse, latency stays low and the free web channel mirrors the paid API without a second code path that could drift.
Integration use cases
Homework graders and modular pipelines
Automated graders and scripts can confirm residues, detect non-prime p via invalid_input, and keep every intermediate product inside documented bounds.
Technical questions
How do I compute C(n,k) mod p with this API?
Send JSON with integer fields n, k, and p (p a prime) to numth.lucas_theorem_binomial. On success the response returns result in 0..p−1, is_zero, base-p digit arrays, and method "lucas".