Vì sao chia lấy dư lại tìm được UCLN? Euclid từ phân số đến mật mã

Thuật toán Euclid tìm UCLN qua chuyện chia quà, cắt dây và lát gạch. Hiểu từng phép chia lấy dư rồi xem cách nó giúp xử lý hình ảnh, phân số và tạo khóa RSA.

11 phút đọcCơ bảnEyeBlogs

Đọc bản tiếng Anh →

Bìa ghi: Euclid từ phân số đến mật mã. Bên trái là chân dung nét khắc Euclid đội mũ, râu dài, nhìn xuống, gắn với André Thevet; dùng lại chân dung trong bài Euclid và phương pháp tiên đề. Ảnh thuộc phạm vi công cộng, qua Wikimedia Commons, đã cắt. Đây là hình dung của hậu thế, không phải chân dung xác thực. Bên phải là hình chữ nhật 210 × 78 được lát bằng các hình vuông và đáp án UCLN bằng 6; đồ họa do ALumiEye vẽ.
Mục lục

Giả sử bạn có 210 chiếc kẹo và 78 chiếc bánh để chia thành các túi quà. Túi nào cũng phải có cùng số kẹo, cùng số bánh, và không được thừa món nào. Chia hai túi thì dễ, ba túi cũng được. Nhưng nhiều nhất là bao nhiêu túi, nếu không muốn thử lần lượt từng số?

Đáp án là 6 túi, mỗi túi 35 chiếc kẹo và 13 chiếc bánh. Thuật toán Euclid tìm ước chung lớn nhất (UCLN) cho ra con số ấy chỉ bằng bốn phép chia lấy dư. Cách làm rất ngắn: chia số lớn cho số nhỏ, rồi lấy số nhỏ chia tiếp cho phần dư; cứ thế cho đến khi chia hết [1].

Chuyện chia quà chỉ là một ví dụ minh họa. Cùng cách tính ấy còn trả lời được chuyện cắt dây, lát gạch, rút gọn tỷ lệ khung hình, và góp một bước trong việc tạo khóa mật mã. Trước hết, ta thử làm bằng tay.

Tìm UCLN bằng cách chia tiếp phần còn dư

Cả 210 và 78 đều phải chia hết cho số túi. Sáu túi thỏa điều kiện ấy, vì 210 chia 6 được 35, còn 78 chia 6 được 13. Tên gọi ước chung lớn nhất chỉ đúng số lớn nhất chia hết cả hai số ban đầu.

Ở trường, bạn có thể phân tích hai số thành thừa số nguyên tố rồi tìm phần chung. Euclid không cần bước đó. Ta bắt đầu bằng phép chia 210 cho 78: lấy được hai lần 78, còn dư 54.

Điều cần nhớ là không lấy thương 2 làm đáp án. Ta giữ lại số chia 78 và phần dư 54. Hai số ấy trở thành cặp mới để tiếp tục chia.

Đang có hai số Làm phép chia Giữ lại để tính tiếp
210 và 78 210 chia 78 được 2, dư 54 78 và 54
78 và 54 78 chia 54 được 1, dư 24 54 và 24
54 và 24 54 chia 24 được 2, dư 6 24 và 6
24 và 6 24 chia 6 được 4, dư 0 Dừng, lấy 6

Đến phép chia cuối, 24 chia hết cho 6, nên thuật toán trả về 6, tức số chia ở dòng vừa chia hết. Số dư 0 chỉ báo rằng công việc đã xong, không phải đáp án. Nhưng làm được các phép chia chưa đủ: ta còn phải giải thích vì sao 6 chia hết cả hai số đầu, và không có đáp án nào lớn hơn.

Nếu muốn tự thử, bạn có thể dùng cặp 48 và 18. Lần lượt chia 48 cho 18 được dư 12, chia 18 cho 12 được dư 6, chia 12 cho 6 thì hết. Vẫn là đáp án 6, nhưng không cần đoán trước bất kỳ ước số nào.

Chứng minh toán học: vì sao thuật toán Euclid đúng?

Ta cần chứng minh cho hai số nguyên dương bất kỳ, không chỉ kiểm tra cặp 210 và 78. Gọi chúng là aa và bb, với a≥b>0a\ge b>0. Nếu số thứ nhất nhỏ hơn số thứ hai, ta đổi chỗ trước; các ước chung không thay đổi.

Chia aa cho bb, ta có:

a=bq+r,0≤r<b.a=bq+r,\qquad 0\le r<b.

Ở đây, qq là thương nguyên và rr là số dư. Công thức chỉ viết lại phép chia quen thuộc: số bị chia bằng số chia nhân thương, cộng số dư. Điều phải chứng minh là thay cặp (a,b)(a,b) bằng (b,r)(b,r) không làm đổi UCLN [1] [3].

Bước 1: mọi ước chung của a và b đều là ước chung của b và r

Lấy một ước chung dương bất kỳ dd của aa và bb. Theo định nghĩa chia hết, tồn tại các số nguyên m,nm,n sao cho:

a=dm,b=dn.a=dm,\qquad b=dn.

Nói cách khác, aa và bb đều bằng dd nhân với một số nguyên. Từ phép chia ban đầu, chuyển bqbq sang vế kia rồi thay hai biểu thức trên vào:

r=a−bq=dm−dnq=d(m−nq).r=a-bq=dm-dnq=d(m-nq).

Vì m−nqm-nq là số nguyên, đẳng thức cuối cho thấy rr cũng chia hết cho dd. Mà bb đã chia hết cho dd, nên dd là ước chung của bb và rr.

Ta chọn dd bất kỳ, không giả định nó bằng một con số cụ thể hay đã là ước lớn nhất. Vì vậy kết luận đúng với mọi ước chung của cặp ban đầu.

Bước 2: mọi ước chung của b và r đều là ước chung của a và b

Ngược lại, lấy một ước chung dương bất kỳ dd của bb và rr. Có các số nguyên u,vu,v sao cho:

b=du,r=dv.b=du,\qquad r=dv.

Thay vào a=bq+ra=bq+r, ta được:

a=duq+dv=d(uq+v).a=duq+dv=d(uq+v).

Vì uq+vuq+v là số nguyên, aa chia hết cho dd. Kết hợp với việc bb chia hết cho dd, ta có dd là ước chung của aa và bb.

Bước 1 cho thấy cặp mới không mất ước chung nào của cặp cũ. Bước 2 cho thấy cặp mới cũng không có thêm ước chung nào khác. Hai cặp có đúng cùng tập ước chung dương, nên phần tử lớn nhất của hai tập phải bằng nhau:

gcd⁡(a,b)=gcd⁡(b,r).\boxed{\gcd(a,b)=\gcd(b,r).}

Ký hiệu gcd⁡\gcd là cách viết quốc tế của UCLN. Nếu r=0r=0, lập luận vẫn đúng: mọi số nguyên dương đều chia hết số 0, vì 0=d×00=d\times0.

Bước 3: vì sao lặp lại phép chia vẫn giữ nguyên UCLN?

Gọi hai số ban đầu là a0,b0a_0,b_0. Ở lượt thứ kk, chia aka_k cho bk>0b_k>0 để lấy số dư rkr_k, rồi đặt:

ak+1=bk,bk+1=rk.a_{k+1}=b_k,\qquad b_{k+1}=r_k.

Chỉ số kk đánh số lượt thực hiện; k=0k=0 là cặp ban đầu. Kết quả vừa chứng minh áp dụng cho từng lượt, nên:

gcd⁡(ak,bk)=gcd⁡(ak+1,bk+1).\gcd(a_k,b_k)=\gcd(a_{k+1},b_{k+1}).

Do đó, sau bất kỳ số lượt nào đã thực hiện, UCLN vẫn bằng UCLN của cặp ban đầu. Ta không giả định đáp án của lượt sau đúng; ta đã chứng minh phép chuyển giữa hai lượt giữ nguyên toàn bộ ước chung.

Bước 4: vì sao quá trình chắc chắn dừng?

Theo điều kiện của phép chia có dư:

0≤bk+1=rk<bk.0\le b_{k+1}=r_k<b_k.

Nếu chưa dừng, bk+1b_{k+1} vẫn là số nguyên dương và nhỏ hơn bkb_k ít nhất 1. Vì vậy không thể có vô hạn lượt mà các số chia vẫn dương: chỉ có hữu hạn số nguyên dương không vượt quá b0b_0.

Suy ra sau một số hữu hạn lượt, số thứ hai phải bằng 0. Đây là chứng minh thuật toán luôn dừng, không phải nhận xét dựa trên những lần chạy thử [3].

Bước 5: vì sao số trả về là ước chung lớn nhất?

Khi dừng, cặp hiện tại có dạng (g,0)(g,0) với g>0g>0. Số gg chia hết cả gg và 0, vì:

g=g×1,0=g×0.g=g\times1,\qquad 0=g\times0.

Mặt khác, mọi ước chung dương dd của gg và 0 đều phải là ước của gg. Khi đó g=dtg=dt với một số nguyên dương t≥1t\ge1, nên d≤gd\le g. Như vậy gg là một ước chung và không ước chung nào lớn hơn nó:

gcd⁡(g,0)=g.\gcd(g,0)=g.

Kết hợp với việc UCLN không đổi qua mọi lượt, ta có:

gcd⁡(a0,b0)=gcd⁡(g,0)=g.\boxed{\gcd(a_0,b_0)=\gcd(g,0)=g.}

Vậy thuật toán dừng và trả về đúng UCLN của mọi cặp số nguyên dương ban đầu. Với cặp trong bảng, g=6g=6 chỉ là trường hợp áp dụng của kết quả tổng quát này, không phải căn cứ thay cho chứng minh.

Ba chuyện quen thuộc hóa ra cùng một phép tính

Chia quà: tìm số phần nhiều nhất

Trở lại 210 chiếc kẹo và 78 chiếc bánh. Sáu túi là nhiều nhất nếu mọi túi giống nhau và dùng hết cả hai loại. Bốn túi không được, vì 78 chiếc bánh không chia đều cho 4. Mười ba túi cũng không được, vì kẹo sẽ bị lẻ.

Có thể chia ít hơn sáu túi, chẳng hạn hai hoặc ba. UCLN trả lời chữ “nhiều nhất”, không khẳng định đó là cách chia duy nhất. Nếu mỗi túi không cần giống nhau, hoặc được phép để thừa, ta đã có một bài toán khác.

Lát gạch: tìm viên vuông lớn nhất không phải cắt

Giả sử một tấm bìa hình chữ nhật rộng 210 cm, cao 78 cm. Ta muốn chia nó thành các ô vuông bằng nhau, xếp theo hàng và cột, không thừa mép. Cạnh ô lớn nhất cũng là 6 cm: chiều rộng vừa 35 ô, chiều cao vừa 13 ô.

Có thể nhìn thuật toán bằng cách đặt những hình vuông lớn vào trước. Hai hình cạnh 78 phủ được phần lớn tấm bìa, còn lại hình chữ nhật 54 × 78. Đặt tiếp một hình cạnh 54, rồi hai hình cạnh 24, cuối cùng là bốn hình cạnh 6.

Hình chữ nhật 210 × 78 được phủ lần lượt bằng hai hình vuông cạnh 78, một hình cạnh 54, hai hình cạnh 24 và bốn hình cạnh 6. Bên phải là bốn phép chia lấy dư tương ứng.
Hình 1. Mỗi phần còn trống tương ứng với một phần dư. Hình dùng các ô lớn nhỏ khác nhau để tìm đáp án; sau khi biết cạnh 6, có thể chia toàn bộ tấm bìa thành các ô vuông cạnh 6. Hình đúng tỷ lệ, được tạo bằng đoạn Python gần cuối bài.

