初等整数論講義/第1章/Eulerの函数φ(n)

削除提案中

現在、この項目の一部の版または全体について、削除の手続きに従って、削除が提案されています。

削除についての議論は削除依頼の該当のセクションで行われています（このページのノートも参照してください）。削除の議論中はこのお知らせを除去しないでください。

この項目の執筆者の方々へ：まだ削除は行われていません。削除に対する議論に参加し、削除の方針に該当するかをどうか検討してください。

テンプレート:Copyrights 1.

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

例ヘバテンプレート:初等整数論講義/equation

コノヤウニ變數ガ整數値ヲ取ルトキニノミ意味ヲ有スル函數ヲ整數論的函數トイフ．特ニ上記ノ $φ (n)$ ヲオイラアノ函數トイフ．

サテ $p$ ガ素數ナラバ，

テンプレート:初等整数論講義/equation

ナルコト明デアル．又テンプレート:初等整数論講義/equation

デアル．ナゼナラバ， $1$ カラ $p^{e}$ マデノ整數ノ中デ， $p^{e}$ ト互ニ素デナイモノハ，即チ $p$ デ割リ切レルモノデ，ソレハテンプレート:初等整数論講義/equation ノ $p^{e - 1}$ 個ダケデアルカラ．

一般ニ $φ (n)$ ハ次ノヤウニシテ計算スルコトガデキル．

テンプレート:初等整数論講義/theorem $n$ ヲ素數冪ニ分解シテテンプレート:初等整数論講義/equation トスレバ，テンプレート:初等整数論講義/equation テンプレート:初等整数論講義/theorem-end

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

テンプレート:初等整数論講義/theorem $(a, b) = 1$ ナラバ， $φ (a b) = φ (a) φ (b)$ ．テンプレート:初等整数論講義/theorem-end

コノ定理ガ證明サレタトスレバ， $a, b, c, . . . . . .$ ガニツヅツ互ニ素ナルトキテンプレート:初等整数論講義/equation 由テテンプレート:初等整数論講義/equation

卽チ定理1.18デアル．

2. サテ定理1.19ノ證明デアルガ，ソレヲ上掲ノ $φ (n)$ ノ定義カラ壓出シナイデ，アラカジメ合同ノ觀念ヲ應用シテ $φ (n)$ ノ意味ヲ練テオケバ，平易ニ解決サレル．

$φ (n)$ ノ定義ノ基礎ニナツタ問題ハ， $1$ カラ $n$ マデノ自然數ノ中ニ， $n$ ト互ニ素ナルモノガイクツアルカ，トイフノデアツタガ，サウイフ見方ハアマリニ狹イ．或ル數ト $n$ トガ互ニ素デアル又ハ素デナイトイフコトハ，ソノ數ヲ $n$ ノ倍數ダケ增減シテモ變ハラナイ．一般ニテンプレート:初等整数論講義/equation デアルカラ， $n$ ヲ法トスル一類ニ屬スル數ハ盡ク $n$ ト互ニ素ナルカ，或ハ $n$ ト組合ハセタトキ，一定ノ最大公約數ヲ有スル．

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

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

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

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

然ラバ， $n$ ヲ法トシテノ旣約類ノ數ガ卽チ $φ (n)$ デアル．

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

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

サテ $φ (n)$ ガ $n$ ヲ法トシテノ旣約類ノ數ヲ示スモノデアルトイフ立場カラ，定理1.19ヲ考察シヨウ．

假定ニ由テ $(a, b) = 1$ デアルカラ，任意ノ整數 $k$ ヲテンプレート:初等整数論講義/equation ノ形ニ表スコトガデキル（定理1.7）

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

由テ $a y + b x$ ナル式ニ於テ， $x$ ニハ $a$ ヲ法トシテノ各類代表ノ一組ナル $a$ 個ノ値ヲ與ヘ，又 $y$ ニハ $b$ ヲ法トシテノ代表ノ一組ナル $b$ 個ノ値ヲ與ヘルトキニ，コノ式 $a y + b x$ カラ出ル $a b$ 個ノ値ハ卽チ $a b$ ヲ法トシテノ各類ノ代表ノ一組デナクテハナラナイ．^[1]

