原根
维基百科，自由的百科全书
對於两个正整数(a,m) = 1，由欧拉定理可知，存在正整数
， 比如说欧拉函数d = φ(m)，即小于等于 m 的正整数中与 m 互質的正整数的个数，使得
。
由此，在(a,m) = 1時，定義a对模m的指数Ordm(a)為使成立的最小的正整数d。由前知Ordm(a) 一定小于等于 φ(m)，若Ordm(a) = φ(m)，則稱a是模m的原根。
目录 |
[编辑] 例子
设m = 7，则
等于6。
- 设a = 2，由于
，而
，所以 2 不是模 7 的一个原根。 - 设a = 3，由于
，
，
，
，
，
，因此有
，所以 3 是模 7 的一个原根。
[编辑] 性质
- 可以证明，如果正整数(a,m) = 1和正整数 d 满足，则 d 整除 φ(m)。因此Ordm(a)整除φ(m)。在例子中，当a = 3时，我们仅需要验证 3 的 1 、2、3 和 6 次方模 7 的余数即可。
模 m 两两不- 模m有原根的充要條件是m = 1,2,4,pn,2pn，其中p是奇質數，n是任意正整數。
- 对正整数(a,m) = 1，如果 a 是模 m 的原根，那么 a 是整数模n乘法群（即加法群 Z/mZ 的可逆元，也就是所有与 m 互素的正整数构成的等价类构成的乘法群）Zn×的一个生成元。由于Zn×有 φ(m)个元素，而它的生成元的个数就是它的可逆元个数，即 φ(φ(m))个，因此当模m有原根時，它有φ(φ(m))個原根。
[编辑] 一些數的原根列表
| m | 模m的原根 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 2,3 |
| 6 | 5 |
| 7 | 3,5 |
除了直接運算以外，至今還沒有一個辦法可以找到模特定m時的原根，但假如已知模m有一個原根，則可找出它其他的原根
[编辑] 參見
|
|
|
|---|---|
| 代数系统 | 群 | 半群 | 幺半群 | 环 | 域 | 伽罗瓦域 | 本原元 | 格 | 逆元素 | 等价关系 | 同构基本定理 | 合成列 | 自由對象 | |
| 群论 | 子群 | 阶 | 阿贝尔群 | 循環群 | 有限群 | 李群 | 中心 | 陪集 | 正规子群 | 拉格朗日定理 | 幂零群 | 商群 | 双陪集 | 共轭类 | 群表示 | 群作用 | 交換子 | 中心化子和正规化子 | 交换子群 | 可解群 | p-群 | 对称群 | 西羅定理 | 稳定子群 | 單群 | 半单群 | 典型群 | 自由群 |
| 环论 | 整环 | 除环 | 多项式环 | 环的理想 | 模 | 幂零元 | 特征 | 主理想环 | 唯一分解环 | 素环 | 商环 | 自由模 | 平坦模 | 諾特環 | 完備化 | 阿廷模 | 諾特模 | 局部化 | 深度 (模論) | 局部環 | 賦值環 | 交換環上的代數 | 單模 |
| 域论 | 域扩张 | 有限域 | 原根 | 有限扩张 | 超越扩张 | 代数闭域 | 局部域 | 分式環 | 单扩张 | 代数扩张 |
| 同态 | 同构 | 商结构(商系统) | |
