# Primes $p$ such that $3$ is a Primitive Root Modulo $p$

In this paper (Proposition 4) you can find statement :

If $p$ is a prime of the form : $p = 2q + 1$ for some odd prime $q$,

then $2$ is a primitive root modulo $p$ if and only if : $q \equiv 1, 5 \pmod 8$.

Is it true that :

If $p$ is a prime of the form : $p =3\cdot q \cdot (q+1)-1$ for some odd prime $q$,

then $3$ is a primitive root modulo $p$ if and only if : $q \equiv 1, 5 \pmod {12}$.

Legendre symbol for $3$ is :

$\left(\frac{3}{p} \right) = \begin{cases} ~~~1, & \text{if } :p \equiv 1,11 \pmod {12} \\ -1, & \text{if } : p \equiv 5,7 \pmod {12} \end{cases}$

It is obvious that necessary condition is : $q \equiv 1, 5 \pmod {12}$ since :

$3 \cdot(12t+7)^2+3(12t+7)-1 \equiv 11 \pmod {12}$

$3 \cdot(12t+11)^2+3(12t+11)-1 \equiv 11 \pmod {12}$

There is a theorem that states :

$a$ is a primitive root modulo $~p~$ iff $~~ord_p(a) = \phi(p)$ .

So , how to prove that : $~~ord_p(3) =3\cdot q \cdot (q+1)-2$ ?

EDIT :

Conjecture is false . Smallest counterexample is : $35862917$

-
A big reason, why the author was successful in deducing primitivity of 2 modulo $p$ is that he knows the prime factorization of $p-1=2q$, can test all the proper factors of $2q$, and exclude them as orders of $2$ modulo $p$. Do you know the factorization of $p-1=3q(q+1)-2$ in your case? – Jyrki Lahtonen Feb 4 '12 at 8:20
@JyrkiLahtonen,In this case number of factors isn't same for all $q$.. – pedja Feb 4 '12 at 8:32
Don't you think that that makes the problem rather difficult? You have to show that $3^{(p-1)/r}$ is not congruent to $1\pmod p$ for all prime divisors $r$ of $p-1$. – Jyrki Lahtonen Feb 4 '12 at 10:44
@JyrkiLahtonen,I know that this isn't easy task...On the other hand I have checked statement for many primes of this form and haven't found any counterexample so it might be true... – pedja Feb 4 '12 at 10:52
Maybe you should tell us which primes you have checked, so we don't duplicate the work. – Gerry Myerson Feb 4 '12 at 11:46