1 什么是模运算

• 模运算的概念
  • 模运算是一种算术运算，常写作a mod n，表示整数a除以正整数n后的余数。
    模数是模运算中的除数n，它决定了结果的范围。
• 公式表达：
  • 对于任意整数a和正整数n，可以将a表示为：a = qn + r，其中0 ≤ r < n，q是整数商，即q = ⌊a/n⌋。
    a除以n的余数是a mod n。
• 示例：
  • 11 mod 7 = 4（11除以7的余数是4）
  • -11 mod 7 = 3（-11除以7的余数是3)

2 模运算性质

• 同余关系：

  • 当两个整数a和b除以同一个正整数n得到相同的余数时，称a和b模n同余。
    表达式为a ≡ b (mod n)。
  • 同余具有传递性 a ≡ b (mod n) and b ≡ c (mod n) 则 a ≡ c (mod n)

• 模运算（加，减，乘）

  • (a + b) mod n = [(a mod n) + (b mod n)] mod n
  • (a + b) mod n = [(a mod n) + (b mod n)] mod n
  • (a * b) mod n = [(a mod n) * (b mod n)] mod n

• 模除运算（逆运算）
  模除运算跟实际意义上的除法并不相同，比如

  • 逆元，如果有如下公式成立
    $$(a^{{}^{\prime }}\ast a)mod(n)=1$$
    则称 $$a^{{}^{\prime }}$$ 为 a 在模n下的一个逆元。
  • 逆元的作用
    逆元在模除的场景下需要使用到，比如在如下取模运算中
    $$((\frac{a}{v}mod(n))\ast v)mod(n)$$
    如下面例子所示：
    $$((\frac{103}{3}mod(5))\ast 3)mod(5)=1$$
    我们希望通过计算机运算的结果为整数3，由于计算机计算精度有限，就会导致实际运算的结果可能为2.999… ，特别是存在多次模除的时候，就会导致实际进行严重下降，计算机处理过程如下：
    $$\begin{array}{rl}& (\frac{103}{3}mod(5))\ast 3)mod(3)\\ & =((\mathrm{34.333.........})mod(5))\ast 3)mod(5)\\ & =(\mathrm{4.333......}\ast 3)mod(5)\\ & =\mathrm{12.999....}mod(5)\\ & =\mathrm{2.999...}\end{array}$$
    故通过逆元的存在将模除过程中的除法运算改为乘法运算，证明如下：