# Thread: How to find a primitive root of N

1. ## How to find a primitive root of N

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

2. Originally Posted by fanfan1609
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
There is no known way to find primitive roots. There are methods which make it faster. Of course, a computer program is the best way to go. See this.

3. Originally Posted by ThePerfectHacker
There is no known way to find primitive roots. There are methods which make it faster. Of course, a computer program is the best way to go. See this.
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

4. For 11 you can use a simple fact that if $\displaystyle p$ is a odd prime and $\displaystyle (p-1)/2$ is also a prime then $\displaystyle 2$ is a primitive root for $\displaystyle p$. I leave that for you to prove.

5. Originally Posted by ThePerfectHacker
For 11 you can use a simple fact that if $\displaystyle p$ is a odd prime and $\displaystyle (p-1)/2$ is also a prime then $\displaystyle 2$ is a primitive root for $\displaystyle p$. I leave that for you to prove.
maybe i am not smart enough to know your advice.YOu can tell clearly .
I know if p is primitive root modulo n ,p^phi(n) =1 mod(n) ,
so how do test all i ,i<11 and (i,11)=1?

6. Originally Posted by fanfan1609
maybe i am not smart enough to know your advice.YOu can tell clearly .
I know if p is primitive root modulo n ,p^phi(n) =1 mod(n) ,
so how do test all i ,i<11 and (i,11)=1?
The direct way with to deal with $\displaystyle 11$ is to list all $\displaystyle n$ with $\displaystyle \gcd (n,11)=1$ so $\displaystyle n=1,2,...,10$. And now eliminate each of these numbers. For example, take $\displaystyle n=4$. Check whether the order of $\displaystyle 4$ mod $\displaystyle 11$ is $\displaystyle \phi(11) = 10$. Remember order means the smallest exponent $\displaystyle k$ so that $\displaystyle 4^k\equiv 1(\bmod 11)$. But since $\displaystyle 4^{10}\equiv 1(\bmod p)$ (Fermat's theorem) it follows by properties of orders that $\displaystyle k|10$ so $\displaystyle k=1,2,5,10$. Since it cannot be $\displaystyle 1$ it means you just need to check $\displaystyle k=2,5,10$. A simple calculation will show that $\displaystyle k=5$ is the order, so $\displaystyle 4$ is not a primitive root. So that eliminates one number on the list $\displaystyle \{ 1,2,...,10\}$. Now pick another number, say $\displaystyle 2$, using the approach as above you will find that $\displaystyle k=10$. So that means $\displaystyle 2$ is a primitive root mod $\displaystyle 11$. Now you can save yourself a lot of time, since you found one primitive root all other primitive roots are $\displaystyle 2^{m}$ where $\displaystyle 1\leq 1\leq 10$ and $\displaystyle \gcd(m,\phi(11)) = \gcd(m,10)=1$. In this case $\displaystyle m=1,3,7,9$. Thus, $\displaystyle 2, 2^3 \equiv 8, 2^7\equiv 7, 2^9\equiv 6$ are the primitive roots.

7. Originally Posted by ThePerfectHacker
The direct way with to deal with $\displaystyle 11$ is to list all $\displaystyle n$ with $\displaystyle \gcd (n,11)=1$ so $\displaystyle n=1,2,...,10$. And now eliminate each of these numbers. For example, take $\displaystyle n=4$. Check whether the order of $\displaystyle 4$ mod $\displaystyle 11$ is $\displaystyle \phi(11) = 10$. Remember order means the smallest exponent $\displaystyle k$ so that $\displaystyle 4^k\equiv 1(\bmod 11)$. But since $\displaystyle 4^{10}\equiv 1(\bmod p)$ (Fermat's theorem) it follows by properties of orders that $\displaystyle k|10$ so $\displaystyle k=1,2,5,10$. Since it cannot be $\displaystyle 1$ it means you just need to check $\displaystyle k=2,5,10$. A simple calculation will show that $\displaystyle k=5$ is the order, so $\displaystyle 4$ is not a primitive root. So that eliminates one number on the list $\displaystyle \{ 1,2,...,10\}$. Now pick another number, say $\displaystyle 2$, using the approach as above you will find that $\displaystyle k=10$. So that means $\displaystyle 2$ is a primitive root mod $\displaystyle 11$. Now you can save yourself a lot of time, since you found one primitive root all other primitive roots are $\displaystyle 2^{m}$ where $\displaystyle 1\leq 1\leq 10$ and $\displaystyle \gcd(m,\phi(11)) = \gcd(m,10)=1$. In this case $\displaystyle m=1,3,7,9$. Thus, $\displaystyle 2, 2^3 \equiv 8, 2^7\equiv 7, 2^9\equiv 6$ are the primitive roots.
oh .i see.Thanks very much?

8. Originally Posted by fanfan1609
oh .i see.Thanks very much?
In my other posts. I say that if $\displaystyle (p-1)/2$ is also a prime then $\displaystyle 2$ is a primitive root of $\displaystyle p$. Say $\displaystyle p=11$ then $\displaystyle (11-1)/2=5$ is prime, which means $\displaystyle 2$ is primitive root of $\displaystyle 11$. Now since you one primitive root you found them all.

9. Originally Posted by ThePerfectHacker
In my other posts. I say that if $\displaystyle (p-1)/2$ is also a prime then $\displaystyle 2$ is a primitive root of $\displaystyle p$. Say $\displaystyle p=11$ then $\displaystyle (11-1)/2=5$ is prime, which means $\displaystyle 2$ is primitive root of $\displaystyle 11$. Now since you one primitive root you found them all.
if i don't misunderstand ,the way you say is if i replace 2 by another number i and $\displaystyle (p-1)/i$ is prime ,then i is primitive root of n .
Do i have mistake ?

10. Originally Posted by fanfan1609
if i don't misunderstand ,the way you say is if i replace 2 by another number i and $\displaystyle (p-1)/i$ is prime ,then i is primitive root of n .
Do i have mistake ?
If $\displaystyle (p-1)/i$ is prime DOES NOT mean $\displaystyle i$ is primitive roots of $\displaystyle p$. That only works for the case $\displaystyle (p-1)/2$. I never said this in generality.

11. Can you make a general statment or "rule" to determining if g^k is a primitive root? Is there a generalization?

12. Originally Posted by duggaboy
Can you make a general statment or "rule" to determining if g^k is a primitive root? Is there a generalization?
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

13. but how would you find d? just choose vales and try?

14. Originally Posted by duggaboy
but how would you find d? just choose vales and try?
it is easy to find d.For example,if n is 10 ,then d is 1,2,and 5.If with every d ,which is diffirent n, a^d mod n is not 1 ,then a is a primitive root modulo n

15. Originally Posted by duggaboy
Can you make a general statment or "rule" to determining if g^k is a primitive root? Is there a generalization?
If $\displaystyle g$ is primitive root mod $\displaystyle n$ then $\displaystyle g^k$ is primitive root iff $\displaystyle \gcd(k,\phi(n)) = 1$.

Page 1 of 2 12 Last