How many primes would a Giuga counterexample need?

Edition 3 · On this site since · last revised · Verify & co-author
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
  1. The statement
  2. Check it yourself
  3. What was checked
  4. Prior work

The statement

For a prime nn, the sum of kn−1k^{n-1} over 1≤k<n1 \le k < n is congruent to −1-1 modulo nn. 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 p,qp,\allowbreak q dividing a counterexample cannot satisfy p∣q−1p\mid q-1. For example, choosing 3 rules out 7 because 7−1=67-1=6. 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).