Menonの恒等式
$m,n$の最大公約数を$(m,n)$として, $\varphi(n)$でEulerの$\varphi$関数, $\tau(n):=\sum_{d|n}1$で$n$の約数の個数を表す. 以下はMenonによって1965年に示された等式である.
整数$n\geq 1$に対し,
\begin{align}
\sum_{\substack{1\leq k\leq n\\(k,n)=1}}(k-1,n)=\varphi(n)\tau(n)
\end{align}
が成り立つ.
\begin{align}
M(n):=\sum_{\substack{1\leq k\leq n\\(k,n)=1}}(k-1,n)
\end{align}
とする. 互いに素な$n_1,n_2$に対し,
\begin{align}
k_1n_2+k_2n_1\qquad 1\leq k_1\leq n_1, 1\leq k_2\leq n_2
\end{align}
を$n_1n_2$で割った余りは全て相異なるので,
\begin{align}
M(n_1n_2)&=\sum_{\substack{1\leq k\leq n\\(k,n)=1}}(k-1,n)\\
&=\sum_{\substack{1\leq k_1\leq n_1\\(k_1,n_1)=1}}\sum_{\substack{1\leq k_2\leq n_2\\(k_2,n_2)=1}}(k_1n_2+k_2n_1-1,n_1n_2)\\
&=\sum_{\substack{1\leq k_1\leq n_1\\(k_1,n_1)=1}}\sum_{\substack{1\leq k_2\leq n_2\\(k_2,n_2)=1}}(k_1n_2+k_2n_1-1,n_1)(k_1n_2+k_2n_1-1,n_2)\\
&=\sum_{\substack{1\leq k_1\leq n_1\\(k_1,n_1)=1}}(k_1n_2-1,n_1)\sum_{\substack{1\leq k_2\leq n_2\\(k_2,n_2)=1}}(k_2n_1-1,n_2)
\end{align}
ここで, $n_1,n_2$が互いに素であることから,
\begin{align}
\sum_{\substack{1\leq k_1\leq n_1\\(k_1,n_1)=1}}(k_1n_2-1,n_1)&=M(n_1)\\
\sum_{\substack{1\leq k_2\leq n_2\\(k_2,n_2)=1}}(k_2n_1-1,n_2)&=M(n_2)
\end{align}
となる. よって, 互いに素な$n_1,n_2$に対して
\begin{align}
M(n_1n_2)=M(n_1)M(n_2)
\end{align}
であることが示せた. よって素数冪$p^{\nu}, \nu\geq 1$の場合について等式を示せば十分である.
\begin{align}
M(p^{\nu})&=\sum_{\substack{1\leq k\leq p^{\nu}\\(k,p)=1}}(k-1,p^{\nu})\\
&=\sum_{k=1}^{p^{\nu}}(k-1,p^{\nu})-\sum_{k=1}^{p^{\nu-1}}(kp-1,p^{\nu})\\
&=\sum_{k=1}^{p^{\nu}}(k,p^{\nu})-p^{\nu-1}
\end{align}
となる. ここで, $0\leq t\leq \nu$に対し, $(k,p^{\nu})=p^t$となる$1\leq k\leq p^{\nu}$は$k=lp^t, 1\leq l\leq p^{\nu-t}, l\nmid p$と書けるものなので, その個数は$\varphi(p^{\nu-t})$個であることから
\begin{align}
\sum_{k=1}^{p^{\nu}}(k,p^{\nu})&=\sum_{t=0}^{\nu}p^t\varphi(p^{\nu-t})\\
&=p^{\nu}+\sum_{t=0}^{\nu-1}p^t(p^{\nu-t}-p^{\nu-t-1})\\
&=(\nu+1)p^{\nu}-\nu p^{\nu-1}
\end{align}
となる. よって
\begin{align}
M(p^{\nu})&=(\nu+1)p^{\nu}-\nu p^{\nu-1}-p^{\nu-1}\\
&=(\nu+1)(p^{\nu}-p^{\nu-1})\\
&=\varphi(p^{\nu})\tau(p^{\nu})
\end{align}
であるから, 示すべき等式が得られた.
証明の途中に現れた
\begin{align}
\sum_{k=1}^{p^{\nu}}(k,p^{\nu})
\end{align}
について,
\begin{align}
P(n)=\sum_{k=1}^n(k,n)
\end{align}
はPillai関数と呼ばれているようである. また, Menonの恒等式には他にも様々な証明や一般化が知られているようである.
