原根維基百科,自由的 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} 的原根。