# 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 $\displaystyle \mathbb{Z}_{101}$, $\displaystyle \mathbb{Z}_{12}$.

I cannot find an example from my lecture notes about primitive roots in $\displaystyle \mathbb{Z}_n$. What is the definition of primitive roots in $\displaystyle \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 $\displaystyle \mathbb Z_n^\times$ is an integer $\displaystyle k$ such that for each $\displaystyle i\in\{1,2,\ldots,n-1\}$ such that $\displaystyle \gcd(i,n)=1,$ there exists an integer $\displaystyle m$ such that $\displaystyle i\equiv k^m\mod n.$ (It follows that $\displaystyle \gcd(k,n)=1.)$

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

If $\displaystyle n$ is not prime, things are a little complicated. For $\displaystyle n=12,$ though, you can easily see that $\displaystyle k^2\equiv1\mod{12}$ for $\displaystyle k=1,5,7,11,$ which are the integers coprime with $\displaystyle 12.$ Hence $\displaystyle \mathbb Z_{12}^\times$ has no primitive roots since there is are no integers $\displaystyle k,m$ such that $\displaystyle k^m\equiv5\mod{12}$ even though $\displaystyle \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 $\displaystyle \mathbb{U}_{101}$ and $\displaystyle \mathbb{U}_{12}$, just in different notation.