Let N have primitive roots .Which the way does find all primitive roots generally ? I think if testing all i ,(i,N)=1, is so long
THanks
I also know that way .YOu can help me my problem .
find the primitive root of 11^2 if we know 2,3 is primitive root of 11.
My teacher said that "if p is primitive root of N ,or p or p+N is primitive root of N^2 " but he didn't said the general primitive root of 11^2.
You can help me ?
Thanks
The direct way with to deal with is to list all with so . And now eliminate each of these numbers. For example, take . Check whether the order of mod is . Remember order means the smallest exponent so that . But since (Fermat's theorem) it follows by properties of orders that so . Since it cannot be it means you just need to check . A simple calculation will show that is the order, so is not a primitive root. So that eliminates one number on the list . Now pick another number, say , using the approach as above you will find that . So that means is a primitive root mod . Now you can save yourself a lot of time, since you found one primitive root all other primitive roots are where and . In this case . Thus, are the primitive roots.
Sorry,I don't know your question.
If you want to determine a is a primitive root modulo n ,i think you should do something :
1/you find phi(n)
2/determine d with d|n
3/you test a^d mod n if the result isn't 1 with every d ,a is a primitive root modulo n
if you want find other primitive root ,you find e with e|phi(phi(n)) ,
with each e ,a^e mod n is a primitive root modulo n