% -------------------------------------------------------------
% NOTE ON THE DETAILED AND SHORT VERSIONS:
% -------------------------------------------------------------
% This paper comes in two versions, a detailed and a short one.
% The short version should be more than sufficient for any
% reasonable use; the detailed one was written purely to
% convince the author of its correctness.
% To switch between the two versions, find the line containing
% "\newenvironment{noncompile}{}{}" in this LaTeX file.
% Look at the two lines right beneath this line.
% To compile the detailed version, they should be as follows:
%   \includecomment{verlong}
%   \excludecomment{vershort}
% To compile the short version, they should be as follows:
%   \excludecomment{verlong}
%   \includecomment{vershort}
% As a rule, the line
%   \excludecomment{noncompile}
% should stay as it is.
% -------------------------------------------------------------
% NOTES ON SOME HACKS USED IN THIS FILE:
% -------------------------------------------------------------
% One of my pet peeves with amsthm is its use of italics in the theorem and
% proposition environments; this makes math and text indistinguishable in said
% enviroments. To avoid this, I redefine the enviroments to use the standard
% font and to use a hanging indent, along with a bold vertical bar to its
% left, to distinguish these environments from surrounding text. (Along with
% the advantage of distinguishing math from text, this also allows nesting
% several such environments inside each other, like a definition inside a
% remark. I'm not sure how good of an idea this is, though. There are also
% downsides related to the hanging indentation, such as footnotes out of it
% being painful to do right.) This is done starting from the line
%   \theoremstyle{definition}
% and until the line
%   {\end{leftbar}\end{exmp}}

\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage{amsmath}
\usepackage{comment}
\usepackage{needspace}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{amsthm}
\usepackage{tabu}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Monday, November 02, 2015 20:28:47}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{TODO}
\newenvironment{todo}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exmp}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\newenvironment{obsolete}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\excludecomment{obsolete}
\newcommand{\kk}{\mathbf{k}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\ev}{\operatorname{ev}}
\newcommand{\Comp}{\operatorname{Comp}}
\newcommand{\bk}{\mathbf{k}}
\newcommand{\Nplus}{\mathbb{N}_{+}}
\newcommand{\NN}{\mathbb{N}}
\newcommand\arxiv[1]{\href{http://www.arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\setlength\textheight{22.5cm}
\setlength\textwidth{15cm}
\ihead{Mathematical Reflections problem U275}
\ohead{\today}
\begin{document}

\title{Mathematical Reflections problem U275}
\author{Darij Grinberg}
\date{\today}
\maketitle

\section{Problem}

Let $\mu$ be the number-theoretical M\"{o}bius function; this is the function
$\left\{  1,2,3,\ldots\right\}  \rightarrow{\mathbb{Z}}$ defined by
\[
\left(
\begin{array}
[c]{c}%
\mu\left(  m\right)  =%
\begin{cases}
0, & \text{if }m\text{ is not squarefree};\\
\left(  -1\right)  ^{\left(  \text{number of primes dividing }m\right)  }, &
\text{if }m\text{ is squarefree}%
\end{cases}
\\
\ \ \ \ \ \ \ \ \ \ \text{for every }m\in\left\{  1,2,3,\ldots\right\}
\end{array}
\right)  .
\]


Let $a_{f}$ be a real number for every positive integer $f$. Prove
that\footnote{Here, as usual, a summation sign of the form $\sum\limits_{h\mid
N}$ (where $N$ is a positive integer) denotes a summation in which $h$ runs
over all \textbf{positive} divisors of $N$.}%
\[
\sum_{d\mid m}\sum_{e\mid n}\sum_{g\mid\gcd\left(  d,e\right)  }\dfrac{\mu
(g)}{g}dea_{de/g}=\sum\limits_{f\mid mn}fa_{f}%
\]
for any positive integers $n$ and $m$.

\subsection{Remark}

The above problem is my Problem U275 published in Mathematical Reflections
2013 (issue 4), slightly rewritten to make it more self-contained.
\footnote{See
\texttt{\url{https://www.awesomemath.org/wp-content/uploads/mr_4_2013_solutions.pdf}}
for a different solution by Daniel Lasoasa.}

Of course, the problem can be straightforwardly generalized: Let $A$ be any
$\mathbb{Q}$-vector space. Then, we can require the $a_{f}$ to be elements of
$A$ instead of requiring them to be real numbers. The problem still remains
valid in this generality, and the solution given below still applies.

\section{Solution}

Before we start solving the problem, let us collect some useful
number-theoretical facts.

For every positive integer $N$, we let $\mathbb{N}_{\mid N}$ denote the set of
all positive divisors of $N$. Thus, for every positive integer $N$, we have%
\begin{align*}
\mathbb{N}_{\mid N}  &  =\left(  \text{the set of all positive divisors of
}N\right) \\
&  =\left\{  h\in\left\{  1,2,3,\ldots\right\}  \ :\ h\mid N\right\}  .
\end{align*}


\begin{verlong}
Let us make some simple observations:

\begin{lemma}
\label{lem.Ndivsum}Let $N$ be a positive integer. Let $\left(  b_{g}\right)
_{g\in\mathbb{N}_{\mid N}}\in\mathbb{R}^{\mathbb{N}_{\mid N}}$ be a family of
real numbers. Then,%
\[
\sum_{g\mid N}b_{g}=\sum_{g\in\mathbb{N}_{\mid N}}b_{g}.
\]

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.Ndivsum}.]The sum $\sum_{g\mid N}b_{g}$ is the sum of
all $b_{g}$, where $g$ runs over all \textbf{positive} divisors of $N$
(because of the definition of the summation sign $\sum_{g\mid N}$). In other
words,%
\[
\sum_{g\mid N}b_{g}=\underbrace{\sum_{\substack{g\text{ is a positive}%
\\\text{divisor of }N}}}_{\substack{=\sum_{g\in\left(  \text{the set of all
positive divisors of }N\right)  }\\=\sum_{g\in\mathbb{N}_{\mid N}%
}\\\text{(since }\left(  \text{the set of all positive divisors of }N\right)
=\mathbb{N}_{\mid N}\text{)}}}b_{g}=\sum_{g\in\mathbb{N}_{\mid N}}b_{g}.
\]
This proves Lemma \ref{lem.Ndivsum}.
\end{proof}
\end{verlong}

\begin{lemma}
\label{lem.divsumdeflate}Let $m$ and $g$ be two positive integers. Let
$\left(  b_{d}\right)  _{d\in\mathbb{N}_{\mid m}}\in\mathbb{R}^{\mathbb{N}%
_{\mid m}}$ be a family of real numbers. Then,%
\[
\sum_{\substack{d\mid m;\\g\mid d}}b_{d/g}=\sum_{\substack{d\mid m;\\g\mid
m/d}}b_{d}.
\]

\end{lemma}

\begin{vershort}
\begin{proof}
[Proof of Lemma \ref{lem.divsumdeflate}.]The condition $g\mid m/d$ on a
divisor $d$ of $m$ is equivalent to the condition $dg\mid m$. Hence,%
\[
\sum_{\substack{d\mid m;\\g\mid m/d}}b_{d}=\sum_{\substack{d\mid m;\\dg\mid
m}}b_{d}=\sum_{\substack{d\mid m;\\g\mid d}}b_{d/g}\ \ \ \ \ \ \ \ \ \ \left(
\text{here, we have substituted }d/g\text{ for }d\text{ in the sum}\right)  .
\]

\end{proof}
\end{vershort}

\begin{verlong}
\begin{proof}
[Proof of Lemma \ref{lem.divsumdeflate}.]We know that $\mathbb{N}_{\mid m}$ is
the set of all positive divisors of $m$ (by the definition of $\mathbb{N}%
_{\mid m}$). In other words,%
\[
\mathbb{N}_{\mid m}=\left(  \text{the set of all positive divisors of
}m\right)  .
\]
Now, the sum $\sum_{\substack{d\mid m;\\g\mid d}}b_{d/g}$ is the sum of all
$b_{d/g}$, where $g$ runs over all \textbf{positive} divisors of $m$
satisfying $g\mid d$ (because of the definition of the summation sign
$\sum_{\substack{d\mid m;\\g\mid d}}$). In other words,%
\begin{equation}
\sum_{\substack{d\mid m;\\g\mid d}}b_{d/g}=\underbrace{\sum_{\substack{d\text{
is a positive divisor of }m\text{;}\\g\mid d}}}_{\substack{=\sum
_{\substack{d\in\left(  \text{the set of all positive divisors of }m\right)
;\\g\mid d}}\\=\sum_{\substack{d\in\mathbb{N}_{\mid m};\\g\mid d}%
}\\\text{(since }\left(  \text{the set of all positive divisors of }m\right)
=\mathbb{N}_{\mid m}\text{)}}}b_{d/g}=\sum_{\substack{d\in\mathbb{N}_{\mid
m};\\g\mid d}}b_{d/g}. \label{pf.lem.divsumdeflate.1}%
\end{equation}
Also, the sum $\sum_{\substack{d\mid m;\\g\mid m/d}}b_{d}$ is the sum of all
$b_{d}$, where $d$ runs over all \textbf{positive} divisors of $m$ satisfying
$g\mid m/d$ (because of the definition of the summation sign $\sum
_{\substack{d\mid m;\\g\mid m/d}}$). In other words,%
\begin{equation}
\sum_{\substack{d\mid m;\\g\mid m/d}}b_{d}=\underbrace{\sum_{\substack{d\text{
is a positive divisor of }m\text{;}\\g\mid m/d}}}_{\substack{=\sum
_{\substack{d\in\left(  \text{the set of all positive divisors of }m\right)
;\\g\mid m/d}}\\=\sum_{\substack{d\in\mathbb{N}_{\mid m};\\g\mid
m/d}}\\\text{(since }\left(  \text{the set of all positive divisors of
}m\right)  =\mathbb{N}_{\mid m}\text{)}}}b_{d}=\sum_{\substack{d\in
\mathbb{N}_{\mid m};\\g\mid m/d}}b_{d}. \label{pf.lem.divsumdeflate.2}%
\end{equation}


On the other hand, for every $d\in\left\{  x\in\mathbb{N}_{\mid m}\ :\ g\mid
x\right\}  $, we have \newline$d/g\in\left\{  x\in\mathbb{N}_{\mid
m}\ :\ g\mid m/x\right\}  $\ \ \ \ \footnote{\textit{Proof.} Let $d\in\left\{
x\in\mathbb{N}_{\mid m}\ :\ g\mid x\right\}  $. We must prove that
$d/g\in\left\{  x\in\mathbb{N}_{\mid m}\ :\ g\mid m/x\right\}  $.
\par
Indeed, we have $d\in\left\{  x\in\mathbb{N}_{\mid m}\ :\ g\mid x\right\}  $.
In other words, $d$ is an $x\in\mathbb{N}_{\mid m}$ satisfying $g\mid x$. In
other words, $d$ is an element of $\mathbb{N}_{\mid m}$ and satisfies $g\mid
d$.
\par
We know that $d$ is an element of $\mathbb{N}_{\mid m}$. In other words, $d$
is an element of the set of all positive divisors of $m$ (since $\mathbb{N}%
_{\mid m}$ is the set of all positive divisors of $m$). In other words, $d$ is
a positive divisor of $m$. In other words, $d$ is a positive integer and a
divisor of $m$.
\par
We have $d\mid m$ (since $d$ divides $m$) and thus $m/d\in\mathbb{Z}$. Also,
$g\mid d$, so that $d/g\in\mathbb{Z}$. Now, $m/\left(  d/g\right)
=\underbrace{\left(  m/d\right)  }_{\in\mathbb{Z}}\underbrace{g}%
_{\in\mathbb{Z}}\in\mathbb{Z}$, and thus $d/g\mid m$ (since $d/g\in\mathbb{Z}%
$). Also, $\left(  m/\left(  d/g\right)  \right)  /g=m/d\in\mathbb{Z}$ and
thus $g\mid m/\left(  d/g\right)  $ (since $m/\left(  d/g\right)
\in\mathbb{Z}$).
\par
Also, the number $d/g$ is positive (since $d$ and $g$ are positive), and thus
a positive integer (since $d/g\in\mathbb{Z}$). Also, $d/g$ is a divisor of $m$
(since $d/g\mid m$). Hence, $d/g$ is a positive divisor of $m$ (since $d/g$ is
a positive integer). In other words, $d/g$ is an element of the set of all
positive divisors of $m$. In other words, $d/g$ is an element of
$\mathbb{N}_{\mid m}$ (since $\mathbb{N}_{\mid m}$ is the set of all positive
divisors of $m$). Hence, $d/g$ is an element of $\mathbb{N}_{\mid m}$ and
satisfies $g\mid m/\left(  d/g\right)  $. In other words, $d/g$ is an
$x\in\mathbb{N}_{\mid m}$ satisfying $g\mid m/x$. In other words,
$d/g\in\left\{  x\in\mathbb{N}_{\mid m}\ :\ g\mid m/x\right\}  $, qed.}.
Hence, we can define a map%
\[
\mathbf{A}:\left\{  x\in\mathbb{N}_{\mid m}\ :\ g\mid x\right\}
\rightarrow\left\{  x\in\mathbb{N}_{\mid m}\ :\ g\mid m/x\right\}
\]
by setting%
\[
\left(  \mathbf{A}\left(  d\right)  =d/g\ \ \ \ \ \ \ \ \ \ \text{for every
}d\in\left\{  x\in\mathbb{N}_{\mid m}\ :\ g\mid x\right\}  \right)  .
\]
Consider this map $\mathbf{A}$.

Furthermore, for every $d\in\left\{  x\in\mathbb{N}_{\mid m}\ :\ g\mid
m/x\right\}  $, we have $dg\in\left\{  x\in\mathbb{N}_{\mid m}\ :\ g\mid
x\right\}  $\ \ \ \ \footnote{\textit{Proof.} Let $d\in\left\{  x\in
\mathbb{N}_{\mid m}\ :\ g\mid m/x\right\}  $. We must prove that
$dg\in\left\{  x\in\mathbb{N}_{\mid m}\ :\ g\mid x\right\}  $.
\par
Indeed, we have $d\in\left\{  x\in\mathbb{N}_{\mid m}\ :\ g\mid m/x\right\}
$. In other words, $d$ is an $x\in\mathbb{N}_{\mid m}$ satisfying $g\mid m/x$.
In other words, $d$ is an element of $\mathbb{N}_{\mid m}$ and satisfies
$g\mid m/d$.
\par
We know that $d$ is an element of $\mathbb{N}_{\mid m}$. In other words, $d$
is an element of the set of all positive divisors of $m$ (since $\mathbb{N}%
_{\mid m}$ is the set of all positive divisors of $m$). In other words, $d$ is
a positive divisor of $m$. In other words, $d$ is a positive integer and a
divisor of $m$.
\par
We have $d\mid m$ (since $d$ divides $m$) and thus $m/d\in\mathbb{Z}$. Also,
$g\mid m/d$, so that $\dfrac{m/d}{g}\in\mathbb{Z}$. Thus, $m/\left(
dg\right)  =\dfrac{m/d}{g}\in\mathbb{Z}$. Hence, $dg\mid m$. In other words,
$dg$ is a divisor of $m$. Clearly, $g\mid dg$.
\par
The number $dg$ is a positive integer (since $d$ and $g$ are positive
integers) and a divisor of $m$. In other words, $dg$ is a positive divisor of
$m$. In other words, $dg$ is an element of the set of all positive divisors of
$m$. In other words, $dg$ is an element of $\mathbb{N}_{\mid m}$ (since
$\mathbb{N}_{\mid m}$ is the set of all positive divisors of $m$). Hence, $dg$
is an element of $\mathbb{N}_{\mid m}$ and satisfies $g\mid dg$. In other
words, $dg$ is an $x\in\mathbb{N}_{\mid m}$ satisfying $g\mid x$. In other
words, $dg\in\left\{  x\in\mathbb{N}_{\mid m}\ :\ g\mid x\right\}  $, qed.}.
Hence, we can define a map%
\[
\mathbf{B}:\left\{  x\in\mathbb{N}_{\mid m}\ :\ g\mid m/x\right\}
\rightarrow\left\{  x\in\mathbb{N}_{\mid m}\ :\ g\mid x\right\}
\]
by setting%
\[
\left(  \mathbf{B}\left(  d\right)  =dg\ \ \ \ \ \ \ \ \ \ \text{for every
}d\in\left\{  x\in\mathbb{N}_{\mid m}\ :\ g\mid m/x\right\}  \right)  .
\]
Consider this map $\mathbf{B}$.

We have $\mathbf{A}\circ\mathbf{B}=\operatorname*{id}$%
\ \ \ \ \footnote{\textit{Proof.} For every $d\in\left\{  x\in\mathbb{N}_{\mid
m}\ :\ g\mid m/x\right\}  $, we have
\begin{align*}
\left(  \mathbf{A}\circ\mathbf{B}\right)  \left(  d\right)   &  =\mathbf{A}%
\left(  \underbrace{\mathbf{B}\left(  d\right)  }_{\substack{=dg\\\text{(by
the definition of }\mathbf{B}\text{)}}}\right)  =\mathbf{A}\left(  dg\right)
=\left(  dg\right)  /g\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of
}\mathbf{A}\right) \\
&  =d=\operatorname*{id}\left(  d\right)  .
\end{align*}
In other words, $\mathbf{A}\circ\mathbf{B}=\operatorname*{id}$, qed.} and
$\mathbf{B}\circ\mathbf{A}=\operatorname*{id}$%
\ \ \ \ \footnote{\textit{Proof.} For every $d\in\left\{  x\in\mathbb{N}_{\mid
m}\ :\ g\mid x\right\}  $, we have
\begin{align*}
\left(  \mathbf{B}\circ\mathbf{A}\right)  \left(  d\right)   &  =\mathbf{B}%
\left(  \underbrace{\mathbf{A}\left(  d\right)  }_{\substack{=d/g\\\text{(by
the definition of }\mathbf{A}\text{)}}}\right)  =\mathbf{B}\left(  d/g\right)
=\left(  d/g\right)  g\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of
}\mathbf{A}\right) \\
&  =d=\operatorname*{id}\left(  d\right)  .
\end{align*}
In other words, $\mathbf{B}\circ\mathbf{A}=\operatorname*{id}$, qed.}. In
other words, the maps $\mathbf{A}$ and $\mathbf{B}$ are mutually inverse.
Hence, the map $\mathbf{A}$ is invertible. In other words, the map
$\mathbf{A}$ is a bijection. Now, (\ref{pf.lem.divsumdeflate.2}) becomes%
\begin{align*}
\sum_{\substack{d\mid m;\\g\mid m/d}}b_{d}  &  =\underbrace{\sum
_{\substack{d\in\mathbb{N}_{\mid m};\\g\mid m/d}}}_{=\sum_{d\in\left\{
x\in\mathbb{N}_{\mid m}\ :\ g\mid m/x\right\}  }}b_{d}=\sum_{d\in\left\{
x\in\mathbb{N}_{\mid m}\ :\ g\mid m/x\right\}  }b_{d}\\
&  =\underbrace{\sum_{d\in\left\{  x\in\mathbb{N}_{\mid m}\ :\ g\mid
x\right\}  }}_{=\sum_{\substack{d\in\mathbb{N}_{\mid m};\\g\mid d}%
}}\underbrace{b_{\mathbf{A}\left(  d\right)  }}_{\substack{=b_{d/g}%
\\\text{(since }\mathbf{A}\left(  d\right)  =d/g\\\text{(by the definition of
}\mathbf{A}\text{))}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we substituted }\mathbf{A}\left(  d\right)  \text{ for }d\text{ in
the sum, since the}\\
\text{map }\mathbf{A}:\left\{  x\in\mathbb{N}_{\mid m}\ :\ g\mid x\right\}
\rightarrow\left\{  x\in\mathbb{N}_{\mid m}\ :\ g\mid m/x\right\} \\
\text{is a bijection}%
\end{array}
\right) \\
&  =\sum_{\substack{d\in\mathbb{N}_{\mid m};\\g\mid d}}b_{d/g}=\sum
_{\substack{d\mid m;\\g\mid d}}b_{d/g}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{pf.lem.divsumdeflate.1})}\right)  .
\end{align*}
This proves Lemma \ref{lem.divsumdeflate}.
\end{proof}
\end{verlong}