Đừng nhầm các ô lớn nhỏ trong hình với loại gạch cuối cùng. Chúng là các bước tìm kiếm. Đáp án là cạnh ô vuông bằng nhau lớn nhất có thể dùng cho toàn bộ tấm bìa. Nếu lát nền thật, còn phải tính mạch vữa, kích thước gạch bán sẵn và sai số thi công.

Hai nhịp lặp: bao giờ lại gặp nhau?

Giả sử hai đèn cùng sáng lúc đầu. Đèn thứ nhất nháy sau mỗi 12 giây, đèn thứ hai sau mỗi 18 giây. Khi nào chúng cùng nháy lại?

Đèn thứ nhất nháy ở giây 12, 24, 36. Đèn thứ hai nháy ở giây 18, 36. Chúng gặp lại ở giây 36. Đây là bội chung nhỏ nhất, tức mốc dương sớm nhất chứa trọn cả hai chu kỳ.

UCLN giúp tính mốc ấy mà không cần viết hết danh sách: lấy 12 × 18 rồi chia cho UCLN của 12 và 18. Vì UCLN là 6, kết quả là 36 giây [3]. Một câu hỏi tìm “phần chung lớn nhất” đã giúp giải câu hỏi tìm “lần gặp sớm nhất”.

Điều kiện cùng bắt đầu rất quan trọng. Nếu hai đèn lệch nhau từ đầu, không thể áp dụng nguyên phép tính trên rồi kết luận chúng sẽ gặp lại sau 36 giây. Ví dụ này chỉ xét hai nhịp đều và cùng mốc xuất phát.

Máy tính dùng UCLN vào việc gì?

Những chuyện trên giúp nhận ra dạng bài toán. Trong phần mềm, cùng nhu cầu xuất hiện khi cần đưa hai con số về một tỷ lệ gọn, hoặc làm việc với phép tính chỉ giữ phần dư.

Nhận ra hai khung hình có cùng tỷ lệ

Một ảnh rộng 1.920 pixel, cao 1.080 pixel có tỷ lệ bao nhiêu? Có thể giữ nguyên cặp số ấy, nhưng 16:9 dễ hiểu và dễ so sánh hơn. Để tìm ra nó, lấy UCLN của 1.920 và 1.080 là 120, rồi chia cả hai cho 120.

Nếu một công cụ xử lý ảnh cần kiểm tra hai kích thước có cùng tỷ lệ, nó có thể rút gọn từng cặp trước. Khung 1.280 × 720 cũng rút về 16:9, còn 1.080 × 1.080 rút về 1:1. Nhờ vậy, chương trình biết khi nào đổi kích thước giữ được hình, khi nào phải cắt mép hoặc thêm viền.

Đây là cách có thể triển khai một bước kiểm tra tỷ lệ, không phải khẳng định mọi phần mềm ảnh đều làm như vậy. UCLN chỉ rút gọn các kích thước; nó không tự quyết định cắt chỗ nào cho đẹp, cũng không làm ảnh nét hơn.

Tính phân số mà không đổi ngay sang số thập phân

Một phần mềm tính toán có thể giữ 210/78 dưới dạng hai số nguyên, rồi rút gọn thành 35/13. Nhờ đó, nó vẫn giữ chính xác phân số, thay vì thay bằng một số thập phân làm tròn.

Đây là ứng dụng có sẵn trong Python: thư viện fractions dùng hàm math.gcd để chuẩn hóa tử và mẫu [8]. Sau mỗi phép cộng hay nhân phân số, việc rút gọn giúp bỏ những thừa số chung không cần giữ lại. Nó giống thu gọn một công thức nấu ăn từ “hai cốc cho bốn người” thành “một cốc cho hai người”, không làm đổi tỷ lệ.

Không phải mọi phép tính tiền hay đo đạc đều nên dùng phân số. Cách lưu số phải phù hợp với bài toán. Ví dụ này chỉ cho thấy một phép tính học ở trường vẫn có công việc cụ thể trong thư viện phần mềm.

