-4
$\begingroup$

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();  }    }   } 
  • 1
    You're asking for help on proving a conjecture which has been open for 60 years. By _definition_ of "open conjecture", no one knows how to solve this!2012-03-30
  • 0
    @Charles I am not asking for help on proving Giuga's conjecture . It seems that you have misunderstood my question .2012-03-30
  • 0
    But you are asking for a proof of Alexa's conjecture? (which is suppose, is still open?). If not, what exactly is your question? Also, your first $\sum$ is missing its term.2012-03-30
  • 0
    @Aryabhata Alexa's conjecture is a brand new conjecture and it is opened an hour ago . We shall see if it will stay open in a next few days .2012-03-30
  • 1
    @pedja: Then please state so clearly that it is a problem you made...2012-03-30
  • 0
    @Aryabhata Actually Alexa made it not me....2012-03-30
  • 2
    Whatever be the case, please clarify it in the question!2012-03-30
  • 0
    @Aryabhata I think that question is clear enough...2012-03-30
  • 6
    @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: http://meta.math.stackexchange.com/questions/3860/unsolved-problem-asked-as-a-question-in-math-se2012-03-30
  • 0
    @Aryabhata Thanks for the link...2012-03-30
  • 2
    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.2012-04-01
  • 0
    my guess is the Alexa= pedja...2012-04-01
  • 0
    @AntonioVargas I can include into post java program that I wrote which examines a conjecture but it is too long2012-04-01
  • 0
    @N.S. I am not Alexa ,I think that Alexa's identity is irrelevant for this question..2012-04-01
  • 3
    @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.2012-04-01
  • 0
    I think the question about Alexa's identity is to shred some light both on the background of the problem, and also to why a problem in number theory got the fancy name of "Alexa Conjecture" after only one hour of being discovered... I know the identity of Alexa is irrelevant, but as Antonio said the background of the problem is relevant for us...2012-04-01
  • 2
    I'm hoping this doesn't come out the wrong way, but it is not our job to solve your problems, it is our pleasure to do this. Solving problems take time, and some problems (this might or might not be one) could actually take lots of time. If you need our help, you have to help us by cooperating and providing some background for the problem (we don't ask for your height or DOB), and this is only fair. And many times in problems like this, an information which seems irrelevant to the poster might actually not be irrelevant... If Alexa is a mathematician which did some research....2012-04-01
  • 5
    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"... ;)2012-04-01
  • 0
    If $p$ is prime then $r_i=1$ for all $i$ up to $(p-1)/2$, so $\sum_1^Qr_i=Q$ for all $Q$ up to $(p-1)/2$. One might pick any $Q$ and conjecture that $\sum_1^Qr_i=Q$ if and only if $p$ is prime. So, why are we particularly interested in $Q=\root3\of p/2$?2012-04-02
  • 2
    By the way, this is essentially http://math.stackexchange.com/questions/124647/counterexample-to-the-general-primality-criteria, which pedja deleted when posting the current question. I am amused that pedja, who had never heard of Giuga's conjecture until two days ago, now calls it "well-known".2012-04-02
  • 0
    @GerryMyerson I guess because Carmichael numbers have at least three prime factors...by the way I am glad that this question amusing you...2012-04-02

2 Answers 2

0

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]$ .

7

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?

  • 0
    Why do you think that only Carmichael numbers can be counterexamples ? I have checked conjecture for all Carmichael numbers from [this list](http://www.kobepharma-u.ac.jp/~math/notes/note02.html) ,and I haven't found any counterexample...2012-04-01
  • 0
    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"....2012-04-01