1. ## Primitive Roots

Hello everyone!

I have a question about primitive roots. I'm just trying to come up with general strategies that would help we remember tricks on how to find all primitive roots. So I came up with a few basic cases and perhaps one of you could explain how to solve them. Here it goes:

Find all primitive roots for:
i) 13
ii) 2 * 13
iii) 13^2
iv) 2 * 13^4

Thanks again for your help. I appreciate it. Happy Easter.

2. Originally Posted by mathmaniac234
Hello everyone!

I have a question about primitive roots. I'm just trying to come up with general strategies that would help we remember tricks on how to find all primitive roots. So I came up with a few basic cases and perhaps one of you could explain how to solve them. Here it goes:

Find all primitive roots for:
i) 13
I claim $2$ is a primitive root modulo $13$ (I'll let you verify).

Let's find all other primitive roots:

Consider $\{2^1,2^2,2^3,\cdots,2^{p-1}\}$. All other primitive roots will be of the form $2^m$ where $(m,\phi(13))=1$.

This means there are $\phi(\phi(13))=4$ primitive roots.

$(1,12)=(5,12)=(7,12)=(11,12)=1$

So our Primitive roots are $\{2, 2^5, 2^7,2^{11}\} = \{2,6,7,11\}$.

3. There's no good way to find primitive roots. There is one computer algorithm which runs in polynomial time *under GRH*, so really I believe that there's no general way to do it.

However, 2 or 3 usually works. Check these two before you complain about finding primitive roots.