Cách tính modulo

Đồng dư thức là phép toán lấy số dư của số này khi chia cho số khác, kí hiệu là $\%$. Ví dụ: $5\%2=1$, khi đó có thể viết là $5\equiv 1$ $[mod$ $2]$.

Phép đồng dư thức có tính chất phân phối đối với phép cộng, phép nhân và phép trừ, cụ thể như sau:

• $[a+b]$ $\%$ $c$ $=[[a$ $\%$ $c]+[b$ $\%$ $c]]$ $\%$ $c$.- $[a-b]$ $\%$ $c$ $=[[a$ $\%$ $c]-[b$ $\%$ $c]]$ $\%$ $c$.
• $[a\times b]$ $\%$ $c$ $=[[a$ $\%$ $c]\times [b$ $\%$ $c]]$ $\%$ $c$.

Riêng đối với phép chia, chúng ta không có tính chất phân phối, mà phải sử dụng một lí thuyết là Nghịch đảo modulo.

2. Nghịch đảo modulo của một số

Như chúng ta đều biết ở chương trình Toán phổ thông, nghịch đảo của một số nguyên $a$ [kí hiệu a−1a^{-1}a−1] là số thỏa mãn: a.a−1=1a.a^{-1}=1a.a−1=1.

Đối với nghịch đảo modulo, ta cũng có khái niệm tương tự, nhưng là xét trên tập số dư khi chia cho $M$. Nghịch đảo modulo $M$ của một số $a$ [cũng kí hiệu a−1a^{-1}a−1] là số nguyên thỏa mãn: a.a−1≡1 [moda.a^{-1}\equiv1\ [moda.a−1≡1 [mod $M]$ [Nói cách khác, a−1a^{-1}a−1 chính là 1a\frac{1}{a}a1​ $\%$ $M]$. Lấy ví dụ, nếu ta chọn M=109+7,a=2M={10}^9+7, a=2M=109+7,a=2 thì a−1=500000004a^{-1}=500000004a−1=500000004.

Không phải lúc nào cũng tồn tại a−1a^{-1}a−1. Chỉ khi $\text{GCD}[a,M]=1$ thì mới tồn tại a−1a^{-1}a−1 là nghịch đảo modulo $M$ của $a$. Để tính nghịch đảo modulo của một số, ta có thể sử dụng hai giải thuật: Giải thuật Euclid mở rộng hoặc dựa trên định lý Fermat nhỏ [áp dụng giải thuật chia để trị tính ab % ca^b \ \% \ cab % c].

2.1. Sử dụng giải thuật Euclid mở rộng

Như đã trình bày ở trên, theo giải thuật Euclid mở rộng, nếu $GCD\left[a,M\right]=1$, ta luôn tìm được $x$ và $y$ thỏa mãn: $a.x+M.y=1$. Mà $M.y$ chia hết cho $M$, do đó phương trình trở thành:

$$a.x\equiv 1[\text{mod}M]$$

Từ đây suy ra $x$ chính là a−1a^{-1}a−1. Tuy nhiên trong giải thuật Euclid mở rộng, $x$ có thể mang giá trị âm, nên ta sẽ điều chỉnh một chút để tính được giá trị a−1a^{-1}a−1 luôn không âm.

long long x; long long modulo_inverse[long long a, long long M] { long long gcd = extended_euclid[a, M]; if [gcd != 1] return -1; return [x % M + M] % M; }

2.2. Tính nghịch đảo modulo bằng định lý Fermat nhỏ

Theo định lý Fermat nhỏ, ta có: Nếu $M$ là số nguyên tố và $a$ không chia hết cho $M$ thì:

aM−1≡1 [mod M]a^{M-1} \equiv 1 \ [\text{mod} \ M] aM−1≡1 [mod M]

hay nói cách khác:

a×aM−2≡1 [mod M]a \times a^{M-2} \equiv 1 \ [\text{mod} \ M] a×aM−2≡1 [mod M]

Điều này tương đương với việc nếu $M$ là số nguyên tố và $a$ không chia hết cho $M$ thì aM−2a^{M-2}aM−2 chính là nghịch đảo modulo $M$ của $a$, cũng tương đương với aM−2a^{M-2}aM−2 $\%$ $M$ là nghịch đảo modulo $M$ của $a$.

long long power_mod[long long a, long long b, long long M] { if [b == 0] return 1; if [b == 1] return a; long long half = power_mod[a, b / 2, M] % M; if [b % 2 == 0] return [half * half] % M; else return [[[half * half] % M] * a] % M; } long long modulo_inverse[int a, int M] { return power_mod[a, M – 2, M]; }

3. Áp dụng nghịch đảo modulo để tính ab % c\frac{a}{b} \ \% \ cba​ % c

Mình đã đề cập ở mục $1$, phép chia không có tính chất phân phối đối với phép đồng dư thức giống như các phép cộng, trừ và nhân. Để tính ab % c,\frac{a}{b} \ \% \ c,ba​ % c, ta làm như sau:

• Tách ab=[a×1b] % c=[a×b−1] % c,\frac{a}{b} = \left[a \times \frac{1}{b}\right] \ \% \ c =\left[a \times b^{-1}\right] \ \% \ c,ba​=[a×b1​] % c=[a×b−1] % c, trong đó b−1b^{-1}b−1 là nghịch đảo modulo $c$ của $b$.
• Sau đó áp dụng tính chất phân phối của phép nhân đối với phép đồng dư thức, lúc này phép chia modulo trở thành phép nhân với nghịch đảo modulo. Lưu ý, tùy vào giá trị $c$ mà ta chọn cách tìm nghịch đảo modulo thích hợp [$c$ có là số nguyên tố hay không].

Cài đặt:

long long modulo_divide[long long a, long long b, long long c] { long long inverse = modulo_inverse[b, c]; return [a % c * inverse] % c; }

4. Bậc lũy thừa theo modulo $N$ [Multiplicative Order]

Xét hai số nguyên $a$ và $N$ nguyên tố cùng nhau, bậc lũy thừa của $a$ theo modulo $N$ là số nguyên dương $K$ nhỏ nhất thỏa mãn: aK≡1 [mod N]a^K \equiv 1 \text{ } [mod \text{ } N]aK≡1 [mod N], kí hiệu là ordN[a]ord_N[a]ordN​[a].

Theo định lý Euler, vì $a$ và $N$ là hai số nguyên tố cùng nhau nên aϕ[N]≡1 [mod N],a^{\phi[N]} \equiv 1 \ [\text{mod} \ N],aϕ[N]≡1 [mod N], với $\varphi [N]$ là số lượng số nguyên dương không vượt quá $N$ và nguyên tố cùng nhau với $N$. Mà $\varphi [N]\le N$, do đó ordN[a]≤Nord_N[a] \le NordN​[a]≤N, vậy để tìm ordN[a]ord_N[a]ordN​[a] chỉ cần duyệt một vòng lặp từ $1$ tới $N$ với độ phức tạp $O[N-1]$.

int find_m_order[int a, int N] { int mul = 1; for [int i = 1; i