2
$\begingroup$

How to prove following statement :

Let $~p~$ be Woodall prime of the form : $p=n\cdot 2^n-1$

$5~$ is a primitive root modulo $~p~$ iff $~n \equiv 3,6,9 \pmod {20}$

For example : $5$ is a primitive root modulo $p$ for following Woodall primes :

$3\cdot 2^3-1~,~6 \cdot 2^6-1~,~123 \cdot 2^{123}-1~,249 \cdot 2^{249}-1 ,....$


Note that : if $~n \equiv 3 ,6 ,9 \pmod {20}~$ then $~p \equiv 2,3 \pmod 5$

Euler's totient function of $~p~$ is given by :

$\phi(p)=2(n \cdot 2^{n-1}-1)$

Suppose that :

$ord_p(5) =n \cdot 2^{n-1}-1~$ where $~n \cdot 2^{n-1}-1~$ is a prime number , then :

$5^{n \cdot 2^{n-1}-1}=5^{\frac{p-1}{2}} \equiv 1 \pmod p$

and we know that :

$\left(\frac{5}{p}\right) \equiv 5^{\frac{p-1}{2}} \pmod p~$, hence :

$\left(\frac{5}{p}\right)=1 \Rightarrow p \equiv 1,4 \pmod 5$

which is a contradiction since $~p \equiv 2, 3 \pmod 5~$ , hence :

$ord_p(5) \neq n\cdot 2^{n-1}-1 \Rightarrow ord_p(5)=2(n\cdot 2^{n-1}-1)~$ , since it cannot be $~2~$ .

Therefore :

$5~$ is a primitive root modulo $~p~$ whenever $~n\cdot 2^{n-1}-1~$ is a prime number .


Any idea how to prove that $~5~$ is a primitive root modulo $~p~$ in a case when $~n\cdot 2^{n-1}-1~$ is a composite number ?

  • 0
    @pedja: It looks like$a$very difficult problem, since there is very little one can say about the prime facorization of $n2^n-1$. We can rule out the situations in which $5$ is a quadratic residue, but there seems to be no way to handle the rest. There is a better chance for Fermat-like primes, that is, numbers of the shape $a_n+1$ where $a_n$ has a simple factorization.2012-02-17

0 Answers 0