指数及其基本性质

定义1

m>1,(a,m)=1m>1,(a,m)=1,则使得同余式aγ1 mod( m)a^{\gamma}\equiv1~mod(~m),成立的最小正整数γ\gamma叫做a对模m的指数。若a对模m的指数等于ϕ(m)\phi(m),则a叫做模m的一个原根

注意1:指数总是存在的,但原根可能不存在。因为由欧拉定理aZ,(a,m)=1\forall a\in Z,(a,m)=1,有aϕ(m)1 (mod m)a^{\phi(m)}\equiv 1~(mod~m),总是能找到一个数,但这个数不一定是原根,但一定是原根的整数倍

注意2:原根是底数对模数的概念,满足条件的最小正整数才叫指数,而不是放在头上的都叫指数。

定理1

若a对模m的指数是δ\delta,则1=a0,a1,...,aδ11=a^{0},a^{1},...,a^{\delta-1}对模m两两不同余。

定理2

若a对模m的指数为δ\delta,则aγaγ (mod m)a^{\gamma}\equiv a^{\gamma'}~(mod~m)的充分必要条件是rr (mod δ)r\equiv r'~(mod~\delta),特别地,当aδ1 (mod m)a^{\delta}\equiv1~(mod~m)的充分必要条件是δr\delta\mid r

推论1

若a对模m的指数是δ\delta,则δϕ(m)\delta \mid\phi(m)

推论2

0<a<b,(a,b)=1,b=2α5βb1,(b1,10)=1,b1≢10<a<b,(a,b)=1,b=2^{\alpha}5^{\beta}b_1,(b_1,10)=1,b_1\not\equiv1,若将有理数ab\frac{a}{b}化成循环小数,则此循环小数的循环节的长度δϕ(b1)\delta \mid \phi(b_1)

定理3:

若x对模m的指数是ab,a>0,b>0a>0,b>0,则xax^{a}对模m的指数是b

定理4

若x对模m的指数是a,y对模m的指数是b,并且(a,b)=1(a,b)=1,则xy对模m的指数是ab。

原根存在的条件

命题1

a,m>1a,m>1都是整数,a=mq+ra=mq+r,则a对模m的指数等于对模m的指数

推论1

ab( mod m)a\equiv b(~mod~m),则a对模m的指数等于b对模m的指数

推论2

a,m>1a,m>1都是整数,a=mq+ra=mq+r,则a是模m的原根当前仅当r是模m的原根。

定理1

若p是奇素数,则模p的原根是存在的

定理2

设g是模p的一个原根,则存在一个整数t0t_0,使得由等式(g+pt0)p1=1+pu0(g+pt_0)^{p-1}=1+pu_0所确定的u0u_0不能被p整除,并且对应于这个t0t_0g+pt0g+pt_0就是模pαp^{\alpha}的原根,其中α\alpha是大于1的任何整数,即对任意正整数α\alpha来说,模pαp^{\alpha}的原根存在。

指标及n次剩余

2α2^{\alpha}及合模数的指标组

特征函数