Tạo khóa mật mã: tìm phép nhân có thể hoàn tác

Trên đồng hồ 12 giờ, đi thêm 12 giờ thì quay về chỗ cũ. Máy tính cũng có kiểu tính tương tự: sau khi nhân, chỉ giữ phần dư khi chia cho một số đã chọn. Cách tính trên vòng ấy được gọi là số học đồng dư.

Lấy một vòng có 43 vị trí. Nhân với 17, rồi nhân tiếp với 38, sẽ đưa mọi vị trí về chỗ ban đầu nếu sau mỗi lần đều lấy dư cho 43. Lý do nằm ở phép tính nhỏ này: 17 × 38 = 646 = 15 × 43 + 1. Đi 15 vòng rồi thêm 1 bước cũng như chỉ thêm 1 bước.

Số 38 là một nghịch đảo, nghĩa là thao tác hoàn tác phép nhân với 17 trên vòng đang xét. Euclid kiểm tra xem phép hoàn tác ấy có tồn tại không: hai số 17 và 43 phải có UCLN bằng 1. Bản Euclid mở rộng còn tìm được chính số 38, bằng cách giữ thêm thông tin từ các lượt chia [4] [5].

Khi tạo khóa RSA, người tạo khóa cần một phép nghịch đảo cùng loại để tính số mũ bí mật từ những thông tin họ đã chọn [6]. Các số thật lớn hơn rất nhiều, nhưng nhu cầu vẫn là tìm một thao tác đảo ngược phù hợp. Bài RSA và chữ ký số trong JWT kể tiếp cách cặp khóa được dùng để ký và kiểm tra thông điệp.

Vì sao cách tính này mang tên Euclid?

Khoảng năm 300 trước Công nguyên, công trình của Euclid đã trình bày cách tìm độ đo chung lớn nhất trong Elements, thường gọi là Cơ sở [1] [3]. Trong cách viết cổ, người đọc bớt số nhỏ khỏi số lớn nhiều lần. Phép chia lấy dư gộp những lần trừ ấy thành một lượt.

Đó cũng là lý do không nên hình dung đây là một mẹo mới dành riêng cho máy tính. Máy tính dùng lại một cách tổ chức phép tính đã có từ lâu. Tuy nhiên, không có đủ tư liệu để kể một ngày cụ thể Euclid nghĩ ra nó; thuật toán có thể có nguồn gốc sớm hơn [2] [3].

Bài Euclid và phương pháp tiên đề theo một ý khác của cùng bộ sách: lập luận toán học bắt đầu từ đâu. Còn ở đây, điều cần nhớ chỉ là một thói quen làm việc: xử lý phần đã chia được, rồi tiếp tục với phần dư. Chân dung trên bìa là hình dung của hậu thế, không phải ảnh xác thực của Euclid [7].

Tự tay chạy Euclid và vẽ tấm bìa

Nếu muốn thử trên máy, đoạn Python dưới đây làm đúng bốn phép chia trong bài và tạo ra Hình 1. Phần tìm UCLN nằm trong vòng while: divmod cho thương và số dư, còn a, b = b, r chuyển sang cặp số tiếp theo. Phần còn lại chỉ để vẽ.

Cần matplotlib. Chạy từ thư mục bạn muốn chứa images/. Dữ liệu cố định, không có yếu tố ngẫu nhiên. Nếu không quan tâm lập trình, bạn có thể bỏ qua mục này; các ví dụ phía trên đã đủ để dùng thuật toán bằng tay.

