数论补全计划:原根

tonyfang posted @ 2016年8月21日 19:50 in 随笔 with tags c++ math OI , 705 阅读

数论补全计划:原根

第一节 基本定义与内容

定义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$原根。

第二节 素数的原根

定理2.1 (拉格朗日定理) 假设$f(n)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0$是一个次数为$n$,首项系数$a_n$不能被$p$整除的整系数多项式,且$1 \leq n$,那么$f(x)$至多有$n$个模$p$不同余的根。

证明

来源 《初等数论及其应用(第五版)》

定理2.2 假设$p$是素数且$d|p-1$,那么多项式$x^d-1$恰有$d$个模$p$不同余的根。

证明 

来源 《初等数论及其应用(第五版)》

推论2.1 假设$p$是素数,且$d|p-1$,那么比$p$小且模$p$的阶为$d$的正整数个数不超过$\phi(d)$

证明 对于每一个$p-1$的因子$d$,令$F(d)$表示模$p$的阶为$d$的正整数个数。

若$F(d)=0$,显然有$F(d) \leq \phi(d)$,否则,有一个整数$a$模$p$的阶为$d$。因为$ord_p(a)=d$,所以整数$a^1, a^2, ... a^d$是模$p$不同余的。由于$(a^d)^k \equiv (a^k)^d \equiv 1 (mod\quad p)$对于所有$k$成立,所以这些幂都是$x^d-1$模$p$的根。由定理2.2知,$x^d-1$恰有$d$个模$p$不同余的根。因此每一个模$p$的根都只同余于$a^1, a^2, ... a^d$的一个。由定理1.4,次数为$d$的$a$的幂都形如$a^k$且$(k, d)=1$。由于恰有$\phi(d)$个$k$满足。所以如果有一个模$p$阶为$d$的元素,就一定有$\phi(d)$个比$p$小的这样的整数。因此$F(d)\leq\phi(d)$。

定理2.3 假设$p$是素数,且$d|p-1$,那么模$p$的阶为$d$且不同余的整数个数为$\phi(d)$

证明 对于每一个$p-1$的因子$d$,令$F(d)$表示模$p$的阶为$d$的正整数个数。
那么有$\sum_{d|p-1}F(d)=p-1$,又因为有$\sum_{d|p-1}\phi(d)=p-1$,所以$\sum_{d|p-1}\phi(d)=\sum_{d|p-1}F(d)$。
根据推论2.1,可以得出对于每个因子$d$,有$F(d) = \phi(d)$成立。
 
定理2.4 每个素数都有原根
 
证明 假设p是素数。定理2.3知,模$p$的阶为$d$且不同余的整数个数为$\phi(d)$。他们中每一个都是原根。
 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter