\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

\begin{description}

\item[(i)]
Define the M\"{o}bius function, $\mu(n)$.

\item[(ii)]
Let $G$ denote the cyclic group of order $n$. For each positive
integer, $d$, dividing $n$ set

$$f(d)=|\{g\in G|\textrm{order}(g)=d\}|,$$

the number of elements of order $d$ in $G$. Use the M\"{o}bius
Inversion Formula to show that

$$f(n)=\sum_{d|n}\mu\left(\frac{n}{d}\right)d,$$

where the sum is over all positive divisors of $n$.

\item[(iii)]
What is the relation between (ii) and Euler's function, $\phi(n)$?

\end{description}



ANSWER

\begin{description}

\item[(i)]
By definition

$$\mu{n}=\left\{\begin{array}{cl}1&\textrm{ if }n=1\\0&\textrm{ if
$n>1$ and $p^2|n$ for some prime $p$,}\\(-1)^t&\textrm{ if $n$ is
the product of $t$ distinct primes.}\end{array}\right.$$

\item[(ii)]
Every element of $G$ has precisely one order, $D$, which divides
$n$. Since $G$ is cyclic every possible $d$ occurs as the order of
some element. Hence we have

$$n=|G|=\sum_{d|n}f(d)=F(n).$$

By the M\"{o}bius Inversion Formula

$$f(n)=\sum_{d|n}\mu\left(\frac{n}{d}\right)F(d)=\sum_{d|n}\mu
\left(\frac{n}{d}\right)d.$$

\item[(iii)]
Let $g\in G$ denote a generator. The element of $G$ of order $n$
are precisely the $g^j$ with gcd$(j,n)=1$. Also distinct such
$j$'s give rise to distinct $g^j$'s so that $f(n)=\phi(n)$. The
formula

$$\phi(n)=\sum_{d|n}\mu\left(\frac{n}{d}\right)d$$

\end{description}




\end{document}