原始根

ウィキペディア

指数 (初等整数論)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/01/17 09:23 UTC 版)

初等整数論における指数（しすう、index）は、解析学における指数関数・対数関数の概念の類似物である。標数と呼ばれることもある。

定義

互いに素な正の整数 n と整数 a に対して a^k ≡ 1 (mod n) なる合同式が成り立つような最小の正の整数 k を、n を法とする a の位数（いすう、multiplicative order of a modulo n）と呼び、 ord_n (a) や O_n(a) などと記す。

φ(n) を n のオイラー数とするとき、ord_n(g) = φ(n) となる整数 g が存在するならば、g の属する法 n の剰余類 g mod n を n を法とする原始根（げんしこん、primitive root modulo n）と呼ぶ。すなわち n を法とする原始根とは、n を法とする既約剰余類全体が乗法に関して成す群 (Z / n Z)^× が巡回群であるときの、その生成元のことである。

原始根が存在するのは n が 2, 4, p^k, 2p^k (p は奇素数 kは自然数) の場合に限られる。

g mod n が法 n に関する原始根であるならば、原始根の定義により任意のa mod n ∈ (Z / n Z)^× に対して

$g^{e}\equiv a{\pmod {n}}$

なる整数 e が φ(n) を法として唯一つ定まる。このときこの e mod φ(n) を、原始根 g mod n を底（てい、base）とする a mod n の指数とよび、Ind_g(a) と記す。

紛れのおそれが無いならば、これらの定義に現れる剰余類（に関する記述）をその代表元となる整数（に関する記述）であるかのように記す。

性質

以下、g を整数 n を法とする原始根として任意に選んで固定しておく。また、a や b は n とは互いに素であるとする。

• 定義：

  $g^{\operatorname {Ind} _{g}(a)}\equiv a{\pmod {n}}.$

• a ≡ b (mod n) であることと Ind_g(a) ≡ Ind_g(b) (mod φ(n)) であることとは同値である。

• Ind_g(1) ≡ 0 (mod φ(n))
• Ind_g(g) ≡ 1 (mod φ(n))
• Ind_g(ab) ≡ Ind_g(a) + Ind_g(b) (mod φ(n))
• Ind_g(a^k) ≡ k * Ind_g(a) (mod φ(n))

参考文献

• 高木, 貞治 『初等整数論講義』 共立出版、1971年、第2版。ISBN 978-4320010017。