1
$\begingroup$

Candidates for primitive roots are 1, 5, 7 and 11. $\phi(12)=\phi(2^2)\phi(3)=4$. $ord_{12}1 =1, ord_{12}5 =2, ord_{12}7 =2, ord_{12}11 =2$. None of these has $\phi(12)=4$, thus number 12 has not primitive root.

My question still remains: How do you get possible candidates for primitive roots? What about when trying to find primitive roots of some prime, how you get then possible candidates for primitive roots?

  • 0
    Oh, and, no, they wouldn't all be primitive roots, they would all be candidates for primitive roots. You have to then check, as above in the case of $12$. Less than half of them will ever be primitive roots if p>2.2011-12-12

2 Answers 2

2

There are primitive roots modulo $m$ iff $m$ is $1, 2, 4$, a power of an odd prime or twice a power of an odd prime. Once you find a primitive root modulo a prime $p$, it is easy to find a primitive root modulo all powers of $p$. So the real problem is the case $m$ prime.

There is no general method for finding a primitive root. See http://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots. However, once you find one, call it $g$, then all other ones are $g^k$ with $k$ coprime with $p-1$.

The least primitive root is generally small. See http://en.wikipedia.org/wiki/Primitive_root_modulo_n#Order_of_magnitude_of_primitive_roots

  • 0
    @alvoutila, in general, if $g$ generates a cyclic group of order $t$ then the other generators are $g^k$ with $k$ coprime with $t$. More generally, the order of $g^k$ is ${t}/{\gcd(k,t)}$.2011-12-12
2

A primitive root exists, i.e. $\rm\:(\mathbb Z/n\mathbb Z)^*\:$ is cyclic, iff $\rm\:n = 2, 4, p^k, 2\:p^k\:$ for an odd prime $\rm\:p\:.\:$ Generally there is no better way to find a primitive root other than brute force: e.g. sequentially test small candidates, verifying that they have the desired order. This usually succeeds quite quickly since e.g. by GRH the least primitive root mod $\rm\:p\:$ is $\rm\:O(\log^6\:p)\:.\:$ See the Wikipedia page for more. It's always a good idea to check there first before posing questions.

There are also very interesting conjectures about primitive roots such as Artin's conjecture. To learn about this and related topics I highly recommend reading Daniel Shanks: Solved and Unsolved Problems in Number Theory, 4ed, 1993, where you will find many expositions on how to make conjectures in number theory. It is essential reading for a budding experimental number theorist. Be sure to get the final $4$th edition (1993), which has much added content, esp. on making and judging conjectures.

More generally you may find of interest Andrew Sutherland's 2007 MIT Thesis Order Computations in Generic Groups.