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 : Java implementation of Counterexample Searching Algorithm (program searches for counterexample from specific list of Carmichael numbers ) :
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]]];
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(); } } }