「指数 (初等整数論)」の版間の差分
編集の要約なし |
|||
1行目: | 1行目: | ||
{{出典の明記|date=2016年9月}} |
|||
#REDIRECT [[離散対数]] |
|||
[[初等整数論]]における'''指数'''(しすう、''index'')は、解析学における[[指数関数]]・[[対数関数]]の概念の類似物である。'''標数'''と呼ばれることもある。 |
|||
== 定義 == |
|||
互いに素な正の整数 ''n'' と整数 ''a'' に対して ''a''<sup>''k''</sup> ≡ 1 (mod ''n'') なる[[合同式]]が成り立つような最小の非負整数 ''k'' を、''n'' を法とする ''a'' の'''位数'''(いすう、''multiplicative order'' of ''a'' modulo ''n'')と呼び、 ord<sub>''n''</sub> (''a'') や O<sub>''n''</sub>(''a'') などと記す。 |
|||
φ(''n'') を ''n'' の[[オイラーのφ関数|オイラー数]]とするとき、ord<sub>''n''</sub>(''g'') = φ(''n'') となる整数 ''g'' が存在するならば、''g'' の属する法 ''n'' の剰余類 ''g'' mod ''n'' を ''n'' を法とする'''原始根'''(げんしこん、''primitive root'' modulo ''n'')と呼ぶ。すなわち ''n'' を法とする原始根とは、''n'' を法とする既約剰余類全体が乗法に関して成す[[群論|群]] ('''Z''' / ''n'' '''Z''')<sup>×</sup> が[[巡回群]]であるときの、その生成元のことである。 |
|||
原始根が存在するのは ''n'' が 2, 4, ''p''<sup>''k''</sup>, 2''p''<sup>''k''</sup> |
|||
(''p'' は奇素数 ''k''は自然数) の場合に限られる。 |
|||
''g'' mod ''n'' が法 ''n'' に関する原始根であるならば、原始根の定義により任意の''a'' mod ''n'' ∈ ('''Z''' / ''n'' '''Z''')<sup>×</sup> に対して |
|||
:<math>g^e \equiv a \pmod{n}</math> |
|||
なる整数 ''e'' が φ(''n'') を法として唯一つ定まる。このときこの ''e'' mod φ(''n'') を、原始根 ''g'' mod ''n'' を'''底'''(てい、''base'')とする ''a'' mod ''n'' の'''指数'''とよび、Ind<sub>''g''</sub>(''a'') と記す。 |
|||
紛れのおそれが無いならば、これらの定義に現れる剰余類(に関する記述)をその代表元となる整数(に関する記述)であるかのように記す。 |
|||
== 性質 == |
|||
以下、''g'' を整数 ''n'' を法とする原始根として任意に選んで固定しておく。また、''a'' や ''b'' は ''n'' とは互いに素であるとする。 |
|||
* 定義: |
|||
*:<math>g^{\operatorname{Ind}_g(a)} \equiv a \pmod{n}.</math> |
|||
* ''a'' ≡ ''b'' (mod ''n'') であることと Ind<sub>''g''</sub>(''a'') ≡ Ind<sub>''g''</sub>(''b'') (mod φ(''n'')) であることとは同値である。 |
|||
* Ind<sub>''g''</sub>(1) ≡ 0 (mod ''n'') |
|||
* Ind<sub>''g''</sub>(''g'') ≡ 1 (mod ''n'') |
|||
* Ind<sub>''g''</sub>(''ab'') ≡ Ind<sub>''g''</sub>(''a'') + Ind<sub>''g''</sub>(''b'') (mod φ(''n'')) |
|||
* Ind<sub>''g''</sub>(''a''<sup>''k''</sup>) ≡ k * Ind<sub>''g''</sub>(''a'') (mod φ(''n'')) |
|||
== 参考文献 == |
|||
* {{Cite book |
|||
| 和書 |
|||
| last1 = 高木 |
|||
| first1 = 貞治 |
|||
| year = 1971 |
|||
| title = 初等整数論講義 |
|||
| edition = 第2版 |
|||
| publisher = 共立出版 |
|||
| isbn = 978-4-320-01001-9 |
|||
| ref = harv |
|||
}} |
|||
{{DEFAULTSORT:しすう しよとうせいすうろん}} |
|||
[[Category:合同算術]] |
|||
[[Category:数学に関する記事]] |
2016年9月4日 (日) 12:50時点における版
初等整数論における指数(しすう、index)は、解析学における指数関数・対数関数の概念の類似物である。標数と呼ばれることもある。
定義
互いに素な正の整数 n と整数 a に対して ak ≡ 1 (mod n) なる合同式が成り立つような最小の非負整数 k を、n を法とする a の位数(いすう、multiplicative order of a modulo n)と呼び、 ordn (a) や On(a) などと記す。
φ(n) を n のオイラー数とするとき、ordn(g) = φ(n) となる整数 g が存在するならば、g の属する法 n の剰余類 g mod n を n を法とする原始根(げんしこん、primitive root modulo n)と呼ぶ。すなわち n を法とする原始根とは、n を法とする既約剰余類全体が乗法に関して成す群 (Z / n Z)× が巡回群であるときの、その生成元のことである。
原始根が存在するのは n が 2, 4, pk, 2pk (p は奇素数 kは自然数) の場合に限られる。
g mod n が法 n に関する原始根であるならば、原始根の定義により任意のa mod n ∈ (Z / n Z)× に対して
なる整数 e が φ(n) を法として唯一つ定まる。このときこの e mod φ(n) を、原始根 g mod n を底(てい、base)とする a mod n の指数とよび、Indg(a) と記す。
紛れのおそれが無いならば、これらの定義に現れる剰余類(に関する記述)をその代表元となる整数(に関する記述)であるかのように記す。
性質
以下、g を整数 n を法とする原始根として任意に選んで固定しておく。また、a や b は n とは互いに素であるとする。
- 定義:
- a ≡ b (mod n) であることと Indg(a) ≡ Indg(b) (mod φ(n)) であることとは同値である。
- Indg(1) ≡ 0 (mod n)
- Indg(g) ≡ 1 (mod n)
- Indg(ab) ≡ Indg(a) + Indg(b) (mod φ(n))
- Indg(ak) ≡ k * Indg(a) (mod φ(n))
参考文献
- 高木, 貞治『初等整数論講義』(第2版)共立出版、1971年。ISBN 978-4-320-01001-9{{ISBN2}}のパラメータエラー: 無効なISBNです。。