Let's define prime number $~p~$ as :
$p=2^a \cdot M_q+1$
where $~M_q~$ is a Mersenne prime number such that $q \geq 3$ and $a$ is an even integer .
Note that :
Since $~M_q \equiv 1 \pmod 6 ~~\text{and}~~ a\equiv 0 \pmod 2~$ it follows that :
$p \equiv 5 \pmod {12}$
Euler's totient function for $p$ is given by :
$\phi(p)=2^a \cdot M_q$
Suppose that : $ord_p(3)=M_q~$ then :
$3^{M_q} \equiv 1 \pmod p \Rightarrow 3^{\frac{p-1}{2^a}} \equiv 1 \pmod p \Rightarrow 3^{\frac{p-1}{2}} \equiv 1 \pmod p$
and we know that :
$\left(\frac{3}{p}\right) \equiv 3^{\frac{p-1}{2}} \pmod p $ , therefore :
$\left(\frac{3}{p}\right)=1 \Rightarrow p \equiv 1,11 \pmod {12}$
which is contradiction since $p \equiv 5 \pmod {12}~$ so :
$ord_p(3) \neq M_q$
Similarly one can show that :
$ord_p(3) \neq 2^b \cdot M_q~$ where $~b
So : $ord_p(3) = 2^c ~;~ c \leq a~$ or $~ord_p(3)=2^a \cdot M_q$
Mostly for all primes of the form : $~p=2^a \cdot M_q+1~$ , $3$ is a primitive root modulo $~p$ .
Primes for which $~3~$ isn't primitive root modulo $p$ are :
$2^{50} \cdot (2^3-1)+1 ~, 2^{140} \cdot (2^5-1)+1 ~, 2^{320} \cdot (2^3-1)+1 , $......
I have noticed that :
$50 \equiv 50 \pmod {90} ~,140 \equiv 50 \pmod {90} ,~320 \equiv 50 \pmod {90}$
My question:
For which values of $~a~ \text {and}~q~$ , $~3~$ isn't primitive root modulo $p$ ?
Can we find some additional constraints on values of $a~~ \text {and}~~ q~$ so that $~3~$ would be a primitive root modulo $~p~$ for every prime $~p~$ ?
EDIT :
Probabilistic primality test for $~p=2^a \cdot M_q+1~$ written in Java :
Input is pair : $(a,q)$
import java.math.BigInteger; public class Test { public static void main(String[] args) { int a; a = Integer.parseInt(args[0]); int q; q = Integer.parseInt(args[1]); BigInteger b = new BigInteger ("2"); BigInteger n = new BigInteger ("3"); BigInteger m; m = b.pow(q).subtract(BigInteger.valueOf(1)); BigInteger p; p = b.pow(a).multiply(m).add(BigInteger.valueOf(1)); BigInteger exponent; exponent = p.subtract(BigInteger.valueOf(1)); BigInteger result = n.modPow(exponent,p); if (result.equals(BigInteger.valueOf(1))) { System.out.println("prime"); } else { System.out.println("composite"); } } }