euclid.py
from pathlib import Path
from math import gcd
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle
def euclid(a, b):
# Giữ số chia và phần dư cho lượt tiếp theo.
a, b = abs(a), abs(b)
steps = []
while b:
q, r = divmod(a, b)
steps.append((a, b, q, r))
a, b = b, r
return a, steps
a, b = 210, 78
result, steps = euclid(a, b)
assert result == gcd(a, b) == 6
for u, v, q, r in steps:
print(f"{u} = {q} × {v} + {r}")
print(f"UCLN = {result}; số phép chia = {len(steps)}")
plt.rcParams.update({"font.family": "DejaVu Sans", "font.size": 12})
fig, (ax, notes) = plt.subplots(1, 2, figsize=(12, 5.2),
gridspec_kw={"width_ratios": [1.7, 1]})
fig.patch.set_facecolor("#fcfcfb")
x = y = 0
w, h = a, b
while w and h:
side = min(w, h)
ax.add_patch(Rectangle((x, y), side, side, facecolor="#dce7ed",
edgecolor="#303c45", linewidth=1.4))
if side >= 24:
ax.text(x + side / 2, y + side / 2, str(side),
ha="center", va="center", color="#17242e", fontsize=14)
if w >= h:
x, w = x + side, w - side
else:
y, h = y + side, h - side
ax.set(xlim=(-4, a + 4), ylim=(-4, b + 4), aspect="equal")
ax.invert_yaxis()
ax.axis("off")
ax.set_title("Hình chữ nhật 210 × 78", color="#17242e", pad=18)
notes.axis("off")
notes.text(0, 0.85, "Mỗi dòng là một phép chia", color="#17242e", weight="bold")
for i, (u, v, q, r) in enumerate(steps):
notes.text(0, 0.69 - i * 0.14, f"{u} = {q} × {v} + {r}", color="#17242e")
notes.text(0, 0.05, "Bốn ô nhỏ nhất có cạnh 6.\nUCLN(210, 78) = 6.",
color="#17242e", linespacing=1.8)
fig.tight_layout(pad=2)
output = Path("images/thuat-toan-euclid/lat-hinh-euclid.png")
output.parent.mkdir(parents=True, exist_ok=True)
fig.savefig(output, dpi=170, facecolor=fig.get_facecolor())
plt.close(fig)

Kết quả chạy:

210 = 2 × 78 + 54
78 = 1 × 54 + 24
54 = 2 × 24 + 6
24 = 4 × 6 + 0
UCLN = 6; số phép chia = 4

Trong ứng dụng chỉ cần đáp án, có thể gọi trực tiếp math.gcd. Hàm minh họa giữ lại các phép chia để ta nhìn thấy quá trình. Phần vẽ dùng riêng hai cạnh dương 210 và 78; muốn đổi hình, bạn cần sửa cả kích thước lẫn nhãn.

Quay lại những túi quà

Sáu túi quà, mỗi túi 35 chiếc kẹo và 13 chiếc bánh. Đáp án không cần một danh sách dài những cách chia thử. Ta chỉ chia, giữ phần dư, rồi chia tiếp.

Khi đổi từ túi quà sang tấm bìa hay tỷ lệ khung hình, tên gọi của việc cần làm thay đổi. Nhưng câu hỏi bên dưới vẫn quen thuộc: hai số này có phần chung lớn nhất là bao nhiêu? Thuật toán Euclid giúp trả lời bằng một chuỗi phép chia ngắn, thay vì phải biết trước mọi thừa số của chúng.

Vẽ minh họa hình học miễn phí cho học sinh và giáo viên: EyeViz.

Tài liệu tham khảo

  1. [1]Euclid; bản tiếng Anh và chú giải của David E. Joyce. Elements, Book VII, Proposition 2. Clark University.
  2. [2]J. J. O’Connor và E. F. Robertson. Euclid of Alexandria. MacTutor History of Mathematics, University of St Andrews.
  3. [3]Euclidean algorithm for computing the greatest common divisor. CP-Algorithms.
  4. [4]Extended Euclidean Algorithm. CP-Algorithms.
  5. [5]Modular Multiplicative Inverse. CP-Algorithms.
  6. [6]RSA Algorithm. DI Management Services.
  7. [7]Chân dung Euclid, André Thevet. Wikimedia Commons.
  8. [8]fractions: Rational numbers. Python documentation.