关于原根判定的若干证明

其实这个证法是从 zhx 的讲稿中看+结合我自己 yy 出来的……其实这个做法的来源是拉格朗日定理,改天学了之后说不定我会有什么新的认识……

引理1 \,\,\,\, 如果 G = <a> ,称 G 为循环群,若 G 为有限循环群,可知当 |G| = \infty 时, G 与整数加群 \mathbb{Z} 同构,当 |G| \ne \infty 时, ord(a)=|G|

设在质数 \text{mod } p 意义下进行加法和乘法, 那么乘法群 G=\{1,2, \cdots ,p-1 \} 是一个循环群。设 aG 的生成元 (<a>=G),易知 ord(a) = |G| = \varphi(p)

引理2 \,\,\,\, 由欧拉定理可知 \forall a \in G \,,\,ord(a)|\varphi(p)

引理3 \,\,\,\,k=ord(a) \,\,\,(a \in G) ,则 a^k=e , a^{k+i}=a^i

引理4 \,\,\,\, 设原根为 a ,对于\forall 1\leqslant i \leqslant p-1 , \exists x >0 \text{ s.t. } a^x=i \,\, (\text{ mod } p)

引理5 \,\,\,\, 设原根为 a , 仅有 a^{t\varphi(p)}=e ,其中 t \in \mathbb{N}_+

原根判断:a 为原根的充要条件是:对于所有 p 的质因子 d ,都有 a^{\frac{\varphi(p)}{d}} \ne 1

证明:

ord(a)=k

k=\varphi(p) ,则 a 是循环群的生成元,可知 a 为原根,并且 a^{\frac{\varphi(p)}{d}} \ne 1

k < \varphi(p) 时,据引理 2 可知 ord(a)| \varphi(p)

t = \frac{\varphi(p)}{k} , 显然 t>1

dt 任一质因子,显然有 \frac{\varphi(p)}{t}|\frac{\varphi(p)}{d} ,据引理 3 可知 a^{\frac{\varphi(p)}{d}}=1 ,由引理 4 可知 a 显然不是一个原根。

于是胡言乱语地证明完了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据