今天看了数论把老师发的博客看了一下，也回顾了一些离散数学上面的知识……先列出几个常用的性质：

剩余系就是可能余数组成的集合简化剩余系也称既约剩余系，是模n的完全剩余系的一个子集其中每个元素与n互素。 这个结论证明可以考虑任意两个x互不同余即可（作差判断）
这就告诉我们一个很厲害的东西 S(M)表示M既约剩余系的大小的话S(M)=S(m1)*S(m2) 原根：阶中要求(a,m)互素，所以a^x与m互素所以ax模m的余数与m互素，这样这个余数只可能有 φ(m) 种不同的取徝
（这里我想到了了一个很有意思的结论：1~n内与n互质的数的和为{n*φ(n)+[n==1]} /2
这有一个显然的结论若 x=0,1,2,3,…,φ(m)-1，则 gx 模 m 的余数都和 m 互素并且模 m 两两不同餘。
指标：简单的说就是一切小于m且与m互质的数r，都存在唯一个数k(k<φ(m))使得gk≡r (mod m)
我们就把k叫作r的指标，记作I?
这是一个非常有用的性质の后的题目我们会经常看到他。
简而言之指标就像是数论里的取对数。
原根和求指标将在后面的同余方程中起到巨大作用但是首先我們要知道什么数有原根
直接上结论： 当且仅当m=2,4,pk,2pk时才有原根，p是某一奇素数
事实上一个数p的原根的数目为φ(φ§) （考虑若g是p的原根，gu是p的原根当且仅当gcd(u,φ§)=1）
另外我们注意到2的原根是14的原根是3，但其他2次幂是没有原根的（在高次剩余里模2次幂会带来不小的麻烦）
在2次幂嘚时候就有a^(2k)≡1 (mod 2k+2) 恒成立，所以2的3次及以上次幂没有原
（补充一个很有意思的结论：5模2k+2的指数正好是2k ）
一个数的原根不止一个一般就找最小嘚那个就可以了
其他的原根可用最小原根的gu表示（gu是p的原根当且仅当gcd(u,φ§)=1）
找m的最小原根一般就是暴力枚举g,然后穷举m的每个质因数p，判断gφ(m)/p≡1 (mod m)是否成立（成立的话就不是原根）这些数学素养都是在将来用的到的地方发挥达到作用，整理的有点乱不过看起来也算顺眼，困叻睡觉