# Sufficient condition for simple primality criterion?

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<p ~ \text{, where } i,p \in \mathbb{N}$

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

}

if (s.equals(r) && !(p.isProbablePrime(10)))

{
System.out.println("counterexample :" +e);

}
}

}catch (FileNotFoundException e) {

e.printStackTrace();
}

}
}

-
Whatever be the case, please clarify it in the question! –  Aryabhata Mar 30 '12 at 17:13
@pedja: This is silly. It is not at all clear who Alexa is, or how long the conjecture has been open. Not everyone reads the comments, so every relevant information must be in the question. I suggest you also read this meta thread: meta.math.stackexchange.com/questions/3860/… –  Aryabhata Mar 30 '12 at 17:54
Who is Alexa? What is the source of this conjecture? Did you show that the conjecture is true up to $10^7$ or did that come from another source? Please include the relevant context and links. –  Antonio Vargas Apr 1 '12 at 18:26
@pedja the source of the conjecture may be irrelevant to the conjecture itself but it is certainly not irrelevant to my (and probably others') motivation to think about it. –  Antonio Vargas Apr 1 '12 at 18:41
in some area of math, and this conjecture comes after a certain theorem, that is a type of information which actually can be extremely important for the problem.... If it is a random name, or your girlfriend, or the computer on which you run the simulation, then I agree it is irrelevant to the question, but in math if a conjecture is named after someone, that person made lots of research on the subject.Anyhow, right now, it sounds like this: "I need your help with this problem, but I don't wanna tell you anything, you just have to spend more time helping me because I like it this way"... ;) –  N. S. Apr 1 '12 at 18:54

First The conjecture you made is false the way you stated. The left side is much larger then the right side, and Fermat Little Theorem can only prove that the two numbers are congruent modulo $p$. I guess that this is what you actually mean.

Second It is easy to make up conjectures in number theory, and often pretty hard to figure how hard they really are. In all these cases, you should explain your motivation for this "conjecture", the reason why you became interested in the problem, the reason why you suspect it is true (for example I tested it by computer up to $2\cdot 10^7$) and what you tried so far.

And personally I don't think that going and asking for help only "one hour after discovering this conjecture"; which is a research level type of question, is the right thing to do. You should not expect other people to spend lots and lots of time on a problem you can't waste more than 1 hour...

The fact that you used Giuga's conjecture in your post shows that you suspect this is a hard question, which in my opinion means that you should spend much more time on it before going for help. And more importantly, when you ask for help for a very hard research type question, you should start by listing all things you tried so far (so people don't waste time trying the same thing). While this is not necessary for assignment problems, because these are easy problems, I think this is needed for "invented conjectures", especially in a domain like number theory where it is very easy to discover extremely hard problems.

The main reason why people ask for feedback is because if this is an homework it means it has an easy solution, while if it is an invented problem we could end up spending months of work trying to prove it....

Last a hint (don't know how good it is, I know some number theory but this is not my domain), if you used FLT to prove the converse, I think the next thing you should do is check if you can find a counterexample which is a Carmichael number. Did you try this?

-
Why do you think that only Carmichael numbers can be counterexamples ? I have checked conjecture for all Carmichael numbers from this list ,and I haven't found any counterexample... –  pedja Apr 1 '12 at 18:23
I didn't say that only they can be counterexamples. But since FLT holds for Carmichael numbers, whenever when you use FLT to prove a statement, and you are looking for a counterexample for the converse, Carmichael numbers look to me like the natural "first try".... –  N. S. Apr 1 '12 at 18:27

We want to prove :

If $\displaystyle \sum_{i=1}^{\left \lfloor \frac{\sqrt[3] p}{2} \right \rfloor} r_i =\left \lfloor \frac{\sqrt[3] p}{2} \right \rfloor$ then $p$ is a prime number .

a) Composite numbers of specific form :

Let $p$ be a composite number of the form :

$p=p^{a_1}_1\cdot p^{a_2}_2 \ldots p^{a_k}_k$ , where $p_1,p_2 , \ldots p_k$ are distinct primes and $k>2$ .

Next , let $p_i$ be a prime factor of $p$ such that :

$p_i \leq 2 \cdot \left \lfloor \frac{\sqrt[3] p}{2} \right \rfloor +1$

We will show that :

If $~p^{p-1}_i \equiv r_i \pmod p ~\text{then}~ r_i >1$

$1.$ suppose $r_i=1$

According to Euler Theorem :

