Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

2 Answers 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
share|improve this answer
2  
Unfortunately $p-1=3\cdot2^n-2\ne3(2^n-2)$. –  joriki Feb 8 '12 at 12:21
    
You have a mistake in fourth line : $p-1 \neq 3(2^n-2)$ –  pedja Feb 8 '12 at 12:24
    
@joriki (and pedja): thanks, I think it's corrected (but still incomplete) now. –  bgins Feb 8 '12 at 13:07
    
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$. –  joriki Feb 8 '12 at 13:55
    
@joriki: you're right; my mistake! I was not adding anything new (except to suggest $n\neq 1$). –  bgins Feb 8 '12 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\%$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.