0
$\begingroup$

Consider $\mathbb Z/n\mathbb Z$ for some $n\in\mathbb Z_{>0}$. Let $d$ be a positive divisor of $n$. Show that the number of elements $\overline a\in\mathbb Z/n\mathbb Z$ ($1\leq a\leq n$) with $\operatorname{order}(\overline a)=d$ is equal to $\phi(d)$, which is defined as $\mid\{a\in\mathbb Z\mid 1\leq a\leq n,\gcd(a,n)=1\}\mid$.

Now my book says that $\operatorname{order}(\overline a)=d$ means the same as $\gcd(a,n)=n/d$, which is equivalent to $$ a=b\cdot\frac{n}{d}\quad\text{with }\gcd(b,d)=1\text{ and }1\leq b\leq d. $$ Because we can find $\phi(d)$ such $b$’s, the proof is complete.

I don't understand where this $b$ comes from. I understand that $\begin{align}\exists m\in\mathbb Z:a=m\cdot\frac{n}{d}\end{align}$, but apparently we can say more about this $m$. It is clear that $1\leq m\leq d$. Assume $\gcd(m,d)=k>1$. I'm guessing we need some contradiction with the fact that $n/d$ is the greatest common divisor of $a$ and $n$, but I can't see how. Could someone give me a hint?

$\endgroup$
0
$\begingroup$

In what follows, (1) is justified by the following simple and useful proposition: in any group $G$, $\operatorname{order}\left(g^k\right) = \frac {\operatorname{order} g} {\gcd(\operatorname{order} g, k)}$ for any element $g$, assuming $\operatorname{order} g$ is a positive integer. Note: here notation $g^k$ corresponds to group operation being written multiplicatively. In your case it would be written additively, namely $kg$.

Let $a = m \cdot \frac n d$. Then

$$\begin{align*}\operatorname{order}\bar a &= \operatorname{order}\left( m \cdot \frac n d \cdot \bar 1\right) \\ (1)&= \frac{\operatorname{order} \bar 1}{\gcd(\operatorname{order} \bar 1, m \cdot \frac n d)} \\ &= \frac n {\gcd(n,m\cdot \frac n d)} \\ &= \frac n {\gcd(d \cdot \frac n d, m \cdot \frac n d)} \\ &= \frac n {\gcd(d, m) \cdot \frac n d} \\ &= \frac d {\gcd(d,m)} \end{align*}$$

Thus, $\operatorname{order}\bar a = d \iff \gcd(d,m) = 1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.