\begin{lemma}
\label{lem.gcd}Let $u$ and $v$ be two positive integers. Let $x$ be an
integer. If $x\mid u$ and $x\mid v$, then $x\mid\gcd\left(  u,v\right)  $.
\end{lemma}

\begin{vershort}
\begin{proof}
[Proof of Lemma \ref{lem.gcd}.]This is a classical result.
\end{proof}
\end{vershort}

\begin{verlong}
\begin{proof}
[Proof of Lemma \ref{lem.gcd}.]We know that $x$ is a divisor of $u$ (since
$x\mid u$) and of $v$ (since $x\mid v$). In other words, $x$ is a common
divisor of $u$ and $v$.

A classical property of the greatest common divisor states the following:
Every common divisor of two positive integers is a divisor of their greatest
common divisor. In other words, if $a$ and $b$ are two positive integers, then
every common divisor of $a$ and $b$ is a divisor of $\gcd\left(  a,b\right)
$. Applying this to $a=u$ and $b=v$, we conclude that every common divisor of
$u$ and $v$ is a divisor of $\gcd\left(  u,v\right)  $. In other words, if $y$
is any common divisor of $u$ and $v$, then $y$ is a divisor of $\gcd\left(
u,v\right)  $. We can apply this to $y=x$ (since $x$ is a common divisor of
$u$ and $v$), and thus conclude that $x$ is a divisor of $\gcd\left(
u,v\right)  $. In other words, $x\mid\gcd\left(  u,v\right)  $. This proves
Lemma \ref{lem.gcd}.
\end{proof}
\end{verlong}

\begin{lemma}
\label{lem.gcdsum}Let $u$ and $v$ be two positive integers. Let $\left(
b_{g}\right)  _{g\in\mathbb{N}_{\mid u}}\in\mathbb{R}^{\mathbb{N}_{\mid u}}$
be a family of real numbers. Then,%
\[
\sum_{\substack{g\mid u;\\g\mid v}}b_{g}=\sum_{g\mid\gcd\left(  u,v\right)
}b_{g}.
\]

\end{lemma}

\begin{vershort}
\begin{proof}
[Proof of Lemma \ref{lem.gcdsum}.]Both sums range over the same set of $g$'s,
since the positive divisors of $u$ which also divide $v$ are precisely the
positive divisors of $\gcd\left(  u,v\right)  $ (because of Lemma
\ref{lem.gcd}).
\end{proof}
\end{vershort}

\begin{verlong}
\begin{proof}
[Proof of Lemma \ref{lem.gcdsum}.]We first notice that%
\begin{equation}
\left\{  g\in\mathbb{N}_{\mid u}\ :\ g\mid v\right\}  =\mathbb{N}_{\mid
\gcd\left(  u,v\right)  } \label{pf.lem.gcdsum.equiv}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.lem.gcdsum.equiv}):} The set
$\mathbb{N}_{\mid u}$ is the set of all positive divisors of $u$ (by the
definition of $\mathbb{N}_{\mid u}$). The set $\mathbb{N}_{\mid\gcd\left(
u,v\right)  }$ is the set of all positive divisors of $\gcd\left(  u,v\right)
$ (by the definition of $\mathbb{N}_{\mid\gcd\left(  u,v\right)  }$).
\par
We shall first prove that $\left\{  g\in\mathbb{N}_{\mid u}\ :\ g\mid
v\right\}  \subseteq\mathbb{N}_{\mid\gcd\left(  u,v\right)  }$.
\par
Let $h\in\left\{  g\in\mathbb{N}_{\mid u}\ :\ g\mid v\right\}  $. Thus, $h$ is
an element $g$ of $\mathbb{N}_{\mid u}$ satisfying $g\mid v$. In other words,
$h$ is an element of $\mathbb{N}_{\mid u}$ and satisfies $h\mid v$.
\par
We know that $h$ is an element of $\mathbb{N}_{\mid u}$. In other words, $h$
is an element of the set of all positive divisors of $u$ (since $\mathbb{N}%
_{\mid u}$ is the set of all positive divisors of $u$). In other words, $h$ is
a positive divisor of $u$. In other words, $h$ is a positive integer and a
divisor of $u$.
\par
So we have $h\mid u$ (since $h$ is a divisor of $u$) and $h\mid v$. Thus,
$h\mid\gcd\left(  u,v\right)  $ (by Lemma \ref{lem.gcd}, applied to $x=h$). In
other words, $h$ is a divisor of $\gcd\left(  u,v\right)  $.
\par
Hence, $h$ is a positive divisor of $\gcd\left(  u,v\right)  $ (since $h$ is a
positive integer and a divisor of $\gcd\left(  u,v\right)  $). In other words,
$h$ is an element of the set of all positive divisors of $\gcd\left(
u,v\right)  $. In other words, $h$ is an element of $\mathbb{N}_{\mid
\gcd\left(  u,v\right)  }$ (since $\mathbb{N}_{\mid\gcd\left(  u,v\right)  }$
is the set of all positive divisors of $\gcd\left(  u,v\right)  $). In other
words, $h\in\mathbb{N}_{\mid\gcd\left(  u,v\right)  }$.
\par
Let us now forget that we fixed $h$. We thus have proven that $h\in
\mathbb{N}_{\mid\gcd\left(  u,v\right)  }$ for every $h\in\left\{
g\in\mathbb{N}_{\mid u}\ :\ g\mid v\right\}  $. In other words, $\left\{
g\in\mathbb{N}_{\mid u}\ :\ g\mid v\right\}  \subseteq\mathbb{N}_{\mid
\gcd\left(  u,v\right)  }$.
\par
Now, we shall prove that $\mathbb{N}_{\mid\gcd\left(  u,v\right)  }%
\subseteq\left\{  g\in\mathbb{N}_{\mid u}\ :\ g\mid v\right\}  $.
\par
Indeed, let $k\in\mathbb{N}_{\mid\gcd\left(  u,v\right)  }$. Thus, $k$ is an
element of $\mathbb{N}_{\mid\gcd\left(  u,v\right)  }$. In other words, $k$ is
an element of the set of all positive divisors of $\gcd\left(  u,v\right)  $
(since $\mathbb{N}_{\mid\gcd\left(  u,v\right)  }$ is the set of all positive
divisors of $\gcd\left(  u,v\right)  $). In other words, $k$ is a positive
divisor of $\gcd\left(  u,v\right)  $. In other words, $k$ is a positive
integer and a divisor of $\gcd\left(  u,v\right)  $.
\par
We have $k\mid\gcd\left(  u,v\right)  $ (since $k$ is a divisor of
$\gcd\left(  u,v\right)  $) and thus $k\mid\gcd\left(  u,v\right)  \mid u$. In
other words, $k$ is a divisor of $u$. Hence, $k$ is a positive integer and a
divisor of $u$. In other words, $k$ is a positive divisor of $u$. In other
words, $k$ is an element of the set of all positive divisors of $u$. In other
words, $k$ is an element of $\mathbb{N}_{\mid u}$ (since $\mathbb{N}_{\mid u}$
is the set of all positive divisors of $u$).
\par
Also, $k\mid\gcd\left(  u,v\right)  \mid v$. Thus, $k$ is an element of
$\mathbb{N}_{\mid u}$ and satisfies $k\mid v$. In other words, $k$ is a
$g\in\mathbb{N}_{\mid u}$ satisfying $g\mid v$. In other words, $k\in\left\{
g\in\mathbb{N}_{\mid u}\ :\ g\mid v\right\}  $.
\par
Let us now forget that we fixed $k$. We thus have proven that $k\in\left\{
g\in\mathbb{N}_{\mid u}\ :\ g\mid v\right\}  $ for every $k\in\mathbb{N}%
_{\mid\gcd\left(  u,v\right)  }$. In other words, $\mathbb{N}_{\mid\gcd\left(
u,v\right)  }\subseteq\left\{  g\in\mathbb{N}_{\mid u}\ :\ g\mid v\right\}  $.
\par
Combining this with $\left\{  g\in\mathbb{N}_{\mid u}\ :\ g\mid v\right\}
\subseteq\mathbb{N}_{\mid\gcd\left(  u,v\right)  }$, we obtain $\left\{
g\in\mathbb{N}_{\mid u}\ :\ g\mid v\right\}  =\mathbb{N}_{\mid\gcd\left(
u,v\right)  }$. This proves (\ref{pf.lem.gcdsum.equiv}).}.

On the other hand, $\mathbb{N}_{\mid u}$ is the set of all positive divisors
of $u$ (by the definition of $\mathbb{N}_{\mid u}$). In other words,%
\[
\mathbb{N}_{\mid u}=\left(  \text{the set of all positive divisors of
}u\right)  .
\]


Now, the sum $\sum_{\substack{g\mid u;\\g\mid v}}b_{g}$ is the sum of all
$b_{g}$, where $g$ runs over all \textbf{positive} divisors of $u$ satisfying
$g\mid v$ (because of the definition of the summation sign $\sum
_{\substack{g\mid u;\\g\mid v}}$). In other words,%
\begin{align*}
\sum_{\substack{g\mid u;\\g\mid v}}b_{g}  &  =\sum_{\substack{g\text{ is a
positive}\\\text{divisor of }u\text{;}\\g\mid v}}b_{g}=\sum_{\substack{g\in
\left(  \text{the set of all positive divisors of }u\right)  ;\\g\mid v}%
}b_{g}=\sum_{\substack{g\in\mathbb{N}_{\mid u};\\g\mid v}}b_{g}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }\left(  \text{the set of all
positive divisors of }u\right)  =\mathbb{N}_{\mid u}\right) \\
&  =\underbrace{\sum_{\substack{h\in\mathbb{N}_{\mid u};\\h\mid v}%
}}_{\substack{=\sum_{h\in\left\{  g\in\mathbb{N}_{\mid u}\ :\ g\mid v\right\}
}\\=\sum_{h\in\mathbb{N}_{\mid\gcd\left(  u,v\right)  }}\\\text{(since
}\left\{  g\in\mathbb{N}_{\mid u}\ :\ g\mid v\right\}  =\mathbb{N}_{\mid
\gcd\left(  u,v\right)  }\\\text{(by (\ref{pf.lem.gcdsum.equiv})))}}%
}b_{h}\ \ \ \ \ \ \ \ \ \ \left(  \text{here, we renamed the summation index
}g\text{ as }h\right) \\
&  =\sum_{h\in\mathbb{N}_{\mid\gcd\left(  u,v\right)  }}b_{h}=\sum
_{g\in\mathbb{N}_{\mid\gcd\left(  u,v\right)  }}b_{g}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{here, we renamed the summation index
}h\text{ as }g\right)  .
\end{align*}
Compared with%
\[
\sum_{g\mid\gcd\left(  u,v\right)  }b_{g}=\sum_{g\in\mathbb{N}_{\mid
\gcd\left(  u,v\right)  }}b_{g}\ \ \ \ \ \ \ \ \ \ \left(  \text{by Lemma
\ref{lem.Ndivsum}, applied to }N=\gcd\left(  u,v\right)  \right)  ,
\]
this shows that $\sum_{\substack{g\mid u;\\g\mid v}}b_{g}=\sum_{g\mid
\gcd\left(  u,v\right)  }b_{g}$. This proves Lemma \ref{lem.gcdsum}.
\end{proof}
\end{verlong}

\begin{lemma}
\label{lem.gcd.d}Let $d$, $u$ and $v$ be three positive integers. Then,
$\gcd\left(  du,dv\right)  =d\gcd\left(  u,v\right)  $.
\end{lemma}

\begin{vershort}
\begin{proof}
[Proof of Lemma \ref{lem.gcd.d}.]This is easy and left to the reader.
\end{proof}
\end{vershort}

\begin{verlong}
\begin{proof}
[Proof of Lemma \ref{lem.gcd.d}.]We have $\gcd\left(  u,v\right)  \mid u$.
Multiplying this relation by $d$, we obtain $d\gcd\left(  u,v\right)  \mid du$.

We have $\gcd\left(  u,v\right)  \mid v$. Multiplying this relation by $d$, we
obtain $d\gcd\left(  u,v\right)  \mid dv$.

Now, Lemma \ref{lem.gcd} (applied to $du$, $dv$ and $d\gcd\left(  u,v\right)
$ instead of $u$, $v$ and $x$) shows that $d\gcd\left(  u,v\right)  \mid
\gcd\left(  du,dv\right)  $ (since $d\gcd\left(  u,v\right)  \mid du$ and
$d\gcd\left(  u,v\right)  \mid dv$).

