81
$\begingroup$

How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly?

Thanks

  • 11
    Finding primitive roots is generally difficult. For $761$, there are exactly $\phi(\phi(761)) = \phi(760) = \phi(2^3\times 5\times 19) = 2^2\times 4\times 18 = 288$ primitive roots, so you have about a 3/8 change of picking a primitive root by picking one at random. So pick one at random and check to see if $a^{380}\equiv -1\pmod{761}$; if yes, then $a$ is a primitive root; if not, then pick something else.2012-03-25
  • 0
    Hi Arturo, could you shed more light on how to verify a, picked randomly, is a primitive root?2012-03-25
  • 7
    A given $a$ is a primitive root modulo $761$ if and only if the order of $a$ modulo $761$ is *exactly* $760$. Since $761$ is prime, there are only two elements whose square is $1$: $1$ and $-1$. Since $a^{760}\equiv 1\pmod{761}$ (Fermat's Little Theorem), we know that $a^{380}\equiv 1$ or $a^{380}\equiv -1$. In the former case, the order of $a$ divides $380$, so $a$ is not a primitive root. In the latter case, the smallest $k$ such that $a^k\equiv1\pmod{761}$ is $760$, so $a$ is in fact a primitive root. So all you need to do is compute $a^{380}\bmod 761$.2012-03-25
  • 1
    [Wolfram Alpha](http://www.wolframalpha.com/input/?i=primitive+root+of+761) says that 6 is the smallest primitive root of 761.2012-03-26
  • 0
    Thank you that answer was very helpful. I am beginning to understand most concepts of the problem and why it is difficult to solve.2012-03-26
  • 5
    @Arturo This is a necessary condition, but not sufficient. :(2012-04-19
  • 0
    @Arturo I have posted my answer below, and among other things, I have an example of why just testing $a^{380}$ is not enough to say that $a$ is a primitive root. See what happens to $3$ when you test it against $761$: $3^{380}\equiv -1\mod 761$, but, in fact, $3^{380/5}=3^{76}\equiv -1\mod 761$ as well, and $3^{152}=1\mod 761$. This is precisely why you need to test all the powers: $760/2$, $760/5$ and $760/19$. In fact, when you test $3$ only power $152$ (among the three powers above) will tell you that it is not a primitive root, when you test 35 -- only 40, and when test 2 -- only 380.2012-04-19
  • 0
    @Vadim: Indeed. Thanks.2012-04-19

3 Answers 3