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 ?

  • $\begingroup$ 5 is primitive modulo of p means that there is always k such that $5^k===a(mod p)$ where $a$ and $p$ are coprime $\endgroup$ – dato datuashvili Feb 17 '12 at 12:41
  • $\begingroup$ en.wikipedia.org/wiki/Primitive_root_modulo_n this site may help you a bit $\endgroup$ – dato datuashvili Feb 17 '12 at 12:46
  • $\begingroup$ If g is a primitive root modulo p, then g is a primitive root modulo all powers p^k unless $g^(p – 1) ≡ 1 (mod p^2)$ $\endgroup$ – dato datuashvili Feb 17 '12 at 12:52
  • $\begingroup$ @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. $\endgroup$ – André Nicolas Feb 17 '12 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.