# A variation on Giuga's conjecture

Can you provide a counterexample to the following claim :

Let $n$ be an odd natural number greater than one , let $k$ be a natural number such that $k \le n$ , then $n$ is prime if and only if : $\displaystyle\sum_{i=0}^{k-1}i^{n-1} + \displaystyle\sum_{j=0}^{n-k}j^{n-1} \equiv -1 \pmod{n}$

You can run this test here .

I was searching for a counterexample using the following two PARI/GP codes :

VariationGiuga1(k,ub)={
forcomposite(n=k,ub,
if(Mod(n,2)==1,
s=sum(i=0,k-1,lift(Mod(i,n)^(n-1)))+sum(j=0,n-k,lift(Mod(j,n)^(n-1)));
if((Mod(s,n)==n-1),print("n="n))))
}

VariationGiuga2(k,ub)={
forprime(n=k,ub,
s=sum(i=0,k-1,lift(Mod(i,n)^(n-1)))+sum(j=0,n-k,lift(Mod(j,n)^(n-1)));
if(!(Mod(s,n)==n-1),print("n="n)))
}

• Since $n$ is odd, I think this is identical to the usual Giuga conjecture, isn’t it? The summand at $n-k$ is equal to the summand at $k$, and so on, so the sum mod $n$ is independent of the choice of $k$. – Erick Wong Jan 22 '18 at 20:57
• On the other hand, when $n$ is even, I suspect that there will exist a $k$ that works for some positive proportion of $n$. – Erick Wong Jan 22 '18 at 21:33

This is exactly equivalent to Giuga's conjecture (for odd $n$). Since $n-1$ is even, $(-1)^{n-1} = 1$, and so $(n-j)^{n-1} = (j-n)^{n-1} \equiv j^{n-1} \pmod n$. So the sum of the left is equivalent mod $n$ to
$$\sum_{i=0}^{k-1}i^{n-1} + \sum_{j=0}^{n-k}(n-j)^{n-1} = \sum_{i=0}^{k-1}i^{n-1} + \sum_{i=k}^{n}i^{n-1} = \sum_{i=0}^{n}i^{n-1},$$ which is the defining sum for Giuga's conjecture (ignoring the first and last terms which are trivial).