阶与原根

需要的数学姿势

阶

若正整数互素且满足，则
对于最小的，我们称之为模的阶，记做。
1.1 对于 ，所有的 结果互不相同
我们假设存在两个整数满足则有，与阶的定义矛盾。
证毕。

1.2 若，则
若，则必有正整数使得于是有又因为，与阶的定义矛盾。
证毕。
推论1 若，。
证明：
由欧拉定理，在时有于是由1.2，有证毕。

1.3 若 为素数，则 的充要条件为 ，其中 为任意正整数
显然也可以表示为，其中为正整数。
由1.2，有则若，则而
所以此时所以为的必要条件。
由1.2，有而若，则于是有又因为，由阶的定义有于是所以为的充分条件。
证毕。

1.4 ，其中为任意正整数
由于由1.2，有也就有又因为所以有而故由1.2，有所以证毕。

原根

设是正整数，是整数，若模的阶且，则称为的一个原根。
2.1 若且，则为的一个原根的充要条件为为的一组简化剩余系
由1.1可知若为原根，则中任意两个元素在模意义下不同余。
又因为，故而为的一组简化剩余系。

2.2 若奇素数 的原根 满足 ，则对于每一个 ，有
在时，显然，显然定理成立。
在时，由欧拉定理，有故可设将上式两侧自乘次，则有其中为整数。
因为，所以因为，所以证毕。

2.3 若为素数，为整数且，则在一个模的完全剩余系中恰有个数模的阶为
证明：我们记小于且与互质的数为由1.3，有
2.3.1
证明：
若则有于是由1.2，有，与定义矛盾。
证毕。
2.3.2 对于任意整数使得，定存在在模意义下与同余
证明：
由拉格朗日定理[1]，同余方程至多有个解。

这个数恰好是方程的全部个在模意义下不同余的解。
由于，所以也满足同余方程，于是必有某个使得证毕。
于是若存在使得，于是而与阶的定义矛盾。
证毕。

2.4 若 为素数，则 有且恰有 个原根
由欧拉定理，若，有由1.2，有由1.3，对于每个自然数，的一个简化剩余系中要么没有模的阶等于的数，要么恰好有个模的阶等于的数。
若中没有原根存在，那么模的阶等于的数总个数至多为个。
因为的简化剩余系中的个数均与互素，因此他们模的阶都有一个确定的数存在。
所以由1.2，应等于，所以中必有原根存在。
再由2.3可知，的原根有个。
证毕。

2.6 一个大于的正整数有原根的充要条件是，其中为奇素数，为正整数
必要性：
令，其中为互不相同的的质因子，为的质因子个数。
任一整数满足，则由欧拉定理，有令 [2]，则而由于，有，所以由引理1.1，若则无原根存在。
显然两两互质是的充要条件。
又因为，所以当具有两个及以上的奇质因子时无原根。那么若有原根，必然是中的一种，其中均大于零。
若，则与不互质，所以。
若，则因为，由欧拉定理，有，于是有。
设成立，则所以对于任意奇数，有此时，故而时，无原根。

充分性：

时，即为原根。

时，即为原根。

，其中为奇素数时，由定理2.5已知此时有原根。
设为的原根，当时，令；当时，令，也是的原根，此时有也就是设整数满足，则因为有由1.2推论1且因为为的原根，也就有，于是我们设。
由欧拉定理可知，故。又因为而，所以有。
于是我们设，这里。若，则有。由1.2，有由2.2，有矛盾。
故而，所以所以也为原根。

，其中为奇素数，为大于一的整数时，令为原根。
若为奇数，我们令；若为偶数，我们令，也是原根。
由于为奇数且为原根，则，故由欧拉定理，有由1.2，有又因为且所以由，有，故为原根。
证毕。

2.7 若 为整数且有一个原根 ，则恰有 个在模意义下不同余的原根，它们由集合中的数给出
对于任意的原根，则存在某个满足因为为原根，所以
又由1.4，有所以有证毕。
参考

^设p是一个素数，f(x)是整系数n次多项式且p不整除f(x)最高项系数，则同余方程f(x)≡0（mod p）至多有n个互不相同（即模p互不同余）的解
^[a,b,...]表示最小公倍数

吴宇 · 2022-7-4 00:26:08

我高一时候好像学过这个

bgwu · 2022-7-4 00:26:45

另外学数学可以参考3b1b的思路，具体推导不重要，重要的是为什么事前能判断出要这么推（很可能原因就是很本质的东西）

archie518 · 2022-7-4 00:27:28

哈哈哈哈，我正在学
[棒]

jsyiniuren · 2022-7-4 00:27:58

这东西没点基础根本看不懂

46u9a · 2022-7-4 00:28:20

原根里面gcd(g, m) = 1中的m是什么意思

niuguobafeit · 2022-7-4 00:29:09

是不是写错了[思考]

su1_ · 2022-7-4 00:29:22

会搜集该问题并浏览的，还是有滴，比如说你[机智]

dzbbs · 2022-7-4 00:29:46

提示: 作者被禁止或删除内容自动屏蔽

bmfyd1 · 2022-7-4 00:30:39

请问下竖杠|，是什么意思呢

82ylb · 2022-7-4 00:31:28

整除

阶与原根

10 个回复