Now, clearly, $d\mid d\gcd\left(  u,v\right)  \mid\gcd\left(  du,dv\right)  $.
Hence, $\dfrac{\gcd\left(  du,dv\right)  }{d}\in\mathbb{Z}$. Let
$h=\dfrac{\gcd\left(  du,dv\right)  }{d}$. Then, $h=\dfrac{\gcd\left(
du,dv\right)  }{d}\in\mathbb{Z}$. From $h=\dfrac{\gcd\left(  du,dv\right)
}{d}$, we obtain $dh=\gcd\left(  du,dv\right)  $.

From $h=\dfrac{\gcd\left(  du,dv\right)  }{d}$, we obtain $u/h=u/\dfrac
{\gcd\left(  du,dv\right)  }{d}=\dfrac{du}{\gcd\left(  du,dv\right)  }%
\in\mathbb{Z}$ (since $\gcd\left(  du,dv\right)  \mid du$). In other words,
$h\mid u$. Also, from $h=\dfrac{\gcd\left(  du,dv\right)  }{d}$, we obtain
$v/h=v/\dfrac{\gcd\left(  du,dv\right)  }{d}=\dfrac{dv}{\gcd\left(
du,dv\right)  }\in\mathbb{Z}$ (since $\gcd\left(  du,dv\right)  \mid dv$). In
other words, $h\mid v$.

Now, from $h\mid u$ and $h\mid v$, we obtain $h\mid\gcd\left(  u,v\right)  $
(by Lemma \ref{lem.gcd}, applied to $x=h$). Multiplying this relation by $d$,
we obtain $dh\mid d\gcd\left(  u,v\right)  $. Since $dh=\gcd\left(
du,dv\right)  $, this rewrites as $\gcd\left(  du,dv\right)  \mid d\gcd\left(
u,v\right)  $.

Now, recall the following simple fact: If $x$ and $y$ are two positive
integers such that $x\mid y$ and $y\mid x$, then $x=y$. Applying this fact to
$x=\gcd\left(  du,dv\right)  $ and $y=d\gcd\left(  u,v\right)  $, we obtain
$\gcd\left(  du,dv\right)  =d\gcd\left(  u,v\right)  $ (since $\gcd\left(
du,dv\right)  \mid d\gcd\left(  u,v\right)  $ and $\gcd\left(  du,dv\right)
\mid d\gcd\left(  u,v\right)  $). This proves Lemma \ref{lem.gcd.d}.
\end{proof}
\end{verlong}

\begin{lemma}
\label{lem.de-sum}Let $u$ and $v$ be two positive integers. Let $b_{f}$ be a
real number for every $f\in\left\{  1,2,3,\ldots\right\}  $. Then,%
\[
\sum_{d\mid u}\sum_{\substack{e\mid v;\\\gcd\left(  de,u\right)  =d}%
}b_{de}=\sum_{f\mid uv}b_{f}.
\]

\end{lemma}

\begin{vershort}
\begin{proof}
[Proof of Lemma \ref{lem.de-sum}.]Let $d$ be a positive divisor of $u$. Then,
we can define a map $\mathbf{B}$ from the set
\[
\left\{  e\text{ is a positive divisor of }v\ :\ \gcd\left(  de,u\right)
=d\right\}
\]
to the set
\[
\left\{  f\text{ is a positive divisor of }uv\ :\ \gcd\left(  f,u\right)
=d\right\}
\]
by setting%
\[
\mathbf{B}\left(  e\right)  =de\ \ \ \ \ \ \ \ \ \ \text{for every }e\text{ in
the former set}%
\]
\ \footnote{\textit{Proof.} To see that this map is well-defined, we merely
need to check that if $e$ is a positive divisor of $v$ satisfying $\gcd\left(
de,u\right)  =d$, then $de$ is a positive divisor of $uv$ satisfying
$\gcd\left(  de,u\right)  =d$. So let $e$ be a positive divisor of $v$
satisfying $\gcd\left(  de,u\right)  =d$. Then, $de\mid uv$ (since $d\mid u$
and $e\mid v$), so that $de$ is a positive divisor of $uv$; also, clearly,
$\gcd\left(  de,u\right)  =d$. Thus, we are done.}. This map $\mathbf{B}$ is
bijective\footnote{\textit{Proof.} The injectivity of $\mathbf{B}$ is obvious
(since $d\neq0$). It remains to prove that $\mathbf{B}$ is surjective. In
other words, it remains to prove that if $f$ is a positive divisor of $uv$
satisfying $\gcd\left(  f,u\right)  =d$, then there exists a positive divisor
$e$ of $v$ satisfying $\gcd\left(  de,u\right)  =d$ and $f=de$.
\par
So let $f$ be a positive divisor of $uv$ satisfying $\gcd\left(  f,u\right)
=d$. Clearly, $d=\gcd\left(  f,u\right)  \mid f$, so that $f/d\in\mathbb{Z}$.
\par
Lemma \ref{lem.gcd.d} (applied to $v$, $f$ and $u$ instead of $d$, $u$ and
$v$) yields $\gcd\left(  vf,vu\right)  =v\underbrace{\gcd\left(  f,u\right)
}_{=d}=vd$.
\par
Now, $f\mid uv=vu$ and $f\mid vf$ (clearly). Hence, Lemma \ref{lem.gcd}
(applied to $vf$, $vu$ and $f$ instead of $u$, $v$ and $x$) shows that
$f\mid\gcd\left(  vf,vu\right)  =vd$. Now, $v/\left(  f/d\right)  =\left(
vd\right)  /f\in\mathbb{Z}$ (since $f\mid vd$), and thus $f/d\mid v$ (since
$f/d\in\mathbb{Z}$). Hence, $f/d$ is a positive divisor of $v$. Moreover,
$\gcd\left(  \underbrace{d\left(  f/d\right)  }_{=f},u\right)  =\gcd\left(
f,u\right)  =d$ and $f=d\left(  f/d\right)  $.
\par
Thus, there exists a positive divisor $e$ of $v$ satisfying $\gcd\left(
de,u\right)  =d$ and $f=de$ (namely, $e=f/d$). This completes the proof that
$\mathbf{B}$ is bijective.}. Hence, we can substitute $\mathbf{B}\left(
e\right)  $ for $f$ in the sum $\sum_{\substack{f\mid uv;\\\gcd\left(
f,u\right)  =d}}b_{f}$. We thus obtain%
\begin{equation}
\sum_{\substack{f\mid uv;\\\gcd\left(  f,u\right)  =d}}b_{f}=\sum
_{\substack{e\mid v;\\\gcd\left(  de,u\right)  =d}}\underbrace{b_{\mathbf{B}%
\left(  e\right)  }}_{\substack{=b_{de}\\\text{(since }\mathbf{B}\left(
e\right)  =de\text{)}}}=\sum_{\substack{e\mid v;\\\gcd\left(  de,u\right)
=d}}b_{de}. \label{pf.lem.de-sum.short.1}%
\end{equation}


Now, let us forget that we fixed $d$. We thus have shown that
(\ref{pf.lem.de-sum.short.1}) holds for every positive divisor $d$ of $u$.

Now, if $f$ is any positive divisor of $uv$, then $\gcd\left(  f,u\right)  $
is a positive divisor of $u$. Hence, we can split the sum $\sum_{f\mid
uv}b_{f}$ into subsums according to the value of $\gcd\left(  f,u\right)  $ as
follows:%
\[
\sum_{f\mid uv}b_{f}=\sum_{d\mid u}\underbrace{\sum_{\substack{f\mid
uv;\\\gcd\left(  f,u\right)  =d}}b_{f}}_{\substack{=\sum_{\substack{e\mid
v;\\\gcd\left(  de,u\right)  =d}}b_{de}\\\text{(by
(\ref{pf.lem.de-sum.short.1}))}}}=\sum_{d\mid u}\sum_{\substack{e\mid
v;\\\gcd\left(  de,u\right)  =d}}b_{de}.
\]
This proves Lemma \ref{lem.de-sum}.
\end{proof}
\end{vershort}

\begin{verlong}
\begin{proof}
[Proof of Lemma \ref{lem.de-sum}.]Let $d$ be a positive divisor of $u$. Thus,
$d$ is a positive integer and a divisor of $u$. We shall show that%
\begin{equation}
\sum_{\substack{e\mid v;\\\gcd\left(  de,u\right)  =d}}b_{de}=\sum
_{\substack{f\mid uv;\\\gcd\left(  f,u\right)  =d}}b_{f}.
\label{pf.lem.de-sum.goal1}%
\end{equation}


But let us first make some simpler observations.

We know that $\mathbb{N}_{\mid v}$ is the set of all positive divisors of $v$
(by the definition of $\mathbb{N}_{\mid v}$). In other words,%
\[
\mathbb{N}_{\mid v}=\left(  \text{the set of all positive divisors of
}v\right)  .
\]


Also, $\mathbb{N}_{\mid uv}$ is the set of all positive divisors of $uv$ (by
the definition of $\mathbb{N}_{\mid uv}$). In other words,%
\[
\mathbb{N}_{\mid uv}=\left(  \text{the set of all positive divisors of
}uv\right)  .
\]


Now, the sum $\sum_{\substack{e\mid v;\\\gcd\left(  de,u\right)  =d}}b_{de}$
is the sum of all $b_{de}$, where $e$ runs over all \textbf{positive} divisors
of $v$ satisfying $\gcd\left(  de,u\right)  =d$ (because of the definition of
the summation sign $\sum_{\substack{e\mid v;\\\gcd\left(  de,u\right)  =d}}$).
In other words,%
\begin{equation}
\sum_{\substack{e\mid v;\\\gcd\left(  de,u\right)  =d}}b_{de}=\underbrace{\sum
_{\substack{e\text{ is a positive divisor of }v\text{;}\\\gcd\left(
de,u\right)  =d}}}_{\substack{=\sum_{\substack{e\in\left(  \text{the set of
all positive divisors of }v\right)  ;\\\gcd\left(  de,u\right)  =d}%
}\\=\sum_{\substack{e\in\mathbb{N}_{\mid v};\\\gcd\left(  de,u\right)
=d}}\\\text{(since }\left(  \text{the set of all positive divisors of
}v\right)  =\mathbb{N}_{\mid v}\text{)}}}b_{de}=\sum_{\substack{e\in
\mathbb{N}_{\mid v};\\\gcd\left(  de,u\right)  =d}}b_{de}.
\label{pf.lem.de-sum.1}%
\end{equation}


Also, the sum $\sum_{\substack{f\mid uv;\\\gcd\left(  f,u\right)  =d}}b_{f}$
is the sum of all $b_{f}$, where $f$ runs over all \textbf{positive} divisors
of $uv$ satisfying $\gcd\left(  f,u\right)  =d$ (because of the definition of
the summation sign $\sum_{\substack{f\mid uv;\\\gcd\left(  f,u\right)  =d}}$).
In other words,%
\begin{equation}
\sum_{\substack{f\mid uv;\\\gcd\left(  f,u\right)  =d}}b_{f}=\underbrace{\sum
_{\substack{f\text{ is a positive divisor of }uv\text{;}\\\gcd\left(
f,u\right)  =d}}}_{\substack{=\sum_{\substack{f\in\left(  \text{the set of all
positive divisors of }uv\right)  ;\\\gcd\left(  f,u\right)  =d}}\\=\sum
_{\substack{f\in\mathbb{N}_{\mid uv};\\\gcd\left(  f,u\right)  =d}%
}\\\text{(since }\left(  \text{the set of all positive divisors of }uv\right)
=\mathbb{N}_{\mid uv}\text{)}}}b_{f}=\sum_{\substack{f\in\mathbb{N}_{\mid
uv};\\\gcd\left(  f,u\right)  =d}}b_{f}. \label{pf.lem.de-sum.2}%
\end{equation}


On the other hand, for every $f\in\left\{  x\in\mathbb{N}_{\mid uv}%
\ :\ \gcd\left(  x,u\right)  =d\right\}  $, we have $f/d\in\left\{
x\in\mathbb{N}_{\mid v}\ :\ \gcd\left(  dx,u\right)  =d\right\}
$\ \ \ \ \footnote{\textit{Proof.} Let $f\in\left\{  x\in\mathbb{N}_{\mid
uv}\ :\ \gcd\left(  x,u\right)  =d\right\}  $. We must prove that
$f/d\in\left\{  x\in\mathbb{N}_{\mid v}\ :\ \gcd\left(  dx,u\right)
=d\right\}  $.
\par
Indeed, we have $f\in\left\{  x\in\mathbb{N}_{\mid uv}\ :\ \gcd\left(
x,u\right)  =d\right\}  $. In other words, $f$ is an $x\in\mathbb{N}_{\mid
uv}$ satisfying $\gcd\left(  x,u\right)  =d$. In other words, $f$ is an
element of $\mathbb{N}_{\mid uv}$ and satisfies $\gcd\left(  f,u\right)  =d$.
\par
We know that $f$ is an element of $\mathbb{N}_{\mid uv}$. In other words, $f$
is an element of the set of all positive divisors of $uv$ (since
$\mathbb{N}_{\mid uv}$ is the set of all positive divisors of $uv$). In other
words, $f$ is a positive divisor of $uv$. In other words, $f$ is a positive
integer and a divisor of $uv$.
\par
Clearly, $\gcd\left(  \alpha,\beta\right)  \mid\alpha$ for any two positive
integers $\alpha$ and $\beta$. Applying this to $\alpha=f$ and $\beta=u$, we
obtain $\gcd\left(  f,u\right)  \mid f$. Thus, $d=\gcd\left(  f,u\right)  \mid
f$, so that $f/d\in\mathbb{Z}$. Also, $f/d$ is positive (since $f$ and $d$ are
positive), and therefore a positive integer (since $f/d\in\mathbb{Z}$).
\par
Moreover, Lemma \ref{lem.gcd.d} (applied to $v$, $f$ and $u$ instead of $d$,
$u$ and $v$) yields $\gcd\left(  vf,vu\right)  =v\underbrace{\gcd\left(
f,u\right)  }_{=d}=vd$.
\par
Now, $f$ is a divisor of $uv$. In other words, $f\mid uv=vu$. Also, $f\mid vf$
(clearly). Hence, Lemma \ref{lem.gcd} (applied to $vf$, $vu$ and $f$ instead
of $u$, $v$ and $x$) shows that $f\mid\gcd\left(  vf,vu\right)  =vd$. Now,
$v/\left(  f/d\right)  =\left(  vd\right)  /f\in\mathbb{Z}$ (since $f\mid
vd$), and thus $f/d\mid v$ (since $f/d\in\mathbb{Z}$). In other words, $f/d$
is a divisor of $v$.
\par
Clearly, $\gcd\left(  \underbrace{d\left(  f/d\right)  }_{=f},u\right)
=\gcd\left(  f,u\right)  =d$.
\par
So we know that $f/d$ is a positive integer and a divisor of $v$. In other
words, $f/d$ is a positive divisor of $v$. In other words, $f/d$ is an element
of the set of all positive divisors of $v$. In other words, $f/d$ is an
element of $\mathbb{N}_{\mid v}$ (since $\mathbb{N}_{\mid v}$ is the set of
all positive divisors of $v$). Hence, $f/d$ is an element of $\mathbb{N}_{\mid
v}$ and satisfies $\gcd\left(  d\left(  f/d\right)  ,u\right)  =d$. In other
words, $f/d$ is an $x\in\mathbb{N}_{\mid v}$ satisfying $\gcd\left(
dx,u\right)  =d$. In other words, $f/d\in\left\{  x\in\mathbb{N}_{\mid
v}\ :\ \gcd\left(  dx,u\right)  =d\right\}  $, qed.}. Hence, we can define a
map%
\[
\mathbf{A}:\left\{  x\in\mathbb{N}_{\mid uv}\ :\ \gcd\left(  x,u\right)
=d\right\}  \rightarrow\left\{  x\in\mathbb{N}_{\mid v}\ :\ \gcd\left(
dx,u\right)  =d\right\}
\]
by setting%
\[
\left(  \mathbf{A}\left(  f\right)  =f/d\ \ \ \ \ \ \ \ \ \ \text{for every
}f\in\left\{  x\in\mathbb{N}_{\mid uv}\ :\ \gcd\left(  x,u\right)  =d\right\}
\right)  .
\]
Consider this map $\mathbf{A}$.

