約数のオイラーの関数の和

$(a,\:x)=d$ を満たす $x$ を求めます

 $15$ 以下の数について、それぞれ $15$ との最大公約数を求めて下の表に並べてみます(左の列です)。

$(15,\:x)$   $(5,\:x/3)$
  $(15,\:1)=1$
  $(15,\:2)=1$
  $(15,\:3)=3$   $(5,\:1)=1$
  $(15,\:4)=1$
  $(15,\:5)=5$
  $(15,\:6)=3$   $(5,\:2)=1$
  $(15,\:7)=1$
  $(15,\:8)=1$
  $(15,\:9)=3$   $(5,\:3)=1$
  $(15,\:10)=5$
  $(15,\:11)=1$
  $(15,\:12)=3$   $(5,\:4)=1$
  $(15,\:13)=1$
  $(15,\:15)=15$

 この中から $15$ と最大公約数が $3$ になる数、すなわち
 
\[(15,\:x)=3\]
を満たす $x$ は
 
\[x=3,\;6,\;9,\;12\]
の計 4 個あります。またこれは右列を見ると
 
\[\left(\frac{15}{3},\:\frac{x}{3}\right)=\left(5,\:\frac{x}{3}\right)=1\]
 すなわち $(5,\:t)=1$ をみたす $t$ の数と一致しています。
 その数は オイラーの関数 を用いて
 
\[\varphi (5)=4\]
で計算することができます。一般に次の定理が成り立ちます。

[定理 D7] $d\:|\:a$ であるとき
\[(a,\:x)=d\;(1\leq x\leq a)\]を満たす $x$ は $\varphi (a/d)$ 個存在します。

[定理 D7 の証明] $x=kd$ とおくと
 
\[(a,\:kd)=d\quad (1\leq kd\leq a)\]
となるので、
 
\[\left(\frac{a}{d},\:k\right)=1\quad (1\leq kd\leq a)\]
 このような $k$ は $\varphi (a/d)$ 個存在するので、$(a,\:x)=d$ を満たす $x$ も $\varphi (a/d)$ 個存在します。(証明終)
 

約数のオイラーの関数の和

 $15$ の約数を並べると
 
\[\{\;1,\;3,\;5,\;15\:\}\]
となります。先ほどの表から $15$ との最大公約数がそれぞれの約数になるように $x$ を分類すると(定理 D7 で計算することもできます)、
 
\[\begin{align*}(15,\:x)&=1\qquad \varphi (15)=8\\[6pt]
(15,\:x)&=3\qquad \varphi (5)=4\\[6pt]
(15,\:x)&=5\qquad \varphi (3)=2\\[6pt]
(15,\:x)&=15\qquad \varphi (1)=1\end{align*}\]
となります。これらは $15$ 以下の数について全て数え上げているのですから、
 
\[\varphi (1)+\varphi (3)+\varphi (5)+\varphi (15)=15\]
が成り立ちます。すなわち $15$ の約数のオイラーの関数の和が $15$ 自身に一致します。このことはもちろん一般にも成り立ちます。

[定理 D8] 正整数 $n$ のすべての約数について、オイラーの関数の和をとると $n$ に等しくなります。すなわち
\[\sum_{d|n}\varphi (d)=n\]

 $n=12$ でも試してみます。$12$ の約数は
 
\[\{\;1,\;2,\;3,\;4,\;6,\;12\:\}\]
なので、
 
\[\begin{align*}\sum_{d|12}\varphi (d)&=\varphi (1)+\varphi (2)+\varphi (3)+\varphi (4)+\varphi (6)+\varphi (12)\\[6pt]&=1+1+2+2+3+2+1=12\end{align*}\]
となって確かに $12$ に一致しています。

 ≫ メビウス関数 ≫ 初等整数論入門講座

スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。