Giuga's Conjecture
One sum of powers should tell you whether a number is prime. Does it ever lie?
In plain terms
Take a number n. Raise every smaller number to the power n−1, add them all up, and divide by n. Giuga noticed that when n is prime the remainder is always n−1 — the sum comes out at "−1" in clock arithmetic. He conjectured the reverse too: only primes do this.
That would make one arithmetic test a perfect primality test. The easy half is proved. The open half is that no composite number sneaks through.
What is known
Nobody has found a cheat, and the constraints on what one would have to look like are extraordinary. A composite counterexample must be simultaneously two rare kinds of number — a Carmichael number and a Giuga number — and that forces its prime factors into a tightly interlocking pattern: each prime p dividing n must divide n/p − 1 exactly.
Those constraints are strong enough to search against. In 1996 Borwein, Borwein, Borwein and Girgensohn showed any counterexample must have at least 3459 distinct prime factors, and therefore more than 13,000 digits. In 2013 Borwein, Maitland and Skerritt pushed the bound past 19,908 digits. Nobody tested numbers one at a time to get there — the searches enumerate possible sets of prime factors and rule out whole branches at once.
There is a second face to the problem. Agoh's reformulation says the same thing using Bernoulli numbers, a completely different piece of machinery. The two statements are known to be equivalent, which is unusually convenient: a claim can be checked two ways that share no arithmetic.
Why it is hard
The bounds grow, but they never close. Every search establishes "no counterexample smaller than this", and there is no known reason the answer should be findable at any particular size — a counterexample, if one exists, is under no obligation to be near the current frontier.
Meanwhile the proof side has no purchase. The condition is a statement about every prime factor at once, and there is no known mechanism forcing that pattern to be impossible rather than merely astronomically rare.
What a breakthrough would mean
A proof would hand number theory a clean characterisation of primality by a single congruence — the sum-shaped companion to Wilson's theorem, which does the same job with a product. That is aesthetically satisfying rather than practically useful: computing the sum is far slower than the primality tests everyone actually uses.
A counterexample would be more interesting than a proof. It would be a specific integer with thousands of prime factors, exhibiting a coincidence that all current heuristics say should not happen — and heuristics that are wrong about this would likely be wrong about neighbouring questions on Carmichael numbers too.
For this lab the appeal is different and more practical: it is the problem here where a modest computation, done carefully, produces a real result with a stated range — and where the published frontier can be recovered from scratch first, which is how any search here earns the right to be believed.
What this lab tried
Standing: Evidence Open. Two blind attempts from one cycle: 001 relaxed the counterexample conditions to a reciprocal-sum problem and certified more than 3355 prime factors and 10^10395, with an explicit witness capping that whole family at 8135; 002 established that a counterexample is too large to be an object and went after the ones that are not -- odd Giuga numbers (none below 12 prime factors, and the count must be even) and Giuga sequences (complete to length 6). Read 001 for the bound, 002 for the objects and the closed forms that make any Giuga enumeration cheap.
Every approach below is recorded in full, including the ones that failed and why. Attempt titles link to the complete record.
Attempt 001blindEvidence
Relaxing the counterexample conditions to 'odd primes, none dividing another minus one, reciprocals summing above 1' yields a searchable bound of more than 3355 prime factors and 10^10395, plus an explicit 8135-prime set proving the relaxation can never exceed 8135.
- Range checked
- Congruence formulations cross-checked for n = 2..4000 (Agoh's form to 261); Giuga numbers enumerated exhaustively to 7 prime factors (8 factors aborts, needing candidate primes to 5.4e10); factor bound at branch limit X = 701 over the odd primes below 3e6; size bound at X = 307; ceiling witness of 8135 primes checked over all 66,170,090 ordered pairs.
- Open gaps
- The bound is about a relaxation: it drops the exact Giuga divisibility conditions, so a large admissible set is not a near-counterexample.
- L(X) for X > 73 rests on one search program; only the winning leaf is re-verified exactly, not the claim that no other configuration is smaller.
- Exhaustiveness of the 6- and 7-factor Giuga lists rests on one enumerator, validated by toggling its pruning rules rather than by a second program.
- Cost grows 4-5x per step of the branch limit (18s, 70s, 336s at X = 503, 601, 701), so the ceiling of 8135 is unreachable in pure Python.
- Note
- target_shape is mixed: the deliverable was a lower bound (proof-shaped), but the most durable artifact was the 8135-prime ceiling witness, which is an object a checker settles. The two pushes past the first partial result were the product/digit objective and the explicit ceiling construction. Fields added after the record was written, when the schema gained them; the record prose is unchanged.
Attempt 002blindEvidence
A Giuga counterexample is object-shaped but provably enormous, so this went after the nearby objects that are not: no odd Giuga number below 12 prime factors, its factor count must be even, Giuga sequences complete to length 6, and a closed form (ap-N)(aq-N) = N^2-a that replaces the last-two-primes scan.
- Range checked
- Odd Giuga numbers exhausted at 9, 10, 11 prime factors and odd Giuga sequences at lengths 7-11, with no unresolved branches; Giuga sequences complete for lengths 3-6; the parity law proved for m <= 1411, where k = 1 is forced; the construction search settled 1,059,471,340 window integers across 1,099,847 prefixes at factor counts 3 to 61 on one seed, finding nothing.
- Open gaps
- Nothing is claimed about whether an odd Giuga number exists; the construction search samples a vanishing fraction of prefixes.
- Exhaustiveness beyond length 11 depends on N^2 - a factoring; branches that resist are reported but not resolved.
- The parity law only bites while k = 1, i.e. m <= 1411; beyond that odd factor counts are not excluded.
- Odd lengths 9 and 11 were searched before the parity law was found, and are vacuous -- the only real exclusion in that range is length 10.
- The 8-prime-factor Giuga list and odd sequences of length 12 both did not finish; measured costs are in the record, and neither is reported as evidence of absence.
- Methodological lesson
- Two rounds of compute went into odd factor counts that a two-line parity argument excludes for free. When a search comes back empty at several consecutive sizes, look for a reason those sizes are vacuous before paying for the next one.
Go deeper
Problem statement and published background · Full prior-art notes · Machine-readable index
Found something, or think we got it wrong?
Both are welcome, and the second especially. Nothing here has been peer-reviewed by a human mathematician, so errors are expected rather than embarrassing — one record in this library was already corrected by a later review.
Challenge something on this page · Report an attempt you ran · Browse open issues
scripts/blind.sh giuga ../workMore on blind and informed mode.