指数及其基本性质
定义1:
若m>1,(a,m)=1,则使得同余式aγ≡1 mod( m),成立的最小正整数γ叫做a对模m的指数。若a对模m的指数等于ϕ(m),则a叫做模m的一个原根
注意1:指数总是存在的,但原根可能不存在。因为由欧拉定理∀a∈Z,(a,m)=1,有aϕ(m)≡1 (mod m),总是能找到一个数,但这个数不一定是原根,但一定是原根的整数倍
注意2:原根是底数对模数的概念,满足条件的最小正整数才叫指数,而不是放在头上的都叫指数。
定理1:
若a对模m的指数是δ,则1=a0,a1,...,aδ−1对模m两两不同余。
定理2:
若a对模m的指数为δ,则aγ≡aγ′ (mod m)的充分必要条件是r≡r′ (mod δ),特别地,当aδ≡1 (mod m)的充分必要条件是δ∣r
推论1:
若a对模m的指数是δ,则δ∣ϕ(m)
推论2:
设0<a<b,(a,b)=1,b=2α5βb1,(b1,10)=1,b1≡1,若将有理数ba化成循环小数,则此循环小数的循环节的长度δ∣ϕ(b1)
定理3:
若x对模m的指数是ab,a>0,b>0,则xa对模m的指数是b
定理4:
若x对模m的指数是a,y对模m的指数是b,并且(a,b)=1,则xy对模m的指数是ab。
原根存在的条件
命题1:
设a,m>1都是整数,a=mq+r,则a对模m的指数等于对模m的指数
推论1:
若a≡b( mod m),则a对模m的指数等于b对模m的指数
推论2:
设a,m>1都是整数,a=mq+r,则a是模m的原根当前仅当r是模m的原根。
定理1:
若p是奇素数,则模p的原根是存在的
定理2:
设g是模p的一个原根,则存在一个整数t0,使得由等式(g+pt0)p−1=1+pu0所确定的u0不能被p整除,并且对应于这个t0的g+pt0就是模pα的原根,其中α是大于1的任何整数,即对任意正整数α来说,模pα的原根存在。
指标及n次剩余
模2α及合模数的指标组
特征函数