If $~\gcd(p_i,p)=1~$ then $~p^{\varphi(p)}_i \equiv 1 \pmod p$

$\bullet$ if $p$ is a prime then $p^{p-1}_i \equiv 1 \pmod p$

$\bullet$ if $p$ is a pseudoprime or composite such that $\varphi(p) \mid p-1$ then $p^{p-1}_i \equiv 1 \pmod p$

By contraposition of Euler Theorem it follows :

if $~\gcd(p_i,p) \neq 1~$ then $~p^{p-1}_i \not\equiv 1 \pmod p$

So , since $~\gcd(p_i,p) \neq 1~$ it follows $r_i \neq 1$

$2.$ suppose $r_i=0$

According to the contraposition of Chinese Remainder Theorem :

$$\text{ iff } \begin{cases} p^{p-1}_i \not\equiv 0 \pmod {p^{a_1}_1} \\ p^{p-1}_i \not\equiv 0 \pmod {p^{a_2}_2} \\ \vdots \\ p^{p-1}_i \equiv 0 \pmod {p^{a_i}_i} \\ \vdots \\ p^{p-1}_i \not\equiv 0 \pmod {p^{a_k}_k} \end{cases} ~\text { then }~ p^{p-1}_i \not \equiv 0 \pmod {p^{a_1}_1\cdot p^{a_2}_2 \ldots p^{a_k}_k}$$

hence $~p^{p-1}_i \not \equiv 0 \pmod p ~$ and therefore $r_i \neq 0$

So , since $r_i \neq 0 \text { and } r_i \neq 1$ it follows $r_i > 1 ~(\star)$

Now suppose that all other odd numbers less than $2 \cdot \left \lfloor \frac{\sqrt[3] p}{2} \right \rfloor +1$ , except $p_i$ are coprime to $p$ ,so :

If $~\gcd(2i+1,p)=1$ then $p \not \mid (2i+1)^{p-1}$ hence $r_i \geq 1 ~(\star \star)$

According to $(\star)$ and $(\star \star)$ we can conclude :

$\displaystyle \sum_{i=1}^{\left \lfloor \frac{\sqrt[3] p}{2} \right \rfloor} r_i >\left \lfloor \frac{\sqrt[3] p}{2} \right \rfloor$ , so we have contradiction .

One can draw same conclusion if some of odd numbers less than $2 \cdot \left \lfloor \frac{\sqrt[3] p}{2} \right \rfloor +1$ , (that are not equal to $p_i$) , are not coprime to $p$ .

Since all Carmichael numbers are numbers of this specific form it means that : Carmichael numbers cannot satisfy equality from conjecture .

b) Possible counterexamples :

Consider a composite numbers of the form :

$p=p^{a_1}_1 \cdot p^{a_2}_2$ where $1 \leq a_1,a_2 \leq 2$ such that :

$p_1 >2 \cdot \left \lfloor \frac{\sqrt[3] p}{2} \right \rfloor +1 ~\text { and } p_2 > 2 \cdot \left \lfloor \frac{\sqrt[3] p}{2} \right \rfloor +1$

Since $\gcd(2i+1,p)=1$ for all $i$ it follows :

$\displaystyle \sum_{i=1}^{\left \lfloor \frac{\sqrt[3] p}{2} \right \rfloor} r_i \geq\left \lfloor \frac{\sqrt[3] p}{2} \right \rfloor$

LHS can be equal to the RHS if there is a such composite number p with property : $\varphi(p) \mid p-1$ or if $p$ is a pseudoprime for all odd bases from interval : $\left[3,2 \cdot \left \lfloor \frac{\sqrt[3] p}{2} \right \rfloor +1\right]$

According to the Lehmer's conjecture if there is such composite number $p$ with property $\varphi(p) \mid p-1$ then $p$ must be divisible by at least seven primes , therefore $p^{a_1}_1 \cdot p^{a_2}_2$ cannot be such number . So the only remaining possibility for $p$ to be a counterexample to the conjecture is that $p$ should be a pseudoprime for all odd bases from interval $\left[3,2 \cdot \left \lfloor \frac{\sqrt[3] p}{2} \right \rfloor +1\right]$ .

c) Conclusion

According to this analysis possible counterexample has to be both odd semiprime and Fermat pseudoprime to the all odd bases from the interval : $\left[3,2 \cdot \left \lfloor \frac{\sqrt[3] p}{2} \right \rfloor +1\right]$ .

-