オイラー関数のある拡張とm乗和の関係について
オイラー関数を
$$
\begin{align}
\varphi(n)=\sum_{\substack{1\leqq k\lt n \\(n,k)=1}}1=\sum_{\substack{1\leqq k\lt n \\(n,k)=1}}k^{0}
\end{align}
$$
とみることにより，$k^{0}$を$k^{m}$として拡張してみよう．
この問題については，例えば飯高茂先生が三谷樹氏(当時，広尾学園高校2年)と共に第13回日本フィボナッチ協会研究集会，日本数学会（代数分科会），第26回数学史シンポジウム，日本数学会(代数分科会)等々でも解説されていますが，ここでは少し違った視点でとりあげてみることにしましょう．
まず，$m=0,~1,~2,\cdot$の場合を確認してみましょう．
$m=0$のときは，$\varphi(n)=\varphi_{0}(n)$であることは明らかですね．
次に$m=1$のときはどのように求められるでしょうか．次のように考えてみましょう．$(n,k)=1$である$k$と$n-k$のペアを並べてみます．
$$
\varphi(n)\mbox{個}\left\{
\begin{array}{ccccc}
1 & + & (n-1) & = & n \\
\vdots & + & \vdots & & \vdots \\
k & + & (n-k) & = & n \\
\vdots & + & \vdots & & \vdots \\
(n-1) & + & 1 & = & n
\end{array}
\right.
$$
ここで
$$
S=\displaystyle\sum_{\substack{1\leqq k\lt n \\(n,k)=1}}k
$$
とおけば，上式から
$$
\begin{align*}
S+S &=n\cdot \varphi(n) \\
2S &=n\varphi(n) \\
S &=\dfrac{n\varphi(n)}{2}
\end{align*}
$$
より
$$
\begin{align*}
\sum_{\substack{1\leqq k\lt n \\(n,k)=1}}k=\dfrac{n\varphi(n)}{2}
\end{align*}
$$
であることが分かりました．
では，$m\gt 1$について考えてみましょう．以下は宮田大輔先生(千葉商科大；2018.1 unpublished+第4回IIARS研究会(2018.10.7))によるものです．
ここで，オイラーの$m$次関数$\varphi_{m}(n)$なるものを
$$
\begin{align*}
\varphi_{m}(n)=\sum_{\substack{1\leqq k\lt n \\(n,k)=1}}k^{m}
\end{align*}
$$
として定義してみます．
まず，$n$以下の自然数の$m$乗和を
$$
\begin{align*}
P_{m}(n)=\sum_{k=1}^{n}k^m
\end{align*}
$$
とおきます．ここで
$$
\begin{align*}
\left(\frac{1}{n}\right)^m+\left(\frac{2}{n}\right)^m+\cdots+\left(\frac{n}{n}\right)^m
\end{align*}
$$
を2通りに評価すると，1つは
$$
\begin{align*}
\dfrac{1}{n^m}P_{m}(n)
\end{align*}
$$
であり，もう1つは，既約分数にして分母が$d^m$のものについての和と見なせます．
たとえば，$n=6$の場合では
$$
\begin{align*}
& \dfrac{1^m+2^m+3^m+4^m+5^m+6^m}{6^m}\\
&=\left(\frac{1}{6}\right)^m+\left(\frac{2}{6}\right)^m+\left(\frac{3}{6}\right)^m+\left(\frac{4}{6}\right)^m+\left(\frac{5}{6}\right)^m++\left(\frac{6}{6}\right)^m \\
&=\left(\frac{1}{6}\right)^m+\left(\frac{1}{3}\right)^m+\left(\frac{1}{2}\right)^m+\left(\frac{2}{3}\right)^m+\left(\frac{5}{6}\right)^m++\left(\frac{1}{1}\right)^m
\end{align*}
$$
と評価することになります．すなわち
$$
\sum_{d|n}\frac{\varphi_{m}(d)}{d^m}
$$
であることから，次の等式を得られます．
$$
\frac{1}{n^m}P_{m}(n)=\sum_{d|n}\frac{\varphi_{m}(n)}{d^m}
$$
ここで，メビウスの反転公式を適用すれば
$$
\frac{1}{n^m}\varphi_{m}(n)=\sum_{d|n}\mu(d)\left(\frac{n}{d}\right)^{-m}P_{m}\left(\frac{n}{d}\right)
$$
を得られ，
$$
\varphi_{m}(n)=\sum_{d|n}\mu(d)d^m P_{m}\left(\frac{n}{d}\right)
$$
の関係式が導かれます．
ここまでで，一応，$\varphi_{m}(n)$の形はわかりましたが，次に後述するジョルダンのトーシェント関数$J_{m}(n)$で眺めてみましょう．
$P_{m}(x)$の$x^k$の係数を$a_{m,k}$として，
$$
P_{m}(x)=a_{m,1}x+a_{m,2}x^2+\cdots+a_{m,m}x^m+a_{m,m+1}x^{m+1}
$$
と表すことにすると
$$
\begin{align*}
\varphi_{m}(n)=\sum_{k=1}^{m+1}a_{m,k}n^k \sum_{d|n}\mu(d)d^{m-k} \\
=\sum_{k=-1}^{m}a_{m,k}n^{m-k} \sum_{d|n}\mu(d)d^k
\end{align*}
$$
であることが分かります．
ここで$\displaystyle J_{m}(n)$を用いると，$ $ ${\rm rad}(n))$で$n$の根基とし，$k\gt 0$について
$$
\begin{align*}
\sum_{d|n}\mu(d)d^{-k}&=\frac{1}{n^k}J_{m}(n) \\
\sum_{d|n}\mu(d)d^{k}&=\mu({\rm rad}(n))\frac{~({\rm rad}(n))^k~}{n^k}J_{k}(n)
\end{align*}
$$
$k=0$のときは
$$
\begin{align*}
\sum_{d|n}\mu(d)=\left\{ \begin{array}{cl}
1 & (n=1) \\
0 & (n>1)
\end{array}
\right.
\end{align*}
$$
となるから，これを用いて，$n\gt 1$のとき$\varphi_{m}(1)=1$として$\varphi_{m}(n)$を表すと
$$
\begin{align*}
\varphi_{m}(n)&=\sum_{k=-1}^{m-1}a_{m,m-k}\ n^{m-k}\sum_{d|n}\mu(d)d^{k}\\
&=a_{m,m+1}\ n^{m}J_{1}(n)+
\mu({\rm rad}(n))\sum_{k=1}^{m-1}a_{m,m-k}\ n^{m-k}\frac{({\rm rad}(n))^k}{n^k}J_{k}(n) \\
&=\frac{n^m\varphi(n)}{m+1}+\mu({\rm rad}(n))\sum_{k=1}^{m-1}a_{m,m-k}\ n^{m-2k}({\rm rad}(n))^k J_{k}(n)
\end{align*}
$$
ここで上の結果から，$n\gt 1$として，具体的に$\varphi_{1}(n), \varphi_{2}(n), \varphi_{3}(n)$を求めてみましょう．
$m=1$のときは，
$$
\begin{align*}
\varphi_{1}(n)=\frac{n\varphi(n)}{2}
\end{align*}
$$
$m=2$のときは，$P_{2}(n)=\frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n$なので
$$
\begin{align*}
\varphi_{2}(n)=\frac{n^2\varphi(n)}{3}+(-1)^{\omega(n)}\frac{1}{6}\mu({\rm rad}(n)){\rm rad}(n)\varphi(n)
\end{align*}
$$
$m=3$のときは，$P_{3}(n)==\frac{1}{4}n^4+\frac{1}{2}n^3+\frac{1}{4}n^2$なので
$$
\begin{align*}
\varphi_{3}(n)=\frac{n^3\varphi(n)}{4}+(-1)^{\omega(n)}\frac{1}{6}\mu({\rm rad}(n)){\rm rad}(n)\varphi(n)
\end{align*}
$$
宮田先生は同時に$\varphi_{m}(n)$のsummatory関数$$
\begin{align*}
H_{m}(n)=\sum_{k=1}^{n}\varphi_{m}(k)
\end{align*}
$$
に関して，次の恒等式を得ています．
$$
\begin{align*}
\sum_{k=1}^{n} H_{m}\left( \Big\lfloor \dfrac{n}{k} \Big\rfloor \right)=\sum_{k=1}^{n}P_{m}(k)
\end{align*}
$$
この恒等式により，任意の$n$について，$H_{m}(n)$を$O(n^{\frac{2}{3}}(m+1))$回の算術演算で求めるアルゴリズムが構成可能であることも示しています．
