数论补全计划：原根

第一节 基本定义与内容

定义1.1 阶：设$(a,m)=1, m>1$，使得$a^n \equiv 1 (mod \quad m)$成立的最小的n成为阶。记作$ord_{m}(a)$。

定义1.2 原根：$m$是正整数，$a$是整数，若$a$模$m$的阶是$\phi(m)$，那么$a$为模$m$的一个原根。

定理1.1 如果$(a,m)=1$，且$m>0$，那么正整数$x$是同余方程$a^x \equiv 1 (mod \quad m)$的一个解，当且仅当$ord_{m}(a) | x$

证明 如果$ord_{m}(a) | x$，那么$a^{k \times ord_{m}(a)} \equiv (a^{ord_{m}(a)})^{k} \equiv 1^{k} \equiv 1 (mod \quad m)$，显然成立。

反过来，令$x=p \times ord_{m}(a) + q$，满足$0 \leq q < ord_{m}(a)$，那么$a^{p \times ord_{m}(a) + q} \equiv (a^{ord_{m}(a)})^{p} \times a^{q} \equiv 1^{k} \times a^{q} \equiv a^{q} (mod \quad m)$。因为$a^x \equiv 1 (mod \quad m)$，所以$a^q \equiv 1 (mod \quad m)$。由于$0 \leq q < ord_{m}(a)$，那么根据阶的定义，$q=0$，所以$ord_{m}(a) | x$

推论1.1 如果$(a,n)=1$，且$n>0$，那么$ord_{n}(a) | \phi(n)$。

证明 由欧拉定理，结合定理1.1即可推出。

定理1.2 如果$(a,n)=1$，且$n>0$，那么$a^i\equiv a^j(mod\quad n)$当且仅当$i\equiv j(mod\quad ord_{n}(a))$。

证明 请读者尝试自行证明。

证明可能所需要用到的引理 如果$(c, m)=1$且$m>0$，而且有$ac \equiv bc (mod \quad m)$，那么有$a\equiv b (mod \quad m)$

上述引理为同余的消去律，是一个重要的定律。

定理1.3 如果$(r,n)=1$且$n>0$，如果$r$是模$n$的一个原根，那么$r^1, r^2, ..., r^{\phi(n)}$构成了一个模$n$的既约剩余系。

补充定义 既约剩余系：在每个剩余类选取1个与$m$互质的代表元构成的剩余系。

补充性质 容易看出，既约剩余系的判定依据是：所有数与$n$互质，且任意两个不同余。

证明 首先由于$(r,n)=1$，所以$(r^k,n)=1$，所有数都与$n$互质；假设有两个同余，即$r^i \equiv r^j (mod \quad n)$，$i \not= j$，那么由定理1.2可知道，$i \equiv j (mod \quad ord_{n}(a))$。更进一步，$i \equiv j (mod \quad \phi(n))$，由于$1 \leq i,j \leq \phi(n)$，所以$i = j$，矛盾，所以命题得证。

定理1.4 如果$ord_{n}(a)=t$，那么有$ord_{n}(a^{u}) = \frac{t}{(t, u)}$

证明 令$s=ord_{n}(a^{u}),v=(t,u)$，$t=t_1v, u=u_1v$。那么$(t_1, u_1)=1$。

首先有，$(a^u)^{t_1} = (a^{u_1v})^{t/v} = (a^t)^{u_1} \equiv 1 (mod \quad n)$，（因为$ord_{n}(a)=t$）。

那么我们根据定理1.1即可得出$s|t_1$

另一方面，由于$(a^u)^s = a^{us} \equiv 1 (mod n)$，所以$t|us$，即$t_1v|u_1vs$，那么$t_1|u_1s$，由于$(t_1, u_1)=1$，所以$t_1 | s$。综合两方面，得出$s=t_1$。原命题得证。

推论1.2 如果$r$是模$n$原根，且$n>1$，那么$r^u$是模$n$的一个原根当且仅当$(u, \phi(n)) = 1$。

证明 由定理1.4可知$ord_{n}(r^u) = \frac{ord_{n}(r)}{(u,ord_{n}(r))}=\frac{\phi(n)}{(u,\phi(n))}$。

当且仅当$(u, \phi(n))=1$时，命题成立。

定理1.5 如果$n$有一个原根，那么它有$\phi(\phi(n))$个原根。

证明 令$r$为模$n$的一个原根，那么定理1.3证明了$r^1, r^2, ..., r^{\phi(n)}$构成了一个模$n$的既约剩余系。由推论1.2知道，$r^u$是模$n$的一个原根当且仅当$(u, \phi(n)) = 1$。所以只有$\phi(\phi(n))$个$u$，从而有$\phi(\phi(n))$个模$n$原根。