上記ノヤウニシテ $a y + b x$ カラ得ラレル $a b$ 個ノ値ノ中カラ，法 $a b$ ヲ互ニ素デナイモノヲ取リ除ケバ， $a b$ ヲ法トシテノ旣約代表ノ一組ヲ得ルノデアルガ， $x$ ト $a$ トガ公約數ヲ有スルナラバ，ソノ公約數ハ $a y + b x$ ノ約數デアリ，マタ $y$ ト　 $b$ トノ公約數モ同様デアルカラ， $a y + b x$ ニ於テ $x$ ガ $a$ ト互ニ素デナイモノ，又ハ $y$ ガ $b$ ト素デナイモノハ，取リ除カネバナラナイ．然ルニ $(x, a) = 1, (y, b) = 1$ トスレバ $(a y + b x, a) = (b x, a) = 1$ ^[2] ，又 $(a y + b x, b) = (a y, b) = 1$ デアルカラ， $(a y + b x, a b) = 1$ ．

故ニ $a y + b x$ ニ於テ， $x$ ニハ $a$ ヲ法トシテノ旣約代表ノ一組，ソノ數 $φ (a)$ ，又 $y$ ニハ $b$ ヲ法トシテ旣約代表ノ一組，ソノ數 $φ (b)$ ヲ與ヘルトキニ， $a y + b x$ ガトルトコロノ合セテ $φ (a) φ (b)$ 個ノ値ハ， $a b$ ヲ法トシテノ旣約代表ノ一組デアル．故ニテンプレート:初等整数論講義/equation 卽チ定理1.19ガ證明サレタノデアル．

定理1.19ノ上記證明ハ第一原理カラ出發シタカラ，長クナツタノデアルガ，若シモ定理 1.14ヲ用ヰルナラバ甚ダ簡單デアル．

今 $α_{1}, α_{2}, \dots \dots, α_{m} [m = φ (a)]$ 及ビ $β_{1}, β_{2}, \dots \dots, β_{n} [n = φ (b)]$ ヲソレゾレ $a$ 及ビ $b$ ヲ法トスル旣約代表ノ一組トスレバ， $α, β$ ノ $m n = φ (a) φ (b)$ 個ノ組合セノ各々ニ對シテ $γ \equiv α (m o d . a), γ \equiv β (m o d . b)$ ナル $γ$ ガ $a b$ ヲ法トシテ一ツヅツアル．ソノ $γ$ ハ勿論 $a b$ ト互ニ素デアル．逆ニ $(γ, a b) = 1$ トスレバ， $(γ, a) = 1, (γ, b) = 1$ デアルカラ， $γ \equiv α (m o d . a), γ \equiv β (m o d .^{} b)$ ナル $α, β$ ガ一意的ニ確定スル．卽チ $a b$ ヲ法トシテノ旣約代表ノ一組ノ各數 $γ$ ト $α, β$ ノ各組トノ間ニ一對一ノ對應ガ成立ツ．從ッテ $φ (a b) = φ (a) φ (b)$ .

テンプレート:初等整数論講義/example $a = 3, b = 5, a b = 15$

$α = 1, 2; β = 1, 2, 3, 4 . φ (3) = 2, φ (5) = 4$

$γ = 1, 2, 4, 7, 8, 11, 13, 14 . φ (15) = 8$

$α$	$1$	$1$	$1$	$1$	$2$	$2$	$2$	$2$
$β$	$1$	$2$	$3$	$4$	$1$	$2$	$3$	$4$
$γ$	$1$	$7$	$13$	$4$	$11$	$2$	$8$	$14$

テンプレート:初等整数論講義/example-end

テンプレート:初等整数論講義/theorem $a, b, c, \dots \dots$ ハ二ツヅツ互ニ素デアルトシテ， $Φ (x)$ ハ實數 $x$ ヲ超エナイ自然數ノ中デ $a$ デモ $b$ デモ $c$ デモ， $\dots \dots$ 割リ切レナイモノノ數ヲ表ハストスレバ，テンプレート:初等整数論講義/equation 但 $[x]$ ハ $x$ ヲ超エナイ最大ノ整數ヲ表ハス（ガウスノ記號)．テンプレート:初等整数論講義/theorem-end テンプレート:初等整数論講義/proof $a$ ガ唯一ツ與ヘラレタトスレバ， $1, 2, \dots \dots, [x]$ ナル自然數ノ中デ， $a$ デ割リ切レルモノハ $1 \cdot a, 2 \cdot a, \dots \dots, [\frac{x}{a}] \cdot a$ ダケデアルカラ，テンプレート:初等整数論講義/equation 由テ數學的歸納法ニ由テ證明ヲ完成スルコトガデキル．

