模运算是指取模运算，即求m/n的余数

    例如：

    1. 7 mod 3 ≡ 1 ——-> 7 / 3 = 2 ……1
    1. 交换律
    2. (a + b) mod m ≡ (b + a) mod m
    3. (a * b) mod m ≡ (b * a) mod m
    5. 结合律
    6. [(a + b) mod m + c] mod m ≡ [(a + (b + c) mod m) mod m]
    7. [(a * b) mod m * c] mod m ≡ [(b * c) mod m * a] mod m
    9. 分配律
    10. [(a + b) mod m * c] mod m ≡ [(a * c) mod m + (b * c) mod m] mod m
    11. (a + b) mod m ≡ (a mod m + b mod m) mod m
    12. (a - b) mod m ≡ (a mod m - b mod m) mod m
    13. (a * b) mod m ≡ (a mod m * b mod m) mod m
    14. a^b mod m ≡ (a mod m)^b mod m
    16. 模运算律
    17. a ≡ c mod m
    18. b ≡ d mod m
    20. a + b ≡ (c + d) mod m
    21. a - b ≡ (c - d) mod m
    22. a * b ≡ (c * d) mod m
    23. a / b ≡ (c / d) mod m
    1. 费马定理
    2. 如果p是素数，a为正整数且不能被p整除
    3. a^(p-1) mod p = 1 mod p
    4. (a^p * a^-1 * a) mod p = (1 * a) mod p 
    5. a^p mod p = a mod p
    1. 欧拉定理
    2. 对于素数p
    3. ϕ(p) = p - 1
    4. 对于素数p^t
    5. ϕ(p^t) = p^(t) - p^(t-1)
    7. 例如：
    8. 90 = 2 * 3^2 * 5
    9. ϕ(90) = ϕ(2) * ϕ(3^2) * ϕ(5)
    10.       = (2-1) * (3^2 - 3^1) * (5 - 1)
    11.       = 24
    13. 如果 m>1 a与互素
    14. a^ϕ(m) ≡ 1 mod m
    16. 例如：
    17. m = 11
    18. a = 2
    19. (2,11) = 1
    20. ϕ(11) = 10
    22. 2^10 ≡ 1 mod 11
    1. Fermat大定理
    2. 当 n > 2 时
    3. x^n + y^n = z^n(没有正整数解)
    1. 欧几里得算法
    3. 欧几里得算法又称为辗转相除法，是为了计算两个数的最大公约数。
    4. 定理：gcd(a,b) = gcd(b,a mod b)  (a > b)
    6. 证明:
    7. 假设 a>b
    8. a = k * b + r  ------> r = a - k * b  -----> r = a mod b
    10. 对于充分性：
    11. 假设d 为 a,b 的一个公约数，即d = gcd(a,b)
    12. 则 a | d, b | d (a与b都能被d整除)
    13. r = a - k * b  ----> r | d 即 d = gcd(b,r)
    15. 对于必要性：
    16. 假设 d 是 gcd(b,a mod b) 的公约数  ---->  b | d , r | d
    17. 因为 a = k * b + r 则 a | d  ---->  d = gcd(d,b)
    18. 由上得知 gcd(a,b) 与 gcd(b,a mod b)公约数相等，所以最大公约数也相等
    20. 辗转相除到最后，gcd(x,0) = x
    1. 欧几里得算法c语言代码
    3. int gcd(int a, int b)
    4. {
    5. 　　if(b == 0)
    6. 　　        return a;
    7.     return  gcd(b, a % b);
    8. }
    10. int gcd(int a,int b)
    11. {
    12.     int r;
    13.     while(b!=0)
    14.     {
    15.         r=a%b;//当a<b时第一个循环交换他们顺序
    16.         a=b;
    17.         b=r;
    18.     }
    19.     return a;
    20. }
    1. 模幂运算
    2. 31^52 mod 33
    3. ϕ(33) = ϕ(3 * 11) = ϕ(3) * ϕ(11)
    4.       = (3-1) * (11-1)
    5.       = 20
    6. 53 = 20 * 2 + 12
    7. 31^53 mod 33 = 31^12 mod 33
    9. 模平方计算
    10. 31^1 mod 33 ≡ 31
    11. 31^2 mod 33 ≡ 4
    12. 31^4 mod 33 ≡ 16
    13. 31^8 mod 33 ≡ 25
    15. 31^12 mod 33 ≡ ((31^4 * 31^8) mod 33) mod 33
    16.              ≡ (16 * 25) mod 33 ≡ 4
    1. 扩展欧几里得求逆元
    2. 若 mx ≡ 1 mod n, 则称m关于1模n的乘法逆元为x。也可表示为mx ≡ 1 (mod n)。逆元相当于数论中的倒数。
    4. 条件：
    5. 只有当gcd(m,n) = 1时,m 才有关于 模n 的逆元。
    7. 方法一:
    8. 利用费马小定理
    9. a * a^(p-2) ≡ 1 mod p
    10. a^(p-2)即为a关于1模p的逆元，但只能求出p为素数的情况下的乘法逆元
    12. 方法二:
    13. 采用扩展欧几里德算法来计算普遍情况下的乘法逆元
    14. 由 mx ≡ 1 mod n 
    15. 推出 
    16. mx -kn = 1
    17. a * x mod b = 1
    18. ax + by = gcd(a,b) = 1 
    19. 令a=m,b=n
    20. 所求出x即为逆元
    21. 加上x = (x mod t + t) mod t 即为最小逆元
    23. 为什么可以用扩展欧几里得求得逆元？
    25. 因为ax ≡ 1 (mod p) 就是ax-yp = 1.
    26. 把y写成+的形式就是ax + py = 1，为方便理解下面我们把p写成b就是ax + by = 1。
    27. ax = 1 - by -----> ax = 1 mod b
    28. by = 1 - ax -----> by = 1 mod a
    29. 就表示x是a的模b乘法逆元，y是b的模a乘法逆元。然后就可以用扩展欧几里得定理求值
    1. 欧几里得c语言代码
    3. #include<bits/stdc++.h>
    4. #define ll long long
    5. using namespace std;
    6. int n,p;
    7. int exgcd (ll a,ll b,ll &x,ll &y)
    8. {
    9.     if(b==0)
    10.     {
    11.         x=1;
    12.         y=0;
    13.         return a;
    14.     }
    15.     int r=exgcd (b,a%b,x,y);
    16.     int tmp=x;
    17.     x=y;
    18.     y=tmp-a/b*y;
    19.     return r;
    20. }
    21. int main()
    22. {
    23.     scanf ("%d%d",&n,&p);
    24.     for (int i=1;i<=n;i++)
    25.     {
    26.         ll x,y;
    27.         exgcd (i,p,x,y);
    28.         x=(x+p)%p;
    29.         printf ("%d\n",x);
    30.     }
    31.     return 0;
    32. }

    模运算参考博客
    算法参考博客