Furthermore, for every $e\in\left\{  x\in\mathbb{N}_{\mid v}\ :\ \gcd\left(
dx,u\right)  =d\right\}  $, we have \newline$de\in\left\{  x\in\mathbb{N}%
_{\mid uv}\ :\ \gcd\left(  x,u\right)  =d\right\}  $%
\ \ \ \ \footnote{\textit{Proof.} Let $e\in\left\{  x\in\mathbb{N}_{\mid
v}\ :\ \gcd\left(  dx,u\right)  =d\right\}  $. We must prove that
$de\in\left\{  x\in\mathbb{N}_{\mid uv}\ :\ \gcd\left(  x,u\right)
=d\right\}  $.
\par
Indeed, we have $e\in\left\{  x\in\mathbb{N}_{\mid v}\ :\ \gcd\left(
dx,u\right)  =d\right\}  $. In other words, $e$ is an $x\in\mathbb{N}_{\mid
v}$ satisfying $\gcd\left(  dx,u\right)  =d$. In other words, $e$ is an
element of $\mathbb{N}_{\mid v}$ and satisfies $\gcd\left(  de,u\right)  =d$.
\par
We know that $e$ is an element of $\mathbb{N}_{\mid v}$. In other words, $e$
is an element of the set of all positive divisors of $v$ (since $\mathbb{N}%
_{\mid v}$ is the set of all positive divisors of $v$). In other words, $e$ is
a positive divisor of $v$. In other words, $e$ is a positive integer and a
divisor of $v$. We have $v/e\in\mathbb{Z}$ (since $e$ is a divisor of $v$).
\par
On the other hand, $d\mid u$ (since $d$ is a divisor of $u$), and thus
$u/d\in\mathbb{Z}$. Now, $\left(  uv\right)  /\left(  de\right)
=\underbrace{\left(  u/d\right)  }_{\in\mathbb{Z}}\underbrace{\left(
v/e\right)  }_{\in\mathbb{Z}}\in\mathbb{Z}$. Hence, $de\mid uv$. In other
words, $de$ is a divisor of $uv$.
\par
Thus, $de$ is a positive integer (since $d$ and $e$ are positive integers) and
a divisor of $uv$. In other words, $de$ is a positive divisor of $uv$. In
other words, $de$ is an element of the set of all positive divisors of $uv$.
In other words, $de$ is an element of $\mathbb{N}_{\mid uv}$ (since
$\mathbb{N}_{\mid uv}$ is the set of all positive divisors of $uv$). Hence,
$de$ is an element of $\mathbb{N}_{\mid uv}$ and satisfies $\gcd\left(
de,u\right)  =d$. In other words, $de$ is an $x\in\mathbb{N}_{\mid uv}$
satisfying $\gcd\left(  x,u\right)  =d$. In other words, $de\in\left\{
x\in\mathbb{N}_{\mid uv}\ :\ \gcd\left(  x,u\right)  =d\right\}  $, qed.}.
Hence, we can define a map%
\[
\mathbf{B}:\left\{  x\in\mathbb{N}_{\mid v}\ :\ \gcd\left(  dx,u\right)
=d\right\}  \rightarrow\left\{  x\in\mathbb{N}_{\mid uv}\ :\ \gcd\left(
x,u\right)  =d\right\}
\]
by setting%
\[
\left(  \mathbf{B}\left(  e\right)  =de\ \ \ \ \ \ \ \ \ \ \text{for every
}e\in\left\{  x\in\mathbb{N}_{\mid v}\ :\ \gcd\left(  dx,u\right)  =d\right\}
\right)  .
\]
Consider this map $\mathbf{B}$.

We have $\mathbf{A}\circ\mathbf{B}=\operatorname*{id}$%
\ \ \ \ \footnote{\textit{Proof.} For every $e\in\left\{  x\in\mathbb{N}_{\mid
v}\ :\ \gcd\left(  dx,u\right)  =d\right\}  $, we have
\begin{align*}
\left(  \mathbf{A}\circ\mathbf{B}\right)  \left(  e\right)   &  =\mathbf{A}%
\left(  \underbrace{\mathbf{B}\left(  e\right)  }_{\substack{=de\\\text{(by
the definition of }\mathbf{B}\text{)}}}\right)  =\mathbf{A}\left(  de\right)
=\left(  de\right)  /d\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of
}\mathbf{A}\right) \\
&  =e=\operatorname*{id}\left(  e\right)  .
\end{align*}
In other words, $\mathbf{A}\circ\mathbf{B}=\operatorname*{id}$, qed.} and
$\mathbf{B}\circ\mathbf{A}=\operatorname*{id}$%
\ \ \ \ \footnote{\textit{Proof.} For every $f\in\left\{  x\in\mathbb{N}_{\mid
uv}\ :\ \gcd\left(  x,u\right)  =d\right\}  $, we have
\begin{align*}
\left(  \mathbf{B}\circ\mathbf{A}\right)  \left(  f\right)   &  =\mathbf{B}%
\left(  \underbrace{\mathbf{A}\left(  f\right)  }_{\substack{=f/d\\\text{(by
the definition of }\mathbf{A}\text{)}}}\right)  =\mathbf{B}\left(  f/d\right)
=d\left(  f/d\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of
}\mathbf{A}\right) \\
&  =f=\operatorname*{id}\left(  f\right)  .
\end{align*}
In other words, $\mathbf{B}\circ\mathbf{A}=\operatorname*{id}$, qed.}. In
other words, the maps $\mathbf{A}$ and $\mathbf{B}$ are mutually inverse.
Hence, the map $\mathbf{B}$ is invertible. In other words, the map
$\mathbf{B}$ is a bijection. Now, (\ref{pf.lem.de-sum.2}) becomes%
\begin{align*}
&  \sum_{\substack{f\mid uv;\\\gcd\left(  f,u\right)  =d}}b_{f}\\
&  =\underbrace{\sum_{\substack{f\in\mathbb{N}_{\mid uv};\\\gcd\left(
f,u\right)  =d}}}_{=\sum_{f\in\left\{  x\in\mathbb{N}_{\mid uv}\ :\ \gcd
\left(  x,u\right)  =d\right\}  }}b_{f}=\sum_{f\in\left\{  x\in\mathbb{N}%
_{\mid uv}\ :\ \gcd\left(  x,u\right)  =d\right\}  }b_{f}\\
&  =\underbrace{\sum_{e\in\left\{  x\in\mathbb{N}_{\mid v}\ :\ \gcd\left(
dx,u\right)  =d\right\}  }}_{=\sum_{\substack{e\in\mathbb{N}_{\mid v}%
;\\\gcd\left(  de,u\right)  =d}}}\underbrace{b_{\mathbf{B}\left(  e\right)  }%
}_{\substack{=b_{de}\\\text{(since }\mathbf{B}\left(  e\right)  =de\\\text{(by
the definition of }\mathbf{B}\text{))}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we substituted }\mathbf{B}\left(  e\right)  \text{ for }f\text{ in
the sum, since the map}\\
\mathbf{B}:\left\{  x\in\mathbb{N}_{\mid uv}\ :\ \gcd\left(  x,u\right)
=d\right\}  \rightarrow\left\{  x\in\mathbb{N}_{\mid v}\ :\ \gcd\left(
dx,u\right)  =d\right\} \\
\text{is a bijection}%
\end{array}
\right) \\
&  =\sum_{\substack{e\in\mathbb{N}_{\mid v};\\\gcd\left(  de,u\right)
=d}}b_{de}=\sum_{\substack{e\mid v;\\\gcd\left(  de,u\right)  =d}%
}b_{de}\ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{pf.lem.de-sum.1})}\right)  .
\end{align*}
This proves (\ref{pf.lem.de-sum.goal1}).

Now, let us forget that we fixed $d$. We thus have proven
(\ref{pf.lem.de-sum.goal1}) for every positive divisor $d$ of $u$.

Now, if $f$ is any positive divisor of $uv$, then $\gcd\left(  f,u\right)  $
is a positive divisor of $u$. Hence, we can split the sum $\sum_{f\mid
uv}b_{f}$ into subsums according to the value of $\gcd\left(  f,u\right)  $ as
follows:%
\[
\sum_{f\mid uv}b_{f}=\sum_{d\mid u}\underbrace{\sum_{\substack{f\mid
uv;\\\gcd\left(  f,u\right)  =d}}b_{f}}_{\substack{=\sum_{\substack{e\mid
v;\\\gcd\left(  de,u\right)  =d}}b_{de}\\\text{(by (\ref{pf.lem.de-sum.goal1}%
))}}}=\sum_{d\mid u}\sum_{\substack{e\mid v;\\\gcd\left(  de,u\right)
=d}}b_{de}.
\]
This proves Lemma \ref{lem.de-sum}.
\end{proof}
\end{verlong}

Now, let us introduce the following notation (known as the \textit{Iverson
bracket notation}): If $\mathcal{A}$ is any logical statement, then $\left[
\mathcal{A}\right]  $ shall denote the integer $%
\begin{cases}
1, & \text{if }\mathcal{A}\text{ is true};\\
0, & \text{if }\mathcal{A}\text{ is false}%
\end{cases}
$.

We shall use the following classical property of the M\"{o}bius function:

\begin{proposition}
\label{prop.mu.iverson}Let $N$ be a positive integer. Then,%
\[
\sum_{d\mid N}\mu\left(  d\right)  =\left[  N=1\right]  .
\]

\end{proposition}

Proposition \ref{prop.mu.iverson} is a classical fact in number
theory\footnote{For example, it appears in \cite[Theorem 4.7, second
part]{NiZuMo}, in \cite[Theorem 1.3]{Hildebr} and in \cite[version with
solutions, Solution to Exercise 2.82, proof of (11.68.3)]{GriRei15}. In order
to convince yourself that the definitions of the function $\mu$ in all of
these sources are equivalent to our definition of $\mu$, you only need to
observe that the number of primes dividing a squarefree integer $m$ is
precisely the number of prime factors of $m$ (because every prime dividing a
squarefree integer $m$ appears in the prime factorization of $m$ with a
multiplicity of exactly $1$).}. We shall nevertheless prove it here soon; but
first, let us prepare by stating some simple facts.

\begin{vershort}
Recall that an integer is said to be \textit{squarefree} if it is not
divisible by any square of a positive integer $>1$. We state two simple facts,
whose proofs we leave to the reader:

\begin{itemize}
\item If $u$ and $v$ are two squarefree integers, and if $u$ and $v$ are
coprime, then
\begin{equation}
uv\text{ is squarefree.} \label{eq.sqfree.short.1}%
\end{equation}


\item If $u$ and $v$ are two integers such that $u\mid v$, and if $v$ is
squarefree, then%
\begin{equation}
u\text{ is squarefree.} \label{eq.sqfree.short.2}%
\end{equation}

\end{itemize}

Also, from the definition of the M\"{o}bius function $\mu$, we immediately
obtain the following two facts:

\begin{itemize}
\item If $m$ is a squarefree integer, then%
\begin{equation}
\mu\left(  m\right)  =\left(  -1\right)  ^{\left(  \text{number of primes
dividing }m\right)  }. \label{eq.mu.short.1}%
\end{equation}


\item If $m$ is a integer such that $m$ is not squarefree, then%
\begin{equation}
\mu\left(  m\right)  =0.\label{eq.mu.short.2}%
\end{equation}

\end{itemize}

Applying (\ref{eq.mu.short.1}) to $m=1$, we obtain $\mu\left(  1\right)  =1$
(since the number of primes dividing $1$ is $0$).
\end{vershort}

\begin{verlong}
Recall that an integer is said to be \textit{squarefree} if it is not
divisible by any square of a positive integer $>1$. In other words, an integer
$n$ is squarefree if and only if no positive integer $m>1$ satisfies
$m^{2}\mid n$. In other words, if $n$ is an integer, then we have the
following logical equivalence:%
\begin{equation}
\left(  n\text{ is squarefree}\right)  \Longleftrightarrow\left(  \text{no
positive integer }m>1\text{ satisfies }m^{2}\mid n\right)  .
\label{eq.sqfree.equiv}%
\end{equation}


Now, we state some simple facts:

\begin{itemize}
\item If $u$ and $v$ are two squarefree integers, and if $u$ and $v$ are
coprime, then
\begin{equation}
uv\text{ is squarefree} \label{eq.sqfree.1}%
\end{equation}
\footnote{\textit{Proof of (\ref{eq.sqfree.1}):} Let $u$ and $v$ be two
squarefree integers. Assume that $u$ and $v$ are coprime. We need to show that
$uv$ is squarefree.
\par
Indeed, we have the logical equivalence $\left(  u\text{ is squarefree}%
\right)  \Longleftrightarrow\left(  \text{no positive integer }m>1\text{
satisfies }m^{2}\mid u\right)  $ (by (\ref{eq.sqfree.equiv}), applied to
$n=u$). Therefore,
\begin{equation}
\left(  \text{no positive integer }m>1\text{ satisfies }m^{2}\mid u\right)
\label{eq.sqfree.1.pf.1}%
\end{equation}
(since we know that $\left(  u\text{ is squarefree}\right)  $).
\par
Also, we have the logical equivalence $\left(  v\text{ is squarefree}\right)
\Longleftrightarrow\left(  \text{no positive integer }m>1\text{ satisfies
}m^{2}\mid v\right)  $ (by (\ref{eq.sqfree.equiv}), applied to $n=v$).
Therefore,
\begin{equation}
\left(  \text{no positive integer }m>1\text{ satisfies }m^{2}\mid v\right)
\label{eq.sqfree.1.pf.2}%
\end{equation}
(since we know that $\left(  v\text{ is squarefree}\right)  $).
\par
Now, we shall show that
\begin{equation}
\left(  \text{no positive integer }m>1\text{ satisfies }m^{2}\mid uv\right)  .
\label{eq.sqfree.1.pf.3}%
\end{equation}
\par
\textit{Proof of (\ref{eq.sqfree.1.pf.3}):} Indeed, assume the contrary (for
the sake of contradiction). Thus, there exists a positive integer $m>1$ that
satisfies $m^{2}\mid uv$. Let $n$ be such an $m$. Thus, $n$ is a positive
integer $m>1$ that satisfies $m^{2}\mid uv$. In other words, $n$ is a positive
integer $>1$ and satisfies $n^{2}\mid uv$.
\par
Applying (\ref{eq.sqfree.1.pf.1}) to $m=n$, we conclude that we cannot have
$n^{2}\mid u$. Applying (\ref{eq.sqfree.1.pf.2}) to $m=n$, we conclude that we
cannot have $n^{2}\mid v$.
\par
Now, recall the following fundamental property of coprime numbers: If $x$, $y$
and $z$ are three integers such that $x$ and $y$ are coprime, and if $z\mid
xy$, then either $z\mid x$ or $z\mid y$ (or both). We can apply this to $x=u$,
$y=v$ and $z=n^{2}$ (since $u$ and $v$ are coprime, and since we have
$n^{2}\mid uv$). As a result, we obtain that either $n^{2}\mid u$ or
$n^{2}\mid v$ (or both). Since we cannot have $n^{2}\mid u$, this shows that
we must have $n^{2}\mid v$. But this contradicts the fact that we cannot have
$n^{2}\mid v$. This contradiction proves that our assumption was wrong. Hence,
(\ref{eq.sqfree.1.pf.3}) is proven.
\par
Now, we have the logical equivalence $\left(  uv\text{ is squarefree}\right)
\Longleftrightarrow\left(  \text{no positive integer }m>1\text{ satisfies
}m^{2}\mid uv\right)  $ (by (\ref{eq.sqfree.equiv}), applied to $n=uv$).
Therefore, $\left(  uv\text{ is squarefree}\right)  $ (since we know that
$\left(  \text{no positive integer }m>1\text{ satisfies }m^{2}\mid uv\right)
$ (by (\ref{eq.sqfree.1.pf.3}))). This proves (\ref{eq.sqfree.1}).}.

