Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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


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


  } else { 


share|cite|improve this question
Your argument actually shows that all factors of $2$ must be present in $\operatorname{ord}_p(3)$, so it's either $2^a$ or $2^a\cdot M_q$. – joriki Feb 12 '12 at 11:46
It seems your primality test consists of the Fermat primality test applied only once? Usually this is applied several times for different bases to exclude false primes. For instance, your test with the single base $3$ would falsely identify $91$ as a prime. The three numbers you tested do appear to be primes, though; you can test this using BigInteger.isProbablePrime (). By the way, you can get $1$ as a BigInteger using BigInteger.ONE. – joriki Feb 13 '12 at 11:19
@joriki,How can you express $91$ in the form $2^a \cdot M_q+1$ , where $M_q$ is a Mersenne isn't possible...Test uses fact that $3$ is a primitive root modulo $p$ for mostly primes of this form . It isn't deterministic but you have very , very good chance to get correct result... – pedja Feb 13 '12 at 11:33
OK, I see that it's far more reliable for numbers of that form; still I wouldn't call it a "primality test" without any explanation if I know that it's not deterministic. – joriki Feb 13 '12 at 11:38
@joriki,OK,It is probabilistic primality test with large certainty... – pedja Feb 13 '12 at 11:44

Your Answer


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

Browse other questions tagged or ask your own question.