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

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

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

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

• The primes with 5 as smallest primitive root are in oeis.org/A001124.
– lhf
Feb 6, 2012 at 11:07
• @lhf,Thanks but my question is related to $321$ primes only.. Feb 6, 2012 at 11:13
• 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$? Feb 6, 2012 at 13:11
• @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... Feb 6, 2012 at 13:28
• @DavidSpeyer,According to Wikipedia : $3 \cdot 2^{7033641}-1$ is a prime number and $7033641 \equiv 1 \pmod 8$... Feb 6, 2012 at 14:29

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\%$.

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

• It seems that now you've just reproduced the part of my answer that deals with $p=2$? Also note that the question is only about odd $n$. Feb 8, 2012 at 13:55
• @joriki: you're right; my mistake! I was not adding anything new (except to suggest $n\neq 1$). Feb 8, 2012 at 14:29

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