原根
维基百科,自由的百科全书
對於(a,m) = 1,有以下關係式: 存在,使得
由此關係式,現在我們定義使對於(a,m) = 1時,成立的最小的d為Ordm(a),若此Ordm(a) = φ(m),則稱a是模m的原根(原根英文:Primitive root modulo m;德文:Primitivwurzel modulo m)
模m有原根的充要條件:m = 1,2,4,pn,2pn,其中p是奇質數,n是任意正整數,另一方面,當模m有原根時,它有φ(φ(m))個原根
[编辑] 一些數的原根列表
m | 模m的原根 |
2 | 1 |
3 | 2 |
4 | -3 |
5 | 2,3 |
至今還沒有一個辦法可以找到模特定m時的原根,但假如已知模m有一個原根,則可找出它其他的原根