On this page
Is 91 prime? A minute of trial division shows 91 = 7 × 13. Now try a number with hundreds of digits, the kind that matters in cryptography. Trial division up to its square root would need more divisions than any computer could ever do. For decades mathematicians had fast tests that were either probably right or relied on an unproven conjecture. In 2002 three people at IIT Kanpur found a test that is both fast and certain. This post explains who they were and the idea behind the test, using numbers small enough to check by hand.
Who is Manindra Agrawal?
According to his Infosys Prize profile, Manindra Agrawal was born on 20 May 1966 in Allahabad. He took his B.Tech (1986) and PhD (1991) in computer science and engineering at IIT Kanpur, and joined its faculty in 1996. The profile records that his joint paper "with two of his former students resolves the centuries-old problem of a fast test of primality". Those students were Neeraj Kayal and Nitin Saxena. He received the Infosys Prize in Mathematical Sciences in 2008, and the Gödel Prize and Fulkerson Prize in 2006.
What did "PRIMES is in P" prove?
The 2006 Gödel Prize citation explains it. In August 2002 the three "presented an unconditional deterministic polynomial time algorithm that determines whether an input number is prime or composite." Earlier polynomial-time tests "were based on probabilistic methods or they relied on an unproven assumption", the generalized Riemann Hypothesis. The citation adds that the preprint "circulated within hours".
"Polynomial time" means the number of steps grows like a fixed power of the number of digits. Trial division up to the square root does not qualify: for a 100-digit number you would need about 10⁵⁰ divisions. The paper, published in Annals of Mathematics in 2004, proves a bound that grows like (log n) to the power 21/2, and a better one using a known result on primes.
What is the key idea?
It starts from Fermat's little theorem: if n is prime, aⁿ leaves the same remainder as a when divided by n. The paper's Lemma 2.1 lifts this to polynomials. For a coprime to n, n is prime if and only if
(X + a)ⁿ = Xⁿ + a (mod n),
meaning every middle coefficient of (X + a)ⁿ is divisible by n. The proof is the binomial theorem: the coefficient of Xⁱ is nCi × aⁿ⁻ⁱ, and for a prime n every nCi with 0 < i < n is a multiple of n.
Worked example: n = 5 and n = 6
Take a = 1.
n = 5. The binomial coefficients are 1, 5, 10, 10, 5, 1. The middle ones, 5, 10, 10, 5, are all multiples of 5. So (X + 1)⁵ = X⁵ + 1 (mod 5), and 5 passes.
n = 6. The coefficients are 1, 6, 15, 20, 15, 6, 1. Here 15 leaves remainder 3 and 20 leaves remainder 2 when divided by 6. The identity fails, so 6 is composite.
Why not just use Fermat's test?
Because some composites pass it. Take n = 341 = 11 × 31. Compute 2³⁴⁰ mod 341 and you get 1, exactly what a prime would give. Base 3 catches it: 3³⁴⁰ mod 341 = 56. Worse, 561 = 3 × 11 × 17 gives a⁵⁶⁰ ≡ 1 (mod 561) for every a coprime to 561, so no such base exposes it. The polynomial identity has no such loophole: for 341 the coefficient 341C11 leaves remainder 31.
There is a catch. (X + 1)ⁿ has n + 1 terms, far too many to check for a huge n. The paper's trick is to check the identity only "mod Xʳ − 1" for a small, carefully chosen r, which keeps the work polynomial, and then to prove that a composite number cannot pass for enough values of a.
Which mistakes does this help you avoid?
Calling 1 prime. The lemma needs n ≥ 2, and so does every definition of a prime.
Trusting one Fermat check. Passing aⁿ⁻¹ ≡ 1 for one base does not prove n prime, as 341 shows.
Assuming nCi is always divisible by n. That holds only for prime n. 4C2 = 6 is not a multiple of 4.
Binomial coefficients and remainders are on the JEE syllabus; our posts on the binomial theorem for JEE and on using it for remainders and divisibility give practice.
What can a student learn from how Agrawal worked?
The Gödel citation notes that the algorithm built on a randomized test by Agrawal and Somenath Biswas from 1999, which the team then made deterministic. The final step came after years on the same question, worked on with students, using simple tools pushed hard. Returning to a problem with a sharper question is often how hard problems give way.
Number theory proofs reward practice with feedback. The Fermi Problem Library has a step-by-step solver that explains the reasoning, so you can check where a divisibility argument went wrong.
Try it now: list the coefficients of (X + 1)⁷ and check that each middle one is a multiple of 7.
