Primes $p$ such that $5$ is primitive root $\bmod{p}$ , where $p$ is a $321$ prime

Question

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}$ ?

Answer 1

I don't have a proof, but here are some heuristics on why you may be seeing this pattern and how hard it will be to find counterexamples.

As David pointed out in a comment, the question reduces to whether $5$ is always a primitive root for $n\equiv3\bmod4$ and $3\cdot2^n-1$ prime. If there were no systematic effects at play, the "probability" for $5$ (or any other positive integer) to be a primitive root modulo $3\cdot2^n-1$ would be

$$\frac{\phi(3\cdot2^n-2)}{3\cdot2^n-2}=\prod_{p\,\mid\,3\cdot2^n-2}\frac{p-1}p\;.$$

Since $2\mid3\cdot2^n-2$, this would always be at most $1/2$. However, $3\cdot2^n-1\equiv3\bmod5$ for $n\equiv3\bmod4$ (since $3\cdot2^3-1=23\equiv3\bmod5$ and the residue cycles with period $5-1=4$), so by quadratic reciprocity

$$ \def\jacobi#1#2{\left(\frac{#1}{#2}\right)} \begin{eqnarray}\jacobi5{3\cdot2^n-1} &=&\jacobi{3\cdot2^n-1}5(-1)^{(5-1)/2}(-1)^{(3\cdot2^n-1-1)/2} \\ &=& \jacobi{3\cdot2^n-1}5(-1) \\ &=& \jacobi{3}5(-1) \\ &=& -1\;. \end{eqnarray}$$

Thus $5$ is not a quadratic residue modulo $3\cdot2^n-1$, so the factor of $1/2$ doesn't come into play, since $3\cdot2^n-2=2\cdot(3\cdot2^{n-1}-1)$ and $2\nmid3\cdot2^{n-1}-1$. The primes $p=3,5$ and $7$ also don't divide $3\cdot2^{n-1}-1$, since $3\cdot2^{n-1}-1\equiv2\bmod3$ and $3\cdot2^{n-1}-1\equiv1\bmod5$ for $n\equiv3\bmod4$, and the residues of $3\cdot2^{n-1}-1\bmod7$ form the cycle $(4,2,5)$.

Thus the first prime that may divide $3\cdot2^{n-1}-1$ is $11$. The residues $\bmod11$ form the cycle $(0,4,2,3,8)$, so we can expect $11$ to be a factor in every fifth case. The residues $\bmod13,17$ and $19$ all form cycles that don't include $0$, and the next possible factor is $23$, for which the residues form an $11$-cycle including $0$, so we can expect $23$ to be a factor in every eleventh case.

There are further systematic effects, since the fact that $3\cdot2^n-1$ is prime may slightly influence the frequencies of the residues; for instance, the residues $\bmod71$ have period $35$ and include $0$, so the fact that the residue of $3\cdot2^n-1\bmod71$ is not $0$ slightly raises the chance that $3\cdot2^{n-1}-1$ is divisible by $11$ or by $71$. However, for a rough estimate we can neglect these effects.

For $5$ not to be a primitive root modulo $3\cdot2^n-1$, a) some prime $p$ must divide $3\cdot2^{n-1}-1$ and b) $5$ must be one of the fraction $1/p$ of residues that are not primitive roots. The "probability" for this to happen for a certain prime $p$ is $1/p$ times the fraction of residues in the residue cycle for $p$ that are $0$, e.g., $1/5$ for $p=11$. This fraction is typically also of the order of $1/p$. As a rough estimate of the total "probability" for $5$ not to be a primitive root, we can sum up these "probabilities" for all primes $p$, and since the terms tend to fall of quadratically with $p$, we can expect the sum to converge; in fact since the first non-zero term is $1/5\cdot1/11=1/55$ for $p=11$, the total is likely to be quite small. A summation for all $p\lt2^{20}$ yields a sum of about $0.03$.

Thus, we should expect roughly every $33$rd case to be a counterexample. This analysis certainly doesn't exclude the possibility that further systematic effects conspire to ensure that $5$ is always a primitive root, but it does show that you haven't produced any significant numerical evidence for this hypothesis, since the expected number of counterexamples in your trials was only about $0.24$. You would need to test $25$ more cases just to bring the expected number of counterexamples to $1$; according to Wikipedia, that would mean testing for $n=391$, $827$, $7559$, $18123$, $18819$, $26459$, $51387$, $71783$, $85687$, $88171$, $97063$, $164987$, $584995$, $727699$, $1232255$, $3136255$ and nine more Thabit primes beyond that that aren't even known yet, and even then the "probability" of finding a counterexample would only be about $1-1/\mathrm e\approx63\%$.

Answer 2

Checking the first few cases with sage, I found $n=3,4,7,11,43,55,64,76,103,143,216,324$, suggesting the condition $n\equiv0,3,4,7\pmod8$, or excluding $n$ even, $n\equiv3\pmod4$.

Your hypothesis should therefore be for $n>1$ odd (since for $n=1$, $5$ is not a primitive root mod $p=5$).

# http://sage.csuohio.edu/home/pub/87/
def is_primitive_root(a,m):
    if gcd(a,m)>1:
        raise ValueError('a must be relatively prime to m')
    phi=euler_phi(m)
    powers = [ phi//q for q in prime_factors(phi) ]
    return all(pow(a,k,m)!=1 for k in powers) 
# our test:
for n in range(1,513):
    p = 3 * 2^n - 1
    if not is_prime(p):
        continue
    k = 1 if gcd(5,p)==1 and is_primitive_root(5,p) else 0
    print 'k=%d n=%3d p=%d' % (k, n, p)

k=0 n=  1 p=5
k=0 n=  2 p=11
k=1 n=  3 p=23
k=1 n=  4 p=47
k=0 n=  6 p=191
k=1 n=  7 p=383
k=1 n= 11 p=6143
k=0 n= 18 p=786431
k=0 n= 34 p=51539607551
k=0 n= 38 p=824633720831
k=1 n= 43 p=26388279066623
k=1 n= 55 p=108086391056891903
k=1 n= 64 p=55340232221128654847
k=1 n= 76 p=226673591177742970257407
k=0 n= 94 p=59421121885698253195157962751
k=1 n=103 p=30423614405477505635920876929023
k=1 n=143 p=33451117797795934712303577408972542258970623
k=0 n=206 p=308532104497726132904056721729503219684262974806296224377864191
k=1 n=216 p=315936875005671560093754083051011296956685286201647333762932932607
k=0 n=306 p=391110907456221328563541572174600606921881931583859760122138966276041209554560647587212296191
k=1 n=324 p=102527377724203683954961041896138501500929817073119332957457997175466546837470746401102180172955647

Answer 3

joriki's answer gives a great analysis.

Calculations with PARI/GP let me find a counterexample (maybe the first one).

The prime $p = 3\cdot 2^{18123}-1$ apparently found by Ballinger in April 1998 is a counterexample. Exponent ends in $3$, so modulo $11$, $p$ is congruent to $3\cdot 2^3-1\equiv 1$, therefore $p-1$ is divisible by $11$.

So I check what $5^{(p-1)/11}$ is modulo $p$. For this, I use PARI/GP:

p = 3*2^18123 - 1 ; Mod(5,p)^((p-1)/11)

This gives Mod(1, 110594...) meaning the result is $1\pmod p$.

So $5$ is not a primitive root modulo prime $3\cdot 2^{18123}-1$, and clearly $18123$ is odd (is $3\pmod 8$ if we do not use observation that odd is sufficient).