Primitive roots, specifically of 18

[abertram28]

this problem is annoying. I've found that the primitive roots of 9 are 2 and 5. since 2|18 it can't be a root. i know via some theorems in my book that if 5 is a primitive root of 3, then its a primitive root of 3^k, and also of 2*3^k.

sorry about not using latex, shouldn't need it for this one though, it won't be too messy I am sure.

so the second one, i know i can find by brute force, but id like something more elegant. i know there are only phi of phi of 18, or 2, primitive roots.

i know also by table lookup that the second one of 18 is 11.

do i need to start with the gcd(a,18) list and just eliminate ones until i can't eliminate 11? that doesn't seem right, i remember seeing something in class about this, but the teacher said not to record it in notes because it was in the book, but the book only identifies the one, because i think it is always the smallest. or do i just take 2 mod 9 congruent to 11 mod 9, and that's it? sorry if i just missed something plain as day.

 

[Hurkyl]

Bleh, it took a minute to figure out about what you're talking.

Did you notice that 11 is a primitive root of 9? (and of 3)

 

[thepatientmental]

It seems like you are on the right track in finding the primitive roots of 18. It is true that if a number is a primitive root of a smaller number, it will also be a primitive root of any power of that smaller number. In this case, since 5 is a primitive root of 9, it will also be a primitive root of 18.

To find the second primitive root of 18, you can use the fact that there are only phi(phi(18)) = 2 primitive roots of 18. This means that you can eliminate all the numbers that are not relatively prime to 18 and the remaining numbers will be the primitive roots. So in this case, you can eliminate 2 since it is not relatively prime to 18, leaving only 5 and 11 as the possible primitive roots.

Now, you can use the property that if a number is a primitive root of a prime p, it will also be a primitive root of any multiple of p. Since 5 is a primitive root of 3, it will also be a primitive root of 6 (multiples of 3). Similarly, since 11 is a primitive root of 2, it will also be a primitive root of 12 (multiples of 2).

Therefore, the only possible primitive roots of 18 are 5 and 11. To determine which one is the second primitive root, you can use the fact that if a number is a primitive root of a prime p, it will also be a primitive root of any multiple of p. Since 5 is a primitive root of 3, it will also be a primitive root of any power of 3. This means that 5 will also be a primitive root of 9, 27, 81, etc. However, since we already know that 5 is not a primitive root of 18, we can conclude that 11 must be the second primitive root of 18.

I hope this helps and clarifies your understanding of finding primitive roots of a number. It is a bit of a trial and error process, but using the properties mentioned above can make it more efficient and elegant.