原根維基百科,自由的 encyclopedia 在数论,特别是整除理论中,原根(英語:Primitive root)是一个很重要的概念。 對於两个正整数 g c d ( a , m ) = 1 {\displaystyle gcd(a,m)=1} ,由欧拉定理可知,存在正整数 d ≤ m − 1 {\displaystyle d\leq m-1} , 比如说欧拉函数 d = φ ( m ) {\displaystyle d=\varphi (m)} ,即小于等于 m {\displaystyle m} 的正整数中与 m {\displaystyle m} 互質的正整数的个数,使得 a d ≡ 1 ( mod m ) {\displaystyle a^{d}\equiv 1{\pmod {m}}} 。 由此,在 g c d ( a , m ) = 1 {\displaystyle gcd(a,m)=1} 時,定義 a {\displaystyle a} 对模 m {\displaystyle m} 的指数 δ m ( a ) {\displaystyle \delta _{m}(a)} 為使 a d ≡ 1 ( mod m ) {\displaystyle a^{d}\equiv 1{\pmod {m}}} 成立的最小的正整数 d {\displaystyle d} 。由前知 δ m ( a ) {\displaystyle \delta _{m}(a)} 一定小于等于 φ ( m ) {\displaystyle \varphi (m)} ,若 δ m ( a ) = φ ( m ) {\displaystyle \delta _{m}(a)=\varphi (m)} ,則稱 a {\displaystyle a} 是模 m {\displaystyle m} 的原根。
在数论,特别是整除理论中,原根(英語:Primitive root)是一个很重要的概念。 對於两个正整数 g c d ( a , m ) = 1 {\displaystyle gcd(a,m)=1} ,由欧拉定理可知,存在正整数 d ≤ m − 1 {\displaystyle d\leq m-1} , 比如说欧拉函数 d = φ ( m ) {\displaystyle d=\varphi (m)} ,即小于等于 m {\displaystyle m} 的正整数中与 m {\displaystyle m} 互質的正整数的个数,使得 a d ≡ 1 ( mod m ) {\displaystyle a^{d}\equiv 1{\pmod {m}}} 。 由此,在 g c d ( a , m ) = 1 {\displaystyle gcd(a,m)=1} 時,定義 a {\displaystyle a} 对模 m {\displaystyle m} 的指数 δ m ( a ) {\displaystyle \delta _{m}(a)} 為使 a d ≡ 1 ( mod m ) {\displaystyle a^{d}\equiv 1{\pmod {m}}} 成立的最小的正整数 d {\displaystyle d} 。由前知 δ m ( a ) {\displaystyle \delta _{m}(a)} 一定小于等于 φ ( m ) {\displaystyle \varphi (m)} ,若 δ m ( a ) = φ ( m ) {\displaystyle \delta _{m}(a)=\varphi (m)} ,則稱 a {\displaystyle a} 是模 m {\displaystyle m} 的原根。