\item If $u$ and $v$ are two integers such that $u\mid v$, and if $v$ is
squarefree, then%
\begin{equation}
u\text{ is squarefree} \label{eq.sqfree.2}%
\end{equation}
\footnote{\textit{Proof of (\ref{eq.sqfree.2}):} Let $u$ and $v$ be two
integers such that $u\mid v$. Assume that $v$ is squarefree. We need to show
that $u$ is squarefree.
\par
Indeed, we have the logical equivalence $\left(  v\text{ is squarefree}%
\right)  \Longleftrightarrow\left(  \text{no positive integer }m>1\text{
satisfies }m^{2}\mid v\right)  $ (by (\ref{eq.sqfree.equiv}), applied to
$n=v$). Therefore,
\begin{equation}
\left(  \text{no positive integer }m>1\text{ satisfies }m^{2}\mid v\right)
\label{eq.sqfree.2.pf.1}%
\end{equation}
(since we know that $\left(  v\text{ is squarefree}\right)  $).
\par
Now, we shall show that
\begin{equation}
\left(  \text{no positive integer }m>1\text{ satisfies }m^{2}\mid u\right)  .
\label{eq.sqfree.2.pf.3}%
\end{equation}
\par
\textit{Proof of (\ref{eq.sqfree.2.pf.3}):} Indeed, assume the contrary (for
the sake of contradiction). Thus, there exists a positive integer $m>1$ that
satisfies $m^{2}\mid u$. Let $n$ be such an $m$. Thus, $n$ is a positive
integer $m>1$ that satisfies $m^{2}\mid u$. In other words, $n$ is a positive
integer $>1$ and satisfies $n^{2}\mid u$.
\par
Applying (\ref{eq.sqfree.2.pf.1}) to $m=n$, we conclude that we cannot have
$n^{2}\mid v$. But this contradicts $n^{2}\mid u\mid v$. This contradiction
proves that our assumption was wrong. Hence, (\ref{eq.sqfree.2.pf.3}) is
proven.
\par
Now, we have the logical equivalence $\left(  u\text{ is squarefree}\right)
\Longleftrightarrow\left(  \text{no positive integer }m>1\text{ satisfies
}m^{2}\mid u\right)  $ (by (\ref{eq.sqfree.equiv}), applied to $n=u$).
Therefore, $\left(  u\text{ is squarefree}\right)  $ (since we know that
$\left(  \text{no positive integer }m>1\text{ satisfies }m^{2}\mid u\right)  $
(by (\ref{eq.sqfree.2.pf.3}))). This proves (\ref{eq.sqfree.2}).}.

\item If $m$ is a squarefree integer, then%
\begin{equation}
\mu\left(  m\right)  =\left(  -1\right)  ^{\left(  \text{number of primes
dividing }m\right)  } \label{eq.mu.1}%
\end{equation}
\footnote{\textit{Proof of (\ref{eq.mu.1}):} Let $m$ be a squarefree integer.
Then, the definition of $\mu$ shows that%
\begin{align*}
\mu\left(  m\right)   &  =%
\begin{cases}
0, & \text{if }m\text{ is not squarefree};\\
\left(  -1\right)  ^{\left(  \text{number of primes dividing }m\right)  }, &
\text{if }m\text{ is squarefree}%
\end{cases}
\\
&  =\left(  -1\right)  ^{\left(  \text{number of primes dividing }m\right)
}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }m\text{ is squarefree}\right)  .
\end{align*}
This proves (\ref{eq.mu.1}).}.

\item If $m$ is a integer such that $m$ is not squarefree, then%
\begin{equation}
\mu\left(  m\right)  =0 \label{eq.mu.2}%
\end{equation}
\footnote{\textit{Proof of (\ref{eq.mu.2}):} Let $m$ be a integer. Assume that
$m$ is not squarefree. Then, the definition of $\mu$ shows that%
\begin{align*}
\mu\left(  m\right)   &  =%
\begin{cases}
0, & \text{if }m\text{ is not squarefree};\\
\left(  -1\right)  ^{\left(  \text{number of primes dividing }m\right)  }, &
\text{if }m\text{ is squarefree}%
\end{cases}
\\
&  =0\ \ \ \ \ \ \ \ \ \ \left(  \text{since }m\text{ is not squarefree}%
\right)  .
\end{align*}
This proves (\ref{eq.mu.2}).}.

\item We have%
\begin{equation}
\mu\left(  1\right)  =1 \label{eq.mu.3}%
\end{equation}
\footnote{\textit{Proof of (\ref{eq.mu.3}):} The integer $1$ is squarefree.
Hence, (\ref{eq.mu.1}) (applied to $m=1$) yields that $\mu\left(  1\right)
=\left(  -1\right)  ^{\left(  \text{number of primes dividing }1\right)
}=\left(  -1\right)  ^{0}$ (since $\left(  \text{number of primes dividing
}1\right)  =0$). Thus, $\mu\left(  1\right)  =\left(  -1\right)  ^{0}=1$. This
proves (\ref{eq.mu.3}).}.
\end{itemize}
\end{verlong}

We are now ready for the proof of Proposition \ref{prop.mu.iverson}:

\begin{vershort}
\begin{proof}
[Proof of Proposition \ref{prop.mu.iverson}.]If $N=1$, then Proposition
\ref{prop.mu.iverson} just states $\mu\left(  1\right)  =1$, which is true.
Hence, for the rest of the proof of Proposition \ref{prop.mu.iverson}, we WLOG
assume that we don't have $N=1$.

Thus, we have $N\neq1$. Hence, the positive integer $N$ has at least one prime
divisor. Pick such a prime divisor, and denote it by $p$. Clearly, $p\mid N$.
Also, $p$ is prime, so that $p>1$.

Let $\operatorname*{Sqf}$ denote the set of all squarefree positive integers.

For every $g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\mid h\right\}  $, we have%
\begin{equation}
g/p\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid
h\right\}  \label{pf.prop.mu.iverson.short.wd1}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.prop.mu.iverson.short.wd1}):} Let
$g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  $.
\par
We have $g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  \subseteq\operatorname*{Sqf}$. In other words, $g$ is a squarefree
positive integer. Hence, for any positive integer $m>1$, we have $m^{2}\nmid
g$. Applying this to $m=p$, we obtain $p^{2}\nmid g$ (since $p>1$). In other
words, $g/p^{2}\notin\mathbb{Z}$.
\par
We have $g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  \subseteq\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}  $.
In other words, $g$ is an element of $\mathbb{N}_{\mid N}$ and satisfies
$p\mid g$. In particular, $g\in\mathbb{N}_{\mid N}$, so that $g$ is a positive
divisor of $N$. Thus, $g\mid N$.
\par
Now, $g/p$ is a positive integer (since $p\mid g$) and satisfies $g/p\mid g$
(since $g=p\left(  g/p\right)  $). Hence, (\ref{eq.sqfree.short.2}) (applied
to $u=g/p$ and $v=g$) shows that $g/p$ is squarefree. In other words,
$g/p\in\operatorname*{Sqf}$.
\par
Now, $g/p$ is a positive divisor of $N$ (since $g/p\mid g\mid N$). In other
words, $g/p\in\mathbb{N}_{\mid N}$.
\par
Thus, $g/p$ is an element of $\mathbb{N}_{\mid N}$ and satisfies $p\nmid g/p$
(since $\left(  g/p\right)  /p=g/p^{2}\notin\mathbb{Z}$). In other words,
$g/p\in\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid h\right\}  $. Combining
this with $g/p\in\operatorname*{Sqf}$, we obtain $g/p\in\operatorname*{Sqf}%
\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid h\right\}  $. This proves
(\ref{pf.prop.mu.iverson.short.wd1}).}. Hence, we can define a map%
\[
\mathbf{A}:\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  \rightarrow\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\nmid h\right\}
\]
by%
\[
\left(  \mathbf{A}\left(  g\right)  =g/p\ \ \ \ \ \ \ \ \ \ \text{for every
}g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  \right)  .
\]
Consider this map $\mathbf{A}$.

For every $g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\nmid h\right\}  $, we have%
\begin{equation}
gp\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  \label{pf.prop.mu.iverson.short.wd2}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.prop.mu.iverson.short.wd2}):} Let
$g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid
h\right\}  $.
\par
We have $g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\nmid h\right\}  \subseteq\operatorname*{Sqf}$. In other words, $g$ is
a squarefree positive integer.
\par
We have $g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\nmid h\right\}  \subseteq\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid
h\right\}  $. In other words, $g$ is an element of $\mathbb{N}_{\mid N}$ and
satisfies $p\nmid g$. In particular, $g\in\mathbb{N}_{\mid N}$; in other
words, $g$ is a positive divisor of $N$. Thus, $g\mid N$.
\par
It is well-known that if $q$ is a prime and $z$ is an integer satisfying
$q\nmid z$, then $q$ is coprime to $z$. Applying this to $q=p$ and $z=g$, we
conclude that $p$ is coprime to $g$ (since $p\nmid g$). In other words, the
integers $g$ and $p$ are coprime. Also, the integer $p$ is prime, and
therefore squarefree (since every prime is squarefree). Hence,
(\ref{eq.sqfree.short.1}) (applied to $u=g$ and $v=p$) shows that $gp$ is
squarefree. In other words, $gp\in\operatorname*{Sqf}$ (since $gp$ is clearly
a positive integer).
\par
A well-known fact from elementary number theory states the following: If $x$,
$y$ and $z$ are three integers such that $x\mid z$ and $y\mid z$, and if the
integers $x$ and $y$ are coprime, then we have $xy\mid z$. We can apply this
to $x=g$, $y=p$ and $z=N$ (since we have $g\mid N$ and $p\mid N$, and since
the integers $g$ and $p$ are coprime). As a consequence, we obtain $gp\mid N$.
Hence, $gp$ is a positive divisor of $N$. In other words, $gp\in
\mathbb{N}_{\mid N}$.
\par
Thus, $gp$ is an element of $\mathbb{N}_{\mid N}$ and satisfies $p\mid gp$
(obviously). In other words, $gp\in\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  $. Combining this with $gp\in\operatorname*{Sqf}$, we obtain
$gp\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  $. This proves (\ref{pf.prop.mu.iverson.short.wd2}).}. Hence, we
can define a map%
\[
\mathbf{B}:\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid
h\right\}  \rightarrow\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\mid h\right\}
\]
by%
\[
\left(  \mathbf{B}\left(  g\right)  =gp\ \ \ \ \ \ \ \ \ \ \text{for every
}g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid
h\right\}  \right)  .
\]
Consider this map $\mathbf{B}$.

The maps $\mathbf{A}$ and $\mathbf{B}$ are mutually inverse\footnote{This
follows immediately from their definitions (since the map $\mathbf{A}$ divides
its input by $p$, whereas the map $\mathbf{B}$ multiplies its input by $p$).}.
Thus, the map $\mathbf{A}$ is invertible, and hence a bijection.

For every $g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\mid h\right\}  $, we have%
\begin{align}
&  \left(  \text{number of primes dividing }\mathbf{A}\left(  g\right)
\right) \nonumber\\
&  =\left(  \text{number of primes dividing }g\right)  -1
\label{pf.prop.mu.iverson.short.num}%
\end{align}
\footnote{\textit{Proof of (\ref{pf.prop.mu.iverson.short.num}):} Let
$g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  $.
\par
We have $g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  \subseteq\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}  $.
In other words, $g$ is an element of $\mathbb{N}_{\mid N}$ and satisfies
$p\mid g$. Thus, $g/p$ is a positive integer. Of course, $p$ is a prime
dividing $g$ (since $p\mid g$).
\par
We have $\mathbf{A}\left(  g\right)  =g/p$ (by the definition of $\mathbf{A}%
$). Thus, $g/p=\mathbf{A}\left(  g\right)  \in\operatorname*{Sqf}\cap\left\{
h\in\mathbb{N}_{\mid N}\ :\ p\nmid h\right\}  \subseteq\operatorname*{Sqf}$,
so that $g/p$ is a squarefree positive integer. In the proof of
(\ref{pf.prop.mu.iverson.short.wd1}), we have seen that $p\nmid g/p$. In other
words, $p$ does not divide $g/p$.
\par
Now, every prime dividing $g/p$ must also divide $g$ (since $g/p\mid g$), but
must be distinct from $p$ (since $p$ does not divide $g/p$). In other words,
every such prime must belong to the set $\left(  \text{the set of all primes
dividing }g\right)  \setminus\left\{  p\right\}  $. Thus,%
\begin{equation}
\left(  \text{the set of all primes dividing }g/p\right)  \subseteq\left(
\text{the set of all primes dividing }g\right)  \setminus\left\{  p\right\}  .
\label{pf.prop.mu.iverson.short.num.pf.1}%
\end{equation}
\par
On the other hand, let $q\in\left(  \text{the set of all primes dividing
}g\right)  \setminus\left\{  p\right\}  $. Then, $q$ is a prime dividing $g$,
but we have $q\neq p$. The primes $q$ and $p$ are distinct, and therefore
coprime. Recall the following general fact: If $x$, $y$ and $z$ are three
integers such that $x$ and $y$ are coprime and such that $x\mid yz$, then
$x\mid z$. Applying this to $x=q$, $y=p$ and $z=g/p$, we obtain $q\mid g/p$
(since $q\mid g=p\left(  g/p\right)  $). Thus, $q$ is a prime dividing $g/p$.
\par
Now, let us forget that we fixed $q$. We thus have shown that every
$q\in\left(  \text{the set of all primes dividing }g\right)  \setminus\left\{
p\right\}  $ is a prime dividing $g/p$. In other words,%
\[
\left(  \text{the set of all primes dividing }g\right)  \setminus\left\{
p\right\}  \subseteq\left(  \text{the set of all primes dividing }g/p\right)
.
\]
Combining this inclusion with (\ref{pf.prop.mu.iverson.short.num.pf.1}), we
obtain%
\[
\left(  \text{the set of all primes dividing }g/p\right)  =\left(  \text{the
set of all primes dividing }g\right)  \setminus\left\{  p\right\}  .
\]
Now,%
\begin{align*}
&  \left(  \text{number of primes dividing }\underbrace{\mathbf{A}\left(
g\right)  }_{=g/p}\right) \\
&  =\left(  \text{number of primes dividing }g/p\right)  =\left\vert
\underbrace{\left(  \text{the set of all primes dividing }g/p\right)
}_{=\left(  \text{the set of all primes dividing }g\right)  \setminus\left\{
p\right\}  }\right\vert \\
&  =\left\vert \left(  \text{the set of all primes dividing }g\right)
\setminus\left\{  p\right\}  \right\vert \\
&  =\underbrace{\left\vert \left(  \text{the set of all primes dividing
}g\right)  \right\vert }_{=\left(  \text{number of primes dividing }g\right)
}-1\ \ \ \ \ \ \ \ \ \ \left(  \text{since }p\text{ is a prime dividing
}g\right) \\
&  =\left(  \text{number of primes dividing }g\right)  -1,
\end{align*}
qed.} and thus%
\begin{equation}
\mu\left(  \mathbf{A}\left(  g\right)  \right)  =-\mu\left(  g\right)
\label{pf.prop.mu.iverson.short.mu}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.prop.mu.iverson.short.mu}):} Let
$g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  $.
\par
Thus, $g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  \subseteq\operatorname*{Sqf}$, so that $g$ is a squarefree positive
integer. Hence, (\ref{eq.mu.short.1}) (applied to $m=g$) shows that
$\mu\left(  g\right)  =\left(  -1\right)  ^{\left(  \text{number of primes
dividing }g\right)  }$.
\par
But the target of the map $\mathbf{A}$ is $\operatorname*{Sqf}\cap\left\{
h\in\mathbb{N}_{\mid N}\ :\ p\nmid h\right\}  $. Thus, $\mathbf{A}\left(
g\right)  \in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\nmid h\right\}  \subseteq\operatorname*{Sqf}$. In other words,
$\mathbf{A}\left(  g\right)  $ is a squarefree positive integer. Hence,
(\ref{eq.mu.short.1}) (applied to $m=\mathbf{A}\left(  g\right)  $) shows
that
\begin{align*}
\mu\left(  \mathbf{A}\left(  g\right)  \right)   &  =\left(  -1\right)
^{\left(  \text{number of primes dividing }\mathbf{A}\left(  g\right)
\right)  }=\left(  -1\right)  ^{\left(  \text{number of primes dividing
}g\right)  -1}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{pf.prop.mu.iverson.short.num})}\right) \\
&  =-\underbrace{\left(  -1\right)  ^{\left(  \text{number of primes dividing
}g\right)  }}_{=\mu\left(  g\right)  }=-\mu\left(  g\right)  .
\end{align*}
This proves (\ref{pf.prop.mu.iverson.short.mu}).}.

