「指数 (初等整数論)」の版間の差分
AlleborgoBot (会話 | 投稿記録) m robot Adding: ta:ஏது மூலம், மாடுலோ p |
m ロボットによる 追加: ca:Arrel primitiva |
||
31行目: | 31行目: | ||
[[Category:数学に関する記事|しすう]] |
[[Category:数学に関する記事|しすう]] |
||
[[ca:Arrel primitiva]] |
|||
[[de:Primitivwurzel]] |
[[de:Primitivwurzel]] |
||
[[en:Primitive root modulo n]] |
[[en:Primitive root modulo n]] |
2007年12月22日 (土) 22:52時点における版
初等整数論における指数(しすう、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,2 pk (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))