「指数 (初等整数論)」の版間の差分

編集の要約なし
(離散対数へのリダイレクト)
編集の要約なし
{{出典の明記|date=2016年9月}}
#REDIRECT [[離散対数]]
[[初等整数論]]における'''指数'''(しすう、''index'')は、解析学における[[指数関数]]・[[対数関数]]の概念の類似物である。'''標数'''と呼ばれることもある。
 
== 定義 ==
互いに素な正の整数 ''n'' と整数 ''a'' に対して ''a''<sup>''k''</sup> &equiv; 1 (mod ''n'') なる[[合同式]]が成り立つような最小の非負整数 ''k'' を、''n'' を法とする ''a'' の'''位数'''(いすう、''multiplicative order'' of ''a'' modulo ''n'')と呼び、 ord<sub>''n''</sub> (''a'') や O<sub>''n''</sub>(''a'') などと記す。
 
&phi;(''n'') を ''n'' の[[オイラーのφ関数|オイラー数]]とするとき、ord<sub>''n''</sub>(''g'') = &phi;(''n'') となる整数 ''g'' が存在するならば、''g'' の属する法 ''n'' の剰余類 ''g'' mod ''n'' を ''n'' を法とする'''原始根'''(げんしこん、''primitive root'' modulo ''n'')と呼ぶ。すなわち ''n'' を法とする原始根とは、''n'' を法とする既約剰余類全体が乗法に関して成す[[群論|群]] ('''Z''' / ''n'' '''Z''')<sup>&times;</sup> が[[巡回群]]であるときの、その生成元のことである。
 
原始根が存在するのは ''n'' が 2, 4, ''p''<sup>''k''</sup>, 2''p''<sup>''k''</sup>
(''p'' は奇素数 ''k''は自然数) の場合に限られる。
 
''g'' mod ''n'' が法 ''n'' に関する原始根であるならば、原始根の定義により任意の''a'' mod ''n'' &isin; ('''Z''' / ''n'' '''Z''')<sup>&times;</sup> に対して
:<math>g^e \equiv a \pmod{n}</math>
なる整数 ''e'' が &phi;(''n'') を法として唯一つ定まる。このときこの ''e'' mod &phi;(''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'' &equiv; ''b'' (mod ''n'') であることと Ind<sub>''g''</sub>(''a'') &equiv; Ind<sub>''g''</sub>(''b'') (mod &phi;(''n'')) であることとは同値である。
 
* Ind<sub>''g''</sub>(1) &equiv; 0 (mod ''n'')
* Ind<sub>''g''</sub>(''g'') &equiv; 1 (mod ''n'')
* Ind<sub>''g''</sub>(''ab'') &equiv; Ind<sub>''g''</sub>(''a'') + Ind<sub>''g''</sub>(''b'') (mod &phi;(''n''))
* Ind<sub>''g''</sub>(''a''<sup>''k''</sup>) &equiv; k * Ind<sub>''g''</sub>(''a'') (mod &phi;(''n''))
 
== 参考文献 ==
* {{Cite book
| 和書
| last1 = 高木
| first1 = 貞治
| year = 1971
| title = 初等整数論講義
| edition = 第2版
| publisher = 共立出版
| isbn = 978-4-320-01001-9
| ref = harv
}}
 
{{DEFAULTSORT:しすう しよとうせいすうろん}}
[[Category:合同算術]]
[[Category:数学に関する記事]]
17,390

回編集