Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

An earlier MO question highlighted Giuga's Conjecture:

A positive integer $n>1$ is prime if and only if $$\sum_{k=1}^{n-1} k^{n-1} \equiv -1 \pmod{n}$$

For example, for the prime $n=5$, the sum is $$ 1^4 + 2^4 + 3^4 + 4^4 = 1+16+81+256 \equiv 1+1+1+1\,(\rm{mod}\, 5)\equiv -1(\rm{mod}\, 5) \;. $$ My question is: Is this conjecture in some sense central in the pursuit of prime properties (as is—surely—e.g., Yitang Zhang's and James Maynard's advances related to prime pairs), or is it rather perceived as peripheral to the general understanding of primes? I ask not only because of the spectacular recent advances, but because the iff nature of the conjecture seems almost too good to be true, even though it has been verified out to $10^{13800}$.

share|improve this question
Just because a property is (provably or conjecturally) equivalent to something of interest doesn't make it important. In fact, that might be grounds for the result being less useful because it is not a good reformulation of the concept. For instance, compare the Fermat "primality test" (really, compositeness test), which is not an equivalent condition for being prime, with the Wilson "primality test", which is equivalent to being prime: an integer $n > 1$ is prime iff $(n-1)! \equiv -1 \bmod n$. Nobody uses Wilson's criterion to test primality: it is computationally infeasible. –  KConrad Feb 16 '14 at 3:07
On the other hand, the Fermat test leads to related ideas (Solovay-Strassen test, Miller-Rabin test) all based on exponentiation in modular arithmetic, which is very feasible. Oh, and to answer your question, Giuga's conjecture is not currently considered central. –  KConrad Feb 16 '14 at 3:08
Ordinarily, I'd vote to close on the grounds that this is opinion-based. But in this case, I doubt there'll be much difference of opinion. Giuga's conjecture is a favorite of mine, but central? I doubt anyone feels that way. –  Gerry Myerson Feb 16 '14 at 7:58
Just playing around: let f(n) = -n/(residue mod n between -n and -1 of the Giuga sum); thus the conjecture is that n is prime iff it is a fixed point of f. Numerical experiments show that if f(n) is a non-prime integer, f(n) is prime. Whereas if it is not integer, iteration still makes sense and gives 1 after few steps. Amusing :) It must be easy to find out which numbers give what. –  მამუკა ჯიბლაძე Feb 16 '14 at 9:06
I do not consider either Guiga's conjecture or this (possible) extension of Sylvester-Schur to be central: mathoverflow.net/questions/136299/… . However, both are interesting statements about primes. If they Clay Institute puts a large prize out for their solution, that will make them more prominent. It's way too early in the game to say if these or RH are central to what number theory will be two hundred years from now. –  The Masked Avenger Feb 16 '14 at 17:09

1 Answer 1

Just from browsing the web, it appears there's a 2009 paper by Luca+Pomerance+Shparlinski which proves that the counting function of counterexamples (i.e. composites that satisfy the congruence, so-called Giuga numbers) is at most $O(\frac{\sqrt{x}}{(log(x))^2})$. If the conjecture is true then the real bound is in fact 0. I don't know what blocks further progress (like getting a conditionnal proof, or a finite large bound). It might be some already known barrier (e.g. parity problem) or something entirely different, probably the experts know that.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.