¶ Thuật toán Euclid

Tác giả:

• Nguyễn Đức Kiên, Trường Đại học Công nghệ, ĐHQGHN.

Reviewer:

• Nguyễn Minh Hiển – Trường Đại học Công nghệ, ĐHQGHN
• Phạm Hoàng Hiệp – University of Georgia
• Nguyễn Minh Nhật – Trường THPT chuyên Khoa học Tự nhiên, ĐHQGHN

¶ Mở đầu

¶ Một số ký hiệu toán học sử dụng trong bài viết

• Cho hai số nguyên aaa và bbb (b≠0)(b neq 0)(b=0). Nếu tồn tại số nguyên qqq sao cho a=bqa = bqa=bq thì ta nói aaa chia hết cho bbb (ký hiệu a ⋮ ba vdots ba ⋮ b) hoặc bbb là ước của aaa (ký hiệu b∣abmid ab∣a).
• Cho ba số nguyên aaa, bbb và mmm (m≠0)(m neq 0)(m=0). Nếu tồn tại một số nguyên rrr sao cho a=mq1+ra = mq_1 + ra=mq1​+r và b=mq2+rb = mq_2 + rb=mq2​+r với q1,q2q_1, q_2q1​,q2​ là các số nguyên thì ta nói aaa đồng dư với bbb theo modulo mmm. Ký hiệu là a≡b(modm)a equiv b pmod ma≡b(modm).
• Ký hiệu log⁡a(b)log_a(b)loga​(b) được hiểu là logarit cơ số aaa của bbb. Bài viết này sẽ sử dụng log⁡(x)log(x)log(x) để thay cho log⁡2(x)log_2(x)log2​(x).

¶ Ước chung lớn nhất

Đây là khái niệm tương đối quen thuộc với chúng ta.

Cho hai số tự nhiên aaa và bbb. Số nguyên dương ddd lớn nhất thoả mãn d∣admid ad∣a và d∣bdmid bd∣b gọi là ước chung lớn nhất (greatest common divisor – GCD) của aaa và bbb. Kí hiệu là gcd⁡(a,b)gcd(a, b)gcd(a,b) (ƯCLN(a, b) trong tiếng Việt) hoặc đơn giản hơn (a,b)(a, b)(a,b).

gcd⁡(a,b)=max⁡{d∈N∗:(d∣a),(d∣b)}gcd(a, b) = max{d in mathbb{N}^* : (d mid a), (dmid b)} gcd(a,b)=max{d∈N∗:(d∣a),(d∣b)}

Về mặt toán học, với k≠0k neq 0k=0 thì gcd⁡(0,k)=kgcd(0, k) = kgcd(0,k)=k, và gcd⁡(0,0)gcd(0, 0)gcd(0,0) không xác định. Tuy nhiên, để lập trình tiện lợi ta quy ước gcd⁡(0,0)=0gcd(0, 0) = 0gcd(0,0)=0.

Định nghĩa ƯCLN cũng có thể mở rộng cho số nguyên. Khi đó gcd⁡(a,b)=gcd⁡(∣a∣,∣b∣)gcd(a, b) = gcd(|a|, |b|)gcd(a,b)=gcd(∣a∣,∣b∣).

Có một vài cách để tìm ƯCLN của hai số aaa và bbb. Cách đơn giản nhất là … duyệt từng số tự nhiên ddd một đến min⁡{a,b}min{a, b}min{a,b} để kiểm tra điều kiện d∣admid ad∣a và d∣bdmid bd∣b. Ngoài ra, trong toán học, ta cũng sử dụng phương pháp phân tích thành thừa số nguyên tố để tìm ƯCLN. Phương pháp này không hiệu quả lắm khi lập trình. Thay vào đó, chúng ta sẽ sử dụng thuật toán Euclid.

¶ Thuật toán Euclid

