4
$\begingroup$

How to prove following statement :

Let $~p~$ be Thabit $(321)$ prime of the form : $p=3\cdot 2 ^n-1$

and let $~n~$ be an odd number then :

$~5~$ is a primitive root modulo $~p~$ iff $~n \equiv 3,7 \pmod 8 $

I have checked statement for following consecutive odd exponents :

$n \in \{1,3,7,11,43,55,103,143 \}$

I guess that one should prove that :

$ord_p(5)=2\cdot(3\cdot 2^{n-1}-1)$


Added :

Note that if : $n \equiv 3,7 \pmod 8$ then : $p \equiv 3 \pmod 5$

Le't assume that :

$ord_p(5)=3\cdot 2^{n-1}-1$ , and $~3\cdot 2^{n-1}-1$ is a prime number ,so:

$$5^{3\cdot 2^{n-1}-1} = 5^{\frac{p-1}{2}} \equiv 1 \pmod p ~~\text {and}~~\left(\frac{5}{p}\right) \equiv 5^{\frac{p-1}{2}} \pmod p \Rightarrow$$

$$\Rightarrow \left(\frac{5}{p}\right) = 1 \Rightarrow p \equiv 1,4 \pmod 5$$

which is contradiction since : $p \equiv 3 \pmod 5$ , therefore :

$ord_p(5) = 2 \cdot(3\cdot 2^{n-1}-1)$ , since it cannot be $2$ , so :

$5$ is primitive root modulo $p$ if both $~3\cdot 2^{n}-1 ~~\text{and}~~ 3\cdot 2^{n-1}-1$ are prime numbers .


However , I didn't manage to prove case when $~3\cdot 2^{n-1}-1~$ is a composite number .

In case when $3 \cdot 2^{n-1}-1$ is a composite number one should prove that :

$(5^m)^2 \not \equiv 1 \pmod p$

where $m$ is a proper factor of $3 \cdot 2^{n-1}-1$

Note that if $n \equiv 3,7 \pmod 8$ then $p \equiv 3 \pmod 4$


Added :

$x^2 \equiv a \pmod n$ where $n$ is a prime number has no solution if : $\left(\frac{a}{n}\right)=-1$

So let's assume that $\left(\frac{a}{n}\right) = 1$, if $n \equiv 3 \pmod 4$, Lagrange found that the solutions are given by :

$x \equiv \pm a^{(n+1)/4} \pmod n$

So :

If $~\left(\frac{1}{p}\right) = 1~$ then :

$5^m \equiv 1 \pmod p ~~\text{and}~~ 5^m \equiv -1 \pmod p$

But if $~5^m \equiv 1 \pmod p~$ then $~5^{\frac{p-1}{2}} \equiv 1 \pmod p ~$ since $m$ is a proper factor of $~\frac{p-1}{2}$ .

$$ 5^{\frac{p-1}{2}} \equiv 1 \pmod p ~~\text {and}~~\left(\frac{5}{p}\right) \equiv 5^{\frac{p-1}{2}} \pmod p \Rightarrow$$

$$\Rightarrow \left(\frac{5}{p}\right) = 1 \Rightarrow p \equiv 1,4 \pmod 5$$

which is contradiction since : $p \equiv 3 \pmod 5$ , therefore :

$5^m \not \equiv 1 \pmod p$

Now , I don't know how to prove or disprove that :

$5^m \not \equiv -1 \pmod p$

Since $~p\equiv 3 \pmod 5~$ question whether $~5^m \not \equiv -1 \pmod p$ ?

is equivalent to the question whether $\frac{5^m+1}{p} \not \equiv 2 \pmod {10}$ ?

  • 0
    The primes with 5 as *smallest* primitive root are in http://oeis.org/A001124.2012-02-06
  • 0
    @lhf,Thanks but my question is related to $321$ primes only..2012-02-06
  • 2
    It is easy to deal with the case that $n \equiv 1$ or $5 \mod 8$: For such $n$, $3 \cdot 2^n-1$ is divisible by $5$ and is hence not prime (except when $n=1$). So the question is whether, for $n \equiv 3 \mod 4$ and $3 \cdot 2^n-1$ prime, the number $5$ is always a primitive root. My gut doubts it. Unlike in your previous examples, standard heurisitics predict that there are infinitely many primes of the form $3 \cdot 2^{n}-1$, so it is likely that enough searching will find a counterexample. PS: Any reason you aren't making the same conjecture for $n \equiv 0 \mod 4$?2012-02-06
  • 0
    @DavidSpeyer,In your opinion is it possible to disprove this statement if you don't use brute force search ? Similar statements can be formulated for all primes of the form : $3^a \cdot 2^b-1$...I was observing only odd exponents...2012-02-06
  • 0
    @DavidSpeyer,According to Wikipedia : $ 3 \cdot 2^{7033641}-1 $ is a prime number and $ 7033641 \equiv 1 \pmod 8 $...2012-02-06
  • 0
    Can't be. Powers of $2$ have last digit cycling $2$, $4$, $8$, $6$, $2$, $4$, $8$, $6$... So $2^{7033641}$ ends in $2$. (Wolfram alpha says that the last few digits are ...6860567552). So $3 \cdot 2^{7033641}$ ends in $6$ and $3 \cdot 2^{7033641}-1$ ends in $5$.2012-02-06
  • 0
    I note that http://primes.utm.edu/primes/lists/short.txt lists $3 \cdot 2^{7033641}+1$ as prime. I suspect that the plus typoed into a minus somewhere along the way. Off to edit Wikipedia...2012-02-06
  • 0
    @DavidSpeyer,Wiki article is being changed...now it is correct..2012-02-06
  • 0
    I think the last line should be $\operatorname{ord}_p(5)=3\cdot2^n-2=2\cdot(3\cdot2^{n-1}-1)$?2012-02-06
  • 0
    @joriki,certainly....thanks2012-02-06
  • 0
    @DavidSpeyer,see edit....2012-02-07
  • 0
    I don't know whether this particular problem is discussed in Wieb Bosma, Explicit primality criteria for $h\cdot2^k\pm1$, Math. Comp. 61 (1993), no. 203, 97–109, S7–S9, MR1197510 (94c:11005), but it looks like a paper that might interest you.2012-02-07
  • 0
    @GerryMyerson,Thanks for reference...I haven't found "primitive root criteria" in this paper...2012-02-08

2 Answers 2