Agrawal's conjecture, due to Manindra Agrawal in 2002, forms the basis for the cyclotomic AKS test. It states that for two coprime positive integers n and r, if a certain polynomial congruence holds modulo n and X^r - 1, then either n is prime or n squared is congruent to 1 modulo r. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
StatementFor two coprime positive integers n and r, if (X - 1)^n is congruent to X^n - 1 modulo (n, X^r - 1), then either n is prime or n squared is congruent to 1 modulo r. 1 Proposed Year Progress Toward ResolutionComputationally verified for r < 100 and n < 10^10, and for r = 5 and n < 10^11, but a heuristic argument by Pomerance and Lenstra suggests there are infinitely many counterexamples. The Primaboinca distributed computing project (2010 to 2020) found no counterexample searching 10^10 < n < 10^17. 1 Classification
Resolution Status Prize Status
Prize Status (category) Connections
In Branch
Source Agrawal's Conjecture (Wikipedia)
Sources
1. Agrawal's Conjecture (Wikipedia)
Wikimedia FoundationLead section
Agrawal's conjecture, due to Manindra Agrawal in 2002, forms the basis for the cyclotomic AKS test.
Lead section, formal statement
Agrawal's conjecture states formally:
Truth or falsehood section
However, a heuristic argument by Carl Pomerance and Hendrik W. Lenstra suggests there are infinitely many counterexamples.
In Branch: Number Theory, Lead sentence
In number theory, Agrawal's conjecture, due to Manindra Agrawal in 2002, forms the basis for the cyclotomic AKS test.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.