Thuật toán này được trình bày trong tác phẩm “Cơ sở” (Elements) của Euclid vào khoảng năm 300 TCN, nhưng cũng có thể đã từng xuất hiện trước đó.

Thuật toán được thực hiện bằng cách liên tục áp dụng công thức sau cho tới khi ra kết quả:

gcd⁡(a,b)={a neˆˊu b=0gcd⁡(b,a mod b) neˆˊu b≠0gcd(a, b) = begin{cases} a &text{ nếu } b = 0 gcd(b, a text{ mod } b) &text{ nếu } b neq 0 end{cases}gcd(a,b)={agcd(b,a mod b)​ neˆˊu b=0 neˆˊu b=0​

¶ Chứng minh

Nếu ddd là ước của aaa và bbb, hiển nhiên nó cũng là ước của a−ba – ba−b.

Nếu d′d’d′ là ước của bbb và b−ab – ab−a, hiển nhiên nó cũng là ước của b+(a−b)=ab + (a – b) = ab+(a−b)=a.

Do vậy với ba số aaa, bbb, a−ba – ba−b, nếu một số ddd bất kỳ là ước của một trong ba số trên thì sẽ là ước của hai số còn lại, tức là ƯC(a, b) = ƯC(b, a – b). Điều này dẫn đến gcd⁡(a,b)=gcd⁡(b,a−b)gcd(a, b) = gcd(b, a – b)gcd(a,b)=gcd(b,a−b).

Phép tính a−ba – ba−b sau khi thực hiện ⌊ab⌋lfloor frac{a}{b} rfloor⌊ba​⌋ lần thì sẽ thoả mãn a≤ba leq ba≤b. Số aaa sau khi trừ đi ⌊ab⌋lfloor frac{a}{b} rfloor⌊ba​⌋ lần bbb trở thành a−b⌊ab⌋=a mod ba – blfloor frac{a}{b} rfloor = a text{ mod } ba−b⌊ba​⌋=a mod b.

Vậy gcd⁡(a,b)=gcd⁡(b,a mod b)gcd(a, b) = gcd(b, a text{ mod } b)gcd(a,b)=gcd(b,a mod b) (đpcm).

¶ Cài đặt

int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }

Hoặc ngắn hơn:

int gcd(int a, int b) { return (b ? gcd(b, a % b) : a); }

¶ Độ phức tạp

Định lý Lamé: Thuật toán Euclid cần thực hiện ít hơn 5log⁡10(min⁡(u,v))5log_{10}(min(u, v))5log10​(min(u,v)) lần chia lấy dư.

Thuật toán chạy chậm nhất khi a=Fna = F_na=Fn​, b=Fn−1b = F_{n – 1}b=Fn−1​, với FiF_iFi​ là số Fibonacci thứ iii. Khi đó thuật toán cần thực hiện n−2n – 2n−2 lần đệ quy.

¶ Cải tiến

So với các phép toán khác, phép lấy phần dư (%) chậm hơn một chút dù vẫn có độ phức tạp là O(1)O(1)O(1). Chúng ta có thể xây dựng một cách cài đặt khác không sử dụng phép toán này.

Ta có một số tính chất sau:

• gcd⁡(2k,2h)=2gcd⁡(k,h)gcd(2k, 2h) = 2gcd(k, h)gcd(2k,2h)=2gcd(k,h)
• gcd⁡(2k,2h+1)=gcd⁡(k,2h+1)gcd(2k, 2h + 1) = gcd(k, 2h + 1)gcd(2k,2h+1)=gcd(k,2h+1)

Kết hợp với gcd⁡(a,b)=gcd⁡(b,a−b)gcd(a, b) = gcd(b, a – b)gcd(a,b)=gcd(b,a−b) ta cài đặt như sau (Code tham khảo từ CP Algorithms):

int gcd(int a, int b) { if (!a || !b) return a | b; int shift = __builtin_ctz(a | b); a >>= __builtin_ctz(a); do { b >>= __builtin_ctz(b); if (a > b) swap(a, b); b -= a; } while (b); return a << shift; }

Đoạn code trên thực hiện những công việc sau:

• Chia cả hai số aaa và bbb cho shiftshiftshift là luỹ thừa của 222, để hai số đều lẻ (Hàm __builtin_ctz(k) đếm số bit 000 tận cùng của kkk).
• Lúc này, ít nhất một trong hai số là lẻ. Liên tục chia số chẵn cho 222 để nó trở thành số lẻ, sau đó áp dụng (a,b)=(b,a−b)(a, b) = (b, a – b)(a,b)=(b,a−b). Lặp lại bước trên tới khi một trong hai số là 000.
• Nhân kết quả (tạm gọi là ansansans) với shiftshiftshift, vì ta đã chia cả hai số này cho shiftshiftshift, vì rõ ràng (shift,ans)=1(shift, ans) = 1(shift,ans)=1.

Thuật toán cải tiến trên sẽ thực hiện chia log⁡(a)+log⁡(b)log(a) + log(b)log(a)+log(b) lần trong trường hợp tệ nhất. Do vậy, độ phức tạp của thuật vẫn không đổi và là O(log⁡min⁡(a,b))O(log min(a, b))O(logmin(a,b)).

¶ Vài chú ý

• Thư viện algorithm của C++ có hỗ trợ hàm __gcd(a, b) để tìm ước chung lớn nhất của hai số aaa và bbb, cũng sử dụng thuật Euclid. Kể từ phiên bản C++17, thư viện numeric hỗ trợ thêm hàm gcd(a, b) với mục đích tương tự. Các hàm có sẵn này có thể được sử dụng để code ngắn gọn.
• Để tính bội chung nhỏ nhất (BCNN) của hai số, ta dùng công thức:

lcm(a,b)=a×bgcd⁡(a,b)text{lcm}(a, b) = frac{a times b}{gcd(a, b)} lcm(a,b)=gcd(a,b)a×b​

Khi tính toán, công thức trên sẽ gây tràn số nếu a×ba times ba×b quá lớn, nhưng ta có thể giải quyết dễ dàng bằng cách thực hiện phép chia trước:

lcm(a,b)=agcd⁡(a,b)×btext{lcm}(a, b)=frac{a}{gcd(a, b)}times b lcm(a,b)=gcd(a,b)a​×b

Kể từ C++17, thư viện numeric cũng hỗ trợ cả hàm lcm(a, b) cho phép tính BCNN của hai số.

¶ Thuật toán Euclid mở rộng

Với hai số tự nhiên aaa và bbb, thuật toán này được sử dụng để viết d=gcd⁡(a,b)d = gcd(a, b)d=gcd(a,b) dưới dạng tổ hợp tuyến tính. Nói cách khác, thuật toán này sẽ tìm một bộ giá trị nguyên (x,y)(x, y)(x,y) thoả mãn:

ax+by=dax + by = d ax+by=d

Ví dụ:

gcd⁡(55,80)=5=55×3+80×(−2)gcd(55, 80) = 5 = 55 times 3 + 80 times (-2)gcd(55,80)=5=55×3+80×(−2)

Các số x,yx, yx,y thoả mãn đẳng thức trên luôn tồn tại theo bổ đề sau:

Bổ đề Bézout: Với hai số nguyên aaa, bbb có ƯCLN là ddd, tồn tại hai số nguyên xxx và yyy thoả mãn ax+by=dax + by = dax+by=d. Hơn nữa, tất cả các số nguyên DDD có dạng D=aX+bYD = aX + bYD=aX+bY đều là bội của ddd.

Chứng minh

Xét trường hợp a=b=0a = b = 0a=b=0. Với quy ước (0,0)=0(0, 0) = 0(0,0)=0 đã nói tới ở trên, mọi giá trị nguyên của x,yx, yx,y đều thoả mãn đẳng thức ax+by=0ax + by = 0ax+by=0. Bây giờ ta sẽ giải quyết bài toán với a,ba, ba,b không đồng thời bằng 000.

Rõ ràng, luôn tồn tại các giá trị x,yx, yx,y để ax+by>0ax + by > 0ax+by>0. Gọi d′d’d′ là số nguyên dương nhỏ nhất thoả mãn d′=ax′+by′d’ = ax’ + by’d′=ax′+by′ (với x′,y′x’, y’x′,y′ là các số nguyên). Ta chứng minh rằng d′d’d′ là ƯCLN của aaa và bbb.

a=d′q+r (0≤r<d′)⇒r=a−qd′⇒r=a−q(ax′+by′)⇒r=a(1−qx′)+b(−qy′)begin{align} &a = d’q + r (0 leq r < d’) &Rightarrow r = a – qd’ &Rightarrow r = a – q(ax’ + by’) &Rightarrow r = a(1 – qx’) + b(-qy’) end{align}​a=d′q+r (0≤r<d′)⇒r=a−qd′⇒r=a−q(ax′+by′)⇒r=a(1−qx′)+b(−qy′)​​

Do đó rrr cũng có dạng ax+byax + byax+by. Tuy nhiên, số dương nhỏ nhất có dạng như vậy là d′d’d′, thế nhưng 0≤r<d′0 leq r < d’0≤r<d′ nên r=0r = 0r=0, đồng nghĩa với d′∣ad’ mid ad′∣a.

Chứng minh tương tự ta cũng được d′∣bd’ mid bd′∣b. Từ đó suy ra ddd là ước chung của aaa và bbb.

Xét ccc là một ước chung bất kỳ khác d′d’d′ của aaa và bbb. Đặt a=cu,b=cva = cu, b = cva=cu,b=cv với u,vu, vu,v là số nguyên. Ta có:

d′=ax′+bt′⇒d′=cux′+cvy′⇒d′=c(ux′+vy′)begin{align} &d’ = ax’ + bt’ &Rightarrow d’ = cux’ + cvy’ &Rightarrow d’ = c(ux’ + vy’) end{align}​d′=ax′+bt′⇒d′=cux′+cvy′⇒d′=c(ux′+vy′)​​

Suy ra c∣d′c mid d’c∣d′. Vì d′d’d′ dương và khác ccc nên c<d′c < d’c<d′.

Vậy d′d’d′ là ƯCLN của aaa và bbb. Bổ đề được chứng minh.

Ứng dụng trực tiếp của thuật toán này là các phương trình Diophantine, sẽ được thảo luận ở phần sau.

¶ Mô tả thuật toán

Xét bài toán với hai số ban đầu là a=Aa = Aa=A và b=Bb = Bb=B. Gọi ddd là ƯCLN của AAA và BBB.

Khi thực hiện thuật toán Euclid (không mở rộng) để tìm ddd, sau khi biến đổi hoàn tất ta thu được a=d,b=0a = d, b = 0a=d,b=0. Lúc này ta có d=d×1+0×0d = d times 1 + 0 times 0d=d×1+0×0, tức là a=d,b=0,x=1,y=0a = d, b = 0, x = 1, y = 0a=d,b=0,x=1,y=0.

Từ các giá trị a,b,x,ya, b, x, ya,b,x,y ở trên, ta truy lại các giá trị a,ba, ba,b ở bước trước và thay đổi các hệ số x,yx, yx,y để đẳng thức d=ax+byd = ax + byd=ax+by đúng trong bước này.

Giả sử tại một bước ta có a=a0,b=b0a = a_0, b = b_0a=a0​,b=b0​. Đặt a0=b0q+r (q,r∈N,r<b0)a_0 = b_0q + r (q, r in mathbb{N} , r < b_0)a0​=b0​q+r (q,r∈N,r<b0​). Ta thấy q=⌊a0b0⌋q = leftlfloor dfrac{a_0}{b_0} rightrfloorq=⌊b0​a0​​⌋ và r=a0 mod b0r = a_0 text{ mod } b_0r=a0​ mod b0​.

Lại giả sử trước bước đó sau khi áp dụng thuật toán Euclid mở rộng, ta được bộ a=b0,b=ra = b_0, b = ra=b0​,b=r và các hệ số x=x1,y=y1x = x_1, y = y_1x=x1​,y=y1​ là .

Ta cần tìm các hệ số x0,y0x_0, y_0x0​,y0​ để: a0x0+b0y0=da_0x_0 + b_0y_0 = da0​x0​+b0​y0​=d.

d=b0x1+ry1⇒d=b0x1+(a0−b0q)y1⇒d=a0y1+b0(x1−qy1)begin{align} &d = b_0x_1 + ry_1 &Rightarrow d = b_0x_1 + (a_0 – b_0q)y_1 &Rightarrow d = a_0y_1 + b_0(x_1 – qy_1) end{align}​d=b0​x1​+ry1​⇒d=b0​x1​+(a0​−b0​q)y1​⇒d=a0​y1​+b0​(x1​−qy1​)​​

Liên tục cập nhật các hệ số x,yx, yx,y theo công thức trên tới khi thu được a=A,b=Ba = A, b = Ba=A,b=B như ban đầu, ta sẽ thu được kết quả.

¶ Cài đặt

// Hàm trả về ƯCLN của a và b đồng thời thay đổi giá trị của x, y int extEuclid(int a, int b, int& x, int& y) { if (b == 0) { x = 1; y = 0; return a; } int q = a / b; int r = a – b * q; int x1 = 0, y1 = 0; int d = extEuclid(b, r, x1, y1); x = y1; y = x1 – q * y1; return d; }

¶ Độ phức tạp

Thuật toán Euclid mở rộng thực tế chỉ là thêm một vài bước tính toán vào thuật toán Euclid thường nên độ phức tạp vẫn là O(log⁡min⁡(a,b))O(logmin(a, b))O(logmin(a,b)).

¶ Phương trình Diophantine tuyến tính hai ẩn

Phương trình Diophantine (Diophantine function) tuyến tính hai ẩn có dạng như sau:

ax+by=c (a,b,c∈Z)ax + by = c (a, b, c in mathbb{Z}) ax+by=c (a,b,c∈Z)

Phương trình trên có vô số nghiệm (x,y)(x, y)(x,y) thực (trừ khi a=b=0,c≠0a = b = 0, c neq 0a=b=0,c=0, khi đó phương trình vô nghiệm). Tuy nhiên, ta chỉ quan tâm đến các nghiệm nguyên của phương trình.

Để cho ngắn gọn, bài viết sẽ sử dụng cụm từ “phương trình Diophantine” để chỉ phương trình Diophantine tuyến tính hai ẩn.

Bài tập áp dụng trực tiếp: CEQU

¶ Thuật toán tìm nghiệm

Khi a=b=0a = b = 0a=b=0, phương trình có nghiệm x=k,y=h (k,h∈Z)x = k, y = h (k, h in mathbb{Z})x=k,y=h (k,h∈Z) nếu c=0c = 0c=0 và vô nghiệm nếu c=0c = 0c=0

Khi a≠0,b=0a neq 0, b = 0a=0,b=0 phương trình có nghiệm x=ca,y=k (k∈Z)x = frac{c}{a}, y = k (k in mathbb{Z})x=ac​,y=k (k∈Z) nếu a∣camid ca∣c và vô nghiệm nếu a∤ca nmid ca∤c. Tương tự khi a=0,b≠0a = 0, b neq 0a=0,b=0.

Bây giờ ta chỉ xét các trường hợp a≠0,b≠0a neq 0, b neq 0a=0,b=0.

¶ Tìm nghiệm tổng quát bằng phương pháp số học

Lưu ý: Phần dưới đây không thực sự liên quan tới thuật toán để giải bài này, đồng thời kết quả cũng khá phức tạp và không phải thứ chúng ta cần lúc này. Bạn đọc cân nhắc trước khi xem.

Tìm nghiệm tổng quát bằng phương pháp số học

Từ ax+by=cax + by = cax+by=c ta rút ra:

ax≡c(modb)ax equiv c pmod b ax≡c(modb)

Vế trái và modulo của đồng dư thức trên cùng chia hết cho d=gcd⁡(a,b)d = gcd(a, b)d=gcd(a,b). Do vậy, d∣cdmid cd∣c. Nếu điều ngược lại xảy ra, phương trình vô nghiệm.

Chia hai vế và modulo của đồng dư thức cho ddd được:

ad×x≡cd ( mod bd)frac{a}{d} times x equiv frac{c}{d} left(bmod dfrac{b}{d}right) da​×x≡dc​ (moddb​)

Vì (ad,bd)=1(frac{a}{d}, frac{b}{d}) = 1(da​,db​)=1 nên tồn tại nghịch đảo modulo bdfrac{b}{d}db​ của adfrac{a}{d}da​. Nhân hai vế của đồng dư thức với giá trị này được:

x≡cd×(ad)−1 ( mod bd)x equiv frac{c}{d} times left(dfrac{a}{d}right) ^{-1} left(bmod dfrac{b}{d}right) x≡dc​×(da​)−1 (moddb​)

Do đó họ các nghiệm của phương trình là:

{x=bd×k+cd×γ(k,γ∈Z,ad×γ≡1 ( mod bd))y=c−axbbegin{cases} x = frac{b}{d} times k + frac{c}{d} times gamma &left(k, gamma in mathbb{Z}, frac{a}{d} times gamma equiv 1 left(bmod dfrac{b}{d}right)right) y = frac{c – ax}{b} end{cases}⎩⎨⎧​x=db​×k+dc​×γy=bc−ax​​(k,γ∈Z,da​×γ≡1 (moddb​))​

¶ Tìm nghiệm bằng thuật toán

Ta đã biết phương trình chỉ có nghiệm nếu gcd⁡(a,b)∣cgcd(a, b)mid cgcd(a,b)∣c. Nếu điều kiện này không thoả mãn, ta kết luận phương trình vô nghiệm.

Giả sử a,ba, ba,b là các số dương. Đặt d=gcd⁡(a,b)d = gcd(a, b)d=gcd(a,b).

Sử dụng thuật toán Euclid mở rộng, ta có:

ax′+by′=d (x′,y′∈Z)ax’ + by’ = d (x’, y’ in mathbb{Z}) ax′+by′=d (x′,y′∈Z)

Nhân hai vế của phương trình với cdfrac{c}{d}dc​ được:

a(x′×cd)+b(y′×cd)=caleft(x’ times frac{c}{d}right) + bleft(y’ times frac{c}{d}right) = c a(x′×dc​)+b(y′×dc​)=c

Suy ra phương trình có nghiệm:

{x0=x′×cdy0=y′×cdbegin{cases} x_0 = x’ times frac{c}{d} y_0 = y’ times frac{c}{d} end{cases}{x0​=x′×dc​y0​=y′×dc​​

Trường hợp a,ba, ba,b không dương, ta thay đổi dấu của x,yx, yx,y để thoả mãn đẳng thức.

Thay nghiệm x0,y0x_0, y_0x0​,y0​ trở lại phương trình, ta được:

ax0+by0=c⇒a(x0+k×bd)+b(y0−k×ad)=c (k∈Z)ax_0 + by_0 = c Rightarrow aleft(x_0 + ktimesfrac{b}{d}right) + bleft(y_0 – ktimesfrac{a}{d}right) = c (k in mathbb{Z})ax0​+by0​=c⇒a(x0​+k×db​)+b(y0​−k×da​)=c (k∈Z)

Từ đẳng thức này ta kết luận các nghiệm của phương trình có dạng:

{x=x0+k×bdy=y0−k×ad (k∈Z)begin{cases} x = x_0 + k times frac{b}{d} y = y_0 – k times frac{a}{d} end{cases} (k in mathbb{Z}){x=x0​+k×db​y=y0​−k×da​​ (k∈Z)

Chốt lại, để tìm nghiệm của một phương trình Diophantine, ta tìm các hệ số x′,y′x’, y’x′,y′ từ thuật toán Euclid mở rộng, rồi từ các hệ số này áp dụng vào các công thức trên để tính ra kết quả.

¶ Cài đặt

Đoạn chương trình sau tìm một nghiệm nguyên của phương trình ax+by=cax + by = cax+by=c, với a,b≠0a, b neq 0a,b=0:

const pair <int, int> INVALID_ROOT = {INT_MAX, INT_MAX}; //Hàm trả về ƯCLN của a và b, biến đổi x, y thoả mãn ax + by = gcd(a, b) int extEuclid(int a, int b, int &x, int&y) { if (b == 0) { x = 1; y = 0; return a; } int q = a / b; int r = a – b * q; int x1 = 0, y1 = 0; int d = extEuclid(b, r, x1, y1); x = y1; y = x1 – q * y1; return d; } //Tìm 1 nghiệm nguyên của phương trình ax + by + c = 0 pair <int, int> diophantineSolve(int a, int b, int c) { int x = 0, y = 0; int d = extEuclid(a, b, x, y); if (c % d != 0) return INVALID_ROOT; x *= c / d; y *= c / d; if (a < 0) x = -x; if (b < 0) y = -y; return make_pair(x, y); }

¶ Một số bài toán liên quan

¶ Đếm số nghiệm của phương trình Diophantine trong một khoảng cho trước

Bài tập áp dụng trực tiếp: SGU 106

Tóm tắt đề bài: Đếm số cặp số nguyên x,yx, yx,y thoả mãn: {ax+by=cx1≤x≤x2y1≤y≤y2begin{cases} ax + by = c x_1 leq x leq x_2 y_1 leq y leq y_2 end{cases}⎩⎨⎧​ax+by=cx1​≤x≤x2​y1​≤y≤y2​​

Các trường hợp có a=0a = 0a=0 hoặc b=0b = 0b=0 là tầm thường. Ta chỉ xét a≠0a neq 0a=0 và b≠0b neq 0b=0.

Ở phần trước, ta đã có công thức nghiệm tổng quát của các phương trình Diophantine từ một nghiệm bất kỳ:

{x=x0+k×bdy=y0−k×ad (k∈Z)begin{cases} x = x_0 + k times frac{b}{d} y = y_0 – k times frac{a}{d} end{cases} (k in mathbb{Z}){x=x0​+k×db​y=y0​−k×da​​ (k∈Z)

Dễ thấy các nghiệm của bài toán lúc này chỉ phụ thuộc vào kkk. Bài toán trở thành tìm kkk sao cho xxx và yyy thoả mãn các điều kiện đã cho. Lúc này ta chỉ cần thay ngược biểu thức của xxx và yyy theo kkk vào rồi suy ngược kkk ra là xong.

Nếu bài toán yêu cầu liệt kê chi tiết các nghiệm này, ta cũng chỉ cần tăng kkk lên dần dần trong khoảng thoả mãn.

¶ Tìm nghiệm có tổng dương nhỏ nhất

Bài toán này yêu cầu chúng ta tìm nghiệm x,yx, yx,y có x+yx + yx+y dương nhỏ nhất.

Cộng từng vế của biểu thức nghiệm xxx và yyy theo kkk được:

x+y=x0+y0+k×b−adx + y = x_0 + y_0 + ktimesfrac{b – a}{d}x+y=x0​+y0​+k×db−a​

Dễ thấy nghiệm nhỏ nhất khi k×b−adktimesfrac{b – a}{d}k×db−a​ nhỏ nhất. Tuỳ thuộc vào dấu của b−ab – ab−a, ta chọn kkk sao cho giá trị của biểu thức là cực tiểu.

Bài tập áp dụng: Euclid Problem. Ở bài này c=dc = dc=d.

¶ Nghịch đảo modulo

Số tự nhiên γgammaγ được gọi là nghịch đảo modulo theo modulo mmm của một số tự nhiên aaa nếu aγ≡1(modM)agamma equiv 1 pmod Maγ≡1(modM). Ký hiệu là a−1(modM)a^{-1} pmod Ma−1(modM).

Ví dụ: 3≡7−1(mod1)03 equiv 7^{-1} pmod 103≡7−1(mod1)0

Không phải số tự nhiên nào cũng có nghịch đảo modulo; chẳng hạn, không có nghịch đảo modulo 444 của 222.

Xét phương trình Diophantine ax+by=1ax + by = 1ax+by=1. Khi phương trình có nghiệm (x0,y0)(x_0, y_0)(x0​,y0​), ta có:

ax0+by0=1⇒ax0=1−by0⇒ax0≡1(modb)⇒x0≡a−1(modb)ax_0 + by_0 = 1 Rightarrow ax_0 = 1 – by_0 Rightarrow ax_0 equiv 1 pmod b Rightarrow x_0 equiv a^{-1} pmod bax0​+by0​=1⇒ax0​=1−by0​⇒ax0​≡1(modb)⇒x0​≡a−1(modb)

Ta thấy nghiệm xxx của phương trình là nghịch đảo modulo bbb của aaa. Qua đó ta cũng thấy, nghịch đảo modulo chỉ tồn tại khi và chỉ khi (a,b)=1(a, b) = 1(a,b)=1.

Nghịch đảo modulo thường được sử dụng trong những bài toán chia số lớn lấy phần dư, điển hình là các bài toán tính tổ hợp. Chẳng hạn:

Cnk=n!k!×(n−k)!≡n!×(k!×(n−k)!)−1(modM)text{C}^k_n = frac{n!}{k!times (n – k)!} equiv n!times (k!times (n – k)!)^{-1} pmod M Cnk​=k!×(n−k)!n!​≡n!×(k!×(n−k)!)−1(modM)

(Lưu ý rằng công thức trên chỉ đúng nếu k!×(n−k)!k!times (n – k)!k!×(n−k)! nguyên tố cùng nhau với MMM với mọi k,nk, nk,n thoả mãn dữ liệu của đề)

Khi modulo MMM là số nguyên tố, để tiện lợi ta thường dùng định lý Fermat nhỏ để suy ra x−1≡xM−2(modM)x^{-1} equiv x^{M – 2} pmod Mx−1≡xM−2(modM) rồi dùng luỹ thừa nhanh để tính. Còn nếu MMM không nguyên tố, ta lại áp dụng thuật toán Euclid mở rộng để tìm nghịch đảo modulo qua phương trình aγ+My=1agamma + My = 1aγ+My=1.

¶ Bài tập áp dụng

• UVA – Gift Dilemma
• Codeforces – Ebony and Ivory
• Codeforces – Beautiful Numbers
• Codechef – Get AC in one go
• VNOJ – VM 08 Bài 05 – Số nguyên

¶ Tài liệu tham khảo

• Một loạt các bài viết trong mục Fundamentals, CP Algorithms
• Wikipedia (phần chứng minh định lý Lamé và bổ đề Bézout)
• VNOI Wiki, Nghịch đảo Modulo (bài viết cũ)
• Post trên VNOI Forum của anh Tăng Khải Hạnh
• Slide về chủ đề này của thầy Lê Minh Hoàng (chưa tìm được nguồn)