$a, b, \dots, k$ ニ關スル上記 $Φ (x)$ ノ値ガ正シイト假定スルトキ，尙ホ一ツノ除數 $l$ ガ追加サレタトスレバ， $l$ デ割リ切レル數 $y l (y \leq \frac{x}{l})$ ヲ控除セネバナラナイガ，ソノ中 $y$ ガ $a, b, \dots \dots, k$ ノドレカデ割リ切レルモノハ旣ニ控除サレテヰルカラ，新ニ控除スベキモノハ $Φ (\frac{x}{l})$ ダケデアル.^[3] 從テ殘リハ $Φ (x) - Φ (\frac{x}{l})$ ，^[4] コレハ丁度 $a, b, \dots \dots, k, l$ ニ關スル上記公式ノ $Φ (x)$ ニナル．テンプレート:初等整数論講義/proof-end テンプレート:初等整数論講義/remark 特ニ $x = n$ トシテ， $a, b, c, \dots \dots$ ハ $n$ ニ含マレル相異ナル素數トスレバ， $Φ (n) = φ (n)$ デアル．由テ上記ノ式カラ $φ (n)$ ヲ得ル．テンプレート:初等整数論講義/remark-end

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

$x = d x^{'}, n = d n^{'}$ ト置ケバ， $(x, n) = d$ ハ $(x^{'}, n^{'}) = 1$ ト同一ニ歸スルカラ，^[5] コノ數ハ， $φ (n^{'})$ 卽チ $φ (\frac{n}{d})$ デアル．

　由テ $x = 1, 2, \dots \dots, n$ ナル $n$ 個ノ數ヲソレニ對應スル $(x, n) = d$ ニ從テ分類スレバ， $d = 1$ ニ對應スルモノガ $φ (n)$ 　個， $d = d_{1}$ ニ對應スルモノガ $φ (\frac{n}{d_{1}})$ 個， $d = d_{2}$ ニ對應スルモノガ $φ (\frac{n}{d_{2}})$ 個，等，等デ，最後ニ $d = n$ ニ對應スルモノガ $φ (1)$ 卽チ $1$ 個デアル．コレラノ總計ガ卽チ $n$ デナケレバナラヌカラ，^[6] テンプレート:初等整数論講義/equation

$n, \frac{n}{d_{1}}, \frac{n}{d_{2}}, \dots \dots, 1$ ハ卽チ $n$ ノスベテノ約數 $1, d_{1}, d_{2}, \dots \dots, n$ ノ餘約數デアルカラ，全體トシテハヤハリ $n$ ノスベテノ約數ニ外ナラズ，由テ次ノ定理ヲ得ル．

テンプレート:初等整数論講義/theorem テンプレート:初等整数論講義/equation 和ハ $n$ ノスベテノ約數 $d$ ノ上ニ亘ル．ソレヲ $d | n$ ナル記號デ示スノデアル．

テンプレート:初等整数論講義/example $n = 15$

$\begin{matrix} d & x & φ (\frac{n}{d}) \\ 1 & 1 & 2 & 4 & 7 & 8 & 11 & 13 & 14 & 8 \\ 3 & 3 & 6 & 9 & 12 & 4 \\ 5 & 5 & 10 & 2 \\ 15 & 15 & 1 \\ 15 \end{matrix}$

$φ (1) + φ (3) + φ (5) + φ (15) = 1 + 2 + 4 + 8 = 15 .$

テンプレート:初等整数論講義/example-end

4. 上記ノ性質ハ $φ (n)$ ノ特徵デアル．卽チ $φ (n)$ ノ外ニハ定理1.20ニ示シタヤウナ性質ヲ有スル整數論的函数ハ存在シナイ．換言スレバ，スベテノ $n$ ニ關シテ $\sum^{d | n} ψ (d) = n$ ナルトキハ， $ψ (n) = φ (n)$ ト斷言スルコトヲ得ル．

ソレヲ證明スルニハ定理1.20 ノ等式カラ， $φ (n)$ ノ公式ヲ算出スルコトガデキルコトヲ示セバ充分デアル．

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

$F (n)$ ヲ任意ノ整數論的函数トシテテンプレート:初等整数論講義/equation ト置ケバ， $G (n)$ ハ又一ツノ整數論的函數デアル．サテ逆ニ $G (n)$ ガ知ラサレテヰルトスレバ，ソレカラ $F (n)$ ノ値ヲ求メルコトガデキル．

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

テンプレート:初等整数論講義/example $n = 15, d = 1, 3, 5, 15$

テンプレート:初等整数論講義/equation

　コレラノ等式ニ順次 $1, - 1, - 1, 1$ ヲ掛ケテ加ヘテテンプレート:初等整数論講義/equation ヲ得ル．

　コノ例デハ， $d$ ノ數ガ四個デ，四個ノ未知数 $F (1), F (3), F (5), F (15)$ ヲ含ム四個ノ聯立一次方程式カラ， $F (15)$ ヲ求メ得タノデアル．テンプレート:初等整数論講義/example-end

一般ノ場合ニ上記ノ問題ヲ解ク爲ニ，メイビウス Moebius ノ函數 $μ (n)$ ヲ用ヰル． $μ (n)$ ノ定義ハ次ノ通リ．

$n = 1$ ノトキ， $μ (1) = 1$

$n$ ガ素數ノ平方デ割リ切レルトキ， $μ (n) = 0$

$n$ ガ $k$ 個ノ相異ナル素數ノ積ニ等シイトキ， $μ (n) = (- 1)^{k}$

例ヘバ，テンプレート:初等整数論講義/note テンプレート:初等整数論講義/equation^[7] テンプレート:初等整数論講義/note-end

コノ定義カラ，直ニ次ニ揭ゲル $μ (n)$ ノ特性ガ出デ來ル．

テンプレート:初等整数論講義/theorem $n > 1$ ナラバ $\sum^{d | n} μ (d) = 0$ テンプレート:初等整数論講義/theorem-end

テンプレート:初等整数論講義/proof $n > 1$ デアルカラ， $n$ ヲ素數羃ニ分解シテテンプレート:初等整数論講義/equation ト置ク．由テテンプレート:初等整数論講義/equation 第二ノ和ハ勿論 $0 ≦ x_{1} ≦ e_{1}, 0 ≦ x_{2} ≦ e_{2}, \dots \dots, 0 ≦ x_{k} ≦ e_{k}$ ナル範圍内ノ $x_{1}, x_{2}, \dots \dots, x_{k}$ ノスベテノ組合セノ上ニ亘ルノデアルガ，コノ和ノ項ノ中デ， $0$ ニ等シイモノ^[8]ヲ省ケバ，テンプレート:初等整数論講義/equation ^[9] テンプレート:初等整数論講義/proof-end

　 $μ (n)$ ヲ用ヰテ容易ニ上記 $F (n), G (n)$ ニ關スル問題ヲ解クコトヲ得ル．テンプレート:初等整数論講義/theorem $\sum^{d | n} F (d) = G (n)$ ナラバ $F (n) = \sum^{d | n} μ (\frac{n}{d}) G (d)$ ．^[10] テンプレート:初等整数論講義/theorem-end テンプレート:初等整数論講義/proof 右邊ノ和ニ於テ， $G (d)$ ニ $\sum^{δ | d} F (δ)$ ヲ代入スレバ，テンプレート:初等整数論講義/equation コノ和ノ項ヲ $F (δ)$ デ括レバ， $δ$ ハ $d$ ノ約數，從テ $\frac{n}{d}$ ハ $\frac{n}{δ}$ ノ約數デアルカラ，テンプレート:初等整数論講義/equation 定理1.21ニ由テ，括弧内ノ和ノ中デ， $\frac{n}{δ} > 1$ ナルモノハ $0$ ニナツテ，唯 $F (n) μ (1)$ ダケガ殘ル．卽チテンプレート:初等整数論講義/equation テンプレート:初等整数論講義/proof-end 特ニ， $F (n) = φ (n)$ ノトキハ定理1.20 ニ由テ， $G (n) = n$ ．故ニテンプレート:初等整数論講義/equation 又ハ文字ヲ變ヘテ，テンプレート:初等整数論講義/equation. $n = p^{α} q^{β} r^{γ} \dots \dots$ トスレバ， $μ (d) = 0$ ナルモノヲ省イテ，テンプレート:初等整数論講義/equation

↑ officious:今 $a y + b x = a y^{'} + b x^{'}, x \neq x^{'}$ と仮定する． $a (y - y^{'}) = b (x^{'} - x)$ にて $x \neq x^{'}$ ならば $a, b$ は互いに素であるから， $(x^{'} - x)$ は $a$ の倍数．ところが $x, x^{'}$ とも $a$ を法とした剰余系だからそれらの差は $a$ 未満であり，これは矛盾する．すなわち， $x = x^{'}$ 同様にして $y = y^{'}$ ．すなわち $x, y$ が相異なれば結果としての $a y + b x$ も重複することなくすべて異なる値である．あるいは， $a x + b y = α$ は $a x \equiv α (m o d . b)$ のことだから，これは定理1.13により，直ちに，それぞれの $α$ に対して $a b$ を法として $x$ がひとつ定まる（ただし $a, b$ は互いに素）ことがわかる． $y$ についても同様である．これはすぐに後述されている．
↑ officious: $(r + n t, n) = (r, n)$ より $(a y + b x, a) = (b x, a)$ がいえ，その後 $(x, a) = 1$ かつ $b, a$ が素より $(b x, a) = 1$ ，(ただし $b < a$ )．
↑ officious: 具体例で示す． $100$ 以下の $2$ と $3$ にそれぞれ互いに素な $Φ_{2, 3} (100)$ 個の整数 $P$ に対して、さらに $5$ で割り切れる数を「新たに控除」するものとする． $P$ に含まれない整数 $Q$ は $2$ または $3$ で割り切れるため， $Q$ に属する整数 $n$ より作る $5 n$ も $2$ や $3$ のすくなくとも一方でそれぞれ互いに素ではない．一方 $P$ に属する整数 $m$ は $2$ と $3$ とそれぞれ互いに素であり、当然 $5$ は $2, 3$ と互いに素であるから、 $5 m$ もまた $2, 3$ とにそれぞれとも互いに素である．「新たに控除する」整数は、これら $2, 3$ と互いに素な $5$ の倍数である．そんな整数は $P$ に属する整数の小さいものから拾い出して $5$ をかければ作ることができる．すなわちその $100$ までの個数は $Φ_{2, 3} (\frac{100}{5})$ ．
↑ officious: $a, b, c$ で展開すると， $Φ_{a, b, c} (n) = Φ_{a, b} (n) - Φ_{a, b} (\frac{n}{c}) = Φ_{a} (n) - Φ_{a} (\frac{n}{b}) - {Φ_{a} (\frac{n}{c}) - Φ_{a} (\frac{n}{b c})}$ , 後は $Φ_{a} (x) = [x] - [\frac{x}{a}]$ を使って展開すればよい．
↑ officious: $(x, n) = d \Leftrightarrow (x^{'}, n^{'}) = 1$ を証明しておく． $\Rightarrow$ ： $d^{'} = (x^{'}, n^{'})$ とし， $x^{'} = x^{″} d^{'}, n^{'} = n^{″} d^{'}$ とすると， $x = x^{'} d = x^{″} d^{'} d, n = n^{'} d = n^{″} d^{'} d$ ．よって， $d^{'} d$ は $x$ と $n$ の公約数である． $d$ が最大公約数であったので， $d^{'} d \leq d$ ，したがって $d^{'} \leq 1$ .当然 $d^{'} \geq 1$ ．ゆえに $d^{'} = (x^{'}, n^{'}) = 1$ ． $\Leftarrow$ ： $x = x^{'} d, n = n^{'} d, (x^{'}, n^{'}) = 1$ のとき， $e = (x, n)$ とおくと， $d$ は $x$ と $n$ の公約数なので，定理1.4より $e = e^{'} d$ と表せる． $e$ は $x$ の約数なので， $e^{'}$ は $x^{'}$ の約数．同様に $e$ は $n$ の約数なので， $e^{'}$ は $n^{'}$ の約数．したがって， $e^{'}$ は $x^{'}, n^{'}$ の公約数．しかし仮定により $(x^{'}, n^{'}) = 1$ なので， $e^{'} = 1$ ，すなわち $d = e$ ．
↑ offisious: 前出 $n = d n^{'}$ より $d$ は $n$ の約数であることが必要． $x$ は $1$ から $n$ まで動き $d$ のいずれかに定まる，したがって $φ$ の総計は $n$ ．
↑ officious: $μ (7) = - 1, μ (8) = 0, μ (9) = 0, μ (10) = 1, μ (11) = - 1, μ (12) = 0$
↑ officitous: $x_{1}, x_{2}, \dots \dots, x_{k}$ のひとつでも $2$ かそれ以上の項 $t$ は平方で割り切れ $μ (t) = 0$ ．
↑ officious: 二項定理テンプレート:Indent に $x = - 1, y = 1$ を代入．
↑ offcious: メビウスの反転公式

テンプレート:PD-Japan math>2, 3

[1] us:今 $a y + b x = a y^{'} + b x^{'}, x \neq x^{'}$ と仮定する． $a (y - y^{'}) = b (x^{'} - x)$ にて $x \neq x^{'}$ ならば $a, b$ は互いに素であるから， $(x^{'} - x)$ は $a$ の倍数．ところが $x, x^{'}$ とも $a$ を法とした剰余系だからそれらの差は $a$ 未満であり，これは矛盾する．すなわち， $x = x^{'}$ 同様にして $y = y^{'}$ ．すなわち $x, y$ が相異なれば結果としての $a y + b x$ も重複することなくすべて異なる値である．あるいは， $a x + b y = α$ は $a x \equiv α (m o d . b)$ のことだから，これは定理1.13により，直ちに，それぞれの $α$ に対して $a b$ を法として $x$ がひとつ定まる（ただし $a, b$ は互いに素）ことがわかる． $y$ についても同様である．これはすぐに後述されている．

[2] us: $(r + n t, n) = (r, n)$ より $(a y + b x, a) = (b x, a)$ がいえ，その後 $(x, a) = 1$ かつ $b, a$ が素より $(b x, a) = 1$ ，(ただし $b < a$ )．

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

[4] us: $a, b, c$ で展開すると， $Φ_{a, b, c} (n) = Φ_{a, b} (n) - Φ_{a, b} (\frac{n}{c}) = Φ_{a} (n) - Φ_{a} (\frac{n}{b}) - {Φ_{a} (\frac{n}{c}) - Φ_{a} (\frac{n}{b c})}$ , 後は $Φ_{a} (x) = [x] - [\frac{x}{a}]$ を使って展開すればよい．

[5] us: $(x, n) = d \Leftrightarrow (x^{'}, n^{'}) = 1$ を証明しておく． $\Rightarrow$ ： $d^{'} = (x^{'}, n^{'})$ とし， $x^{'} = x^{″} d^{'}, n^{'} = n^{″} d^{'}$ とすると， $x = x^{'} d = x^{″} d^{'} d, n = n^{'} d = n^{″} d^{'} d$ ．よって， $d^{'} d$ は $x$ と $n$ の公約数である． $d$ が最大公約数であったので， $d^{'} d \leq d$ ，したがって $d^{'} \leq 1$ .当然 $d^{'} \geq 1$ ．ゆえに $d^{'} = (x^{'}, n^{'}) = 1$ ． $\Leftarrow$ ： $x = x^{'} d, n = n^{'} d, (x^{'}, n^{'}) = 1$ のとき， $e = (x, n)$ とおくと， $d$ は $x$ と $n$ の公約数なので，定理1.4より $e = e^{'} d$ と表せる． $e$ は $x$ の約数なので， $e^{'}$ は $x^{'}$ の約数．同様に $e$ は $n$ の約数なので， $e^{'}$ は $n^{'}$ の約数．したがって， $e^{'}$ は $x^{'}, n^{'}$ の公約数．しかし仮定により $(x^{'}, n^{'}) = 1$ なので， $e^{'} = 1$ ，すなわち $d = e$ ．

[6] sious: 前出 $n = d n^{'}$ より $d$ は $n$ の約数であることが必要． $x$ は $1$ から $n$ まで動き $d$ のいずれかに定まる，したがって $φ$ の総計は $n$ ．

[7] us: $μ (7) = - 1, μ (8) = 0, μ (9) = 0, μ (10) = 1, μ (11) = - 1, μ (12) = 0$

[8] tous: $x_{1}, x_{2}, \dots \dots, x_{k}$ のひとつでも $2$ かそれ以上の項 $t$ は平方で割り切れ $μ (t) = 0$ ．

[9] us: 二項定理テンプレート:Indent に $x = - 1, y = 1$ を代入．

[10] us: メビウスの反転公式

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

初等整数論講義/第1章/Eulerの函数φ(n)

ナビゲーション メニュー

検索

ナビゲーションメニュー