Exercise 4.3.24* ($\prod\limits_{\underset{(a,n) = 1}{a=1}}^n a = n^{\phi(n)} \prod_{d \mid n} (d!/d^d)^{\mu(n/d)}$)

Question

Show that $\prod\limits_{\underset{(a,n) = 1}{a=1}}^n a = n^{\phi(n)} \prod_{d \mid n} (d!/d^d)^{\mu(n/d)}

Richard Ganaye · Accepted Answer

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

\begin{proof} 
We define
$$f(n) = \prod_{a \in [\![1,n]\!],\, a \wedge n = 1} \frac{a}{n}, \qquad F(n) = \prod_{d \mid n} f(d).$$
Since this product has $\phi(n)$ factors,
\begin{align}
f(n) =  n^{-\phi(n)}\prod_{a \in [\![1,n]\!],\, a \wedge n = 1} a.
\end{align}

Consider the set $An$ of fractions $x$ of the form $x = k/n$, where $1 \leq k \leq n$:
\begin{align*}
A_n&= \{x \in \Q \mid  \exists k \in [\![1,n]\!],\ x = k/n\} \
&= \left\{\frac{1}{n}, \frac{2}{n}, \cdots, \frac{n}{n}ight \}.
\end{align*}
Consider also the set $B_n$ of fractions $x$ of the form $x = a/d$, where $d \mid n$ and $1 \leq a \leq d$:
\begin{align*}
B_n = \{x \in \Q \mid \exists a \in \N^*,\ \exists d \in \N^*,\ d \mid n 	ext{ and } 1 \leq a \leq d\}.
\end{align*}

We show that $A_n = B_n$.

If $x \in A_n$, then $x = k/n$, where $1 \leq k \leq n$, thus $0 < x \leq 1$. Put $\delta = k \wedge n$. Then there are integers $a$ and $d$ such that $k = \delta a, n = \delta d$ and $a\wedge d = 1$.  So $x$ is equal to a reduced fraction  $x =a/d$, where $a \wedge d = 1$ and $d \mid n$. Since $0<x\leq 1$, we have $1 \leq a \leq n$, so $x \in B$.
 
 Conversely, if $x \in B_n$, then $x = a/d$, where $a\wedge d = 1$, $d \mid n$ and $1 \leq a \leq d$, thus $0<x\leq 1$. Then $n = q d$ for some integer $q$. Put $k = qa$. Then $x = a/d = k/n$. Since $0 < x \leq 1$, we have $1 \leq k \leq n$, so $x \in A_n$.
 
 The equality $B_n = A_n$ gives $\prod_{x \in B_n} x = \prod_{x \in A_n} x$, so
 \begin{align*}
 \prod_{d\mid n}\  \prod_{a\in [\![1,d]\!],\, a\wedge d = 1} \frac{a}{d} &= \frac{1}{n} \cdot \frac{2}{n}\cdots \cdots \frac{n}{n} = \frac{n!}{n^n}.
 \end{align*}
 By definition of $f$ and $F$, this gives
 \begin{align}
F(n) &=  \prod_{d \mid n} f(d) = \frac{n!}{n^n}.
 \end{align}
 Then the Möbius multiplicative inversion formula (Problem 23) and (2) give 
 \begin{align*}
 f(n) &= \prod_{\delta \mid n} F\left(\frac{n}{\delta}ight)^{\mu(\delta)}\
 &= \prod_{d \mid n} F(d)^{\mu(n/d)}&(d = n/\delta)\
 &=\prod_{d \mid n} \left(\frac{d!}{d^d}ight)^{\mu(n/d)}.
 \end{align*}
 This shows, using (1),  that
 $$ n^{-\phi(n)}\prod_{a \in [\![1,n]\!],\, a \wedge n = 1} a = \prod_{d \mid n} \left(\frac{d!}{d^d}ight){\mu(n/d)},$$
 so
 $$ \prod_{a \in [\![1,n]\!],\, a \wedge n = 1} a = n^{\phi(n)} \prod_{d \mid n} \left(\frac{d!}{d^d}ight)^{\mu(n/d)}.$$
 For every positive integer $n$, $\prod\limits_{\underset{(a,n) = 1}{a=1}}^n a = n^{\phi(n)} \prod_{d \mid n} (d!/d^d)^{\mu(n/d)}$.
 
 \end{proof}

Exercise 4.3.24* ($\prod\limits_{\underset{(a,n) = 1}{a=1}}^n a = n^{\phi(n)} \prod_{d \mid n} (d!/d^d)^{\mu(n/d)}$)

Answers

Comments

Exercise 4.3.24* ($\prod\limits_{\underset{(a,n) = 1}{a=1}}^n a = n^{\phi(n)} \prod_{d \mid n} (d!/d^d)^{\mu(n/d)}$)

Answers

Comments

Add answer