Agrawal's conjecture

Agrawal's conjecture asserts that an integer n is prime exactly when (x+a)^n ≡ x^n+a modulo n holds for every integer a, as a polynomial identity.

Connect

Polynomial congruence: A congruence between polynomials whose coefficients are compared modulo a specified integer. The conjecture's criterion is equality of polynomial coefficients modulo n.
Manindra Agrawal: An Indian theoretical computer scientist known for work on computational complexity and primality testing. He proposed the polynomial identity criterion with Neeraj Kayal and Nitin Saxena.
Polynomial: An expression formed from variables and coefficients using addition, subtraction, and nonnegative integer powers. The conjecture compares two polynomials by their coefficients modulo n.
AKS conjecture: The conjecture that the polynomial identity criterion for primality holds for every integer greater than one. This is another name for Agrawal's conjecture in the primality-testing literature.
Binomial theorem: A formula expanding powers of a sum into terms involving binomial coefficients. Expanding (x+a)^n exposes the coefficients that must vanish modulo n.
Neeraj Kayal: An Indian computer scientist who co-discovered the AKS primality test as a graduate student. Kayal coauthored the paper that stated the conjecture and proved the resulting primality test.
Finite field: A field containing finitely many elements, with addition and multiplication performed within the set. For prime n, residues modulo n form a field, underlying the identity's behavior.
Counterexample: A specific instance showing that a universal mathematical claim is false. A single composite satisfying the identity for every a would refute the conjecture.
Binomial coefficient: An integer counting the ways to choose a fixed-size subset from a finite set. Intermediate coefficients determine whether the polynomial identity holds.
Nitin Saxena: An Indian theoretical computer scientist whose work includes algebraic complexity and primality testing. Saxena coauthored the original AKS paper with Agrawal and Kayal.