I. Phép đồng dư thức

1. Định nghĩa

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

Bạn đang xem: Đồng dư

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ừ, ví dụ như sau:

(a+b)(a + b)(a+b) %\%% ccc =<(a= <(a=<(a %\%% c)+(bc) + (bc)+(b %\%% c)>c)>c)> %\%% ccc.- (a−b)(a - b)(a−b) %\%% ccc =<(a= <(a=<(a %\%% c)−(bc) - (bc)−(b %\%% c)>c)>c)> %\%% ccc.(a×b)(a imes b)(a×b) %\%% ccc =<(a= <(a=<(a %\%% c)×(bc) imes (bc)×(b %\%% c)>c)>c)> %\%% ccc.

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

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

Như họ đều biết ở lịch trình Toán phổ thông, nghịch hòn đảo của một vài nguyên aaa (kí hiệu a−1a^-1a−1) là số thỏa mãn: a.a−1=1a.a^-1=1a.a−1=1.

Đối cùng 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 MMM. Nghịch đảo modulo MMM của một vài aaa (cũng kí hiệu a−1a^-1a−1) là số nguyên thỏa mãn: a.a−1≡1 (moda.a^-1equiv1 (moda.a−1≡1 (mod M)M)M) (Nói giải pháp khác, a−1a^-1a−1 đó là 1afrac1aa1​ %\%% M)M)M). Lấy ví dụ, trường hợp 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 bắt buộc lúc nào cũng tồn trên a−1a^-1a−1. Chỉ lúc GCD(a,M)=1 extGCD(a, M)=1GCD(a,M)=1 thì mới tồn trên a−1a^-1a−1 là nghịch đảo modulo MMM của aaa. Để tính nghịch đảo modulo của một số, ta hoàn toàn có thể sử dụng nhị giải thuật: giải thuật Euclid không ngừng mở rộng hoặc dựa vào định lý Fermat nhỏ tuổi (áp dụng lời giải chia để trị tính ab % ca^b \% cab % c).

2.1. Sử dụng lời giải Euclid mở rộng

Như đã trình bày ở trên, theo lời giải Euclid mở rộng, nếu GCD(a,M)=1GCDleft(a,M ight)=1GCD(a,M)=1, ta luôn tìm kiếm được xxx và yyy thỏa mãn: a.x+M.y=1a.x+M.y=1a.x+M.y=1. Cơ mà M.yM.yM.y phân tách hết mang lại MMM, do đó phương trình trở thành:

a.x≡1(mod M)a.x equiv 1 ( extmod M)a.x≡1(mod M)

Từ phía trên suy ra xxx đó là a−1a^-1a−1. Mặc dù trong giải thuật Euclid mở rộng, xxx hoàn toàn có thể mang giá trị âm, đề xuất ta sẽ kiểm soát và điều chỉnh một chút nhằm tính được giá trị a−1a^-1a−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; // a với M ko nguyên tố cùng nhau, không tồn trên nghịch hòn đảo modulo M của a. Return (x % M + M) % M; // vày x rất có thể âm, ta có tác dụng dương nó.

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

Theo định lý Fermat nhỏ, ta có: ví như MMM là số nguyên tố với aaa không chia hết đến MMM thì:

aM−1≡1 (mod M)a^M-1 equiv 1 ( extmod M)aM−1≡1 (mod M)

hay nói cách khác:

a×aM−2≡1 (mod M)a imes a^M-2 equiv 1 ( extmod M)a×aM−2≡1 (mod M)

Điều này tương tự với bài toán nếu MMM là số nguyên tố cùng aaa không phân tách hết cho MMM thì aM−2a^M-2aM−2 chính là nghịch hòn đảo modulo MMM của aaa, cũng tương đương với aM−2a^M-2aM−2 %\%% MMM là nghịch đảo modulo MMM của aaa.

long long power_mod(long long a, long long b, long long M) // Tính a^b % 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 nhằm tính ab % cfracab \% cba​ % c

Mình vẫn đề cập sinh hoạt mục 111, phép chia không tồn tại tính hóa học phân phối so với phép đồng dư thức giống hệt như các phép cộng, trừ với nhân. Để tính ab % c,fracab \% c,ba​ % c, ta làm cho như sau:

