初等整数論講義/第1章/Eulerの函数φ(n)のソースを表示

<!-- 削除についての議論が終了するまで、下記部分は除去しないでください。 -->
<dl style="font-size:smaller;border:solid #999 1px;width:75%;background:#eff;padding:1ex 1em;margin:0 auto 1em;">
<dt style="text-align:center;font-size:130%">'''削除提案中'''</dt>
<dd style="float:left;width:50px;margin:0;padding-bottom:10px">[[Image:Icono_aviso_borrar.png|50px|]]</dd>
<dd style="margin:0 0 0 60px"><p>現在、この項目の一部の版または全体について、[[Wikisource:削除の方針|削除の手続き]]に従って、削除が提案されています。</p>
<p>削除についての議論は[[Wikisource:削除依頼#{{#if:高木貞治氏の著書|高木貞治氏の著書|{{FULLPAGENAME}} - ノート}}|削除依頼の該当のセクション]]で行われています（[[{{TALKPAGENAME}}|このページのノート]]も参照してください）。削除の議論中はこのお知らせを'''除去しないで'''ください。</p>
</dd>
<dd style="margin:0;clear:left">'''この項目の執筆者の方々へ'''： まだ削除は行われていません。削除に対する議論に参加し、[[Wikisource:削除の方針|削除の方針]]に該当するかをどうか検討してください。</dd>
</dl>__NOINDEX__ [[Category:削除依頼中の記事]]
<!-- 削除についての議論が終了するまで、上記部分は除去しないでください。 -->
{{Copyrights}}
<strong>1.</strong>

自然數 <math>1, 2, ......, n</math> ノ中ニ <math>n</math> ト互ニ素ナル數 <math>x</math> ガイクツアルカ． ソノ數ヲ <math>\varphi(n)</math> デ表ハスノデアル．

例ヘバ
{{初等整数論講義/equation
|<math>
 \begin{align}
 \varphi(1)=1&, (x=1)\\
 \varphi(2)=1&, (x=1)\\
 \varphi(3)=2&, (x=1, 2)\\
 \varphi(4)=2&, (x=1, 3)\\
 \varphi(5)=4&, (x=1, 2, 3, 4)\\
 \varphi(6)=2&, (x=1, 5)\\
.......&...........
\end{align}
</math>
}}

コノヤウニ變數ガ整數値ヲ取ルトキニノミ意味ヲ有スル函數ヲ整數論的函數トイフ．特ニ上記ノ<math>\varphi(n)</math>ヲ'''[[Wikipedia:ja:%E3%83%AC%E3%82%AA%E3%83%B3%E3%83%8F%E3%83%AB%E3%83%88%E3%83%BB%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC|<ins>オイラア</ins>]][[Wikipedia:ja:%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E3%81%AE%CF%86%E9%96%A2%E6%95%B0|ノ函數]]'''トイフ．

サテ<math>p</math>ガ素數ナラバ，

{{初等整数論講義/equation|
<math>\varphi(p)=p-1</math>
|label = eq:8.1
|tag= (1)}}

ナルコト明デアル．又
{{初等整数論講義/equation|
<math>\varphi(p^e)=p^e-p^{e-1}</math>
|label = eq:8.2
|tag= (2)}}

デアル．ナゼナラバ，<math>1</math>カラ<math>p^e</math>マデノ整數ノ中デ，<math>p^e</math>ト互ニ素デナイモノハ，即チ<math>p</math>デ割リ切レルモノデ，ソレハ
{{初等整数論講義/equation|
<math>1\cdot p,\  2 \cdot p,\  ......, p^{e-1} \cdot p</math>
}}
ノ<math>p^{e-1}</math>個ダケデアルカラ．

一般ニ<math>\varphi(n)</math>ハ次ノヤウニシテ計算スルコトガデキル．

{{初等整数論講義/theorem|1.18}} <math>n</math> ヲ素數冪ニ分解シテ
{{初等整数論講義/equation|
<math>n=p^\alpha q^\beta r^\gamma ......</math>
}}
トスレバ，
{{初等整数論講義/equation|
<math>\varphi(n)=n(1- \frac{1}{p})(1 - \frac{1}{q})(1 - \frac{1}{r}) ... ...</math>
}}
{{初等整数論講義/theorem-end}}

コノ定理ハ次ノ定理カラ導カレル．

{{初等整数論講義/theorem|1.19}} <math>(a, b)=1</math>ナラバ，<math>\varphi(ab) = \varphi(a)\varphi(b)</math>．
{{初等整数論講義/theorem-end}}

コノ定理ガ證明サレタトスレバ，<math>a,b,c,... ...</math> ガニツヅツ互ニ素ナルトキ
{{初等整数論講義/equation|
<math>
 \begin{align}
   \varphi(abc...) &= \varphi(a)\phi(bc...)=\varphi(a)\varphi(b)\varphi(c...)=... \\
                   &= \varphi(a)\varphi(b)\varphi(c)...
 \end{align}
</math>
}}
由テ
{{初等整数論講義/equation
|<math>
 \begin{align}
   \varphi(n) &= \varphi(p^\alpha)\varphi(q^\beta)\varphi(r^\gamma)...... \\
              &= (p^\alpha - p^{\alpha - 1})(q^\beta - q^{\beta - 1})(r^\gamma - r^{\gamma - 1})......  ((2)kara) \\
              &= p^\alpha q^\beta r^\gamma ......(1- \frac{1}{p})(1 - \frac{1}{q})(1 - \frac{1}{r})...... \\
              &= n(1- \frac{1}{p})(1 - \frac{1}{q})(1 - \frac{1}{r})......
 \end{align}
</math>
}}

卽チ[[初等整数論講義/第1章/Eulerの函数φ(n)#th:1.18|定理1.18]]デアル．

<strong>2.</strong>
サテ[[初等整数論講義/第1章/Eulerの函数φ(n)#th:1.19|定理1.19]]ノ證明デアルガ，ソレヲ上掲ノ <math>\varphi (n)</math> ノ定義カラ壓出シナイデ，アラカジメ合同ノ觀念ヲ應用シテ
<math>\varphi (n)</math> ノ意味ヲ練テオケバ，平易ニ解決サレル．

<math>\varphi (n)</math> ノ定義ノ基礎ニナツタ問題ハ，<math>1</math> カラ <math>n</math> マデノ自然數ノ中ニ，
<math>n</math> ト互ニ素ナルモノガイクツアルカ，トイフノデアツタガ，サウイフ見方ハアマリニ狹イ．
或ル數ト <math>n</math> トガ互ニ素デアル又ハ素デナイトイフコトハ，ソノ數ヲ <math>n</math> ノ倍數ダケ增減シテモ變ハラナイ．
一般ニ
{{初等整数論講義/equation|<math>(r + nt, n) = (r, n)</math><ref>
officious: <math>r \equiv r + nt\  (mod.\  n)</math> すなわち，<math>r</math> を <math>n</math> で除しても，<math>r + nt</math> を <math>n</math> で除しても剰余は変わらない．以降，[[初等整数論講義/第1章/最大公約数，最小公倍数#prop:1|ユークリッドの互除法]]を適用する．
</ref>}}
デアルカラ，<math>n</math> ヲ法トスル一類ニ屬スル數ハ盡ク <math>n</math> ト互ニ素ナルカ，或ハ <math>n</math> ト組合ハセタトキ，
一定ノ最大公約數ヲ有スル．

今ソノ最大公約數ヲ <math>d</math> トシテ，<math>(r, n) = d, n = n'd, r = r'd</math> トオケバ，<math>r</math> ニ由テ代表セラルル，
法 <math>n</math> ニ關スル一類ノ數ナル <math>nt + r = d(n't + r')</math> ハ， 卽チ法 <math>n'</math> ニ關シテ，
<math>(r', n') = 1</math> ナル <math>r'</math> ニ由テ代表セラルル一類ノ各數ニ <math>d</math> ヲ乘ジテ得ラレルモノニ外ナラヌノデアル．

卽チ數ノ類ノ中デ法ト互ニ素ナル數ノミヲ含ム類ガ基本的デアル．

{{初等整数論講義/note}}
例ヘバ <math>4</math> ヲ法トスルトキノ數ノ四類ノ中デ，二類ハ奇数ノミヲ含ム．ソレハ <math>4h + 1</math> ノ形及ビ <math>4h - 1</math> ノ形ノモノデアル．
偶數ノミヲ含ム他ノ二類ノ中デ，<math>4h</math> ノ形ノモノハ偶數ノ <math>2</math> 倍ナル數ノ集合デ，又 <math>4h + 2</math> ノ形ノモノハ奇數ノ <math>2</math> 倍ナル數ノ集合デアル．
偶數ノ 2 倍，又ハ奇數ノ 2 倍トイウノハ，ツマリ <math>2</math> ヲ法トシテノ差別デアル．
{{初等整数論講義/note-end}}

由テ <math>n</math> ヲ法トスルトキノ數ノ類ノ中デ <math>n</math> ト互ニ素ナル數ノミヲ含ムモノヲ <math>n</math> ヲ法トシテノ'''旣約類'''トイフコトニスル．

然ラバ，<math>n</math> ヲ法トシテノ旣約類ノ數ガ卽チ <math>\varphi(n)</math> デアル．

<math>n</math> ヲ法トシテノ各類ヲ代表スル <math>n</math> 個ノ整數ノ一組ノ中カラ旣約類ヲ代表スル <math>\varphi(n)</math> 個ダケヲ取ツテ，
ソレヲ <math>n</math> ヲ法トシテノ'''旣約ノ代表ノ一組'''（又ハ旣約剩餘系）トイフコトニスル．


{{初等整数論講義/note}}
旣約剩餘系＝ reduced system of residues, 直譯スレバ，縮小サレタル剩餘系デアル．縮小トハ旣約ナラザルモノヲ除外スルコトヲ意味スル．
{{初等整数論講義/note-end}}

サテ <math>\varphi(n)</math> ガ <math>n</math> ヲ法トシテノ旣約類ノ數ヲ示スモノデアルトイフ立場カラ，[[初等整数論講義/第1章/Eulerの函数φ(n)#th:1.19|定理1.19]]ヲ考察シヨウ．


假定ニ由テ <math>(a, b)=1</math> デアルカラ，任意ノ整數 <math>k</math> ヲ
{{初等整数論講義/equation|<math>ay + bx = k</math>}}
ノ形ニ表スコトガデキル（[[初等整数論講義/第1章/一次の不定方程式#th:1.7|定理1.7]]）

今法 <math>ab</math> ニ關シテ考察スレバ，<math>x</math> ヲ <math>a</math> ノ倍數ダケ增減シテモ又ハ <math>y</math> ヲ <math>b</math> ノ倍數ダケ增減シテモ，
<math>ay + bx</math> ハ <math>ab</math> ノ倍數ダケ增減スルノデアルカラ，<math>ab</math> ヲ法トシテノ一類ニ屬スル．

由テ <math>ay + bx</math> ナル式ニ於テ，<math>x</math> ニハ <math>a</math> ヲ法トシテノ各類代表ノ一組ナル <math>a</math> 個ノ値ヲ與ヘ，
又 <math>y</math> ニハ <math>b</math> ヲ法トシテノ代表ノ一組ナル <math>b</math> 個ノ値ヲ與ヘルトキニ，コノ式 <math>ay + bx</math> カラ出ル
<math>ab</math> 個ノ値ハ卽チ <math>ab</math> ヲ法トシテノ各類ノ代表ノ一組デナクテハナラナイ．<ref>

officious:今 <math>ay + bx = ay' + bx', x \neq x'</math> と仮定する．<math> a(y - y') = b(x' - x)</math> にて <math>x \neq x'</math> ならば <math>a, b</math> は互いに素であるから，
<math>(x' - x)</math> は <math>a</math> の倍数．ところが <math>x, x'</math> とも <math>a</math> を法とした剰余系だからそれらの差は <math>a</math>未満であり，これは矛盾する．すなわち，<math>x = x'</math>
同様にして <math>y=y'</math>．すなわち <math>x, y</math> が相異なれば結果としての <math>ay + bx</math> も重複することなくすべて異なる値である．

あるいは，<math>ax+by=\alpha</math> は <math>ax\equiv\alpha(mod.\ b)</math> のことだから，これは[[初等整数論講義/第1章/一次合同式#th:1.13|定理1.13]]により，直ちに，それぞれの <math>\alpha</math> に対して <math>ab</math> を法として <math>x</math> がひとつ定まる（ただし <math>a, b</math> は互いに素）ことがわかる．<math>y</math> についても同様である．これはすぐに後述されている．  
</ref>

上記ノヤウニシテ <math>ay + bx</math> カラ得ラレル <math>ab</math> 個ノ値ノ中カラ，法 <math>ab</math> ヲ互ニ素デナイモノヲ取リ除ケバ，
<math>ab</math> ヲ法トシテノ旣約代表ノ一組ヲ得ルノデアルガ，<math>x</math> ト <math>a</math> トガ公約數ヲ有スルナラバ，
ソノ公約數ハ <math>ay + bx</math> ノ約數デアリ，マタ <math>y</math> ト　<math>b</math> トノ公約數モ同様デアルカラ，
<math>ay + bx</math> ニ於テ <math>x</math> ガ <math>a</math> ト互ニ素デナイモノ，又ハ <math>y</math> ガ <math>b</math> ト素デナイモノハ，
取リ除カネバナラナイ．
然ルニ <math>(x, a) = 1, (y, b) = 1</math> トスレバ <math>(ay + bx, a) = (bx, a) = 1</math><ref>
officious: <math>(r + nt, n) = (r, n)</math>より <math>(ay + bx, a) = (bx, a)</math> がいえ，その後 <math>(x, a) = 1</math> かつ <math>b, a</math> が素より <math>(bx, a) = 1</math>，(ただし<math>b < a\ </math>)．
</ref> 
，又 <math>(ay + bx, b) = (ay, b) = 1</math> デアルカラ，<math>(ay + bx, ab) = 1</math>．

故ニ <math>ay + bx</math> ニ於テ，<math>x</math> ニハ <math>a</math> ヲ法トシテノ旣約代表ノ一組，ソノ數 <math>\varphi(a)</math>，
又 <math>y</math> ニハ <math>b</math> ヲ法トシテ旣約代表ノ一組，ソノ數 <math>\varphi(b)</math> ヲ與ヘルトキニ，
<math>ay + bx</math> ガトルトコロノ合セテ <math>\varphi(a)\varphi(b)</math>個
ノ値ハ，<math>ab</math>ヲ法トシテノ旣約代表ノ一組デアル．故ニ
{{初等整数論講義/equation|<math>\varphi(ab)=\varphi(a)\varphi(b)</math>}}
卽チ[[初等整数論講義/第1章/Eulerの函数φ(n)#th:1.19|定理1.19]]ガ證明サレタノデアル．


[[初等整数論講義/第1章/Eulerの函数φ(n)#th:1.19|定理1.19]]ノ上記證明ハ第一原理カラ出發シタカラ，長クナツタノデアルガ，
若シモ[[初等整数論講義/第1章/一次合同式#th:1.14|定理 1.14]]ヲ用ヰルナラバ甚ダ簡單デアル．

今 <math>\alpha_1, \alpha_2,\ldots\ldots, \alpha_m [m = \varphi(a)]</math> 及ビ <math>\beta_1, \beta_2,\ldots\ldots, \beta_n [n = \varphi(b)]</math>
ヲソレゾレ <math>a</math> 及ビ <math>b</math> ヲ法トスル旣約代表ノ一組トスレバ，<math>\alpha, \beta</math> ノ <math> mn = \varphi(a)\varphi(b)</math>
個ノ組合セノ各々ニ對シテ <math>\gamma \equiv \alpha\  (mod.\  a), \gamma \equiv \beta\  (mod.\  b)</math> ナル <math>\gamma</math> ガ <math>ab</math>
ヲ法トシテ一ツヅツアル．ソノ <math>\gamma</math> ハ勿論 <math>ab</math> ト互ニ素デアル．
逆ニ <math>(\gamma, ab)=1</math>トスレバ，<math>(\gamma, a)=1, (\gamma, b)=1</math> デアルカラ，
<math>\gamma \equiv \alpha(mod.\ a), \gamma \equiv \beta(mod.^\ b)</math>
ナル <math>\alpha, \beta</math> ガ一意的ニ確定スル．
卽チ <math>ab</math> ヲ法トシテノ旣約代表ノ一組ノ各數 <math>\gamma</math> ト <math>\alpha, \beta</math>
ノ各組トノ間ニ一對一ノ對應ガ成立ツ．從ッテ <math>\varphi(ab)=\varphi(a)\varphi(b)</math>.


{{初等整数論講義/example}}
<math>a=3, b=5, ab=15</math>

<math>\alpha=1, 2; \beta=1, 2, 3, 4.  \varphi(3)=2, \varphi(5)=4</math>

<math>\gamma = 1, 2, 4, 7, 8, 11, 13, 14. \varphi(15)=8</math>

{| class="wikitable" style="text-align:right"
|-
! <math>\alpha</math>
| <math>1</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>2</math>
|-
! <math>\beta</math>
| <math>1</math> || <math>2</math> || <math>3</math> || <math>4</math> || <math>1</math> || <math>2</math> || <math>3</math> || <math>4</math>
|-
! <math>\gamma</math>
| <math>1</math> || <math>7</math> || <math>13</math> || <math>4</math> || <math>11</math> || <math>2</math> || <math>8</math> || <math>14</math>
|}
{{初等整数論講義/example-end}}

{{初等整数論講義/theorem|type=prop|1}}
<math>a,b,c, \ldots\ldots</math>
ハ二ツヅツ互ニ素デアルトシテ，<math>\mathit{\Phi}(x)</math> ハ實數 <math>x</math> ヲ超エナイ自然數ノ中デ <math>a</math> デモ <math>b</math> デモ <math>c</math> デモ，<math>\ldots\ldots</math>
割リ切レナイモノノ數ヲ表ハストスレバ，
{{初等整数論講義/equation|<math>
\begin{align}
\mathit{\Phi}(x) = [x] &- \left[ \frac{x}{a} \right] 
                        - \left[\frac{x}{b}\right] 
                        - \left[\frac{x}{c}\right]
                        - \ldots\ldots \\
                       &+ \left[\frac{x}{ab}\right] 
                        + \left[\frac{x}{ab}\right] 
                        + \left[\frac{x}{bc}\right] 
                        + \ldots\ldots \\
                       &- \left[\frac{x}{abc}\right] - \ldots\ldots \\
\end{align}</math>}}
但 <math>[x]</math> ハ <math>x</math> ヲ超エナイ最大ノ整數ヲ表ハス（<ins>ガウス</ins>ノ記號)．
{{初等整数論講義/theorem-end}}
{{初等整数論講義/proof|type=prop}}
<math>a</math> ガ唯一ツ與ヘラレタトスレバ，<math>1, 2, \ldots\ldots, [x]</math> ナル自然數ノ中デ，
<math>a</math> デ割リ切レルモノハ <math>1\cdot a, \ 2\cdot a, \ \ldots\ldots, 
\left[\frac{x}{a}\right]\cdot a</math>
ダケデアルカラ，
{{初等整数論講義/equation|<math>
\mathit{\Phi}(x) = [x] - \left[\frac{x}{a}\right]
</math>．}}
由テ數學的歸納法ニ由テ證明ヲ完成スルコトガデキル．

<math>a, b, \ldots, k</math> ニ關スル上記 <math>\mathit{\Phi}(x)</math> ノ値ガ
正シイト假定スルトキ， 尙ホ一ツノ除數 <math>l</math> ガ追加サレタトスレバ，
<math>l</math> デ割リ切レル數 <math>yl (y \le \frac{x}{l}) </math>ヲ
控除セネバナラナイガ，ソノ中 <math>y</math> ガ <math>a, b, \ldots\ldots, k</math>
ノドレカデ割リ切レルモノハ旣ニ控除サレテヰルカラ，新ニ控除スベキモノハ
<math>\mathit{\Phi}(\frac{x}{l})</math> ダケデアル.<ref>

officious: 具体例で示す．<math>100</math> 以下の <math>2</math> と <math>3</math> にそれぞれ互いに素な <math>\mathit{\Phi}_{2, 3}(100)</math> 個の整数 <math>P</math> に対して、さらに <math>5</math> で割り切れる数を「新たに控除」するものとする．<math>P</math> に含まれない整数 <math>Q</math> は <math>2</math> または <math>3</math> で割り切れるため，<math>Q</math> に属する整数 <math>n</math> より作る <math>5n</math> も <math>2</math> や <math>3</math> のすくなくとも一方でそれぞれ互いに素ではない．一方 <math>P</math> に属する整数 <math>m</math> は <math>2</math> と <math>3</math> とそれぞれ互いに素であり、当然 <math>5</math> は <math>2, 3</math> と互いに素であるから、<math>5m</math> もまた <math>2, 3</math> とにそれぞれとも互いに素である．「新たに控除する」整数は、これら <math>2, 3</math> と互いに素な <math>5</math> の倍数である．そんな整数は <math>P</math> に属する整数の小さいものから拾い出して <math>5</math> をかければ作ることができる．すなわちその <math>100</math> までの個数は <math>\mathit{\Phi}_{2, 3}(\frac{100}{5})</math>．

</ref>
從テ殘リハ
<math>\mathit{\Phi}(x)-\mathit{\Phi}(\frac{x}{l})</math>，<ref>

officious: <math>a, b, c</math> で展開すると，<math>\mathit{\Phi}_{a, b, c}(n) = \mathit{\Phi}_{a, b}(n) - \mathit{\Phi}_{a, b}(\frac{n}{c}) = \mathit{\Phi}_{a}(n) - \mathit{\Phi}_{a}(\frac{n}{b}) - \{ \mathit{\Phi}_{a}(\frac{n}{c}) - \mathit{\Phi}_{a}(\frac{n}{bc})\}</math>, 後は <math>\mathit{\Phi}_{a}(x) = [x] - \left[\frac{x}{a}\right]</math> を使って展開すればよい．

</ref>
コレハ丁度 <math>a, b, \ldots\ldots, k, l</math> ニ關スル上記公式ノ
<math>\mathit{\Phi}(x)</math> ニナル．
{{初等整数論講義/proof-end}}
{{初等整数論講義/remark}}
特ニ <math>x=n</math> トシテ，<math>a, b, c, \ldots\ldots</math> ハ <math>n</math> ニ含マレル相異ナル素數トスレバ，
<math>\mathit{\Phi}(n)=\varphi(n)</math>
デアル．由テ上記ノ式カラ <math>\varphi(n)</math> ヲ得ル．
{{初等整数論講義/remark-end}}


<strong>3.</strong>
<math>n</math> ノ任意ノ約數ヲ <math>d</math> トスルトキ，
<math>1, 2, \ldots\ldots, n</math> ナル <math>n</math> 個ノ整數中ニ
<math>(x, n) = d</math> ナル <math>x</math> ハイクツアルカ．

<math>x = dx', n = dn'</math> ト置ケバ，<math>(x, n) = d</math> ハ
<math>(x', n') = 1</math> ト同一ニ歸スルカラ，<ref>

officious: <math>(x, n)=d  \Leftrightarrow (x', n')=1</math>を証明しておく．<math> \Rightarrow</math>：
<math>d'=(x', n')</math> とし，<math>x'=x''d', n'=n''d'</math> とすると，
<math>x = x'd = x''d'd, n = n'd = n''d'd</math>．よって，<math>d'd</math> は
<math>x</math> と <math>n</math> の公約数である．<math>d</math> が最大公約数であったので，
<math>d'd \le d</math>，したがって <math>d' \le 1</math>.当然 <math>d' \ge 1</math>．
ゆえに <math>d' = (x', n') = 1</math>．
<math>\Leftarrow</math>：<math>x = x'd, n = n'd, (x', n') = 1</math> のとき，
<math>e = (x, n)</math> とおくと，<math>d</math> は <math>x</math> と <math>n</math> の公約数なので，
[[初等整数論講義/第1章/最大公約数，最小公倍数#th:1.4|定理1.4]]より <math>e = e'd</math>と表せる．
<math>e</math> は <math>x</math> の約数なので，<math>e'</math> は <math>x'</math> の約数．
同様に <math>e</math> は <math>n</math> の約数なので，<math>e'</math> は <math>n'</math> の約数．
したがって，<math>e'</math> は <math>x', n'</math> の公約数．
しかし仮定により <math>(x', n') = 1</math> なので，<math>e' = 1</math>，すなわち <math>d = e</math>．

</ref>
コノ數ハ，<math>\varphi(n')</math> 卽チ <math>\varphi(\frac{n}{d})</math> デアル．

　由テ <math>x = 1, 2, \ldots\ldots, n</math> ナル <math>n</math> 個ノ數ヲソレニ對應スル <math>(x, n) = d</math> ニ從テ分類スレバ，
<math>d = 1</math> ニ對應スルモノガ <math>\varphi(n)</math>　個，<math>d = d_1 </math> ニ對應スルモノガ <math>\varphi(\frac{n}{d_1})</math> 個，
<math>d = d_2 </math> ニ對應スルモノガ <math>\varphi(\frac{n}{d_2})</math> 個，等，等デ，最後ニ <math>d = n</math> ニ對應スルモノガ
<math>\varphi(1)</math>  卽チ <math>1</math> 個デアル．コレラノ總計ガ卽チ <math>n</math> デナケレバナラヌカラ，<ref>

offisious: 前出 <math>n = dn'</math> より <math>d</math> は <math>n</math> の約数であることが必要．<math>x</math> は <math>1</math> から <math>n</math> まで動き <math>d</math> のいずれかに定まる，したがって <math>\varphi</math> の総計は <math>n</math> ．
</ref>
{{初等整数論講義/equation|<math>
\varphi(n)+\varphi(\frac{n}{d_1})+\varphi(\frac{n}{d_2})+\ldots\ldots+\varphi(1)=n
</math>}}

<math>n, \frac{n}{d_1}, \frac{n}{d_2}, \ldots\ldots, 1</math> ハ卽チ <math>n</math> ノスベテノ約數 <math>1, d_1, d_2, \ldots\ldots, n</math> ノ餘約數デアルカラ，全體トシテハヤハリ <math>n</math> ノスベテノ約數ニ外ナラズ，由テ次ノ定理ヲ得ル．


{{初等整数論講義/theorem|1.20}}
{{初等整数論講義/equation|<math>
\sum^{d|n} \varphi(d) = n.
</math>}}
和ハ <math>n</math> ノスベテノ約數 <math>d</math> ノ上ニ亘ル．ソレヲ <math>d|n</math> ナル記號デ示スノデアル．


{{初等整数論講義/example}}
<math>n = 15</math>


<math>
\begin{array}{c | cccccccc | c} d &&&&& x &&&& \varphi(\frac{n}{d})  \\
\hline
1  & 1 & 2 & 4 & 7 & 8 & 11 & 13 & 14 & 8 \\
3  & 3 & 6 & 9 & 12&   &    &    &    & 4 \\
5  & 5 & 10&   &   &   &    &    &    & 2 \\
15 &15 &   &   &   &   &    &    &    & 1 \\ \hline
   &   &   &   &   &   &    &    &    & 15 
\end{array}
</math>

<math>
\varphi(1) + \varphi(3) + \varphi(5) + \varphi(15) = 1 + 2 + 4 + 8 = 15.
</math>

{{初等整数論講義/example-end}}


<strong>4.</strong>
上記ノ性質ハ <math>\varphi(n)</math> ノ特徵デアル． 
卽チ <math>\varphi(n)</math> ノ外ニハ[[初等整数論講義/第1章/Eulerの函数φ(n)#th:1.20|定理1.20]]ニ示シタヤウナ性質ヲ有スル整數論的函数ハ存在シナイ．
換言スレバ，スベテノ <math>n</math> ニ關シテ <math>\sum^{d|n} \psi(d) = n</math> ナルトキハ，<math>\psi(n) = \varphi(n)</math> ト斷言スルコトヲ得ル．

ソレヲ證明スルニハ [[初等整数論講義/第1章/Eulerの函数φ(n)#th:1.20|定理1.20]] ノ等式カラ，<math>\varphi(n)</math> ノ公式ヲ算出スルコトガデキルコトヲ示セバ充分デアル．

サテコノ證明ヲスル前ニ，先ヅ問題ヲ次ノヤウニ擴張スル．

<math>F(n)</math> ヲ任意ノ整數論的函数トシテ
{{初等整数論講義/equation|<math>
\sum^{d|n}F(d) = G(n)
</math>}}
ト置ケバ，<math>G(n)</math> ハ又一ツノ整數論的函數デアル．サテ逆ニ <math>G(n)</math> ガ知ラサレテヰルトスレバ，ソレカラ <math>F(n)</math> ノ値ヲ求メルコトガデキル．

コノヤウナ計算ガ可能デアルコトハ次ノ例ニ由テ明デアル．

{{初等整数論講義/example}}
<math>n=15, d=1, 3, 5, 15</math>

{{初等整数論講義/equation|
<math>
\begin{align}

F(1) &       &       &        & =G(1) \\
F(1) & +F(3) &       &        & =G(3) \\
F(1) &       & +F(5) &        & =G(5) \\
F(1) & +F(3) & +F(5) & +F(15) & =G(15)
\end{align}
</math>}}

　コレラノ等式ニ順次 <math>1, -1, -1, 1</math> ヲ掛ケテ加ヘテ
{{初等整数論講義/equation|
<math>F(15)=G(1)-G(3)-G(5)+G(15)</math>
}}
ヲ得ル．

　コノ例デハ，<math>d</math> ノ數ガ四個デ，四個ノ未知数 <math>F(1), F(3), F(5), F(15)</math> ヲ含ム四個ノ聯立一次方程式カラ，<math>F(15)</math> ヲ求メ得タノデアル．
{{初等整数論講義/example-end}}


一般ノ場合ニ上記ノ問題ヲ解ク爲ニ，[[Wikipedia:ja:%E3%82%A2%E3%82%A6%E3%82%B0%E3%82%B9%E3%83%88%E3%83%BB%E3%83%95%E3%82%A7%E3%83%AB%E3%83%87%E3%82%A3%E3%83%8A%E3%83%B3%E3%83%88%E3%83%BB%E3%83%A1%E3%83%93%E3%82%A6%E3%82%B9|<ins>メイビウス</ins> Moebius]] [[Wikipedia::ja:%E3%83%A1%E3%83%93%E3%82%A6%E3%82%B9%E9%96%A2%E6%95%B0|ノ函數]] <math>\mu(n)</math> ヲ用ヰル．
<math>\mu(n)</math> ノ定義ハ次ノ通リ．

<math>n=1</math> ノトキ，<math>\mu(1)=1</math>

<math>n</math> ガ素數ノ平方デ割リ切レルトキ，<math>\mu(n)=0</math>

<math>n</math> ガ <math>k</math> 個ノ相異ナル素數ノ積ニ等シイトキ，<math>\mu(n)=(-1)^{k}</math>

例ヘバ，
{{初等整数論講義/note}}
{{初等整数論講義/equation|
<math>\mu(1)=1, \mu(2)=-1, \mu(3)=-1, \mu(4)=0, \mu(5)=-1, \mu(6)=1</math>}}<ref>
officious: <math>\mu(7)=-1, \mu(8)=0, \mu(9)=0, \mu(10)=1, \mu(11)=-1, \mu(12)=0</math>
</ref>
{{初等整数論講義/note-end}}

コノ定義カラ，直ニ次ニ揭ゲル <math>\mu(n)</math> ノ特性ガ出デ來ル．

{{初等整数論講義/theorem|1.21}}
<math>n>1</math> ナラバ <math>\sum^{d|n}\mu(d)=0</math>
{{初等整数論講義/theorem-end}}

{{初等整数論講義/proof|type=prop}}
<math>n>1</math> デアルカラ，<math>n</math> ヲ素數羃ニ分解シテ
{{初等整数論講義/equation|
<math>n=p_1^{e_1}p_2^{e_2}\ldots\ldots p_k^{e_k}</math>
}}
ト置ク．由テ
{{初等整数論講義/equation|
<math>\sum^{d|n}\mu(d)=\sum^{x}\mu(p_1^{x_1}p_2^{x_2} \ldots\ldots p_k^{x_k})</math>.
}}
第二ノ和ハ勿論 <math>0\leqq x_1\leqq e_1, 0\leqq x_2\leqq e_2, \ldots\ldots, 0\leqq x_k\leqq e_k</math>
ナル範圍内ノ <math>x_1, x_2, \ldots\ldots, x_k</math> ノスベテノ組合セノ上ニ亘ルノデアルガ，
コノ和ノ項ノ中デ，<math>0</math> ニ等シイモノ<ref>

officitous: <math>x_1, x_2, \ldots\ldots, x_k</math> のひとつでも <math>2</math> か
それ以上の項 <math>t</math> は平方で割り切れ <math>\mu(t)=0</math>．

</ref>ヲ省ケバ，
{{初等整数論講義/equation|
<math>
\begin{align}
\sum^{d|n}\mu(d) & =\mu(1) +\{\mu(p_1)+\mu(p_2)+\ldots\ldots+\mu(p_k))\} \\
                 &         +\{\mu(p_1 p_2)+\mu(p_1 p_3)+\ldots\ldots+\mu(p_{k-1} p_k)\} \\
                 &         +\ldots\ldots \\
                 &         +\mu(p_1 p_2 \ldots\ldots p_k) \\
                 & =1      -k + \binom{k}{2}  - \binom{k}{3}+ \ldots\ldots +(-1)^k \\
                 & = (1-1)^k  \\
                 & = 0        \\
\end{align}
</math>}}
<ref>
officious: [[Wikipedia:ja:%E4%BA%8C%E9%A0%85%E5%AE%9A%E7%90%86|二項定理]]{{Indent|
<math>(x+y)^n = \sum_{k=0}^n \binom{n}{k}x^k y^{n-k}</math>}}
に <math>x=-1, y=1</math>を代入．
</ref>
{{初等整数論講義/proof-end}}


　<math>\mu(n)</math> ヲ用ヰテ容易ニ上記 <math>F(n), G(n)</math> ニ關スル問題ヲ解クコトヲ得ル．
{{初等整数論講義/theorem|1.22}}
<math>
\sum^{d|n}F(d)=G(n)
</math> ナラバ <math>
F(n)=\sum^{d|n}\mu\left (\frac{n}{d}\right )G(d)
</math>．<ref>
offcious: [[Wikipedia:ja:%E3%83%A1%E3%83%93%E3%82%A6%E3%82%B9%E3%81%AE%E5%8F%8D%E8%BB%A2%E5%85%AC%E5%BC%8F|メビウスの反転公式]]
</ref>
{{初等整数論講義/theorem-end}}
{{初等整数論講義/proof|type=prop}}
右邊ノ和ニ於テ，<math>G(d)</math> ニ <math>\sum^{\delta|d}F(\delta)</math> ヲ代入スレバ，
{{初等整数論講義/equation|
<math>\sum^{d|n}\mu\left (\frac{n}{d}\right )G(d)=\sum^{d|n}\sum^{\delta|d}\mu\left (\frac{n}{d}\right )F(\delta)</math>
}}
コノ和ノ項ヲ <math>F(\delta)</math> デ括レバ，<math>\delta</math> ハ <math>d</math> ノ約數， 
從テ <math>\frac{n}{d}</math> ハ <math>\frac{n}{\delta}</math> ノ約數デアルカラ，
{{初等整数論講義/equation|
<math>= \sum^{\delta|n}\left [F(\delta) \sum^{\delta'|\frac{n}{\delta}}\mu(\delta') \right]
</math>．}}
[[初等整数論講義/第1章/Eulerの函数φ(n)#th:1.21|定理1.21]]ニ由テ，括弧内ノ和ノ中デ，
<math>\frac{n}{\delta}>1</math> ナルモノハ <math>0</math> ニナツテ，唯 <math>F(n)\mu(1)</math> ダケガ殘ル．卽チ
{{初等整数論講義/equation|<math>
\sum^{d|n}\mu\left (\frac{n}{d}\right )G(d)=F(n)
</math>}}
{{初等整数論講義/proof-end}}
特ニ，<math>F(n)=\varphi(n)</math> ノトキハ [[初等整数論講義/第1章/Eulerの函数φ(n)#th:1.20|定理1.20]] ニ由テ，
<math>G(n)=n</math>．
故ニ
{{初等整数論講義/equation|<math>
\varphi(n)=\sum^{d|n}\mu\left (\frac{n}{d}\right )d,
</math>}}
又ハ文字ヲ變ヘテ，
{{初等整数論講義/equation|<math>
\varphi(n)=\sum^{d|n}\mu(d)\frac{n}{d}
</math>}}.
<math>n = p^{\alpha}q^{\beta}r^{\gamma}\ldots\ldots</math> トスレバ，
<math>\mu(d)=0</math> ナルモノヲ省イテ，
{{初等整数論講義/equation|<math>
 \begin{align}
   \varphi(n)  & = \mu(1)n+\mu(p)\frac{n}{p}+\mu(q)\frac{n}{q}+\ldots\ldots         \\
               & + \mu(pq)\frac{n}{pq}+\mu(pr)\frac{n}{pr}+\ldots\ldots             \\
               & + \ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots                 \\
               & + \mu(pqr\ldots\ldots)\frac{n}{pqr\ldots}                          \\
               & = n - \frac{n}{p} - \frac{n}{q} - \frac{n}{r} - \ldots\ldots + \frac{n}{pq} + \frac{n}{pr} + \ldots\ldots - \frac{n}{pqr} - \ldots\ldots \\
              & = n(1- \frac{1}{p})(1 - \frac{1}{q})(1 - \frac{1}{r})\ldots\ldots  
 \end{align}
</math>
}}



<references/>

----
{{PD-Japan}}
{{DEFAULTSORT:しよとうせいすうろんこうき1Eulerのかんすう}}
[[Category:初等整数論講義|1Eulerのかんすう]]
math>2, 3