Exercise 2.18

Question

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\D}{\mathrm{d}}

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

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

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

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{
}{\mathrm{N}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

Prove that $\phi(n)\phi(m) = \phi((n, m))\phi([n, m])$.

Richard Ganaye · Accepted Answer

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\D}{\mathrm{d}}

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

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

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

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{
}{\mathrm{N}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\begin{proof}
Let $p_1,\cdots,p_r$ be the common prime factors of $n$ and $m$.
\begin{align*}
n &= p_1^{\alpha_1}\cdots p_r^{\alpha_r} q_1^{\lambda_1}\cdots q_s^{\lambda_s},\
m&= p_1^{\beta_1}\cdots p_r^{\beta_r} s_1^{\mu_1}\cdots s_t^{\mu_t}.\
\end{align*}
where $\alpha_i, \beta_i, \lambda_j,\mu_k \in \N^*, \ 1\leq i \leq r, 1\leq j \leq s, 1\leq k \leq t$ (the formula $\phi(p^\alpha) = p^\alpha - p^{\alpha - 1}$ is not valid if $\alpha = 0$).
Then 
\begin{align*}
n\wedge m &= p_1^{\gamma_1}\cdots p_r^{\gamma_r}\
n \vee m &= p_1^{\delta_1}\cdots p_r^{\delta_r} q_1^{\lambda_1}\cdots q_s^{\lambda_s}s_1^{\mu_1}\cdots s_t^{\mu_t},\
\end{align*}
where $\gamma_i = \min(\alpha_i,\beta_i) , \delta_i = \max(\alpha_i,\beta_i)\ (\gamma_i \geq 1, \delta_i \geq 1), 1\leq i \leq r$.
Then
\begin{align*}
\phi(n\wedge m) &=  \prod_{i=1}^r (p_i^{\gamma_i} - p_i^{\gamma_i - 1})\
\phi(n\vee m)      &=  \prod_{i=1}^r(p_i^{\delta_i} - p_i^{\delta_i - 1}) \prod_{i=1}^s (q_i^{\lambda_i} - q_i^{\lambda_i - 1}) \prod_{i=1}^t (s_i^{\mu_i} - s_i^{\mu_i - 1})
\end{align*}
As $\alpha_i + \beta_i = \min(\alpha_i,\beta_i) +  \max(\alpha_i,\beta_i) = \gamma_i + \delta_i, 1\leq i \leq r$, then
\begin{align*}
\phi(n)\phi(m) &= \prod_{i=1}^r(p_i^{\alpha_i} - p_i^{\alpha_i - 1}) \prod_{i=1}^s(q_i^{\lambda_i} - q_i^{\lambda_i - 1}) \prod_{i=1}^r(p_i^{\beta_i} - p_i^{\beta_i - 1}) \prod_{i=1}^t(s_i^{\mu_i} - s_i^{\mu_i - 1})\
&=\prod_{i=1}^r \left [ p_i^{\alpha_i + \beta_i} \left( 1- \frac{1}{p_i}ight)^2 ight]  \prod_{i=1}^s(q_i^{\lambda_i} - q_i^{\lambda_i - 1})  \prod_{i=1}^t(s_i^{\mu_i}- s_i^{\mu_i - 1})\
&=\prod_{i=1}^r \left [ p_i^{\gamma_i+\delta_i} \left( 1- \frac{1}{p_i}ight)^2 ight]  \prod_{i=1}^s(q_i^{\lambda_i} - q_i^{\lambda_i - 1})  \prod_{i=1}^t(s_i^{\mu_i}- s_i^{\mu_i - 1})\
&=\prod_{i=1}^r (p_i^{\gamma_i} - p_i^{\gamma_i - 1}) \prod_{i=1}^r(p_i^{\delta_i} - p_i^{\delta_i - 1})  \prod_{i=1}^s(q_i^{\lambda_i} - q_i^{\lambda_i - 1})  \prod_{i=1}^t(s_i^{\mu_i}- s_i^{\mu_i - 1})\
&= \phi(n\wedge m) \phi(n\vee m).
\end{align*}
\end{proof}

Exercise 2.18

Answers

Comments

Exercise 2.18

Answers

Comments

Add answer