#原根

###定义

#####对于整数a,n(n>1),使得gcd(a,n)=1,存在一个使得$a^r≡1$(mod n)成立的最小的r,r称为a对mod n的阶,记为$δ_n(a)$.

###关于阶

#####根据欧拉定理$a^{φ(n)}$≡1 (mod n),所以r<=φ(n),且$a^0$~$a^{r-1}$在mod n意义下不同余,因为若$a^i$≡$a^j$(mod n)(i>j),则存在($a^i-a^j$)%n=0,即$a^j*(a^{i-j}-1)$%n=0,因为gcd(a,n)=1,所以gcd($a^j$,n)=1,所以($a^{i-j}$-1)%n=0,所以$a^{i-j}$≡1(mod n),因为j<i<=r-1,且r是最小的满足$a^r$≡1(mod n),i-j<r,所以与r最小相矛盾,所以$a^1$~$a^{r-1}$在mod n意义下不同余

###关于原根

#####对于上述过程中的a和r,若r=φ(n),则称a为模n的一个原根,则$a^0$~$a^{φ(n)}$在%n意义下有φ(n)个不同的余数,则这φ(n)个余数构成了%n意义下的简化剩余系,这φ(n)个数也都和n互质,因为我们考虑gcd的过程中,若存在一个余数可以整除,则这个数是a和n的gcd,但是gcd(a,n)=1,所以这φ(n)个数还是和n互质

5b6ecf17aea62

a=5,n=9

$5^0$%9=1 , $5^1$%9=5 , $5^2$%9=7 , $5^3$%9=8 , $5^4$%9=4 , $5^5$%9=2 , $5^6$%9=1

φ(9)={1,2,4,5,7,8}=6

则5是9的一个原根,而且余数都和9互质

###离散对数

#####对于整数a,b,n(n>1,1<=b<n),a是模n的一个原根,gcd(b,n)=1。存在k,使得$a^k$≡b(mod n),我们把k称为对模n到基a上的b的一个离散对数(先这么记着,后面再讲离散对数)

性质

1.a对模n的阶r,r满足r|φ(n)

证明:显然$a^r$≡1(mod n),$a^{φ(n)}$≡1(mod n),r<=φ(n),假设r不能整除φ(n),则φ(n)=k*r+t(0<t<r),所以$a^{φ(n)}$≡$a^{kr+t}$≡$(a^r)^k\ast a^t$≡1(mod n),然后因为$(a^r)^k$≡$a^r$(mod n),(由($a\ast b$)%k=(a%k$\ast$b%k)%k)易得$a^t$%n=1,因为0<t<r,所以t不存在,所以r|φ(n)

#####证明一下$a^t$≡$(a^r)^k\ast a^t$≡1(mod n),因为$a^r$%=1,所以$a^r$=en+1,所以$(a^r)^k$=$(e\ast n+1)^k$,将右侧式子按二项式定理展开,发现除了最后的$1^k$,其他项都含有n,所以%n之后余1,然后由($a\ast b$)%k=(a%k$\ast$b%k)%k可得$(a^r)^k\ast a^t$=($(a^r)^k$%n*$a^t$%n)%n=($1\ast a^t$)%n=1,证毕

####性质1的延伸

阶的计算: 只需要找出φ(n)的一个最小的满足$a^x$%=1的约数x,即为r

#####原根的计算: 将φ(n)分解质因数,φ(n)=$p_1^{x1}+p_2^{x2}+…+p_k^{xk}$然后从2开始枚举a,第一个满足任意i(1<=i<=k),使得$a^{φ(n)/pi}$%n!=1,那么a就是原根

证明:因为原根的定义是$a^{φ(n)}$%n=1,φ(n)是最小的r,而且任意一个不是原根的a对于模n的阶r,r|φ(n),所以我们枚举φ(n)的约数x,若a是原根,则对于任意一个x,$a^x$%n!=1,然后一个显然的结论就是任意一个约数x,都能被某一个φ(n)/pi整除,即若存在一个x(x<φ(n)),使得$a^x$%n=1,则一定存在i,使得x|(φ(n)/pi),根据性质1,$a^{φ(n)/pi}$%n=1

2.对于整数n(n>1),若模n有原根,则模n的原根中大小不超过n的原根的个数为φ(φ(n))

#####小性质:假设a是模n的一个原根,那么任意原根c可以表示为$a^b$mod n,(1<=b<φ(n)),$a^b$mod n是原根的充要条件是b与φ(n)互质.

#####证明:由于a是原根,则φ(n)是满足$a^x$≡1(mod n)的x的最小正整数,且x的其他取值必定是φ(n)的倍数,也就是说满足$(a^b)^x$≡1(mod n)的x一定满足φ(n)|b*n.当b与φ(n)互质时,有φ(n)|x,所以x的最小值为φ(n),所以$a^b$%n是模n的原根.当b与φ(n)不互质时,令d=gcd(b,φ(n)),则x的最小值为φ(n)/p,x<φ(n),所以不是原根

#####证明:由小性质得到b与φ(n)互质是$a^b$%n是原根的充要条件,与φ(n)互质的且小于φ(n)的有φ(φ(n))个,因为实在mod n意义下,所以小于n的原根由φ(φ(n))个

5b6ecf17aea62

2是模27的原根,φ(27)=18,φ(18)=6

{$2^1$mod 27, $2^5$mod 27, $2^7$mod 27, $2^{11}$mod 27, $2^{13}$mod 27, $2^17$mod 27}共6个

3.对于所有素数p>2和所有正整数e,当n=2,4,$p^e$,2$p^e$时%n有原根

####定理1: 每个素数都有原根

####证明 : 根据欧拉定理/费马小定理 ,这个定理显然成立

####定理2: 对于上述的素数p(即p!=2),假如他有原根a,那么a或a+p是模$p^2$的一个原根(不会证)

####定理3: 假设p是一个奇素数,那么对任意的正整数e都存在模$p^e$的原根.如果r是模$p^2$的一个原根,那么对任意的正整数k,r也是模$p^e$的原根。

####定理4:如果p为奇素数并且e是正整数,那么$2\ast p^e$的有原根。如果r是模$p^e$的一个原根且r是奇数,那么它同样是模$2\ast p^e$的一个原根;而如果r是偶数,则r+$p^e$的是模$2\ast p^e$的一个原根。

####据说由上面四个定理可以推出来性质3,但我不会啊(摊手


离散对数

####这是哟中基于同余运算和原根的一种对数运算