The Agoh-Giuga Conjecture

Number theory accommodates a lot of conjectures and a lot of them resist proof attempts since many years or even decades. Most of them have to do with prime numbers and its behaviour. 

One of those conjectures is the Agoh-Giuga Conjecture (AGC). Actually, it was Guiseppe Giuga who formulated the conjecture in 1950 and Takasi Agoh reformulated it 40-years later.

The original statement from Giuga was the following:

[Agoh-Giuga-Conjecture] The integer \(p\) is a prime number if and only if $$\sum^{p-1}_{k=1}k^{p-1} \equiv -1\pmod{p}$$

and the reformulation due to Agoh is

[Agoh-Giuga-Conjecture] The integer \(p\) is a prime number if and only if $$pB_{p-1} \equiv -1\pmod{p}$$

It is not hard to show that these two formulations are actually equal.


Proof. [Equality]. As usual we define \(s_n(x) := \sum^x_{k=1}k^n\). So the AGC says \(s_{p-1}(p-1)\equiv -1\pmod{p}\). Power sums could also be expressed in terms of Bernoulli Polynomials, in particular \( s_n(x) = \frac{B_{n+1}(x+1)-B_{n+1}(0)}{n+1} \), whereof the Bernoulli Polynomial is defined as \(B_n(x) = \sum^n_{k=0}\binom{n}{k}B_kx^{n-k}\) and \(B_k\) is the \(k\)-th Bernoulli number. Hence
$$s_{p-1}(p-1) = \frac{B_{p}(p)-B_{p}(0)}{p}$$ which is equal to
$$s_{p-1}(p-1) = \frac{ \sum^p_{k=0}\binom{p}{k}B_kp^{p-k}-B_p}{p}$$
$$s_{p-1}(p-1) = \frac{\sum^{p-1}_{k=0}\binom{p}{k}B_kp^{p-k}}{p} = \frac{\sum^{p-2}_{k=0}\binom{p}{k}B_kp^{p-k}}{p} + \frac{pB_{p-1}p}{p}$$
Each term in the sum of the RHS is a multiple of \(p\). Thus, reducing both sides modulo \(p\) one gets
$$s_{p-1}(p-1) = \sum^{p-1}_{k=1}k^{p-1} \equiv  pB_{p-1} \pmod{p}$$ Q.e.d.
One could understand the Agoh-Giuga conjecture are the additive counterpart to Wilson's Theorem, i.e.,  a characterisation of a prime number in terms of sums of integers.
$$\text{Wilson's Theorem}\;\; p\in \mathbb{P} \Leftrightarrow \prod^{p-1}_{k=1}k \equiv -1\pmod{p}$$ $$\text{AGC}\;\; p \in \mathbb{P} \Leftrightarrow \sum^{p-1}_{k=1}k^{p-1} \equiv -1\pmod{p}$$

In this series of posts i will give a further reformulation for the Agoh-Giuga conjecture, that i have not seen in the literature so far.

To begin, we first compute the value \(s_{p-2}(p-2)\), that is $$s_{p-2}(p-2) = \frac{B_{p-1}(p-1)-B_{p-1}(0)}{p-1} $$ Switching to \(\mathbb{F}_p\) $$s_{p-2}(p-2) \equiv -\left(B_{p-1}(p-1)-B_{p-1}\right)\pmod{p}$$ which is $$(*)\;s_{p-2}(p-2) \equiv -\left(\sum^{p-1}_{k=0}\binom{p-1}{k}B_k(-1)^{-k}-B_{p-1}\right)\pmod{p}$$ The generalization of Wilson's Theorem says that \((n-1)!(p-n)!\equiv (-1)^n\pmod{p}\) which allows to rewrite the binomial coefficients \(\binom{p-1}{k} = \frac{(p-1)!}{k!(p-1-k)!}\) as $$\frac{(p-1)!}{k!(p-(k+1))!} \equiv \frac{-1}{(-1)^{k+1}} \equiv (-1)^k \pmod{p} $$ hence (*) turns into $$s_{p-2}(p-2) \equiv -\sum^{p-2}_{k=0}B_k \pmod{p}$$ \(s_{p-2}(p-2)\) just sum over all integers from \(\mathbb{F}_p\) except \(-1\) hence $$(\text{Eq}.1)\;\;\;\;-1 \equiv \sum^{p-2}_{k=0}B_k \pmod{p}$$ The denominator of the \(n\)-th Bernoulli number is defined as \(\prod_{(q-1)|n}q\) for primes \(q\), hence all Bernoulli numbers \(B_n\) for \(0 \leq n \leq p-2\) are well defined in \(\mathbb{F}_p\).

A further fact from Wilson's Theorem is that $$\binom{p-2}{k} \equiv (-1)^k(k+1)\pmod{p}$$ . All odd Bernoulli number, except \(B_1 = -1/2\) are zero and it holds $$\sum^{n-1}_{k=0}\binom{n}{k}B_k = 0$$ Setting \(n=p-2\) we get
$$  \sum^{p-3}_{k=0}\binom{p-2}{k}B_k \equiv \sum^{p-3}_{k=0}(-1)^k(k+1)B_k \equiv 0\pmod{p}$$
$$  \sum^{p-3}_{k=0}(-1)^k(k+1)B_k \equiv \sum^{p-3}_{k=0}(k+1)B_k  - 4B_1\equiv 0\pmod{p}$$ Using Eq. 1 and the fact that \(p-2\) is odd and thus \(B_{p-2} = 0\) and
$$(\text{Eq}.2)\;\;\;\;\sum^{p-2}_{k=0}(k+1)B_k \equiv -2 \pmod{p} $$
If one increases the upper bound of the sum of LHS form \(p-2\) to \(p-1\), the additional summand for the LHS is \(pB_{p-1}\) and \(-1\) for the RHS. That means we use the equation from the AGC. So at least for prime numbers, we know that
$$(\text{Eq}.3)\;\;\;\;\sum^{p-1}_{k=0} (k+1)B_k \equiv -3 \pmod{p} $$
 Note that Eq. 3 is not equivalent to the AGC, since for a composite integer \(n\) it could hold that Eq. 2 is congruent to \(a\) and \(nB_n \equiv b \pmod{n}\) and \(a+b\equiv -3 \pmod{n}\).

What could be said about Eq.2 for a composite modulus \(n\)? Bernoulli numbers are rational numbers, so one could ran into problems if the denominator contains a factor from \(m\) that does not cancel out.

So to circumvent this problem, we use another way. Bernoulli numbers have an integer counterpart, the Genocchi numbers \(G_n\). They are defined as
$$ G_n = 2(1-2^n)B_n = 2B_n - 2^{n+1}B_n, \;\;\;\text{with}\;G_n \in \mathbb{Z}, B_n \in \mathbb{Q} $$ Using again the Bernoulli polynomial power sum expression $$ s_n(x) = \sum^x_{k=1}k^n = \frac{B_{n+1}(x+1)-B_{n+1}(0)}{n+1} = \frac{1}{n+1}\sum^{n}_{k=0}\binom{n+1}{k}B_kx^{n+1-k}$$ We now set \(x = (p-1)/2\)
$$\sum^{(p-1)/2}_{k=1}k^n  = \frac{1}{n+1}\sum^{n}_{k=0}\binom{n+1}{k}B_k\left(\frac{p-1}{2}\right)^{n+1-k}$$
which is equal to
$$(\text{Eq}.4)\;\;\;\;(n+1)2^{n+1}\sum^{(p-1)/2}_{k=1}k^n  =\sum^{n}_{k=0}\binom{n+1}{k}(p-1)^{n+1-k}B_k2^{k}$$ Now doing the same with \(x = p-1\)
$$(\text{Eq}.5)\;\;\;\;(n+1)\sum^{p-1}_{k=1}k^n  =\sum^{n}_{k=0}\binom{n+1}{k}(p-1)^{n+1-k}B_k$$
Mutliplying Eq. 4 and Eq. 5 with \(2\) and subtracting Eq. 5 from Eq.4, yields
$$(n+1)2\left(2^{n+1}\sum^{(p-1)/2}_{k=1}k^n - \sum^{p-1}_{k=1}k^n\right)  =\sum^{n}_{k=0}\binom{n+1}{k}(p-1)^{n+1-k}B_k(2^k-1)2$$ And hence
$$(n+1)2\left(2^{n+1}\sum^{(p-1)/2}_{k=1}k^n - \sum^{p-1}_{k=1}k^n\right)  = -\sum^{n}_{k=0}\binom{n+1}{k}(p-1)^{n+1-k}G_k$$
So we removed the fractional Bernoulli numbers and replaced them with the Genocchi numbers, which let us safely bring this into a ring \(\mathbb{Z}_N\) for some composite integer \(N\).