Now,%
\begin{align*}
&  \sum_{d\mid N}\mu\left(  d\right) \\
&  =\sum_{g\mid N}\mu\left(  g\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{here,
we have renamed the summation index }d\text{ as }g\right) \\
&  =\underbrace{\sum_{\substack{g\mid N;\\g\text{ is squarefree}}%
}}_{\substack{=\sum_{\substack{g\mid N;\\g\in\operatorname*{Sqf}%
}}\\\text{(because a positive integer }g\\\text{is squarefree if and only
if}\\\text{it satisfies }g\in\operatorname*{Sqf}\text{)}}}\mu\left(  g\right)
+\sum_{\substack{g\mid N;\\g\text{ is not squarefree}}}\underbrace{\mu\left(
g\right)  }_{\substack{=0\\\text{(by (\ref{eq.mu.short.2}), applied to
}m=g\text{)}}}\\
&  =\underbrace{\sum_{\substack{g\mid N;\\g\in\operatorname*{Sqf}}}}%
_{=\sum_{\substack{g\in\mathbb{N}_{\mid N};\\g\in\operatorname*{Sqf}}%
}=\sum_{\substack{g\in\operatorname*{Sqf};\\g\in\mathbb{N}_{\mid N}}}}%
\mu\left(  g\right)  +\underbrace{\sum_{\substack{g\in\mathbb{N}_{\mid
N};\\g\text{ is not squarefree}}}0}_{=0}=\sum_{\substack{g\in
\operatorname*{Sqf};\\g\in\mathbb{N}_{\mid N}}}\mu\left(  g\right) \\
&  =\underbrace{\sum_{\substack{g\in\operatorname*{Sqf};\\g\in\mathbb{N}_{\mid
N};\\p\mid g}}}_{\substack{=\sum_{\substack{g\in\operatorname*{Sqf}%
;\\g\in\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}  }}\\=\sum
_{g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  }}}\mu\left(  g\right)  +\underbrace{\sum_{\substack{g\in
\operatorname*{Sqf};\\g\in\mathbb{N}_{\mid N};\\p\nmid g}}}_{\substack{=\sum
_{\substack{g\in\operatorname*{Sqf};\\g\in\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\nmid h\right\}  }}\\=\sum_{g\in\operatorname*{Sqf}\cap\left\{
h\in\mathbb{N}_{\mid N}\ :\ p\nmid h\right\}  }}}\mu\left(  g\right)
\end{align*}%
\begin{align*}
&  =\sum_{g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\mid h\right\}  }\mu\left(  g\right)  +\underbrace{\sum_{g\in
\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid h\right\}
}\mu\left(  g\right)  }_{\substack{=\sum_{g\in\operatorname*{Sqf}\cap\left\{
h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}  }\mu\left(  \mathbf{A}\left(
g\right)  \right)  \\\text{(here, we have substituted }\mathbf{A}\left(
g\right)  \text{ for }g\text{ in the sum,}\\\text{since the map}%
\\\mathbf{A}:\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  \rightarrow\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\nmid h\right\}  \\\text{is a bijection)}}}\\
&  =\sum_{g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\mid h\right\}  }\mu\left(  g\right)  +\sum_{g\in\operatorname*{Sqf}%
\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}  }\mu\left(
\mathbf{A}\left(  g\right)  \right) \\
&  =\sum_{g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\mid h\right\}  }\underbrace{\left(  \mu\left(  g\right)  +\mu\left(
\mathbf{A}\left(  g\right)  \right)  \right)  }_{\substack{=0\\\text{(by
(\ref{pf.prop.mu.iverson.short.mu}))}}}\\
&  =\sum_{g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\mid h\right\}  }0=0=\left[  N=1\right] \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }\left[  N=1\right]  =0\text{
(since we don't have }N=1\text{)}\right)  .
\end{align*}
This proves Proposition \ref{prop.mu.iverson}.
\end{proof}
\end{vershort}

\begin{verlong}
\begin{proof}
[Proof of Proposition \ref{prop.mu.iverson}.]If $N=1$, then Proposition
\ref{prop.mu.iverson} holds\footnote{\textit{Proof.} Assume that $N=1$. Thus,
$\sum_{d\mid N}\mu\left(  d\right)  =\sum_{d\mid1}\mu\left(  d\right)
=\mu\left(  1\right)  $ (since the only divisor of $1$ is $1$). Thus,
$\sum_{d\mid N}\mu\left(  d\right)  =\mu\left(  1\right)  =1$ (by
(\ref{eq.mu.3})). On the other hand, $N=1$ holds, and thus we have $\left[
N=1\right]  =1$. Compared with $\sum_{d\mid N}\mu\left(  d\right)  =1$, this
shows that $\sum_{d\mid N}\mu\left(  d\right)  =\left[  N=1\right]  $. Hence,
Proposition \ref{prop.mu.iverson} holds, qed.}. Hence, for the rest of the
proof of Proposition \ref{prop.mu.iverson}, we can WLOG assume that we don't
have $N=1$. Assume this.

We have $N\neq1$ (since we don't have $N=1$). Hence, $N$ has at least one
prime divisor (since $N$ is a positive integer). Pick such a prime divisor,
and denote it by $p$. Thus, $p$ is a prime divisor of $N$. In other words, $p$
is a prime and divides $N$.

Let $\operatorname*{Sqf}$ denote the set of all squarefree positive integers.

We have $p\mid N$ (since $p$ divides $N$) and thus $N/p\in\mathbb{Z}$.

For every $g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\mid h\right\}  $, we have%
\begin{equation}
g/p\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid
h\right\}  \label{pf.prop.mu.iverson.wd1}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.prop.mu.iverson.wd1}):} Let $g\in
\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}
$.
\par
Notice that $p$ is a prime, and thus a positive integer $>1$.
\par
We have $g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  \subseteq\operatorname*{Sqf}$. In other words, $g$ is an element of
$\operatorname*{Sqf}$. In other words, $g$ is an element of the set of all
squarefree positive integers (since $\operatorname*{Sqf}$ is the set of all
squarefree positive integers). In other words, $g$ is a squarefree positive
integer.
\par
We have $g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  \subseteq\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}  $.
In other words, $g$ is an $h\in\mathbb{N}_{\mid N}$ satisfying $p\mid h$. In
other words, $g$ is an element of $\mathbb{N}_{\mid N}$ and satisfies $p\mid
g$.
\par
From $p\mid g$, we obtain $g/p\in\mathbb{Z}$. Also, $g/p$ is positive (since
$g$ and $p$ are positive), and thus $g/p$ is a positive integer (since $g/p$
is positive and since $g/p\in\mathbb{Z}$). Moreover, $g/p\mid g$ (since
$g=p\left(  g/p\right)  $). Hence, (\ref{eq.sqfree.2}) (applied to $u=g/p$ and
$v=g$) shows that $g/p$ is squarefree. Thus, $g/p$ is a squarefree positive
integer. In other words, $g/p$ is an element of the set of all squarefree
positive integers. In other words, $g/p$ is an element of $\operatorname*{Sqf}%
$ (since $\operatorname*{Sqf}$ is the set of all squarefree positive
integers). In other words, $g/p\in\operatorname*{Sqf}$.
\par
Also, $g$ is an element of $\mathbb{N}_{\mid N}$. In other words, $g$ is an
element of the set of all positive divisors of $N$ (since $\mathbb{N}_{\mid
N}$ is the set of all positive divisors of $N$). In other words, $g$ is a
positive divisor of $N$. In other words, $g$ is a positive integer and a
divisor of $N$.
\par
Now, $g/p\mid g\mid N$ (since $g$ is a divisor of $N$). Hence, $g/p$ is a
divisor of $N$. Thus, $g/p$ is a positive divisor of $N$ (since $g/p$ is a
positive integer and a divisor of $N$). In other words, $g/p$ is an element of
the set of all positive divisors of $N$. In other words, $g/p$ is an element
of $\mathbb{N}_{\mid N}$ (since $\mathbb{N}_{\mid N}$ is the set of all
positive divisors of $N$).
\par
Also, we have $p\nmid g/p$.
\par
[\textit{Proof of }$p\nmid g/p$\textit{:} For the sake of contradiction,
assume the contrary. Thus, $p\mid g/p$. Multiplying this divisibility by $p$,
we obtain $pp\mid\left(  g/p\right)  p=g$. Thus, $p^{2}=pp\mid g$.
\par
But we have the logical equivalence $\left(  g\text{ is squarefree}\right)
\Longleftrightarrow\left(  \text{no positive integer }m>1\text{ satisfies
}m^{2}\mid g\right)  $ (by (\ref{eq.sqfree.equiv}), applied to $n=g$).
Therefore, $\left(  \text{no positive integer }m>1\text{ satisfies }m^{2}\mid
g\right)  $ (since we know that $\left(  g\text{ is squarefree}\right)  $).
Applying this to $m=p$, we conclude that we cannot have $p^{2}\mid g$ (since
$p$ is a positive integer $>1$). This contradicts $p^{2}\mid g$. This
contradiction proves that our assumption was wrong. Hence, $p\nmid g/p$ is
proven.]
\par
Thus, $g/p$ is an element of $\mathbb{N}_{\mid N}$ and satisfies $p\nmid g/p$.
In other words, $g/p$ is an $h\in\mathbb{N}_{\mid N}$ satisfying $p\nmid h$.
In other words, $g/p\in\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid h\right\}
$.
\par
Combining $g/p\in\operatorname*{Sqf}$ with $g/p\in\left\{  h\in\mathbb{N}%
_{\mid N}\ :\ p\nmid h\right\}  $, we obtain $g/p\in\operatorname*{Sqf}%
\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid h\right\}  $. This proves
(\ref{pf.prop.mu.iverson.wd1}).}. Hence, we can define a map%
\[
\mathbf{A}:\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  \rightarrow\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\nmid h\right\}
\]
by%
\[
\left(  \mathbf{A}\left(  g\right)  =g/p\ \ \ \ \ \ \ \ \ \ \text{for every
}g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  \right)  .
\]
Consider this map $\mathbf{A}$.

For every $g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\nmid h\right\}  $, we have%
\begin{equation}
gp\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  \label{pf.prop.mu.iverson.wd2}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.prop.mu.iverson.wd2}):} Let $g\in
\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid h\right\}
$.
\par
We have $g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\nmid h\right\}  \subseteq\operatorname*{Sqf}$. In other words, $g$ is
an element of $\operatorname*{Sqf}$. In other words, $g$ is an element of the
set of all squarefree positive integers (since $\operatorname*{Sqf}$ is the
set of all squarefree positive integers). In other words, $g$ is a squarefree
positive integer.
\par
We have $g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\nmid h\right\}  \subseteq\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid
h\right\}  $. In other words, $g$ is an $h\in\mathbb{N}_{\mid N}$ satisfying
$p\nmid h$. In other words, $g$ is an element of $\mathbb{N}_{\mid N}$ and
satisfies $p\nmid g$.
\par
It is well-known that if $q$ is a prime and $z$ is an integer satisfying
$q\nmid z$, then $q$ is coprime to $z$. Applying this to $q=p$ and $z=g$, we
conclude that $p$ is coprime to $g$ (since $p\nmid g$). In other words, the
integers $g$ and $p$ are coprime. Also, the integer $p$ is prime, and
therefore squarefree (since every prime is squarefree). Hence,
(\ref{eq.sqfree.1}) (applied to $u=g$ and $v=p$) shows that $gp$ is
squarefree. Also, $gp$ is a positive integer (since $g$ and $p$ are positive
integers). Thus, $gp$ is a squarefree positive integer. In other words, $gp$
is an element of the set of all squarefree positive integers. In other words,
$gp$ is an element of $\operatorname*{Sqf}$ (since $\operatorname*{Sqf}$ is
the set of all squarefree positive integers). In other words, $gp\in
\operatorname*{Sqf}$.
\par
Also, $g$ is an element of $\mathbb{N}_{\mid N}$. In other words, $g$ is an
element of the set of all positive divisors of $N$ (since $\mathbb{N}_{\mid
N}$ is the set of all positive divisors of $N$). In other words, $g$ is a
positive divisor of $N$. In other words, $g$ is a positive integer and a
divisor of $N$.
\par
We have $g\mid N$ (since $g$ is a divisor of $N$) and $p\mid N$. Also, the
integers $g$ and $p$ are coprime.
\par
A well-known fact from elementary number theory states the following: If $x$,
$y$ and $z$ are three integers such that $x\mid z$ and $y\mid z$, and if the
integers $x$ and $y$ are coprime, then we have $xy\mid z$. We can apply this
to $x=g$, $y=p$ and $z=N$ (since we have $g\mid N$ and $p\mid N$, and since
the integers $g$ and $p$ are coprime). As a consequence, we obtain $gp\mid N$.
Thus, $gp$ is a divisor of $N$. Thus, $gp$ is a positive divisor of $N$ (since
$gp$ is a positive integer and a divisor of $N$). In other words, $gp$ is an
element of the set of all positive divisors of $N$. In other words, $gp$ is an
element of $\mathbb{N}_{\mid N}$ (since $\mathbb{N}_{\mid N}$ is the set of
all positive divisors of $N$). Also, we have $p\mid gp$.
\par
Thus, $gp$ is an element of $\mathbb{N}_{\mid N}$ and satisfies $p\mid gp$. In
other words, $gp$ is an $h\in\mathbb{N}_{\mid N}$ satisfying $p\mid h$. In
other words, $gp\in\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}  $.
\par
Combining $gp\in\operatorname*{Sqf}$ with $gp\in\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\mid h\right\}  $, we obtain $gp\in\operatorname*{Sqf}\cap\left\{
h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}  $. This proves
(\ref{pf.prop.mu.iverson.wd2}).}. Hence, we can define a map%
\[
\mathbf{B}:\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid
h\right\}  \rightarrow\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\mid h\right\}
\]
by%
\[
\left(  \mathbf{B}\left(  g\right)  =gp\ \ \ \ \ \ \ \ \ \ \text{for every
}g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid
h\right\}  \right)  .
\]
Consider this map $\mathbf{B}$.

We have $\mathbf{A}\circ\mathbf{B}=\operatorname*{id}$%
\ \ \ \ \footnote{\textit{Proof.} For every $g\in\operatorname*{Sqf}%
\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid h\right\}  $, we have%
\begin{align*}
\left(  \mathbf{A}\circ\mathbf{B}\right)  \left(  g\right)   &  =\mathbf{A}%
\left(  \underbrace{\mathbf{B}\left(  g\right)  }_{\substack{=gp\\\text{(by
the definition of }\mathbf{B}\text{)}}}\right)  =\mathbf{A}\left(  gp\right)
=gp/p\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of }\mathbf{A}\right)
\\
&  =g=\operatorname*{id}\left(  g\right)  .
\end{align*}
In other words, $\mathbf{A}\circ\mathbf{B}=\operatorname*{id}$, qed.} and
$\mathbf{B}\circ\mathbf{A}=\operatorname*{id}$%
\ \ \ \ \footnote{\textit{Proof.} For every $g\in\operatorname*{Sqf}%
\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}  $, we have%
\begin{align*}
\left(  \mathbf{B}\circ\mathbf{A}\right)  \left(  g\right)   &  =\mathbf{B}%
\left(  \underbrace{\mathbf{A}\left(  g\right)  }_{\substack{=g/p\\\text{(by
the definition of }\mathbf{A}\text{)}}}\right)  =\mathbf{B}\left(  g/p\right)
=\left(  g/p\right)  p\ \ \ \ \ \ \ \ \ \ \left(  \text{by the definition of
}\mathbf{B}\right) \\
&  =g=\operatorname*{id}\left(  g\right)  .
\end{align*}
In other words, $\mathbf{B}\circ\mathbf{A}=\operatorname*{id}$, qed.}. Hence,
the maps $\mathbf{A}$ and $\mathbf{B}$ are mutually inverse. Therefore, the
map $\mathbf{A}$ is invertible. In other words, the map $\mathbf{A}$ is a bijection.

