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

提供: Wikisource
移動先: 案内検索

1.

自然數 ノ中ニ ト互ニ素ナル數 ガイクツアルカ. ソノ數ヲ デ表ハスノデアル.

例ヘバ

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

サテガ素數ナラバ,

(1)

ナルコト明デアル.又

(2)

デアル.ナゼナラバ,カラマデノ整數ノ中デ,ト互ニ素デナイモノハ,即チデ割リ切レルモノデ,ソレハ

個ダケデアルカラ.

一般ニハ次ノヤウニシテ計算スルコトガデキル.

定理 1.18.
ヲ素數冪ニ分解シテ

トスレバ,

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

定理 1.19.
ナラバ,

コノ定理ガ證明サレタトスレバ, ガニツヅツ互ニ素ナルトキ

由テ

卽チ定理1.18デアル.

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

ノ定義ノ基礎ニナツタ問題ハ, カラ マデノ自然數ノ中ニ, ト互ニ素ナルモノガイクツアルカ,トイフノデアツタガ,サウイフ見方ハアマリニ狹イ. 或ル數ト トガ互ニ素デアル又ハ素デナイトイフコトハ,ソノ數ヲ ノ倍數ダケ增減シテモ變ハラナイ. 一般ニ

[1]

デアルカラ, ヲ法トスル一類ニ屬スル數ハ盡ク ト互ニ素ナルカ,或ハ ト組合ハセタトキ, 一定ノ最大公約數ヲ有スル.

今ソノ最大公約數ヲ トシテ, トオケバ, ニ由テ代表セラルル, 法 ニ關スル一類ノ數ナル ハ, 卽チ法 ニ關シテ, ナル ニ由テ代表セラルル一類ノ各數ニ ヲ乘ジテ得ラレルモノニ外ナラヌノデアル.

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

例ヘバ ヲ法トスルトキノ數ノ四類ノ中デ,二類ハ奇数ノミヲ含ム.ソレハ ノ形及ビ ノ形ノモノデアル. 偶數ノミヲ含ム他ノ二類ノ中デ, ノ形ノモノハ偶數ノ 倍ナル數ノ集合デ,又 ノ形ノモノハ奇數ノ 倍ナル數ノ集合デアル. 偶數ノ 2 倍,又ハ奇數ノ 2 倍トイウノハ,ツマリ ヲ法トシテノ差別デアル.

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

然ラバ, ヲ法トシテノ旣約類ノ數ガ卽チ デアル.

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


旣約剩餘系= reduced system of residues, 直譯スレバ,縮小サレタル剩餘系デアル.縮小トハ旣約ナラザルモノヲ除外スルコトヲ意味スル.

サテ ヲ法トシテノ旣約類ノ數ヲ示スモノデアルトイフ立場カラ,定理1.19ヲ考察シヨウ.


假定ニ由テ デアルカラ,任意ノ整數

