Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
The title does not really reflect the question. –  lhf Dec 12 '11 at 15:25
1  
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
1  
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

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.