Factorial divisibility calculator: does a!b! divide n!k!

What this calculator does

Some ratios of factorials are whole numbers and some are not, and which is which is not obvious from the size of the numbers. The binomial coefficient is the familiar case: n! divided by a!(n−a)! is always an integer, even though nothing about the division looks guaranteed. Shift the terms slightly and the guarantee disappears.

This checks a specific shape: whether a!·b! divides n!·k! where k = a + b − n. When a + b = n it reduces to a binomial coefficient and always works. When a and b are both a decent fraction of n and their sum overshoots, it usually fails, and the question of how often it can still succeed is Erdős problem 728, resolved in January 2026.

The formula

Formulaa!b! divides n!k! with k = a + b − n exactly when v_p(a!) + v_p(b!) ≤ v_p(n!) + v_p(k!) for every prime p, where v_p(m!) = Σ floor(m ÷ pⁱ)

Never compute the factorials. Legendre's formula gives the exponent of a prime p in m! as floor(m/p) + floor(m/p²) + floor(m/p³) + …, a sum with only about log_p(m) terms. The division works exactly when, for every prime, the exponent on top is at least the exponent underneath. The calculator checks every prime up to n and reports the first one that fails, along with the primes where the margin is tightest.

Term	Meaning
n, a, b	The three inputs. a and b should each be at most n.
k	Shorthand for a + b − n. It must not be negative, so a + b has to reach n.
v_p(m!)	The exponent of the prime p in m!, given by Legendre's formula.
Slack	How much room a prime has: the exponent available minus the exponent needed. A negative slack is a failure.
Density	min(a, b) ÷ n. Erdős problem 728 is about keeping this bounded away from zero.

The inputs explained

Field	What to enter
n	The largest of the three. Capped at 20,000 to keep the prime sieve quick.
a	At most n, and a + b must be at least n.
b	At most n, and a + b must be at least n.

When to use it

Checking a binomial coefficient

Set a + b = n, for example n = 100 with a = b = 50. Then k = 0, the test reduces to whether a!b! divides n!, and the quotient is the binomial coefficient C(100,50), a 30-digit whole number. This case always succeeds.

Finding where it fails

Raise a and b so their sum overshoots n. The first failing prime is usually small, because small primes accumulate the largest exponents and therefore have the least room. The slack table shows which primes are closest to the edge.

Exploring Erdős problem 728

The problem asks whether there are infinitely many triples where the divisibility holds while a and b both stay at least a fixed fraction of n. Solutions are rare and the search is not something to do by hand, which is part of why the problem stood for so long.

Worked examples

Every figure in the tables below is produced by this page’s own calculator at build time, so the numbers and the tool always agree. Select any row to load that scenario.

When does the divisibility hold?

a rises, so a + b overshoots n by more and more.

n fixed at 100, b fixed at 70

a	Does a!·b! divide n!·k!	k = a + b − n	First prime that fails
30	Yes	0	none
40	No	10	13
50	No	20	7
60	No	30	17
70	No	40	7
80	No	50	2

At a = 30 the sum is exactly 100, so k = 0 and the test is a binomial coefficient, which always divides. Every row above that overshoots and every one of them fails, with the first failing prime small in each case. That is the typical behaviour, and it is why the existence of infinitely many successes with a and b both large was a genuine question rather than an obvious yes.

What happens as the overshoot closes?

n climbs towards 100, which shrinks k from 40 down to nothing.

a and b both fixed at 50, so a + b is always 100

n	Does a!·b! divide n!·k!	k = a + b − n	Density min(a,b) ÷ n
60	No	40	0.833
70	No	30	0.714
80	No	20	0.625
90	No	10	0.556
100	Yes	0	0.500

Only the last row divides. With a and b both held at 50 the product a!b! never changes, and shrinking the overshoot by raising n does not rescue the divisibility until it vanishes entirely at n = 100, where the quotient becomes C(100,50) and runs to 30 digits. The density column shows the tension in Erdős problem 728: keeping min(a,b) ÷ n high is easy on its own and the divisibility is easy on its own, and the difficulty is holding both at once.

Questions

Why not just compute the factorials and divide?

Because they overflow almost immediately. 100! has 158 digits and 20,000! has over 77,000. Legendre's formula answers the divisibility question using only the prime exponents, which stay small.

What is Erdős problem 728?

It asks whether there are infinitely many triples (a, b, n) with a and b both at least a fixed fraction of n for which a!b! divides n!(a+b−n)!. It was resolved in January 2026 by a proof generated by GPT-5.2 Pro and formalised in Lean by Harmonic's Aristotle.

Why is the first failing prime usually small?

Because small primes have the largest exponents in a factorial, so a small imbalance in the counts shows up there first. The slack table makes that visible: the tightest primes are nearly always at the bottom of the list.

What happens when k is zero?

0! is 1, so the test becomes whether a!b! divides n! with a + b = n. That is exactly the statement that the binomial coefficient is a whole number, which it always is.

Is the quotient the number of digits shown?

The digit count comes from summing the prime exponents times their logarithms, so it is exact rather than an estimate, but the quotient itself is far too large to print for most inputs.

For the related whole-number ratios, see permutations and combinations and binomial expansion. How the problem was solved is in the piece on Erdős problem 728.