取余¶
\[(ab) \bmod q = ((a\bmod q)\times(b\bmod q))\bmod q\]
证明：不妨设 \(a = k_1q+r_1\) ， \(b=k_2q+r_2\) ，则有
\[ab = q(k_1k_2q+k_1r_2+k_2r_1) + r_1r_2\]
因此， \((ab) \bmod q = (r_1r_2) \bmod q\) ，而 \(r_1 = a\bmod q\) ，\(r_2 = b \bmod q\) .
证明：不妨设 \(a = k_1q+r_1\) ， \(b=k_2q+r_2\) ，则有
因此， \((ab) \bmod q = (r_1r_2) \bmod q\) ，而 \(r_1 = a\bmod q\) ，\(r_2 = b \bmod q\) .