For every $g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\mid h\right\}  $, we have%
\begin{equation}
\left(  \text{number of primes dividing }\mathbf{A}\left(  g\right)  \right)
=\left(  \text{number of primes dividing }g\right)  -1
\label{pf.prop.mu.iverson.num}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.prop.mu.iverson.num}):} Let $g\in
\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}
$.
\par
We have $g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  \subseteq\operatorname*{Sqf}$. In other words, $g$ is an element of
$\operatorname*{Sqf}$. In other words, $g$ is an element of the set of all
squarefree positive integers (since $\operatorname*{Sqf}$ is the set of all
squarefree positive integers). In other words, $g$ is a squarefree positive
integer.
\par
We have $g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  \subseteq\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}  $.
In other words, $g$ is an $h\in\mathbb{N}_{\mid N}$ satisfying $p\mid h$. In
other words, $g$ is an element of $\mathbb{N}_{\mid N}$ and satisfies $p\mid
g$.
\par
We have $\mathbf{A}\left(  g\right)  =g/p$ (by the definition of $\mathbf{A}%
$).
\par
Let $X$ denote the set of all primes dividing $g$. Let $Y$ denote the set of
all primes dividing $\mathbf{A}\left(  g\right)  $. We shall show that
$Y=X\setminus\left\{  p\right\}  $.
\par
First, we claim that $Y\subseteq X\setminus\left\{  p\right\}  $.
\par
[\textit{Proof of }$Y\subseteq X\setminus\left\{  p\right\}  $\textit{:} Let
$y\in Y$. Thus, $y$ is an element of $Y$. In other words, $y$ is an element of
the set of all primes dividing $\mathbf{A}\left(  g\right)  $ (since $Y$ is
the set of all primes dividing $\mathbf{A}\left(  g\right)  $). In other
words, $y$ is a prime dividing $\mathbf{A}\left(  g\right)  $. In other words,
$y$ is a prime and a divisor of $\mathbf{A}\left(  g\right)  $.
\par
We have $\mathbf{A}\left(  g\right)  \in\operatorname*{Sqf}\cap\left\{
h\in\mathbb{N}_{\mid N}\ :\ p\nmid h\right\}  $ (since the target of the map
$\mathbf{A}$ is $\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\nmid h\right\}  $). Thus, $\mathbf{A}\left(  g\right)  \in
\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid h\right\}
\subseteq\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid h\right\}  $. In other
words, $\mathbf{A}\left(  g\right)  $ is an $h\in\mathbb{N}_{\mid N}$
satisfying $p\nmid h$. In other words, $\mathbf{A}\left(  g\right)  $ is an
element of $\mathbb{N}_{\mid N}$ and satisfies $p\nmid\mathbf{A}\left(
g\right)  $. We have $p\nmid\mathbf{A}\left(  g\right)  =g/p$.
\par
We have $y\mid\mathbf{A}\left(  g\right)  $ (since $y$ is a divisor of
$\mathbf{A}\left(  g\right)  $), so that $y\mid\mathbf{A}\left(  g\right)
=g/p$. Hence, $y\mid g/p\mid g$ (since $g=p\left(  g/p\right)  $). In other
words, $y$ is a divisor of $g$. Hence, $y$ is a prime divisor of $g$ (since
$y$ is a prime and a divisor of $g$). In other words, $y$ is an element of the
set of all primes dividing $g$. In other words, $y$ is an element of $X$
(since $X$ is the set of all primes dividing $g$). Thus, $y\in X$. Also, if we
had $y=p$, then we would have $p=y\mid g/p$, which would contradict $p\nmid
g/p$. Hence, we cannot have $y=p$. In other words, we have $y\neq p$.
Combining $y\in X$ with $y\neq p$, we obtain $y\in X\setminus\left\{
p\right\}  $.
\par
Now, let us forget that we fixed $y$. We thus have proven that $y\in
X\setminus\left\{  p\right\}  $ for every $y\in Y$. In other words,
$Y\subseteq X\setminus\left\{  p\right\}  $. This proves $Y\subseteq
X\setminus\left\{  p\right\}  $.]
\par
Next, we claim that $X\setminus\left\{  p\right\}  \subseteq Y$.
\par
[\textit{Proof of }$X\setminus\left\{  p\right\}  \subseteq Y$\textit{:} Let
$x\in X\setminus\left\{  p\right\}  $. Thus, $x\neq p$ (since $x\in
X\setminus\left\{  p\right\}  $). Also, $x\in X\setminus\left\{  p\right\}
\subseteq X$. Thus, $x$ is an element of $X$. In other words, $x$ is an
element of the set of all primes dividing $g$ (since $X$ is the set of all
primes dividing $g$). In other words, $x$ is a prime dividing $g$. In other
words, $x$ is a prime and a divisor of $g$. Thus, $x$ and $p$ are two prime
numbers. Furthermore, $x$ and $p$ are distinct (since $x\neq p$).
\par
A well-known fact says that if $q$ and $r$ are two distinct prime numbers,
then $q\nmid r$. We can apply this to $q=x$ and $r=p$ (since $x$ and $p$ are
two distinct prime numbers). As a result, we obtain $x\nmid p$.
\par
We have $x\mid g$ (since $x$ is a divisor of $g$). But $g/p$ is an integer
(since $p\mid g$). Hence, $x\mid g=p\left(  g/p\right)  $.
\par
We now recall the following basic result from number theory: If $q$ is a prime
number and if $y$ and $z$ are two integers such that $q\mid yz$, then either
$q\mid y$ or $q\mid z$ (or both). We can apply this to $q=x$, $y=p$ and
$g=g/p$ (because $x$ is a prime, because $p$ and $g/p$ are integers, and
because $x\mid p\left(  g/p\right)  $). As a result, we conclude that either
$x\mid p$ or $x\mid g/p$ (or both). Since $x\mid p$ cannot hold (because we
have $x\nmid p$), this shows that we have $x\mid g/p$. Since $\mathbf{A}%
\left(  g\right)  =g/p$, this rewrites as $x\mid\mathbf{A}\left(  g\right)  $.
In other words, $x$ is a divisor of $\mathbf{A}\left(  g\right)  $.
\par
Hence, $x$ is a prime dividing $\mathbf{A}\left(  g\right)  $ (since $x$ is a
prime and a divisor of $\mathbf{A}\left(  g\right)  $). In other words, $x$ is
an element of the set of all primes dividing $\mathbf{A}\left(  g\right)  $.
In other words, $y$ is an element of $Y$ (since $Y$ is the set of all primes
dividing $\mathbf{A}\left(  g\right)  $). Thus, $y\in Y$.
\par
Now, let us forget that we fixed $y$. We thus have proven that $y\in Y$ for
every $y\in X\setminus\left\{  p\right\}  $. In other words, $X\setminus
\left\{  p\right\}  \subseteq Y$. This proves $X\setminus\left\{  p\right\}
\subseteq Y$.]
\par
Combining $Y\subseteq X\setminus\left\{  p\right\}  $ with $X\setminus\left\{
p\right\}  \subseteq Y$, we obtain $Y=X\setminus\left\{  p\right\}  $.
\par
Furthermore, $p$ is a prime and a divisor of $g$ (since $p\mid g$). In other
words, $p$ is a prime dividing $g$. In other words, $p$ is an element of the
set of all primes dividing $g$. In other words, $p$ is an element of $X$
(since $X$ is the set of all primes dividing $g$). Thus, $p\in X$. Hence,
$\left\vert X\setminus\left\{  p\right\}  \right\vert =\left\vert X\right\vert
-1$. Since $Y=X\setminus\left\{  p\right\}  $, this rewrites as $\left\vert
Y\right\vert =\left\vert X\right\vert -1$.
\par
Now, $X$ is the set of all primes dividing $g$. Thus, $X=\left(  \text{the set
of primes dividing }g\right)  $, so that%
\[
\left\vert X\right\vert =\left\vert \left(  \text{the set of primes dividing
}g\right)  \right\vert =\left(  \text{number of primes dividing }g\right)  .
\]
Also, $Y$ is the set of all primes dividing $\mathbf{A}\left(  g\right)  $.
Thus, $Y=\left(  \text{the set of primes dividing }\mathbf{A}\left(  g\right)
\right)  $, so that%
\[
\left\vert Y\right\vert =\left\vert \left(  \text{the set of primes dividing
}\mathbf{A}\left(  g\right)  \right)  \right\vert =\left(  \text{number of
primes dividing }\mathbf{A}\left(  g\right)  \right)  .
\]
Hence,%
\begin{align*}
\left(  \text{number of primes dividing }\mathbf{A}\left(  g\right)  \right)
&  =\left\vert Y\right\vert =\underbrace{\left\vert X\right\vert }_{=\left(
\text{number of primes dividing }g\right)  }-1\\
&  =\left(  \text{number of primes dividing }g\right)  -1.
\end{align*}
This proves (\ref{pf.prop.mu.iverson.num}).} and thus%
\begin{equation}
\mu\left(  \mathbf{A}\left(  g\right)  \right)  =-\mu\left(  g\right)
\label{pf.prop.mu.iverson.mu}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.prop.mu.iverson.mu}):} Let $g\in
\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}
$.
\par
We have $g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  \subseteq\operatorname*{Sqf}$. In other words, $g$ is an element of
$\operatorname*{Sqf}$. In other words, $g$ is an element of the set of all
squarefree positive integers (since $\operatorname*{Sqf}$ is the set of all
squarefree positive integers). In other words, $g$ is a squarefree positive
integer. Hence, (\ref{eq.mu.1}) (applied to $m=g$) shows that
\begin{equation}
\mu\left(  g\right)  =\left(  -1\right)  ^{\left(  \text{number of primes
dividing }g\right)  }. \label{pf.prop.mu.iverson.mu.pf.1}%
\end{equation}
\par
Also, the target of the map $\mathbf{A}$ is $\operatorname*{Sqf}\cap\left\{
h\in\mathbb{N}_{\mid N}\ :\ p\nmid h\right\}  $. Thus, $\mathbf{A}\left(
g\right)  \in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\nmid h\right\}  \subseteq\operatorname*{Sqf}$. In other words,
$\mathbf{A}\left(  g\right)  $ belongs to $\operatorname*{Sqf}$. In other
words, $\mathbf{A}\left(  g\right)  $ belongs to the set of all squarefree
positive integers (since $\operatorname*{Sqf}$ is the set of all squarefree
positive integers). In other words, $\mathbf{A}\left(  g\right)  $ is a
squarefree positive integer. Hence, (\ref{eq.mu.1}) (applied to $m=\mathbf{A}%
\left(  g\right)  $) shows that
\begin{align*}
\mu\left(  \mathbf{A}\left(  g\right)  \right)   &  =\left(  -1\right)
^{\left(  \text{number of primes dividing }\mathbf{A}\left(  g\right)
\right)  }=\left(  -1\right)  ^{\left(  \text{number of primes dividing
}g\right)  -1}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{pf.prop.mu.iverson.num})}\right) \\
&  =\dfrac{\left(  -1\right)  ^{\left(  \text{number of primes dividing
}g\right)  }}{-1}=-\underbrace{\left(  -1\right)  ^{\left(  \text{number of
primes dividing }g\right)  }}_{\substack{=\mu\left(  g\right)  \\\text{(by
(\ref{pf.prop.mu.iverson.mu.pf.1}))}}}=-\mu\left(  g\right)  .
\end{align*}
This proves (\ref{pf.prop.mu.iverson.mu}).}.

Now, if $g\in\mathbb{N}_{\mid N}$, then $g$ is a positive
integer\footnote{\textit{Proof.} Let $g\in\mathbb{N}_{\mid N}$. Thus, $g$
belongs to $\mathbb{N}_{\mid N}$. In other words, $g$ belongs to the set of
all positive divisors of $N$ (since $\mathbb{N}_{\mid N}$ is the set of all
positive divisors of $N$). In other words, $g$ is a positive divisor of $N$.
In other words, $g$ is a positive integer and divides $N$. Thus, $g$ is a
positive integer, qed.}. Hence, if $g\in\mathbb{N}_{\mid N}$, then we have the
following logical equivalence:%
\begin{align}
&  \ \left(  g\text{ is squarefree}\right) \nonumber\\
&  \Longleftrightarrow\ \left(  g\text{ is a squarefree positive
integer}\right) \nonumber\\
&  \Longleftrightarrow\ \left(  g\in\operatorname*{Sqf}\right)
\label{pf.prop.mu.iverson.Sqf}%
\end{align}
(since $\operatorname*{Sqf}$ is the set of all squarefree positive integers).