Tách ab=(a×1b) % c=(a×b−1) % c,fracab = left(a imes frac1b ight) \% c =left(a imes b^-1 ight) \% c,ba​=(a×b1​) % c=(a×b−1) % c, trong những số ấy b−1b^-1b−1 là nghịch hòn đảo modulo ccc của bbb.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, từ bây giờ phép chia modulo trở thành phép nhân với nghịch hòn đảo modulo. Giữ ý, tùy vào giá trị ccc cơ mà ta chọn cách tìm nghịch hòn đảo modulo phù hợp (ccc bao gồm là số nguyên tố tốt 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 NNN (Multiplicative Order)

Xét nhì số nguyên aaa cùng NNN nguyên tố thuộc nhau, bậc lũy thừa của aaa theo modulo NNN là số nguyên dương KKK bé dại nhất thỏa mãn: aK≡1 (mod N)a^K equiv 1 ext (mod ext N)aK≡1 (mod N), kí hiệu là ordN(a)ord_N(a)ordN​(a).

Theo định lý Euler, bởi aaa với NNN là hai số nguyên tố thuộc nhau yêu cầu aϕ(N)≡1 (mod N),a^phi(N) equiv 1 ( extmod N),aϕ(N)≡1 (mod N), cùng với ϕ(N)phi(N)ϕ(N) là con số số nguyên dương ko vượt quá NNN và nguyên tố bên nhau với NNN. Nhưng ϕ(N)≤Nphi(N) le Nϕ(N)≤N, vì vậy ordN(a)≤Nord_N(a) le NordN​(a)≤N, vậy nhằm tìm ordN(a)ord_N(a)ordN​(a) chỉ cần duyệt một vòng lặp từ 111 tới NNN cùng với độ phức tạp O(N−1)O(N - 1)O(N−1).

int find_m_order(int a, int N) int mul = 1; for (int i = 1; i N; ++i) mul = (mul * a) % N; if (mul == 1) return i;

5. Tiêu chuẩn chỉnh Euler (Euler"s Criterion)

Đầu tiên, ta làm quen với có mang Thặng dư bậc hai: một số trong những nguyên qqq được hotline là thặng dư bậc hai theo modulo NNN nếu nó đồng dư với một số trong những chính phương theo modulo N,N,N, nghĩa là tồn tại một số trong những nguyên xxx làm sao để cho x2≡q (mod N)x^2 equiv q ( extmod N)x2≡q (mod N).

Trong lý thuyết số, tiêu chuẩn chỉnh Euler là 1 trong công thức dùng để xác định xem một số trong những nguyên bao gồm phải là 1 thặng dư bậc hai theo modulo PPP (với PPP là một số trong những nguyên tố) giỏi không. Theo đó, xét hai số nguyên aaa cùng PPP nguyên tố cùng nhau, trong những số ấy PPP là một số nguyên tố lẻ. Ta tất cả công thức sau:

*

Đối với trường vừa lòng P=2,P=2,P=2, phần lớn số nguyên phần đa là thặng dư bậc hai theo modulo PPP.

Ví dụ, xét P=7P = 7P=7, ta tất cả a=2a = 2a=2 là thặng dư bậc hai của 7,7,7, bởi tồn tại nhì số nguyên x=3x = 3x=3 cùng x=4x = 4x=4 thỏa mãn nhu cầu a≡x2 (mod P)a equiv x^2 ext (mod ext P)a≡x2 (mod P).

Xem thêm: Đáp Án Đề Thi Tuyển Sinh Lớp 10 Môn Toán 2020, Đề Thi Thử Vào Lớp 10 Môn Toán 2022 Có Đáp Án

long long power_mod(long long a, long long b, long long P) if (b == 0) return 1; if (b == 1) return a; long long half = power_mod(a, b / 2, P) % P; if (b % 2 == 0) return (half * half) % P; else return (((half * half) % P) * (a % P)) % P; // chất vấn N tất cả phải thặng dư bậc 2 của phường hay không.bool check_quadratic_residue(long long N, long long P) if (P == 2) return true; else return (power_mod(N, (P - 1) / 2, P) == 1);Trong trường thích hợp NNN và PPP cùng bao gồm dạng 4i+3 (i>0)4i + 3 (i > 0)4i+3 (i>0), thì giá trị xxx thỏa mãn nhu cầu x2≡N (mod P)x^2 equiv N ( extmod P)x2≡N (mod P) (nếu tồn tại) chỉ hoàn toàn có thể là: x=± NP+14x=pm ext N^fracP + 14x=± N4P+1​. Phụ thuộc vào nhận xét này ta có thể tính nhanh ra quý hiếm xxx. Chứng minh nhận xét như sau:

Theo định lý Euler, ta có: NP−12 % P=1N^fracP - 12 \% phường = 1N2P−1​ % P=1.Nhân cả nhị vế với NNN:

NP+12 % P=N % P (1)N^fracP + 12 \% p. = N \% p (1)N2P+1​ % P=N % P (1)

Lại có: x2≡N (mod P)x^2 equiv N ( extmod P)x2≡N (mod P). ⇔x2≡NP+12 (mod P)Leftrightarrow x^2 equiv N^fracP+12 ( extmod P)⇔x2≡N2P+1​ (mod P) (do đẳng thức (1)(1)(1)). ⇔x2≡N2i+2 (mod P)Leftrightarrow x^2 equiv N^2i + 2 ( extmod P)⇔x2≡N2i+2 (mod P) (do N=4i+3N=4i + 3N=4i+3). ⇔x≡ Ni+1 (mod P)Leftrightarrow x equiv N^i + 1 ( extmod P)⇔x≡ Ni+1 (mod P). ⇔x≡± NP+14 (mod P)Leftrightarrow x equiv pm N^fracP + 14 ( extmod P)⇔x≡± N4P+1​ (mod P) (do P=4i+3P=4i + 3P=4i+3).

Cài đặt:

int find_quadratic_residue(int N, int P)II. Tài liệu tham khảo: