There is a well known Giuga's Conjecture on Primality that states :
$p~$ is a prime iff $~\displaystyle \sum_{i=1}^{p-1} i^{p-1} \equiv -1 \pmod p$
If we define $r_i$ as non-negative integer such that :
$(2i+1)^{p-1} \equiv r_i \pmod p ~\text { and } r_i
then we can formulate following conjecture (in further text : Alexa's conjecture) :
$\text{Positive integer } p~ ;(p\geq 8) \text{ is a prime iff : }$
$$\displaystyle \sum_{i=1}^{\left \lfloor \frac{\sqrt[3] p}{2} \right \rfloor} r_i =\left \lfloor \frac{\sqrt[3] p}{2} \right \rfloor $$
There is no counterexample for this statement below $2\cdot 10^7$ (see Mathematica code below). Also , I checked statement for all Carmichael numbers from this list (see Java code below) and I haven't found any counterexample .
Question :
Using Fermat Little Theorem one can show that if $p$ is a prime then relation from Alexa's conjecture is satisfied , but how to prove vice versa ?
P.S.
I am interested in hints (not full solution) .
EDIT :
Mathematica implementation of Counterexample Searching Algorithm :
For[p = 8, p <= 2*10^7, p++,
For[i = 1; s = 0, i <= Floor[((p)^(1/3))/2], i++,
s = s + PowerMod[2*i + 1, p - 1, p]];
If[s == Floor[((p)^(1/3))/2] && ! (PrimeQ[p]),
Print["counterexample " + p]]];
Java implementation of Counterexample Searching Algorithm (program searches for counterexample from specific list of Carmichael numbers ) :
import java.math.BigInteger;
import java.lang.Math;
import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
public class ACC
{
public static double cubeRoot(double x)
{
return Math.pow(x , 1.0/3);
}
public static void main(String[] args)
{
File file = new File("C:/Users/Pedja/Desktop/txt/input.txt");
try {
Scanner sk = new Scanner(file);
while (sk.hasNextLong())
{
Long e = sk.nextLong();
Double m = e.doubleValue();
BigInteger p;
p = BigInteger.valueOf(e);
BigInteger s;
s = BigInteger.ZERO;
double n;
n = Math.floor(cubeRoot(m)/2);
int k;
k = (int)n;
BigInteger r;
r = BigInteger.valueOf(k);
for (int i = 1; i <= k; i ++)
{
BigInteger j;
j = BigInteger.valueOf(i);
s = s.add(j.multiply(BigInteger.valueOf(2)).add(BigInteger.ONE).modPow(p.subtract(BigInteger.ONE),p));
}
if (s.equals(r) && !(p.isProbablePrime(10)))
{
System.out.println("counterexample :" +e);
}
}
}catch (FileNotFoundException e) {
e.printStackTrace();
}
}
}