2
$\begingroup$

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)))
}
$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Erick Wong Jan 22 '18 at 20:57
  • $\begingroup$ On the other hand, when $n$ is even, I suspect that there will exist a $k$ that works for some positive proportion of $n$. $\endgroup$ – Erick Wong Jan 22 '18 at 21:33
1
+50
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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