跳至內容

原根

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

數論,特別是整除理論中,原根(英語:Primitive root)是一個很重要的概念。

對於兩個正整數,由歐拉定理可知,存在正整數, 比如說歐拉函數,即小於等於的正整數中與互質的正整數的個數,使得

由此,在時,定義對模的指數為使成立的最小的正整數。由前知 一定小於等於 ,若,則稱是模的原根

例子

[編輯]

,則等於6。

  • ,由於,因此有,所以 2 不是模 7 的一個原根。
  • ,由於,因此有,所以 3 是模 7 的一個原根。

性質

[編輯]
  • 可以證明,如果正整數和正整數 d 滿足,則 整除 d。[1]因此整除。在例子中,當時,我們僅需要驗證 3 的 2、3 次方模 7 的餘數即可,如果其中有一個是1,則3就不是原根。
  • ,則模 m 兩兩不同餘。因此當是模的原根時,構成模 m 的簡化剩餘系
  • 有原根的充要條件是,其中是奇質數,是任意正整數
  • 對正整數,如果 a 是模 m 的原根,那麼 a 是整數模m乘法群(即加法群 Z/mZ 的可逆元素,也就是所有與 m 互質的正整數構成的等價類構成的乘法群)Zm×的一個生成元。由於Zm×個元素,而它的生成元的個數就是它的可逆元素個數,即 個,因此當模有原根時,它有個原根。

一些數的原根列表

[編輯]
m 模m的原根(有*號的數沒有原根,此時是有最大模m週期的數) 週期 (OEISA002322)
1 0 1
2 1 1
3 2 2
4 3 2
5 2, 3 4
6 5 2
7 3, 5 6
8* 3, 5, 7 2
9 2, 5 6
10 3, 7 4
11 2, 6, 7, 8 10
12* 5, 7, 11 2
13 2, 6, 7, 11 12
14 3, 5 6
15* 2, 7, 8, 13 4
16* 3, 5, 11, 13 4
17 3, 5, 6, 7, 10, 11, 12, 14 16
18 5, 11 6
19 2, 3, 10, 13, 14, 15 18
20* 3, 7, 13, 17 4
21* 2, 5, 10, 11, 17, 19 6
22 7, 13, 17, 19 10
23 5, 7, 10, 11, 14, 15, 17, 19, 20, 21 22
24* 5, 7, 11, 13, 17, 19, 23 2
25 2, 3, 8, 12, 13, 17, 22, 23 20
26 7, 11, 15, 19 12
27 2, 5, 11, 14, 20, 23 18
28* 3, 5, 11, 17, 19, 23 6
29 2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27 28
30* 7, 13, 17, 23 4
31 3, 11, 12, 13, 17, 21, 22, 24 30
32* 3, 5, 11, 13, 19, 21, 27, 29 8
33* 2, 5, 7, 8, 13, 14, 17, 19, 20, 26, 28, 29 10
34 3, 5, 7, 11, 23, 27, 29, 31 16
35* 2, 3, 12, 17, 18, 23, 32, 33 12
36* 5, 7, 11, 23, 29, 31 6

除了直接運算以外,至今還沒有一個辦法可以找到模特定m時的原根,但假如已知模m有一個原根,則可找出它其他的原根。

最小原根

[編輯]

模 p 的最小原根 g p 定義為在 1 到 p-1 中最小的原根。數學家已經給出最小原根的上界及下界的一些限制。

伯吉斯(1962)證明對任何 ε>0,存在一個 C>0,使得

Emil Grosswald (1981) 證明如果 ,則

參考資料及註釋

[編輯]

參見

[編輯]