ノ形ニ表スコトガデキル(定理1.7

今法 ニ關シテ考察スレバ, ノ倍數ダケ增減シテモ又ハ ノ倍數ダケ增減シテモ, ノ倍數ダケ增減スルノデアルカラ, ヲ法トシテノ一類ニ屬スル.

由テ ナル式ニ於テ, ニハ ヲ法トシテノ各類代表ノ一組ナル 個ノ値ヲ與ヘ, 又 ニハ ヲ法トシテノ代表ノ一組ナル 個ノ値ヲ與ヘルトキニ,コノ式 カラ出ル 個ノ値ハ卽チ ヲ法トシテノ各類ノ代表ノ一組デナクテハナラナイ.[2]

上記ノヤウニシテ カラ得ラレル 個ノ値ノ中カラ,法 ヲ互ニ素デナイモノヲ取リ除ケバ, ヲ法トシテノ旣約代表ノ一組ヲ得ルノデアルガ, トガ公約數ヲ有スルナラバ, ソノ公約數ハ ノ約數デアリ,マタ ト  トノ公約數モ同様デアルカラ, ニ於テ ト互ニ素デナイモノ,又ハ ト素デナイモノハ, 取リ除カネバナラナイ. 然ルニ トスレバ [3] ,又 デアルカラ,

故ニ ニ於テ, ニハ ヲ法トシテノ旣約代表ノ一組,ソノ數 , 又 ニハ ヲ法トシテ旣約代表ノ一組,ソノ數 ヲ與ヘルトキニ, ガトルトコロノ合セテ 個 ノ値ハ,ヲ法トシテノ旣約代表ノ一組デアル.故ニ

卽チ定理1.19ガ證明サレタノデアル.


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

及ビ ヲソレゾレ 及ビ ヲ法トスル旣約代表ノ一組トスレバ, 個ノ組合セノ各々ニ對シテ ナル ヲ法トシテ一ツヅツアル.ソノ ハ勿論 ト互ニ素デアル. 逆ニ トスレバ, デアルカラ, ナル ガ一意的ニ確定スル. 卽チ ヲ法トシテノ旣約代表ノ一組ノ各數 ノ各組トノ間ニ一對一ノ對應ガ成立ツ.從ッテ .


[例]

命題 1.

ハ二ツヅツ互ニ素デアルトシテ, ハ實數 ヲ超エナイ自然數ノ中デ デモ デモ デモ, 割リ切レナイモノノ數ヲ表ハストスレバ,

ヲ超エナイ最大ノ整數ヲ表ハス(ガウスノ記號).

[証]

ガ唯一ツ與ヘラレタトスレバ, ナル自然數ノ中デ, デ割リ切レルモノハ ダケデアルカラ,

由テ數學的歸納法ニ由テ證明ヲ完成スルコトガデキル.

ニ關スル上記 ノ値ガ 正シイト假定スルトキ, 尙ホ一ツノ除數 ガ追加サレタトスレバ, デ割リ切レル數 ヲ 控除セネバナラナイガ,ソノ中 ノドレカデ割リ切レルモノハ旣ニ控除サレテヰルカラ,新ニ控除スベキモノハ ダケデアル.[4] 從テ殘リハ [5] コレハ丁度 ニ關スル上記公式ノ ニナル.

[注意] 

特ニ トシテ, ニ含マレル相異ナル素數トスレバ, デアル.由テ上記ノ式カラ ヲ得ル.


3. ノ任意ノ約數ヲ トスルトキ, ナル 個ノ整數中ニ ナル ハイクツアルカ.

ト置ケバ, ト同一ニ歸スルカラ,[6] コノ數ハ, 卽チ デアル.

 由テ ナル 個ノ數ヲソレニ對應スル ニ從テ分類スレバ, ニ對應スルモノガ  個, ニ對應スルモノガ 個, ニ對應スルモノガ 個,等,等デ,最後ニ ニ對應スルモノガ 卽チ 個デアル.コレラノ總計ガ卽チ デナケレバナラヌカラ,[7]

ハ卽チ ノスベテノ約數 ノ餘約數デアルカラ,全體トシテハヤハリ ノスベテノ約數ニ外ナラズ,由テ次ノ定理ヲ得ル.


定理 1.20.

和ハ ノスベテノ約數 ノ上ニ亘ル.ソレヲ ナル記號デ示スノデアル.


[例]



4. 上記ノ性質ハ ノ特徵デアル. 卽チ ノ外ニハ定理1.20ニ示シタヤウナ性質ヲ有スル整數論的函数ハ存在シナイ. 換言スレバ,スベテノ ニ關シテ ナルトキハ, ト斷言スルコトヲ得ル.

ソレヲ證明スルニハ 定理1.20 ノ等式カラ, ノ公式ヲ算出スルコトガデキルコトヲ示セバ充分デアル.

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

ヲ任意ノ整數論的函数トシテ

ト置ケバ, ハ又一ツノ整數論的函數デアル.サテ逆ニ ガ知ラサレテヰルトスレバ,ソレカラ ノ値ヲ求メルコトガデキル.

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

[例]

 コレラノ等式ニ順次 ヲ掛ケテ加ヘテ

ヲ得ル.

 コノ例デハ, ノ數ガ四個デ,四個ノ未知数 ヲ含ム四個ノ聯立一次方程式カラ, ヲ求メ得タノデアル.


一般ノ場合ニ上記ノ問題ヲ解ク爲ニ,メイビウス Moebius ノ函數 ヲ用ヰル. ノ定義ハ次ノ通リ.

ノトキ,

ガ素數ノ平方デ割リ切レルトキ,

個ノ相異ナル素數ノ積ニ等シイトキ,

例ヘバ,

[8]

コノ定義カラ,直ニ次ニ揭ゲル ノ特性ガ出デ來ル.

定理 1.21.

ナラバ

[証]

デアルカラ, ヲ素數羃ニ分解シテ

ト置ク.由テ

.

第二ノ和ハ勿論 ナル範圍内ノ ノスベテノ組合セノ上ニ亘ルノデアルガ, コノ和ノ項ノ中デ, ニ等シイモノ[9]ヲ省ケバ,

[10]


  ヲ用ヰテ容易ニ上記 ニ關スル問題ヲ解クコトヲ得ル.

定理 1.22.

ナラバ [11]

[証]

右邊ノ和ニ於テ, ヲ代入スレバ,

コノ和ノ項ヲ デ括レバ, ノ約數, 從テ ノ約數デアルカラ,

定理1.21ニ由テ,括弧内ノ和ノ中デ, ナルモノハ ニナツテ,唯 ダケガ殘ル.卽チ

特ニ, ノトキハ 定理1.20 ニ由テ, . 故ニ

又ハ文字ヲ變ヘテ,

.

トスレバ, ナルモノヲ省イテ,


  1. officious: すなわち, で除しても, で除しても剰余は変わらない.以降,ユークリッドの互除法を適用する.
  2. officious:今 と仮定する. にて ならば は互いに素であるから, の倍数.ところが とも を法とした剰余系だからそれらの差は 未満であり,これは矛盾する.すなわち, 同様にして .すなわち が相異なれば結果としての も重複することなくすべて異なる値である. あるいは, のことだから,これは定理1.13により,直ちに,それぞれの に対して を法として がひとつ定まる(ただし は互いに素)ことがわかる. についても同様である.これはすぐに後述されている.
  3. officious: より がいえ,その後 かつ が素より ,(ただし).
  4. officious: 具体例で示す. 以下の にそれぞれ互いに素な 個の整数 に対して、さらに で割り切れる数を「新たに控除」するものとする. に含まれない整数 または で割り切れるため, に属する整数 より作る のすくなくとも一方でそれぞれ互いに素ではない.一方 に属する整数 とそれぞれ互いに素であり、当然 と互いに素であるから、 もまた とにそれぞれとも互いに素である.「新たに控除する」整数は、これら と互いに素な の倍数である.そんな整数は に属する整数の小さいものから拾い出して をかければ作ることができる.すなわちその までの個数は
  5. officious: で展開すると,, 後は を使って展開すればよい.
  6. officious: を証明しておく. とし, とすると, .よって, の公約数である. が最大公約数であったので, ,したがって .当然 . ゆえに のとき, とおくと, の公約数なので, 定理1.4より と表せる. の約数なので, の約数. 同様に の約数なので, の約数. したがって, の公約数. しかし仮定により なので,,すなわち
  7. offisious: 前出 より の約数であることが必要. から まで動き のいずれかに定まる,したがって の総計は
  8. officious:
  9. officitous: のひとつでも か それ以上の項 は平方で割り切れ
  10. officious: 二項定理

    を代入.

  11. offcious: メビウスの反転公式

この日本を法管轄とする文書は、著作者(共同著作物にあっては、最終に死亡した著作者)の死亡した日の属する年の翌年から起算して50年を経過したものであるため、日本の著作権法第51条及び57条の規定により著作権の保護期間が満了しています。


注意: ウィキソースのサーバ設置国であるアメリカ合衆国において著作権を有している場合があるため、この著作権タグのみでは著作権ポリシーの要件を満たすことができません。その場合は、アメリカ合衆国の著作権上パブリックドメインの状態にある著作物、またはCC BY-SA 3.0及びGDFLに適合しているライセンスのもとに公表している著作物のいづれかであることを提示するテンプレートを追加してください。

math>2, 3