Agoh–Giuga Conjecture

The Agoh–Giuga conjecture states that p is prime if and only if:

∑_{i=1}^{p-1} i^{p-1} ≡ -1 (mod p)

The forward direction (prime → congruence) is a direct consequence of Fermat's little theorem: each nonzero element of ZMod p raised to the (p-1)-th power equals 1, so the sum is (p-1) · 1 = p - 1 ≡ -1 (mod p).

The reverse direction is open: no composite number satisfying the congruence is known, but neither has it been proved that none exists. A composite counterexample would need to be both a Carmichael number and a Giuga number, with at least 13,800 digits.

References

• Agoh, T. (1990). "On Giuga's conjecture". Manuscripta Mathematica.
• Giuga, G. (1950). "Su una presumibile proprietà caratteristica dei numeri primi".

def giugaSum (n : ℕ) : ZMod n

The Giuga sum: ∑_{i=1}^{n-1} i^(n-1) computed in ZMod n.

Equations

• giugaSum n = ∑ i ∈ Finset.range (n - 1), ↑(i + 1) ^ (n - 1)

theorem agoh_giuga_forward (p : ℕ) [hp : Fact (Nat.Prime p)] : giugaSum p = -1

Forward direction of the Agoh–Giuga conjecture.

If p is prime, then ∑_{i=1}^{p-1} i^{p-1} ≡ -1 (mod p).

Each term equals 1 by Fermat's little theorem, so the sum is (p - 1) · 1 = p - 1 = -1 in ZMod p.