Question

Find all primitive roots of 41 and 82.

Answer 1

This should help https://answers.yahoo.com/question/index?qid=20150407193751AAnlAo6

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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.

Answer 6

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

Answer 7

@ganeshie8 Would you please show me an example.

Answer 8

Lets work primitive roots of 41

Answer 9

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

Answer 10

So there are 16 primitive roots

Answer 11

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

Answer 12

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\)

Answer 13

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

Answer 14

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

Answer 15

\(\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

Answer 16

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

Answer 17

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

Answer 18

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

Answer 19

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

Answer 20

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

Answer 21

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.