Số học đồng dư

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 chia cho số khác, kí hiệu là %%%. Ví dụ: 5%2=15 % 2=15%2=1, khi đó có thể viết là 5≡15 equiv 15≡1(mod(mod(mod2)2)2). Phép đồng dư thức có tính chất phân phối đối với phép

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 chia cho số khác, kí hiệu là %%. Ví dụ: 5%2=15 % 2=1, khi đó có thể viết là 5≡15 equiv 1(mod(mod2)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)(a + b)%%cc=[(a= [(a%%c)+(bc) + (b%%c)]c)]%%cc.- (a−b)(a – b)%%cc=[(a= [(a%%c)−(bc) – (b%%c)]c)]%%cc.
  • (a×b)(a times b)%%cc=[(a= [(a%%c)×(bc) times (b%%c)]c)]%%cc.

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 aa (kí hiệu a−1a^{-1}) là số thỏa mãn: a.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 MM. Nghịch đảo modulo MM của một số aa (cũng kí hiệu a−1a^{-1}) là số nguyên thỏa mãn: a.a−1≡1 (moda.a^{-1}equiv1 (modM)M) (Nói cách khác, a−1a^{-1} chính là 1afrac{1}{a}%%M)M). Lấy ví dụ, nếu ta chọn M=109+7,a=2M={10}^9+7, a=2 thì a−1=500000004a^{-1}=500000004.

Không phải lúc nào cũng tồn tại a−1a^{-1}. Chỉ khi GCD(a,M)=1text{GCD}(a, M)=1 thì mới tồn tại a−1a^{-1} là nghịch đảo modulo MM của aa. Để 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 % 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(a,M)=1GCDleft(a,Mright)=1, ta luôn tìm được xxyy thỏa mãn: a.x+M.y=1a.x+M.y=1. Mà M.yM.y chia hết cho MM, do đó phương trình trở thành:

a.x≡1(mod M)a.x equiv 1 (text{mod} M)

Từ đây suy ra xx chính là a−1a^{-1}. Tuy nhiên trong giải thuật Euclid mở rộng, xx 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} luôn không âm.

