How to find a primitive root of N

**fanfan1609** · May 13th 2008, 06:19 PM

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

**ThePerfectHacker** · May 13th 2008, 07:14 PM

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.

**fanfan1609** · May 13th 2008, 08:49 PM

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

**ThePerfectHacker** · May 13th 2008, 09:08 PM

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

**fanfan1609** · May 13th 2008, 10:38 PM

Originally Posted by ThePerfectHacker

For 11 you can use a simple fact that if $p$ is a odd prime and $(p-1)/2$ is also a prime then $2$ is a primitive root for $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?

**ThePerfectHacker** · May 14th 2008, 06:59 AM

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

**fanfan1609** · May 14th 2008, 03:17 PM

Originally Posted by ThePerfectHacker

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

oh .i see.Thanks very much?

**ThePerfectHacker** · May 14th 2008, 03:19 PM

Originally Posted by fanfan1609

oh .i see.Thanks very much?

In my other posts. I say that if $(p-1)/2$ is also a prime then $2$ is a primitive root of $p$ . Say $p=11$ then $(11-1)/2=5$ is prime, which means $2$ is primitive root of $11$ . Now since you one primitive root you found them all.

**fanfan1609** · May 14th 2008, 03:27 PM

Originally Posted by ThePerfectHacker

In my other posts. I say that if $(p-1)/2$ is also a prime then $2$ is a primitive root of $p$ . Say $p=11$ then $(11-1)/2=5$ is prime, which means $2$ is primitive root of $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 $(p-1)/i$ is prime ,then i is primitive root of n .
Do i have mistake ?

**ThePerfectHacker** · May 14th 2008, 04:08 PM

Originally Posted by fanfan1609

if i don't misunderstand ,the way you say is if i replace 2 by another number i and $(p-1)/i$ is prime ,then i is primitive root of n .
Do i have mistake ?

If $(p-1)/i$ is prime DOES NOT mean $i$ is primitive roots of $p$ . That only works for the case $(p-1)/2$ . I never said this in generality.

**duggaboy** · June 14th 2008, 07:42 AM

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

**fanfan1609** · June 14th 2008, 08:01 AM

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?

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

**duggaboy** · June 14th 2008, 08:27 AM

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

**fanfan1609** · June 14th 2008, 03:17 PM

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

**ThePerfectHacker** · June 14th 2008, 05:46 PM

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 $g$ is primitive root mod $n$ then $g^k$ is primitive root iff $\gcd(k,\phi(n)) = 1$ .

Thread: How to find a primitive root of N

LinkBack

Thread Tools

Display

How to find a primitive root of N

Similar Math Help Forum Discussions

Prove if a is a primitive root mod p^2, then it is a primitive root mod p

Algebra help: Find a primitive root β of F3[x]/(x^2 + 1)...etc

Primitive root help

primitive root

find the primitive root

Search Tags