## anonymous one year ago Find all primitive roots of 41 and 82.

1. misssunshinexxoxo
2. anonymous

If you knew that 41 is a prime number, has no integer factors and that this number will divide into 82, would that help?

3. anonymous

Is there a formula that would help me find the roots? @robtobey

4. ganeshie8

It is easy to find all the primitive roots after finding one primitive root

5. ganeshie8

If $$n$$ has a primitive root, then it has exactly $$\phi(\phi(n))$$ primitive roots. These can be found trivially by using any known primitive root.

6. ganeshie8

So you may try finding one primitive root by trial and error

7. anonymous

@ganeshie8 Would you please show me an example.

8. ganeshie8

Lets work primitive roots of 41

9. ganeshie8

$$\phi(41) = 40$$, so if $$a$$ is a primitive root, then the order of $$a$$ must be $$40$$

10. anonymous

So there are 16 primitive roots

11. UsukiDoll

can we not post links to yahoo answers? What is the point? thanks.

12. ganeshie8

There is no known analytic method for finding a primitive root. Once you find one primitive root, there is an easy way to find all other primitive roots. So lets go ahead and find one primitive root by work each integer : $$\large 2$$ : $$2^{20} \equiv (2^5)^4\equiv (-9)^4 \equiv 81^2\equiv (-1)^2\equiv 1 \pmod{41}$$ That means the order of $$2$$ must be $$\le 20$$. so $$2$$ cannot be a primitive root of $$41$$

13. ganeshie8

$$\large 3$$ : $$3^8 \equiv 81^2 \equiv 1 \pmod{41}$$ so this is a fail too

14. ganeshie8

$$\large 5$$ : $$5^{20} \equiv (5^5)^4 \equiv 9^4 \equiv 81^2 \equiv 1 \pmod{41}$$ so this is a fail too

15. ganeshie8

$$\large 6$$ : $$6^{20} \equiv (6^2)^{10} \equiv (-5)^{10} \equiv 9^2 \equiv \color{red}{-1} \pmod{41}$$ Also $$6^{8} \equiv (6^2)^4 \equiv (-5)^4 \equiv \color{red}{10} \pmod{41}$$ so we got lucky just now, $$6$$ is a primitive root of $$41$$. we can go use this to find all other primitive roots

16. ganeshie8

see if everything makes sense so far, all we did is tested each interger successively for primitive root

17. ganeshie8

And yes there are exactly $$\phi(\phi(41)) = 16$$ incongruent primitive roots for $$41$$

18. anonymous

Then how would we use 6 to find the rest @ganeshie8

19. ganeshie8

Since $$6$$ is a primitive root of $$41$$, any coprime intger is congruent to an integer of form $$6^{k}$$, where $$1\le k\le 30$$. You must be knowing that the order of $$6^k$$ is given by $\dfrac{41}{\gcd(k,~40)}$ This will equal $$41$$ if and only if $$\gcd(k, 40)=1$$. so $$k \in\{1,3,7,9,11,13,17,19,21,23,27,29,31,33,37,39\}$$ and the corresponding primitive roots are $$\{6^{1},6^{3},6^{7},6^{9},6^{11},6^{13},6^{17},6^{19},6^{21},6^{23},6^{27},6^{29},6^{31},6^{33},6^{37},6^{39}\}$$ you may reduce them under mod 41 if you wish

20. anonymous

I think I can follow your steps to get for 82. Thanks @ganeshie8

21. ganeshie8

Yw, as you can see almost all the effort was spent finding one primitive root, once you know one primitive root, generating the remaining is trivial.