longlong x;longlongmodulo_inverse(longlong a,longlong M){longlong gcd =extended_euclid(a, M);if(gcd !=1)return-1;// a và M không nguyên tố cùng nhau, không tồn tại nghịch đảo modulo M của a.return(x % M + M)% M;// Do x có thể âm, ta làm dương nó.}

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

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

aM−1≡1 (mod M)a^{M-1} equiv 1 (text{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)

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

longlongpower_mod(longlong a,longlong b,longlong M)// Tính a^b % M.{if(b ==0)return1;if(b ==1)return a;longlong half =power_mod(a, b /2, M)% M;if(b %2==0)return(half * half)% M;elsereturn(((half * half)% M)* a)% M;}longlongmodulo_inverse(int a,int M){returnpower_mod(a, M – 2, M);}

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

Mình đã đề cập ở mục 11, 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, 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, trong đó b−1b^{-1} là nghịch đảo modulo cc của bb.
  • 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ị cc mà ta chọn cách tìm nghịch đảo modulo thích hợp (cc có là số nguyên tố hay không).

Cài đặt:

longlongmodulo_divide(longlong a,longlong b,longlong c){longlong inverse =modulo_inverse(b, c);return(a % c * inverse)% c;}

4. Bậc lũy thừa theo modulo NN (Multiplicative Order)

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

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

intfind_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 Euler (Euler’s Criterion)

Đầu tiên, ta làm quen với khái niệm Thặng dư bậc hai: Một số nguyên qq được gọi là thặng dư bậc hai theo modulo NN nếu như nó đồng dư với một số chính phương theo modulo N,N, nghĩa là tồn tại một số nguyên xx sao cho x2≡q (mod N)x^2 equiv q (text{mod} N).

Trong lý thuyết số, tiêu chuẩn Euler là một công thức dùng để xác định xem một số nguyên có phải là một thặng dư bậc hai theo modulo PP (với PP là một số nguyên tố) hay không. Theo đó, xét hai số nguyên aaPP nguyên tố cùng nhau, trong đó PP là một số nguyên tố lẻ. Ta có công thức sau:

Đối với trường hợp P=2,P=2, mọi số nguyên đều là thặng dư bậc hai theo modulo PP.

Ví dụ, xét P=7P = 7, ta có a=2a = 2 là thặng dư bậc hai của 7,7, vì tồn tại hai số nguyên x=3x = 3x=4x = 4 thỏa mãn a≡x2 (mod P)a equiv x^2 text{ } (mod text{ } P).

longlongpower_mod(longlong a,longlong b,longlong P){if(b ==0)return1;if(b ==1)return a;longlong half =power_mod(a, b /2, P)% P;if(b %2==0)return(half * half)% P;elsereturn(((half * half)% P)*(a % P))% P;}// Kiểm tra N có phải thặng dư bậc 2 của P hay không.boolcheck_quadratic_residue(longlong N,longlong P){if(P ==2)returntrue;elsereturn(power_mod(N,(P -1)/2, P)==1);}

Trong trường hợp NNPP cùng có dạng 4i+3 (i>0)4i + 3 (i > 0), thì giá trị xx thỏa mãn x2≡N (mod P)x^2 equiv N (text{mod} P) (nếu tồn tại) chỉ có thể là: x=± NP+14x=pm text{ }N^{frac{P + 1}{4}}. Dựa vào nhận xét này ta có thể tính nhanh ra giá trị xx. Chứng minh nhận xét như sau:

  • Theo định lý Euler, ta có: NP−12 % P=1N^{frac{P – 1}{2}} % P = 1.
  • Nhân cả hai vế với NN:

NP+12 % P=N % P (1)N^{frac{P + 1}{2}} % P = N % P (1)

  • Lại có: x2≡N (mod P)x^2 equiv N (text{mod} P).
          ⇔x2≡NP+12 (mod P)Leftrightarrow x^2 equiv N^{frac{P+1}{2}} (text{mod} P) (do đẳng thức (1)(1)).
          ⇔x2≡N2i+2 (mod P)Leftrightarrow x^2 equiv N^{2i + 2} (text{mod} P) (do N=4i+3N=4i + 3).
          ⇔x≡ Ni+1 (mod P)Leftrightarrow x equiv N^{i + 1} (text{mod} P).
          ⇔x≡± NP+14 (mod P)Leftrightarrow x equiv pm N^{frac{P + 1}{4}} (text{mod} P) (do P=4i+3P=4i + 3).

Cài đặt:

intfind_quadratic_residue(int N,int P){// P và N không ở đúng dạng 4i + 3, không tính được theo cách này.if(P %4!=3|| N %4!=3)return-1;int x =power_mod(N,(P +1)/2, P);// Kiểm tra giá trị x thứ nhất có hợp lệ không.if((x * x)% P == N % P)return x;// Kiểm tra giá trị x thứ hai có hợp lệ không.
    x = P - x;if((x * x)% P == N % P)return x;// Nếu không tồn tại x, kết luận N không phải thặng dư bậc 2 của Preturn-1;}

II. Tài liệu tham khảo:

Nguồn: viblo.asia

Bài viết liên quan

Thay đổi Package Name của Android Studio dể dàng với plugin APR

Nếu bạn đang gặp khó khăn hoặc bế tắc trong việc thay đổi package name trong And

Lỗi không Update Meta_Value Khi thay thế hình ảnh cũ bằng hình ảnh mới trong WordPress

Mã dưới đây hoạt động tốt có 1 lỗi không update được postmeta ” meta_key=

Bài 1 – React Native DevOps các khái niệm và các cài đặt căn bản

Hướng dẫn setup jenkins agent để bắt đầu build mobile bằng jenkins cho devloper an t

Chuyển đổi từ monolith sang microservices qua ví dụ

1. Why microservices? Microservices là kiến trúc hệ thống phần mềm hướng dịch vụ,