1. ## primitive roots

could you please tell me the primitive roots of 83, and 149.

also do you know a way to find out the number of primitive roots a number has, it doesn't necessarily have to tell me what they are

thanks

2. Originally Posted by hanjp123
could you please tell me the primitive roots of 83, and 149.

also do you know a way to find out the number of primitive roots a number has, it doesn't necessarily have to tell me what they are

thanks

3. i'm still kind of confused

4. Once you find a primitive root, then you can find all other primitive roots by using this fact:

Let $\displaystyle g$ be a primitive root modulo $\displaystyle n$. Then $\displaystyle g^k$ is also a primitive root if and only if $\displaystyle \gcd(k, \phi (n)) = 1$.

So for 89, notice that 3 is a primitive root. Then $\displaystyle 3^k$ where $\displaystyle \gcd(k, \phi (89)) = 1$ occurs will give you another primitive root.

As for the number of primitive roots, all primes have $\displaystyle \phi (p-1)$ primitive roots.

Even more general, if some $\displaystyle n$ has primitive roots, then there are $\displaystyle \phi \left( \phi (n)\right)$ of them.