Hw6 Problem 4

Return to Homework 6, Glossary, Theorems

Problem 4

Let $p$ and $q$ be distinct primes.
(a) Find the number of generators of the cyclic group $\mathbb{Z}_{pq}$.
(b) Find the number of generators of the cyclic group $\mathbb{Z}_{p^r}$, where $r\in \mathbb{Z}^+$.

Solution

(a) There are $p-1$ multiples of $q$ and $q-1$ of $p$ that are less than $pq$. Thus there are $(pq-1)-(p-1)-(q-1)= pq - p - q +1=(p-1)(q-1)$ positive integers less than $pq$ and relatively prime to $pq$.

(b) There are $p^{r-1}-1$ multiples of $p$ less than $p^{r}$. Thus we see that there are $p^{r}-1)-(p^{r-1})=p^{r}-p^{r-1}=p^{r-1}(p-1)$ positive integers less than $p^{r}$ and relatively prime to $p^{r}$