# How do you get possible candidates for primitive roots of 12?

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?

-
The title does not really reflect the question. – lhf Dec 12 '11 at 15:25
One can describe precisely the numbers for which there is a primitive root: see en.wikipedia.org/wiki/… – Mariano Suárez-Alvarez Dec 12 '11 at 15:28
I think you are asking how did the problem reduce the candidates to 1,5,7,11. These are the only numbers between $1$ and $11$ which are relatively prime to 12. – Thomas Andrews Dec 12 '11 at 15:46
@Thomas: But what about when you have assignment to find primitive roots of 11, then all 1,2,3,4,5,6,7,8,9,10 would be primitive roots? – alvoutila Dec 12 '11 at 17:45
Yes, any one of them could be a primitive root, although you can fairly easily rule out $1$ and $10=-1$ and any obvious perfect squares, such as $4$ and $9$. But the candidates that were chosen for $12$ are all the candidates. – Thomas Andrews Dec 12 '11 at 17:49

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

-
I have hard time figuring out that "if $g$ is primitive root, then all other ones are $g^k$ with $k$ coprime with $p-1$". Could you give some example on how to use that "rule"? – alvoutila Dec 12 '11 at 16:01
@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)}$. – lhf Dec 12 '11 at 18:11

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.

-