How many primes would a Giuga counterexample need?
- Kind
- Computer-assisted lower bound
- Status
- Proved (computer-assisted): checked by certificates for 8,138 prime divisors and 40,748 digits; Lean-verified for 578 prime divisors and 1,803 digits; unrefereed
- Prior work
- Extends the compatible-prime and reciprocal-sum bounds of Borwein and coauthors
On this page
The statement
For a prime , the sum of over is congruent to modulo . Giuga conjectured that this test characterizes primes. A composite passing it would need at least 8,138 distinct prime divisors and 40,748 decimal digits.
Check it yourself
Two different primes dividing a counterexample cannot satisfy . For example, choosing 3 rules out 7 because . The checker uses these exclusions, a reciprocal-sum condition and a congruence to bound the number and product of the primes. It reconstructs all 15 cases and checks the supplied integer weights.
A constructed set of primes gives a 40,750-digit product satisfying the relaxed local tests. Its cofactor at 5 has remainder 2, whereas Giuga’s condition requires 1. This example bounds the relaxed minimum from above. Finding an actual composite satisfying the congruence remains open.
What was checked
The downloadable checker replays the count and digit bounds with exact integers. The Lean proof gives smaller bounds of 578 factors and 1,803 digits. The manuscript traces the compatible-prime method to Borwein and coauthors and distinguishes their stronger question about prime prefixes from the numerical bounds here.
Prior work
Searches run. Bedocchi (1985), Borwein–Borwein–Borwein–Girgensohn (1996), Borwein–Maitland–Skerritt (2013), and Wong's 1997 thesis (relevant sections) were read, along with dated searches of arXiv (and DataCite), zbMATH Open, OEIS, CORE, OpenAlex (including citers of the 1996 and 2013 papers), Math Stack Exchange, MathOverflow, Zenodo, and GitHub. No source found states a stronger unconditional counterexample bound or a dual conflict-free certificate over tail primes.
Still owed. Google Scholar (including its full cited-by lists for the 1996 paper and Burcsi et al. 2011), follow-up CORE and Semantic Scholar passes, the five unreturned arXiv hits for Giuga, and full texts of Giuga (1950), Agoh (1995), Borwein–Wong (1997), Sorini (2001), Borwein–Bailey–Girgensohn (2004), Banks–Nevans–Pomerance (2009), Skerritt (2014), and Mavrotheris's full lattice proof (2026).