Now, Lemma \ref{lem.Ndivsum} (applied to $b_{g}=\mu\left(  g\right)  $) shows
that $\sum_{g\mid N}\mu\left(  g\right)  =\sum_{g\in\mathbb{N}_{\mid N}}%
\mu\left(  g\right)  $. Now%
\begin{align*}
&  \sum_{d\mid N}\mu\left(  d\right) \\
&  =\sum_{g\mid N}\mu\left(  g\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{here,
we have renamed the summation index }d\text{ as }g\right) \\
&  =\sum_{g\in\mathbb{N}_{\mid N}}\mu\left(  g\right)  =\underbrace{\sum
_{\substack{g\in\mathbb{N}_{\mid N};\\g\text{ is squarefree}}}}%
_{\substack{=\sum_{\substack{g\in\mathbb{N}_{\mid N};\\g\in\operatorname*{Sqf}%
}}\\\text{(because for any }g\in\mathbb{N}_{\mid N}\text{,}\\\text{the
statement }\left(  g\text{ is squarefree}\right)  \\\text{is equivalent to
}\left(  g\in\operatorname*{Sqf}\right)  \\\text{(due to
(\ref{pf.prop.mu.iverson.Sqf})))}}}\mu\left(  g\right)  +\sum_{\substack{g\in
\mathbb{N}_{\mid N};\\g\text{ is not squarefree}}}\underbrace{\mu\left(
g\right)  }_{\substack{=0\\\text{(by (\ref{eq.mu.2}), applied to }m=g\text{)}%
}}\\
&  =\sum_{\substack{g\in\mathbb{N}_{\mid N};\\g\in\operatorname*{Sqf}}%
}\mu\left(  g\right)  +\underbrace{\sum_{\substack{g\in\mathbb{N}_{\mid
N};\\g\text{ is not squarefree}}}0}_{=0}=\underbrace{\sum_{\substack{g\in
\mathbb{N}_{\mid N};\\g\in\operatorname*{Sqf}}}}_{=\sum_{\substack{g\in
\operatorname*{Sqf};\\g\in\mathbb{N}_{\mid N}}}}\mu\left(  g\right)
=\sum_{\substack{g\in\operatorname*{Sqf};\\g\in\mathbb{N}_{\mid N}}}\mu\left(
g\right) \\
&  =\underbrace{\sum_{\substack{g\in\operatorname*{Sqf};\\g\in\mathbb{N}_{\mid
N};\\p\mid g}}}_{\substack{=\sum_{\substack{g\in\operatorname*{Sqf}%
;\\g\in\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}  }%
}\\\text{(because for any }g\in\operatorname*{Sqf}\text{,}\\\text{the
statement }\left(  g\in\mathbb{N}_{\mid N}\text{ and }p\mid g\right)
\\\text{is equivalent to }\left(  g\in\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\mid h\right\}  \right)  \text{)}}}\mu\left(  g\right)
+\underbrace{\sum_{\substack{g\in\operatorname*{Sqf};\\g\in\mathbb{N}_{\mid
N};\\p\nmid g}}}_{\substack{=\sum_{\substack{g\in\operatorname*{Sqf}%
;\\g\in\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid h\right\}  }%
}\\\text{(because for any }g\in\operatorname*{Sqf}\text{,}\\\text{the
statement }\left(  g\in\mathbb{N}_{\mid N}\text{ and }p\nmid g\right)
\\\text{is equivalent to }\left(  g\in\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\nmid h\right\}  \right)  \text{)}}}\mu\left(  g\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since every }g\in\operatorname*{Sqf}%
\text{ satisfies either }p\mid g\text{ or }p\nmid g\text{ (but not
both)}\right) \\
&  =\underbrace{\sum_{\substack{g\in\operatorname*{Sqf};\\g\in\left\{
h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}  }}}_{\substack{=\sum
_{g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  }\\\text{(since the elements }g\in\operatorname*{Sqf}\text{
satisfying}\\g\in\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}  \text{
are precisely}\\\text{the elements }g\in\operatorname*{Sqf}\cap\left\{
h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}  \text{)}}}\mu\left(  g\right)
+\underbrace{\sum_{\substack{g\in\operatorname*{Sqf};\\g\in\left\{
h\in\mathbb{N}_{\mid N}\ :\ p\nmid h\right\}  }}}_{\substack{=\sum
_{g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid
h\right\}  }\\\text{(since the elements }g\in\operatorname*{Sqf}\text{
satisfying}\\g\in\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid h\right\}  \text{
are precisely}\\\text{the elements }g\in\operatorname*{Sqf}\cap\left\{
h\in\mathbb{N}_{\mid N}\ :\ p\nmid h\right\}  \text{)}}}\mu\left(  g\right)
\end{align*}%
\begin{align*}
&  =\sum_{g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\mid h\right\}  }\mu\left(  g\right)  +\underbrace{\sum_{g\in
\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\nmid h\right\}
}\mu\left(  g\right)  }_{\substack{=\sum_{g\in\operatorname*{Sqf}\cap\left\{
h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}  }\mu\left(  \mathbf{A}\left(
g\right)  \right)  \\\text{(here, we have substituted }\mathbf{A}\left(
g\right)  \text{ for }g\text{ in the sum,}\\\text{since the map}%
\\\mathbf{A}:\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid
h\right\}  \rightarrow\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\nmid h\right\}  \\\text{is a bijection)}}}\\
&  =\sum_{g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\mid h\right\}  }\mu\left(  g\right)  +\sum_{g\in\operatorname*{Sqf}%
\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}  }\mu\left(
\mathbf{A}\left(  g\right)  \right) \\
&  =\sum_{g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\mid h\right\}  }\left(  \mu\left(  g\right)  +\underbrace{\mu\left(
\mathbf{A}\left(  g\right)  \right)  }_{\substack{=-\mu\left(  g\right)
\\\text{(by (\ref{pf.prop.mu.iverson.mu}))}}}\right) \\
&  =\sum_{g\in\operatorname*{Sqf}\cap\left\{  h\in\mathbb{N}_{\mid
N}\ :\ p\mid h\right\}  }\underbrace{\left(  \mu\left(  g\right)  +\left(
-\mu\left(  g\right)  \right)  \right)  }_{=0}=\sum_{g\in\operatorname*{Sqf}%
\cap\left\{  h\in\mathbb{N}_{\mid N}\ :\ p\mid h\right\}  }0=0\\
&  =\left[  N=1\right]  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }\left[
N=1\right]  =0\text{ (since we don't have }N=1\text{)}\right)  .
\end{align*}
This proves Proposition \ref{prop.mu.iverson}.
\end{proof}
\end{verlong}

Proposition \ref{prop.mu.iverson} leads to a neat corollary\footnote{I have
stated this corollary in the form that makes it most useful to the solution of
the problem; hence, the useless-looking variable $d$.}:

\begin{corollary}
\label{cor.mu.iverson2}Let $u$, $v$ and $d$ be three positive integers. Then,%
\[
\sum_{\substack{g\mid u;\\g\mid v}}\mu\left(  g\right)  =\left[  \gcd\left(
du,dv\right)  =d\right]  .
\]

\end{corollary}

\begin{vershort}
\begin{proof}
[Proof of Corollary \ref{cor.mu.iverson2}.]From Lemma \ref{lem.gcd.d}, we have
$\gcd\left(  du,dv\right)  =d\gcd\left(  u,v\right)  $. Thus, we have the
logical equivalence%
\[
\left(  \gcd\left(  du,dv\right)  =d\right)  \Longleftrightarrow\left(
d\gcd\left(  u,v\right)  =d\right)  \Longleftrightarrow\left(  \gcd\left(
u,v\right)  = 1\right)
\]
(because the nonzero integer $d$ can be cancelled). Hence, $\left[
\gcd\left(  du,dv\right)  =d\right]  =\left[  \gcd\left(  u,v\right)
=1\right]  $.

On the other hand, Lemma \ref{lem.gcdsum} (applied to $b_{g}=\mu\left(
g\right)  $) shows that%
\begin{align*}
\sum_{\substack{g\mid u;\\g\mid v}}\mu\left(  g\right)   &  =\sum_{g\mid
\gcd\left(  u,v\right)  }\mu\left(  g\right)  =\sum_{d\mid\gcd\left(
u,v\right)  }\mu\left(  d\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we renamed the summation index
}g\text{ as }d\right) \\
&  =\left[  \gcd\left(  u,v\right)  =1\right]  \ \ \ \ \ \ \ \ \ \ \left(
\text{by Proposition \ref{prop.mu.iverson}, applied to }N=\gcd\left(
u,v\right)  \right) \\
&  =\left[  \gcd\left(  du,dv\right)  =d\right]  \ \ \ \ \ \ \ \ \ \ \left(
\text{since }\left[  \gcd\left(  du,dv\right)  =d\right]  =\left[  \gcd\left(
u,v\right)  =1\right]  \right)  .
\end{align*}
This proves Corollary \ref{cor.mu.iverson2}.
\end{proof}
\end{vershort}

\begin{verlong}
\begin{proof}
[Proof of Corollary \ref{cor.mu.iverson2}.]From Lemma \ref{lem.gcd.d}, we have
$\gcd\left(  du,dv\right)  =d\gcd\left(  u,v\right)  $. Thus, we have the
logical equivalence%
\[
\left(  \gcd\left(  du,dv\right)  =d\right)  \Longleftrightarrow\left(
\gcd\left(  u,v\right)  =1\right)
\]
\footnote{\textit{Proof.} Assume that $\gcd\left(  du,dv\right)  =d$. Then,
$d\gcd\left(  u,v\right)  =\gcd\left(  du,dv\right)  =d=d\cdot1$. Since $d$ is
nonzero (because $d$ is a positive integer), we can cancel $d$ from this
equality. As a result, we obtain $\gcd\left(  u,v\right)  =1$.
\par
Now, let us forget that we assumed that $\gcd\left(  du,dv\right)  =d$. We
thus have proven that $\gcd\left(  u,v\right)  =1$ under the assumption that
$\gcd\left(  du,dv\right)  =d$. In other words, we have proven the
implication
\begin{equation}
\left(  \gcd\left(  du,dv\right)  =d\right)  \Longrightarrow\left(
\gcd\left(  u,v\right)  =1\right)  . \label{pf.cor.mu.iverson.fn1}%
\end{equation}
But the implication%
\begin{equation}
\left(  \gcd\left(  u,v\right)  =1\right)  \Longrightarrow\left(  \gcd\left(
du,dv\right)  =d\right)  \label{pf.cor.mu.iverson.fn2}%
\end{equation}
also holds (because if $\gcd\left(  u,v\right)  =1$, then $\gcd\left(
du,dv\right)  =d\underbrace{\gcd\left(  u,v\right)  }_{=1}=d$). Combining the
implications (\ref{pf.cor.mu.iverson.fn1}) and (\ref{pf.cor.mu.iverson.fn2}),
we obtain the equivalence $\left(  \gcd\left(  du,dv\right)  =d\right)
\Longleftrightarrow\left(  \gcd\left(  u,v\right)  =1\right)  $. Qed.}. Hence,
$\left[  \gcd\left(  du,dv\right)  =d\right]  =\left[  \gcd\left(  u,v\right)
=1\right]  $.

On the other hand, Lemma \ref{lem.gcdsum} (applied to $b_{g}=\mu\left(
g\right)  $) shows that%
\begin{align*}
\sum_{\substack{g\mid u;\\g\mid v}}\mu\left(  g\right)   &  =\sum_{g\mid
\gcd\left(  u,v\right)  }\mu\left(  g\right)  =\sum_{d\mid\gcd\left(
u,v\right)  }\mu\left(  d\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we renamed the summation index
}g\text{ as }d\right) \\
&  =\left[  \gcd\left(  u,v\right)  =1\right]  \ \ \ \ \ \ \ \ \ \ \left(
\text{by Proposition \ref{prop.mu.iverson}, applied to }N=\gcd\left(
u,v\right)  \right) \\
&  =\left[  \gcd\left(  du,dv\right)  =d\right]  \ \ \ \ \ \ \ \ \ \ \left(
\text{since }\left[  \gcd\left(  du,dv\right)  =d\right]  =\left[  \gcd\left(
u,v\right)  =1\right]  \right)  .
\end{align*}
This proves Corollary \ref{cor.mu.iverson2}.
\end{proof}
\end{verlong}

Now, let us step to the solution of the problem. Let $n$ and $m$ be two
positive integers.

Let $e$ be a positive divisor of $n$. Then, for every positive divisor $d$ of
$m$, we have%
\begin{align}
&  \sum_{\substack{g\mid e;\\g\mid d}}\dfrac{\mu(g)}{g}dea_{de/g}\nonumber\\
&  =\sum_{g\mid\gcd\left(  e,d\right)  }\dfrac{\mu(g)}{g}dea_{de/g}\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by Lemma \ref{lem.gcdsum}, applied to
}u=e\text{, }v=d\text{ and }b_{g}=\dfrac{\mu(g)}{g}dea_{de/g}\right)
\nonumber\\
&  =\sum_{g\mid\gcd\left(  d,e\right)  }\dfrac{\mu(g)}{g}dea_{de/g}%
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\gcd\left(  e,d\right)  =\gcd\left(
d,e\right)  \right)  . \label{sol.mrmoeb.2}%
\end{align}
Now,%
\begin{align}
&  \sum_{d\mid m}\underbrace{\sum_{g\mid\gcd\left(  d,e\right)  }\dfrac
{\mu(g)}{g}dea_{de/g}}_{\substack{=\sum_{\substack{g\mid e;\\g\mid d}%
}\dfrac{\mu(g)}{g}dea_{de/g}\\\text{(by (\ref{sol.mrmoeb.2}))}}}\nonumber\\
&  =\underbrace{\sum_{d\mid m}\sum_{\substack{g\mid e;\\g\mid d}}}%
_{=\sum_{g\mid e}\sum_{\substack{d\mid m;\\g\mid d}}}\underbrace{\dfrac
{\mu(g)}{g}d}_{=\mu\left(  g\right)  \left(  d/g\right)  }%
e\underbrace{a_{de/g}}_{\substack{=a_{\left(  d/g\right)  e}\\\text{(since
}de/g=\left(  d/g\right)  e\text{)}}}=\sum_{g\mid e}\sum_{\substack{d\mid
m;\\g\mid d}}\mu\left(  g\right)  \left(  d/g\right)  ea_{\left(  d/g\right)
e}\nonumber\\
&  =\sum_{g\mid e}\mu\left(  g\right)  e\underbrace{\sum_{\substack{d\mid
m;\\g\mid d}}\left(  d/g\right)  a_{\left(  d/g\right)  e}}_{\substack{=\sum
_{\substack{d\mid m;\\g\mid m/d}}da_{de}\\\text{(by Lemma
\ref{lem.divsumdeflate}, applied to }b_{d}=da_{de}\text{)}}}=\sum_{g\mid e}%
\mu\left(  g\right)  e\sum_{\substack{d\mid m;\\g\mid m/d}}da_{de}\nonumber\\
&  =\underbrace{\sum_{g\mid e}\sum_{\substack{d\mid m;\\g\mid m/d}}}%
_{=\sum_{d\mid m}\sum_{\substack{g\mid e;\\g\mid m/d}}}\mu\left(  g\right)
eda_{de}=\sum_{d\mid m}\sum_{\substack{g\mid e;\\g\mid m/d}}\mu\left(
g\right)  eda_{de}=\sum_{d\mid m}\left(  \sum_{\substack{g\mid e;\\g\mid
m/d}}\mu\left(  g\right)  \right)  eda_{de}. \label{sol.mrmoeb.4}%
\end{align}
But every positive divisor $d$ of $m$ satisfies%
\begin{equation}
\sum_{\substack{g\mid e;\\g\mid m/d}}\mu\left(  g\right)  =\left[  \gcd\left(
de,m\right)  =d\right]  \label{sol.mrmoeb.6}%
\end{equation}
\footnote{\textit{Proof of (\ref{sol.mrmoeb.6}):} Let $d$ be a positive
divisor of $m$. Thus, $d$ is a positive integer and a divisor of $m$. We have
$d\mid m$ (since $d$ is a divisor of $m$) and thus $m/d\in\mathbb{Z}$. Also,
$m/d$ is positive (since $m$ and $d$ are positive) and thus a positive integer
(since $m/d\in\mathbb{Z}$). Hence, Corollary \ref{cor.mu.iverson2} (applied to
$u=e$ and $v=m/d$) shows that%
\[
\sum_{\substack{g\mid e;\\g\mid m/d}}\mu\left(  g\right)  =\left[  \gcd\left(
de,\underbrace{d\left(  m/d\right)  }_{=m}\right)  =d\right]  =\left[
\gcd\left(  de,m\right)  =d\right]  .
\]
This proves (\ref{sol.mrmoeb.6}).}. Thus, (\ref{sol.mrmoeb.4}) becomes%
\begin{align}
&  \sum_{d\mid m}\sum_{g\mid\gcd\left(  d,e\right)  }\dfrac{\mu(g)}%
{g}dea_{de/g}\nonumber\\
&  =\sum_{d\mid m}\underbrace{\left(  \sum_{\substack{g\mid e;\\g\mid m/d}%
}\mu\left(  g\right)  \right)  }_{\substack{=\left[  \gcd\left(  de,m\right)
=d\right]  \\\text{(by (\ref{sol.mrmoeb.6}))}}}\underbrace{ed}_{=de}%
a_{de}=\underbrace{\sum_{d\mid m}\left[  \gcd\left(  de,m\right)  =d\right]
dea_{de}}_{\substack{=\sum_{\substack{d\mid m;\\\gcd\left(  de,m\right)
=d}}\left[  \gcd\left(  de,m\right)  =d\right]  dea_{de}+\sum_{\substack{d\mid
m;\\\gcd\left(  de,m\right)  \neq d}}\left[  \gcd\left(  de,m\right)
=d\right]  dea_{de}\\\text{(since every positive divisor }d\text{ of }m\text{
satisfies either }\gcd\left(  de,m\right)  =d\\\text{or }\gcd\left(
de,m\right)  \neq d\text{ (but not both))}}}\nonumber\\
&  =\sum_{\substack{d\mid m;\\\gcd\left(  de,m\right)  =d}}\underbrace{\left[
\gcd\left(  de,m\right)  =d\right]  }_{\substack{=1\\\text{(since }\gcd\left(
de,m\right)  =d\text{ holds)}}}dea_{de}+\sum_{\substack{d\mid m;\\\gcd\left(
de,m\right)  \neq d}}\underbrace{\left[  \gcd\left(  de,m\right)  =d\right]
}_{\substack{=0\\\text{(since }\gcd\left(  de,m\right)  =d\text{ does not
hold}\\\text{(since we have }\gcd\left(  de,m\right)  \neq d\text{))}%
}}dea_{de}\nonumber\\
&  =\sum_{\substack{d\mid m;\\\gcd\left(  de,m\right)  =d}}1dea_{de}%
+\underbrace{\sum_{\substack{d\mid m;\\\gcd\left(  de,m\right)  \neq
d}}0dea_{de}}_{=0}\nonumber\\
&  =\sum_{\substack{d\mid m;\\\gcd\left(  de,m\right)  =d}}\underbrace{1de}%
_{=de}a_{de}=\sum_{\substack{d\mid m;\\\gcd\left(  de,m\right)  =d}}dea_{de}.
\label{sol.mrmoeb.10}%
\end{align}


Now, let us forget that we fixed $e$. We thus have proven that
(\ref{sol.mrmoeb.10}) holds for every positive divisor $e$ of $n$.

Now,%
\begin{align*}
&  \underbrace{\sum_{d\mid m}\sum_{e\mid n}}_{=\sum_{e\mid n}\sum_{d\mid m}%
}\sum_{g\mid\gcd\left(  d,e\right)  }\dfrac{\mu(g)}{g}dea_{de/g}\\
&  =\sum_{e\mid n}\underbrace{\sum_{d\mid m}\sum_{g\mid\gcd\left(  d,e\right)
}\dfrac{\mu(g)}{g}dea_{de/g}}_{\substack{=\sum_{\substack{d\mid m;\\\gcd
\left(  de,m\right)  =d}}dea_{de}\\\text{(by (\ref{sol.mrmoeb.10}))}%
}}=\underbrace{\sum_{e\mid n}\sum_{\substack{d\mid m;\\\gcd\left(
de,m\right)  =d}}}_{=\sum_{d\mid m}\sum_{\substack{e\mid n;\\\gcd\left(
de,m\right)  =d}}}dea_{de}\\
&  =\sum_{d\mid m}\sum_{\substack{e\mid n;\\\gcd\left(  de,m\right)
=d}}dea_{de}=\sum_{f\mid mn}fa_{f}%
\end{align*}
(by Lemma \ref{lem.de-sum}, applied to $u=m$, $v=n$ and $b_{f}=fa_{f}$). This
solves the problem.

\begin{thebibliography}{99999999}                                                                                         %


\bibitem[GriRei18]{GriRei15}Darij Grinberg, Victor Reiner, \textit{Hopf
algebras in Combinatorics}, version of 11 May 2018,
\arxiv{1409.8356v5}. \newline%
See also \url{http://www.cip.ifi.lmu.de/~grinberg/algebra/HopfComb-sols.pdf} for a version that gets updated.

\bibitem[Hildeb13]{Hildebr}A. J. Hildebrand, \textit{Introduction to Analytic
Number Theory: Math 531 Lecture Notes, Fall 2005}, version 2013.01.07.\newline%
\texttt{\url{http://www.math.uiuc.edu/~hildebr/ant/main1.pdf}}

\bibitem[NiZuMo91]{NiZuMo}Ivan Niven, Herbert S. Zuckerman, Hugh L.
Montgomery, \textit{An Introduction to the Theory of Numbers}, 5th edition,
Wiley 1991.
\end{thebibliography}


\end{document}