第 $1$ 章 初 等 整 数 論
$\S\ 8.$ Euler の函数 $\varphi\left(n\right)$
$\boldsymbol{1.}$ 自然数 $1$，$2$，$\cdots\cdots$，$n$ の中に $n$ と互いに素なる数 $x$ がいくつあるか．その数を $\varphi\left(n\right)$ で表わすのである．例えば\[\begin{alignat*}{3}&\varphi\left(\ 1\ \right)&&=1,&\hspace{1cm}&\left(x=1\right)\\&\varphi\left(\ 2\ \right)&&=1,&\hspace{1cm}&\left(x=1\right)\\&\varphi\left(\ 3\ \right)&&=2,&\hspace{1cm}&\left(x=1,\ 2\right)\\&\varphi\left(\ 4\ \right)&&=2,&\hspace{1cm}&\left(x=1,\ 3\right)\\&\varphi\left(\ 5\ \right)&&=4,&\hspace{1cm}&\left(x=1,\ 2,\ 3,\ 4\right)\\&\varphi\left(\ 6\ \right)&&=2,&\hspace{1cm}&\left(x=1,\ 5\right)\end{alignat*}\]\[\lower{1em}{\small\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots}\] このように変数が整数値をとるときにのみ意味を有する函数を整数論的函数という．特に上記の $\varphi\left(n\right)$ をEuler の函数という．
さて $p$ が素数ならば，\[\varphi\left(p\right)=p-1\tag{$\ 1\ $}\]であることは明らかである．また\[\varphi\left(p^e\right)=p^e-p^{e-1}\tag{$\ 2\ $}\]である．なぜならば，$1$ から $p^e$ までの整数のうちで，$p^e$ と互いに素でないものは，すなわち $p$ で割り切れるもので，それは\[1\hspace{0.7mm}\cdotp p,\ 2\hspace{0.7mm}\cdotp p,\ \cdots\cdots,\ p^{e-1}\hspace{0.7mm}\cdotp p\]の $p^{e-1}$ 個だけであるから．
一般に $\varphi\left(n\right)$ は次のようにして計算することができる．
〔定理 $\boldsymbol{1.\ 18}$〕 $n$ を素数巾に分解して\[n=p^\alpha q^\beta r^\gamma\cdots\cdots\]とすれば，\[\varphi\left(n\right)=n\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\left(1-\frac{1}{r}\right)\cdots\cdots.\] この定理は次の定理から導かれる．
〔定理 $\boldsymbol{1.\ 19}$〕 $\left(a,\ b\right)=1$ ならば，$\varphi\left(ab\right)=\varphi\left(a\right)\varphi\left(b\right)$．
この定理が証明されたとすれば，$a$，$b$，$c$，$\cdots\cdots$ が二つずつ互いに素であるとき\begin{alignat*}{1}\varphi\left(abc\cdots\right)&=\varphi\left(a\right)\varphi\left(bc\cdots\right)=\varphi\left(a\right)\varphi\left(b\right)\varphi\left(c\cdots\right)=\cdots\\&=\varphi\left(a\right)\varphi\left(b\right)\varphi\left(c\right)\cdots\end{alignat*}よって\begin{alignat*}{1}\varphi\left(n\right)&=\varphi\left(p^\alpha\right)\varphi\left(q^\beta\right)\varphi\left(r^\gamma\right)\cdots\cdots\\&=\left(p^\alpha-p^{\alpha-1}\right)\left(q^\beta-q^{\beta-1}\right)\left(r^\gamma-r^{\gamma-1}\right)\cdots\cdots\tag{$\left(\ 2\ \right)\ $から}\\&=p^\alpha q^\beta r^\gamma\cdots\cdots\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\left(1-\frac{1}{r}\right)\cdots\cdots\\&=n\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\left(1-\frac{1}{r}\right)\cdots\cdots\end{alignat*} すなわち定理 $1.\ 18$ である．
$\boldsymbol{2.}$ さて定理 $1.\ 19$ の証明であるが，それを上掲の $\varphi\left(n\right)$ の定義から圧出しないで，あらかじめ合同の観念を応用して $\varphi\left(n\right)$ の意味を練っておけば，平易に解決される．
$\varphi\left(n\right)$ の定義の基礎になった問題は，$1$ から $n$ までの自然数の中に，$n$ と互いに素なるものがいくつあるか，というのであったが，そういう見方はあまりに狭い．或る数と $n$ とが互いに素である，または素でないということは，その数を $n$ の倍数だけ増減しても変わらない．一般に\[\left(r+nt,\ n\right)=\left(r,\ n\right)\]であるから，$n$ を法とする一類に属する数はことごとく $n$ と互いに素であるか，あるいは $n$ と組み合わせたとき，一定の最大公約数を有する．
いまその最大公約数を $d$ として，$\left(r,\ n\right)=d$，$n=n^\prime d$，$r=r^\prime d$ とおけば，$r$ によって代表される，法 $n$ に関する一類の数である $nt+r=d\left(n^\prime t+r^\prime\right)$ は，すなわち法 $n^\prime$ に関して，$\left(r^\prime,\ n^\prime\right)=1$ である $r^\prime$ によって代表される一類の各数に $d$ を乗じて得られるものにほかならないのである．
すなわち，数の類の中で法と互いに素なる数のみを含む類が基本的である．
例えば $4$ を法とするときの数の四類の中で，二類は奇数のみを含む．それは $4h+1$ の形および $4h-1$ の形のものである．偶数のみを含む他の二類の中で，$4h$ の形のものは偶数の $2$ 倍である数の集合で，また $4h+2$ の形のものは奇数の $2$ 倍なる数の集合である．偶数の $2$ 倍，または奇数の $2$ 倍というのは，つまり $2$ を法としての差別である．
よって $n$ を法とするときの数の類の中で $n$ と互いに素である数のみを含むものを $n$ を法としての既約類ということにする．
しからば，$n$ を法としての既約類の数がすなわち $\varphi\left(n\right)$ である．
$n$ を法としての各類を代表する $n$ 個の整数の一組の中から既約類を代表する $\varphi\left(n\right)$ 個だけをとって，それを $n$ を法としての既約の代表の一組（または既約剰余系）ということにする．
既約剰余系 $=$ reduced system of residues，直訳すれば，縮小された剰余系である．縮小とは既約でないものを除外することを意味する．
さて $\varphi\left(n\right)$ が $n$ を法としての既約類の数を示すものであるという立場から，定理 $1.\ 19$ を考察しよう．
仮定によって $\left(a,\ b\right)=1$ であるから，任意の整数 $k$ を\[ay+bx=k\]の形に表わすことができる（定理 $1.\ 7$）．
いま法 $ab$ に関して考察すれば，$x$ を $a$ の倍数だけ増減しても，または $y$ を $b$ の倍数だけ増減しても，$ay+bx$ は $ab$ の倍数だけ増減するのであるから，$ab$ を法としての一類に属する．
よって $ay+bx$ なる式において，$x$ には $a$ を法としての各類代表の一組である $a$ 個の値を与え，また $y$ には $b$ を法としての代表の一組である $b$ 個の値を与えるときに，この式 $ay+bx$ から出る $ab$ 個の値はすなわち $ab$ を法としての各類の代表の一組でなくてはならない．
上記のようにして $ay+bx$ から得られる $ab$ 個の値の中から，法 $ab$ と互いに素でないものをとり除けば，$ab$ を法としての既約代表の一組を得るのであるが，$x$ と $a$ とが公約数を有するならば，その公約数は $ay+bx$ の約数であり，また $y$ と $b$ との公約数も同様であるから，$ay+bx$ において $x$ が $a$ と互いに素でないもの，または $y$ が $b$ と互いに素でないものは，取り除かなくてはならない．しかるに $\left(x,\ a\right)=1$，$\left(y,\ b\right)=1$ とすれば $\left(ay+bx,\ a\right)=\left(bx,\ a\right)=1$，また $\left(ay+bx,\ b\right)=1$ であるから，$\left(ay+bx,\ ab\right)=1$．
故に $ay+bx$ において，$x$ には $a$ を法としての既約代表の一組の値，その数$\varphi\left(a\right)$，また $y$ には $b$ を法としての既約代表の一組の値，その数 $\varphi\left(b\right)$ を与えるときに，$ay+bx$ がとるところの合わせて $\varphi\left(a\right)\varphi\left(b\right)$ 個の値は，$ab$ を法としての既約代表の一組である．故に\[\varphi\left(ab\right)=\varphi\left(a\right)\varphi\left(b\right).\] すなわち定理 $1.\ 19$ が証明されたのである．
定理 $1.\ 19$ の上記証明は，第一原理から出発したから，長くなったのであるが，もしも定理 $1.\ 14$ を用いるならばはなはだ簡単である．
いま $\alpha_1$，$\alpha_2$，$\cdots\cdots$，$\alpha_m$［$\raise{0.05em}{m=\varphi\left(a\right)}$］および $\beta_1$，$\beta_2$，$\cdots\cdots$，$\beta_n$［$\raise{0.05em}{n=\varphi\left(b\right)}$］をそれぞれ $a$ および $b$ を法とする既約代表の一組とすれば，$\alpha$，$\beta$ の $mn=\varphi\left(a\right)\hspace{0.7mm}\cdotp\varphi\left(b\right)$ 個の組合せのおのおのに対して $\gamma\equiv\alpha\hphantom{m}\left(\text{mod}.\ a\right)$，$\gamma\equiv\beta\hphantom{m}\left(\text{mod}.\ b\right)$ である $\gamma$ が $ab$ を法として一つずつある．その $\gamma$ はもちろん $ab$ と互いに素である．逆に $\left(\gamma,\ ab\right)=1$ とすれば，$\left(\gamma,\ a\right)=1$，$\left(\gamma,\ b\right)=1$ であるから，$\gamma\equiv\alpha\hphantom{m}\left(\text{mod}.\ a\right)$，$\gamma\equiv\beta\hphantom{m}\left(\text{mod}.\ b\right)$ である $\alpha$，$\beta$ が一意的に確定する．すなわち $ab$ を法としての既約代表の一組の各数 $\gamma$ と $\alpha$，$\beta$ の各組との間に一対一の対応が成り立つ．したがって $\varphi\left(ab\right)=\varphi\left(a\right)\varphi\left(b\right)$．
| 〔例〕 | $\begin{alignat*}{2}&a=3,\ \ b=5,\ \ ab=15.&&\\&\alpha=1,\ 2;\ \ \beta=1,\ 2,\ 3,\ 4.&\hspace{1cm}&\varphi\left(3\right)=2,\ \ \varphi\left(5\right)=4.\\&\gamma=1,\ 2,\ 4,\ 7,\ 8,\ 11,\ 13,\ 14.&\hspace{1cm}&\varphi\left(15\right)=8.\end{alignat*}$
|
〔解〕 $a$ がただ一つ与えられたとすれば，$1$，$2$，$\cdots\cdots$，$\left[x\right]$ である自然数の中で，$a$ で割り切れるものは $1\hspace{0.7mm}\cdotp a$，$2\hspace{0.7mm}\cdotp a$，$\cdots\cdots$，$\left[x/a\right]\hspace{0.7mm}\cdotp a$ だけであるから，\[\varPhi\left(x\right)=\left[x\right]-\left[\frac{x}{a}\right].\] よって数学的帰納法によって証明を完成することができる．
$a$，$b$，$\cdots\cdots$，$k$ に関する上記 $\varPhi\left(x\right)$ の値が正しいと仮定するとき，なお一つの除数 $l$ が追加されたとすれば，$l$ で割り切れる数 $yl$（$y\leqq x/l$）を控除しなくてはならないが，そのうち $y$ が $a$，$b$，$\cdots\cdots$，$k$ のどれかで割り切れるものはすでに控除されているから，新に控除すべきものは $\varPhi\left(x/l\right)$ だけある．したがって残りは $\varPhi\left(x\right)-\varPhi\left(x/l\right)$，これはちょうど $a$，$b$，$\cdots\cdots$，$k$，$l$ に関する上記公式の $\varPhi\left(x\right)$ になる．
〔注意〕 特に $x=n$ として，$a$，$b$，$c$，$\cdots\cdots$ は $n$ に含まれる相異なる素数とすれば，$\varPhi\left(n\right)=\varphi\left(n\right)$ である．よって上記の式から $\varphi\left(n\right)$ を得る．
$\boldsymbol{3.}$ $n$ の任意の約数を $d$ とするとき，$n$ 個の数 $1$，$2$，$\cdots\cdots$，$n$ の中に $\left(x,\ n\right)=d$ である $x$ はいくつあるか．$x=dx^\prime$，$n=dn^\prime$ と置けば，$\left(x,\ n\right)=d$ は $\left(x^\prime,\ n^\prime\right)=1$ と同一に帰するから，この数は$\varphi\left(n^\prime\right)$，すなわち $\varphi\left(n/d\right)$ である．
よって $n$ 個の数 $x=1$，$2$，$\cdots\cdots$，$n$ をそれに対応する $\left(x,\ n\right)=d$ にしたがって分類すれば，$d=1$ に対応するものが $\varphi\left(n\right)$ 個，$d=d_1$ に対応するものが $\varphi\left(n/d_1\right)$ 個，$d=d_2$ に対応するものが $\varphi\left(n/d_2\right)$ 個，等等で，最後に $d=n$ に対応するものが $\varphi\left(1\right)$，すなわち $1$ 個である．これらの総計がすなわち $n$ でなければならないから，\[\varphi\left(n\right)+\varphi\left(\frac{n}{d_1}\right)+\varphi\left(\frac{n}{d_2}\right)+\cdots\cdots+\varphi\left(1\right)=n.\] $n$，$n/d_1$，$n/d_2$，$\cdots\cdots$，$1$ はすなわち $n$ のすべての約数 $1$，$d_1$，$d_2$，$\cdots\cdots$，$n$ の余約数であるから，全体としては，やはり $n$ のすべての約数にほかならない．よって次の定理を得る．
〔定理 $\boldsymbol{1.\ 20}$〕 $\displaystyle\overset{d|n}{\textstyle\sum}\varphi\left(d\right)=n$．
和は $n$ のすべての約数 $d$ の上にわたる．それを $d|n$ なる記号で示すのである．
〔例〕 $n=15$．
| $\ \ d\ \ $ | $x$ | $\varphi\left(\dfrac{n}{d}\right)$ |
| $\hphantom{11}1\hphantom{1}$ | $1$，$2$，$4$，$7$，$8$，$11$，$13$，$14$， | $\hphantom{11}8$ |
| $\hphantom{11}3\hphantom{1}$ | $3$，$6$，$9$，$12$． | $\hphantom{11}4$ |
| $\hphantom{11}5\hphantom{1}$ | $5$，$10$ | $\hphantom{11}2$ |
| $\hphantom{1}15\hphantom{1}$ | $15.$ | $\hphantom{11}1$ |
| 計 $\rule{0em}{1em}15$ |
$\varphi\left(1\right)+\varphi\left(3\right)+\varphi\left(5\right)+\varphi\left(15\right)=1+2+4+8=15.$
$\boldsymbol{4.}$ 上記の性質は $\varphi\left(n\right)$ の特徴である．すなわち $\varphi\left(n\right)$ のほかには定理 $1.\ 20$ に示したような性質を有する整数論的函数は存在しない．換言すれば，すべての $n$ に関して $\displaystyle\overset{d|n}{\textstyle\sum}\psi\left(d\right)=n$ であるときは，$\psi\left(n\right)=\varphi\left(n\right)$ と断言することができる．
それを証明するには定理 $1.\ 20$ の等式から，$\varphi\left(n\right)$ の公式を算出することができることを示せば十分である．
さてこの証明をする前に，まず問題を次のように拡張する．
$F\left(n\right)$ を任意の整数論的函数として\[\overset{d|n}{\textstyle\sum}F\left(d\right)=G\left(n\right)\]と置けば，$G\left(n\right)$ はまた一つの整数論的函数である．さて逆に $G\left(n\right)$ が知られているとすれば，それから $F\left(n\right)$ の値を求めることができる．
このような計算が可能であることは，次の例によって明らかである．
〔例〕 $n=15$，$d=1$，$3$，$5$，$15$．\begin{alignat*}{4}&F\left(1\right)&&&&&&&&=G\left(1\right),\\&F\left(1\right)&&+F\left(3\right)&&&&&&=G\left(3\right),\\&F\left(1\right)&&&&+F\left(5\right)&&&&=G\left(5\right),\\&F\left(1\right)&&+F\left(3\right)&&+F\left(5\right)&&+F\left(15\right)&&=G\left(15\right)\end{alignat*} これらの等式に順次 $1$，$-1$，$-1$，$1$ を掛けて加えて\[F\left(15\right)=G\left(1\right)-G\left(3\right)-G\left(5\right)+G\left(15\right)\]を得る．
この例では，$d$ の数が $4$ 個で，$4$ 個の未知数 $F\left(1\right)$，$F\left(3\right)$，$F\left(5\right)$，$F\left(15\right)$ を含む $4$ 個の連立一次方程式から，$F\left(15\right)$ を求め得たのである．
一般の場合に上記の問題を解くために，Möbius の函数 $\mu\left(n\right)$ を用いる．$\mu\left(n\right)$ の定義は次の通り．
$n=1$ のとき，$\mu\left(1\right)=1$．
$n$ が素数の平方で割り切れるとき，$\mu\left(n\right)=0$．
$n$ が $k$ 個の相異なる素数の積に等しいとき，$\mu\left(n\right)=\left(-1\right){}^k$．
例えば，\[\mu\left(1\right)=1,\ \mu\left(2\right)=-1,\ \mu\left(3\right)=-1,\ \mu\left(4\right)=0,\ \mu\left(5\right)=-1,\ \mu\left(6\right)=1,\ \cdots\cdots\] この定義から，直に次に掲げる $\mu\left(n\right)$ の特性が出てくる．
〔定理 $\boldsymbol{1.\ 21}$〕 $n\gt1$ ならば，$\displaystyle\overset{d|n}{\textstyle\sum}\mu\left(d\right)=0$．
〔証〕 $n\gt1$ であるから，$n$ を素数巾に分解して\[n={p_1}^{e_1}{p_2}^{e_2}\cdots\cdots{p_k}^{e_k}\]と置く．よって\[\overset{d|n}{\textstyle\sum}\mu\left(d\right)=\overset{x}{\textstyle\sum}\mu\left({p_1}^{x_1}{p_2}^{x_2}\cdots\cdots{p_k}^{x_k}\right).\]第二の和はもちろん $0\leqq x_1\leqq e_1$，$0\leqq x_2\leqq e_2$，$\cdots\cdots$，$0\leqq x_k\leqq e_k$ なる範囲内の $x_1$，$x_2$，$\cdots\cdots$，$x_k$ のすべての組合せの上にわたるのであるが，この和の項の中で，$0$ に等しいものを省けば，\begin{alignat*}{1}\overset{d|n}{\textstyle\sum}\mu\left(d\right)=\mu\left(1\right)&+\left\{\mu\left(p_1\right)+\mu\left(p_2\right)+\cdots\cdots+\mu\left(p_k\right)\right\}\\&+\left\{\mu\left(p_1p_2\right)+\mu\left(p_1p_3\right)+\cdots\cdots+\mu\left(p_{k-1}p_k\right)\right\}\\&+{\small\cdots\cdots\cdots\cdots\cdots\cdots}\\&+\mu\left(p_1p_2\cdots\cdots p_k\right)\\&=1-k+\binom{k}{2}-\binom{k}{3}+\cdots\cdots+\left(-1\right){}^k\\&=\left(1-1\right){}^k=0.\end{alignat*} $\mu\left(n\right)$ を用いて容易に上記 $F\left(n\right)$，$G\left(n\right)$ に関する問題を解くことができる．
〔定理 $\boldsymbol{1.\ 22}$〕 $\displaystyle\overset{d|n}{\textstyle\sum}F\left(d\right)=G\left(n\right)$ ならば，$\displaystyle F\left(n\right)=\overset{d|n}{\textstyle\sum}\mu\left(\dfrac{n}{d}\right)G\left(d\right)$．
〔証〕 右辺の和において，$G\left(d\right)$ に $\displaystyle\overset{\delta|d}{\textstyle\sum}F\left(\delta\right)$ を代入すれば，\[\overset{d|n}{\textstyle\sum}\mu\left(\frac{n}{d}\right)G\left(d\right)=\overset{d|n}{\textstyle\sum}\overset{\delta|d}{\textstyle\sum}\mu\left(\frac{n}{d}\right)F\left(\delta\right),\]この和の項を $F\left(\delta\right)$ でくくれば，$\delta$ は $d$ の約数，したがって $n/d$ は $n/\delta$ の約数であるから，\[=\overset{\delta|n}{\textstyle\sum}\Bigl[\lower{0.15em}{F\left(\delta\right)}\overset{\displaystyle\small\delta\prime|\frac{n}{\delta}}{\textstyle\sum}\lower{0.15em}{\mu\left(\delta^\prime\right)}\Bigr].\] 定理 $1.\ 21$ によって，括弧内の和の中で，$n/\delta\gt1$ なるものは $0$ になって，ただ $F\left(n\right)\mu\left(1\right)$ だけが残る．すなわち\[\overset{d|n}{\textstyle\sum}\mu\left(\frac{n}{d}\right)G\left(d\right)=F\left(n\right).\] 特に，$F\left(n\right)=\varphi\left(n\right)$ のときは定理 $1.\ 20$ によって，$G\left(n\right)=n$．故に\[\varphi\left(n\right)=\overset{d|n}{\textstyle\sum}\mu\left(\frac{n}{d}\right)d,\]または文字を変えて，\[\varphi\left(n\right)=\overset{d|n}{\textstyle\sum}\mu\left(d\right)\frac{n}{d}.\] $n=p^\alpha q^\beta r^\gamma\cdots\cdots$ とすれば，$\mu\left(d\right)=0$ なるものを省いて，\begin{alignat*}{1}\varphi\left(n\right)&=\mu\left(1\right)n+\mu\left(p\right)\frac{n}{p}+\mu\left(q\right)\frac{n}{q}+\cdots\cdots\\&\hphantom{=\mu(}+\mu\left(pq\right)\frac{n}{pq}+\mu\left(pr\right)\frac{n}{pr}+\cdots\cdots\\&\hphantom{=\mu(}+{\small\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots}\\&\hphantom{=\mu(}+\mu\left(pqr\cdots\cdots\right)\frac{n}{pqr\cdots}\end{alignat*}\begin{alignat*}{1}&=n-\frac{n}{p}-\frac{n}{q}-\frac{n}{r}-\cdots\cdots+\frac{n}{pq}+\frac{n}{pr}+\cdots\cdots-\frac{n}{pqr}-\cdots\cdots\\&=n\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\left(1-\frac{1}{r}\right)\cdots\cdots\end{alignat*}