2
$\begingroup$

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");       } } } 
  • 0
    @joriki,OK,It is probabilistic primality test with large certainty...2012-02-13

0 Answers 0