一般涉及到取模($\bmod$)的题目,会用到如下两个恒等式 $$
\begin{align}
(a+b) \bmod m &= ((a \bmod m) + (b \bmod m)) \bmod m \\
(a \cdot b) \bmod m &= ((a \bmod m) \cdot (b \bmod m)) \bmod m \\
\end{align}
$$
证明:根据带余除法,∀a ∈ 𝕫,都可以表示为a = qm + r (m ≠ 0),其中整数q为a除以m的商(quotient),整数r为a除以m的余数(remainder),即r = a mod m。
设a = q1m + r1,b = q2m + r2。
第一个恒等式: $$
\begin{align}
(a+b) \bmod m &= (q_1 m + r_1 +q_2 m + r_2) \bmod m \\
&=((q_1 + q_2)m + r_1 + r_2) \bmod m \\
&=(r_1 + r_2) \bmod m
\end{align}
$$ 又因为r1 = a mod m,r2 = b mod m有:
(a + b) mod m = ((a mod m) + (b mod m)) mod m
第二个恒等式: $$
\begin{align}
(a\cdot b) \bmod m &= ((q_1 m + r_1)(q_2 m + r_2)) \bmod m \\
&= (q_1 q_2 m^2 + (q_1 r_2 + q_2 r_1)m + r_1 r_2) \bmod m \\
&=(r_1 r_2) \bmod m
\end{align}
$$
同样有: (a ⋅ b) mod m = ((a mod m) ⋅ (a mod m)) mod m