# Find the number of primitive roots in Z_101, Z_12

• Apr 25th 2012, 07:23 AM
math2011
Find the number of primitive roots in Z_101, Z_12
Find the number of primitive roots in $\mathbb{Z}_{101}$, $\mathbb{Z}_{12}$.

I cannot find an example from my lecture notes about primitive roots in $\mathbb{Z}_n$. What is the definition of primitive roots in $\mathbb{Z}_n$?

The answers are 40 and none respectively.
• Apr 25th 2012, 07:42 AM
Sylvia104
Re: Find the number of primitive roots in Z_101, Z_12
A primitive root in $\mathbb Z_n^\times$ is an integer $k$ such that for each $i\in\{1,2,\ldots,n-1\}$ such that $\gcd(i,n)=1,$ there exists an integer $m$ such that $i\equiv k^m\mod n.$ (It follows that $\gcd(k,n)=1.)$

When $n=p$ is a prime, $\mathbb Z_p^\times$ always has primitive roots. Indeed $\mathbb Z_p^\times$ is a cyclic group of order $p-1$ generated by any primitive root; hence the number of primitive roots is $\varphi(p-1).$ This answers your question for $\mathbb Z_{101}^\times.$

If $n$ is not prime, things are a little complicated. For $n=12,$ though, you can easily see that $k^2\equiv1\mod{12}$ for $k=1,5,7,11,$ which are the integers coprime with $12.$ Hence $\mathbb Z_{12}^\times$ has no primitive roots since there is are no integers $k,m$ such that $k^m\equiv5\mod{12}$ even though $\gcd(5,12)=1.$
• Apr 26th 2012, 06:49 AM
math2011
Re: Find the number of primitive roots in Z_101, Z_12
Thank you. I see. This is really the same as primitive roots in $\mathbb{U}_{101}$ and $\mathbb{U}_{12}$, just in different notation.