「指数 (初等整数論)」の版間の差分
削除された内容 追加された内容
m ロボットによる 追加: es:Raíz primitiva módulo n |
|||
| 1行目: | 1行目: | ||
#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'')) |
|||
[[Category:合同算術|しすう]] |
|||
[[Category:数学に関する記事|しすう]] |
|||
[[ca:Arrel primitiva]] |
|||
[[de:Primitivwurzel]] |
|||
[[en:Primitive root modulo n]] |
|||
[[es:Raíz primitiva módulo n]] |
|||
[[fr:Racine primitive modulo n]] |
|||
[[hu:Primitív gyök]] |
|||
[[it:Generatore (teoria dei numeri)]] |
|||
[[pl:Pierwiastek pierwotny]] |
|||
[[ru:Первообразный корень (теория чисел)]] |
|||
[[ta:ஏது மூலம், மாடுலோ p]] |
|||
[[vi:Căn nguyên thủy modulo n]] |
|||
[[zh:原根]] |
|||
2009年5月31日 (日) 15:08時点における版
転送先: