Skip to content

模運算

基本介紹

有兩數字 \(a\)、\(b\)
\(a\%b\) 時回傳 \(a/b\) 的餘數

運算的符號

根據維基百科：
通常情況下，在數論中總是選擇正餘數。但在編程中，選擇餘數的符號依賴於程式語言和被除數 \(a\) 或除數 \(n\) 的符號。在程式語言所定義的整數模除中，ISO/IEC 標準 Pascal 和 ALGOL 68，在計算出的餘數 \(r\) 為負數時，返回正數 \(r + |n|\) 作為結果。

所以在 \(a\%b=c\) 時
\(c\) 總是為正數

程式碼根據定義可以這樣寫：

#include <bits/stdc++.h>
using namespace std;
int mod(int a, int n) {
    int r = a - (n * int(a / n));
    if (r < 0) {
        r += abs(n); // 若餘數為負數，加上 |n| 使之為非負
    }
    return r;
}
int main() {
    cout << mod(-5, 3);
}

也可以簡化寫：

#include <bits/stdc++.h>
using namespace std;
int mod(int a,int b){
    b=abs(b);
    return ((a % b) + b) % b; //要多%一次b，不然a % b=0時會回傳b
}
int main(){
    cout<<mod(-5,3);
}

輸出：
mod(5,3)=2
mod(-5,3)=1
mod(5,-3)=2
mod(-5,-3)=1

同餘性質

\(a \equiv b \pmod{k}\)

當兩個整數 \(a\) 和 \(b\) 滿足同餘關係 \(a \equiv b \pmod{k}\) 時，表示 \(a\) 和 \(b\) 在除以 \(k\) 的餘數相同。這個關係有許多重要的性質：

1.反身性（Reflexivity）：對於任何整數 \(a\) 和 \(k\)，\(a \equiv a \pmod{k}\)。

2.對稱性（Symmetry）：如果 \(a \equiv b \pmod{k}\)，則 \(b \equiv a \pmod{k}\)。

3.傳遞性（Transitivity）：如果 \(a \equiv b \pmod{k}\) 且 \(b \equiv c \pmod{k}\)，則 \(a \equiv c \pmod{k}\)。

4.加法和減法的閉合性：

  • 如果 \(a \equiv b \pmod{k}\) 且 \(c \equiv d \pmod{k}\)，則 \(a + c \equiv b + d \pmod{k}\)。
  • 如果 \(a \equiv b \pmod{k}\)，則 \(a - c \equiv b - c \pmod{k}\)。

5.乘法的閉合性：如果 \(a \equiv b \pmod{k}\) 且 \(c \equiv d \pmod{k}\)，則 \(ac \equiv bd \pmod{k}\)。

6.乘法和加法的結合性：

  • 如果 \(a \equiv b \pmod{k}\)，則對於任何整數 \(c\)，\(ca \equiv cb \pmod{k}\)。
  • 如果 \(a \equiv b \pmod{k}\)，則 \(a + c \equiv b + c \pmod{k}\)。

7.除法：如果 \(ac \equiv bc \pmod{k}\) 且 \(c\) 與 \(k\) 互質（\(\gcd(c, k) = 1\)），則 \(a \equiv b \pmod{k}\)。

這些性質使得模 \(k\) 同餘關係在數學中非常有用，特別是在數論和密碼學領域。

模運算性質

當進行模運算（\%）時，有一些重要的性質和公式可以幫助我們更好地理解和應用模運算。以下是一些常用的模運算性質：

1.保留同餘性質 (Congruence Property)

  • 若 \(a \equiv b \pmod{m}\)，則 \(a \% m = b \% m\)
  • 例如，\(14 \equiv 2 \pmod{12}\)，因為 \(14 \% 12 = 2 \% 12\)

2.加法性質 (Addition Property)

  • \((a + b) \% m = ((a \% m) + (b \% m)) \% m\)
  • 例如，\((7 + 5) \% 3 = ((7 \% 3) + (5 \% 3)) \% 3 = (1 + 2) \% 3 = 0\)

3.減法性質 (Subtraction Property)

  • \((a - b) \% m = ((a \% m) - (b \% m) + m) \% m\)
  • 例如，\((7 - 5) \% 3 = ((7 \% 3) - (5 \% 3) + 3) \% 3 = (1 - 2 + 3) \% 3 = 2\)

4.乘法性質 (Multiplication Property)

  • \((a \times b) \% m = ((a \% m) \times (b \% m)) \% m\)
  • 例如，\((7 \times 5) \% 3 = ((7 \% 3) \times (5 \% 3)) \% 3 = (1 \times 2) \% 3 = 2\)

5.冪次性質 (Exponentiation Property)

  • \((a^b) \% m = ((a \% m)^b) \% m\)
  • 例如，\((2^5) \% 3 = ((2 \% 3)^5) \% 3 = 2^5 \% 3 = 32 \% 3 = 2\)

6.除法性質 (Division Property)

  • 若要計算 \((a / b) \% m\)，我們需要找到 \(b\) 在模 \(m\) 下的乘法逆元 \(b^{-1}\)，這樣 \((a / b) \% m = (a \times b^{-1}) \% m\)
  • \(b^{-1}\) 是滿足 \((b \times b^{-1}) \% m = 1\) 的數字

7.分配性質 (Distributive Property)

  • \(a \times (b + c) \% m = ((a \times b) \% m + (a \times c) \% m) \% m\)

  • 例如，

    \(3 \times (4 + 5) \% 7\)
    \(= ((3 \times 4) \% 7 + (3 \times 5) \% 7) \% 7\)
    \(= (12 \% 7 + 15 \% 7) \% 7 = (5 + 1) \% 7\)
    \(= 6\)

證明

證明模運算的加法和乘法分配律需要一些基本的數學知識。讓我們逐步證明這些性質。

加法分配律證明

首先，我們要證明：

\[
(a + b) \% c = [(a \% c) + (b \% c)] \% c
\]

1.定義符號和等式：

  • 設 \(a = kc + r_a\) ，其中 \(k\) 是整數，\(r_a = a \% c\) 且 \(0 \le r_a < c\)
  • 設 \(b = mc + r_b\) ，其中 \(m\) 是整數，\(r_b = b \% c\) 且 \(0 \le r_b < c\)

2.代入加法分配律左邊：

\[
a + b = (kc + r_a) + (mc + r_b) = (k + m)c + (r_a + r_b)
\]

3.取模運算：

\[
(a + b) \% c = [(k + m)c + (r_a + r_b)] \% c
\]

由於 \((k + m)c\) 是 \(c\) 的整數倍，對 \(c\) 取模後結果為 \(0\)。因此：

\[
(a + b) \% c = (r_a + r_b) \% c
\]

4.右邊運算：

\[
[(a \% c) + (b \% c)] \% c = (r_a + r_b) \% c
\]

5.結論：

左右兩邊相等，因此：

\[
(a + b) \% c = [(a \% c) + (b \% c)] \% c
\]

乘法分配律證明

接下來，我們要證明：

\[
(a \times b) \% c = [(a \% c) \times (b \% c)] \% c
\]

1.定義符號和等式：

  • 設 \(a = kc + r_a\)，其中 \(k\) 是整數，\(r_a = a \% c\) 且 \(0 \le r_a < c\)。
  • 設 \(b = mc + r_b\)，其中 \(m\) 是整數，\(r_b = b \% c\)且 \(0 \le r_b < c\)。

2.代入乘法分配律左邊：

\[
a \times b = (kc + r_a) \times (mc + r_b)
\]

3.展開並簡化：

\[
a \times b = kcmc + kcr_b + mcr_a + r_a r_b
\]
\[
a \times b = c(kmc + kr_b + mr_a) + r_a r_b
\]

4.取模運算：

\[
(a \times b) \% c = [c(kmc + kr_b + mr_a) + r_a r_b] \% c
\]

由於 \(c(kmc + kr_b + mr_a)\) 是 \(c\) 的整數倍，對 \(c\) 取模後結果為 \(0\)。因此：

\[
(a \times b) \% c = (r_a r_b) \% c
\]

5.右邊運算：

\[
[(a \% c) \times (b \% c)] \% c = (r_a \times r_b) \% c
\]

6.結論：
左右兩邊相等，因此：

\[
(a \times b) \% c = [(a \% c) \times (b \% c)] \% c
\]