数论基础-原根与指标

指数及其基本性质

定义1：

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

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

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

定理1：

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

定理2：

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

推论1：

若a对模m的指数是$\delta$，则$\delta \mid\phi(m)$

推论2：

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

定理3:

若x对模m的指数是ab，$a>0,b>0$，则$x^{a}$对模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\equiv b(~mod~m)$，则a对模m的指数等于b对模m的指数

推论2：

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

定理1：

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

定理2：

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

指标及n次剩余

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

特征函数