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

Printable View

- May 13th 2008, 06:19 PMfanfan1609How 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 - May 13th 2008, 07:14 PMThePerfectHacker
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.

- May 13th 2008, 08:49 PMfanfan1609
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 - May 13th 2008, 09:08 PMThePerfectHacker
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.

- May 13th 2008, 10:38 PMfanfan1609
- May 14th 2008, 06:59 AMThePerfectHacker
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. - May 14th 2008, 03:17 PMfanfan1609
- May 14th 2008, 03:19 PMThePerfectHacker
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.

- May 14th 2008, 03:27 PMfanfan1609
- May 14th 2008, 04:08 PMThePerfectHacker
- Jun 14th 2008, 07:42 AMduggaboy
Can you make a general statment or "rule" to determining if g^k is a primitive root? Is there a generalization?

- Jun 14th 2008, 08:01 AMfanfan1609
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 - Jun 14th 2008, 08:27 AMduggaboy
but how would you find d? just choose vales and try?

- Jun 14th 2008, 03:17 PMfanfan1609
- Jun 14th 2008, 05:46 PMThePerfectHacker