Wikipedia

Giải thuật Euclid

(Đổi hướng từ Thuật toán Euclid)

Trong toán học, giải thuật Euclid[gc 1] (hay thuật toán Euclid) là một giải thuật để tính ước chung lớn nhất (ƯCLN) của hai số nguyên, là số lớn nhất có thể chia được bởi hai số nguyên đó với số dư bằng không. Giải thuật này được đặt tên theo nhà toán học người Hy Lạp cổ đại Euclid, người đã viết nó trong bộ Cơ sở của ông (khoảng năm 300 TCN). Nó là một ví dụ về thuật toán, một chuỗi các bước tính toán theo điều kiện nhất định và là một trong số những thuật toán lâu đời nhất được sử dụng rộng rãi.

Thuật toán Euclid để tìm ước chung lớn nhất (ƯCLN) của hai đoạn thẳng BA và DC, độ dài của cả hai đều là bội của một "đơn vị" độ dài chung. Vì độ dài của DC ngắn hơn nên nó được dùng để "đo" BA, nhưng chỉ được một lần do phần còn lại là đoạn EA ngắn hơn DC. Bây giờ EA lại được dùng để đo độ dài đoạn DC hai lần. Cuối cùng đoạn FC được dùng để đo độ dài đoạn EA ba lần. Vì không còn đoạn nào dư ra nên quá trình này kết thúc với FC trở thành ƯCLN. Bên phải là ví dụ của Nicomachus với hai số 49 và 21 có kết quả ƯCLN là 7.

Giải thuật Euclid dựa trên nguyên tắc là ước chung lớn nhất của hai số nguyên không thay đổi khi thay số lớn hơn bằng hiệu của nó với số nhỏ hơn. Chẳng hạn, 21 là ƯCLN của 252 và 105 (vì 252 = 21 × 12 và 105 = 21 × 5) và cũng là ƯCLN của 105 và 252 − 105 = 147. Khi lặp lại quá trình trên thì hai số trong cặp số ngày càng nhỏ đến khi chúng bằng nhau, và khi đó chúng là ƯCLN của hai số ban đầu. Bằng cách đảo ngược lại các bước, ƯCLN này có thể được biểu diễn thành tổng của hai số hạng, mỗi số hạng bằng một trong hai số đã cho nhân với một số nguyên dương hoặc âm (đồng nhất thức Bézout), chẳng hạn, 21 = 5 × 105 + (−2) × 252.

Dạng ban đầu của giải thuật như trên có thể tốn nhiều bước thực hiện phép trừ để tìm ƯCLN nếu một trong hai số lớn hơn rất nhiều so với số còn lại. Một dạng khác của giải thuật rút ngắn lại các bước này, thay vào đó thế số lớn hơn bằng số dư của nó khi chia cho số nhỏ hơn (dừng lại khi số dư bằng không). Dạng thuật toán này chỉ tốn số bước nhiều nhất là năm lần số chữ số của số nhỏ hơn trên hệ thập phân. Gabriel Lamé chứng minh được điều này vào năm 1844, đánh dấu sự ra đời của lý thuyết độ phức tạp tính toán. Nhiều phương pháp khác để tăng hiệu quả của thuật toán cũng đã được phát triển trong thế kỷ 20.

Giải thuật Euclid có rất nhiều ứng dụng trong lý thuyết và thực tế. Nó được dùng để rút gọn phân số về dạng tối giản và thực hiện phép chia trong số học module. Thuật toán cũng là một thành phần then chốt trong giao thức mật mã để bảo mật kết nối Internet và được dùng để phá vỡ hệ thống mật mã này qua phân tích số nguyên. Nó cũng được áp dụng để giải phương trình Diophantine, chẳng hạn như tìm một số thỏa mãn nhiều biểu thức đồng dư theo định lý số dư Trung Quốc, để xây dựng liên phân số hay tìm xấp xỉ gần đúng nhất cho số thực. Cuối cùng, nó là công cụ cơ bản để chứng minh nhiều định lý trong lý thuyết số như định lý bốn số chính phương của Lagrange và tính duy nhất của phân tích số nguyên ra thừa số nguyên tố. Thuật toán Euclid ban đầu chỉ được giới hạn về số tự nhiên và độ dài hình học (số thực), nhưng đến thế kỷ 19 đã được mở rộng cho nhiều dạng số khác như số nguyên Gauss và đa thức một biến, dẫn đến các khái niệm về đại số trừu tượng như miền Euclid.

Ý tưởng

sửa
Bài chi tiết: Ước số chung lớn nhất

Giải thuật Euclid dùng để tính ước chung lớn nhất (ƯCLN) của hai số tự nhiên a và b. Ước chung lớn nhất g là số lớn nhất chia được bởi cả a và b mà không để lại số dư và được ký hiệu là ƯCLN(a, b) hoặc (a, b).[1]

Nếu ƯCLN(a, b) = 1 thì a và b được gọi là hai số nguyên tố cùng nhau.[2] Tính chất này không khẳng định a và b là số nguyên tố.[3] Chẳng hạn, 6 và 35 đều không phải là số nguyên tố vì chúng đều có thể được phân tích thành tích của các thừa số nguyên tố: 6 = 2 × 3 và 35 = 5 × 7. Tuy nhiên, 6 và 35 nguyên tố cùng nhau vì chúng không có một thừa số chung nào.

 
Một hình chữ nhật kích thước 24 × 60 được chia thành 10 hình vuông nhỏ cạnh 12, trong đó 12 là ƯCLN của 24 và 60. Tổng quát hơn, một hình chữ nhật kích thước a × b có thể được chia thành các hình vuông cạnh c khi và chỉ khi c là ước chung của a và b.

Gọi g = ƯCLN(a, b). Vì a và b đều là bội của g nên chúng có thể được viết thành a = mg và b = ng, và không tồn tại số G > g nào để các biểu thức trên đúng. Hai số tự nhiên m và n phải nguyên tố cùng nhau vì không thể phân tích bất kỳ thừa số chung nào lớn hơn 1 từ m và n để g lớn hơn. Do đó, một số c bất kỳ được chia bởi a và b cũng được chia bởi g. Ước chung lớn nhất g của a và b là ước chung (dương) duy nhất của chúng có thể chia được bởi một ước chung c bất kỳ.[4]

ƯCLN có thể được minh họa như sau.[5] Xét một hình chữ nhật có kích thước là a × b và một ước chung c bất kỳ có thể chia được hết cả a và b. Cả hai cạnh của hình chữ nhật có thể được chia thành các đoạn thẳng bằng nhau có độ dài là c để chia hình chữ nhật thành các hình vuông có cạnh bằng c. Ước chung lớn nhất g chính là giá trị lớn nhất của c để điều này có thể xảy ra. Chẳng hạn, một hình chữ nhật có kích thước 24 × 60 có thể được chia thành các hình vuông có cạnh là 1, 2, 3, 4, 6 hoặc 12, nên 12 là ước chung lớn nhất của 24 và 60, tức là hình chữ nhật trên có hai hình vuông nằm trên một cạnh (24/12 = 2) và năm hình vuông nằm trên cạnh còn lại (60/12 = 5).

Ước chung lớn nhất của hai số a và b là tích của các thừa số nguyên tố chung của hai số đã cho, trong đó một thừa số có thể được nhân lên nhiều lần, chỉ khi tích của các thừa số đó chia được cả a và b.[6] Chẳng hạn, ta phân tích được 1386 = 2 × 3 × 3 × 7 × 11 và 3213 = 3 × 3 × 3 × 7 × 17 nên ước chung lớn nhất 1386 và 3213 bằng 63 = 3 × 3 × 7 (là tích của các thừa số nguyên tố chung). Nếu hai số không có một thừa số nguyên tố chung nào thì ước chung lớn nhất của chúng bằng 1 (một trường hợp của tích rỗng), hay nói cách khác chúng nguyên tố cùng nhau. Một ưu điểm quan trọng của giải thuật Euclid là nó có thể tính được ƯCLN đó mà không cần phân tích ra thừa số nguyên tố.[7][8] Bài toán phân tích các số nguyên lớn là rất khó và tính bảo mật của nhiều giao thức mật mã phổ biến được dựa trên tính chất này.[9]

Một định nghĩa khác của ƯCLN rất hữu ích trong toán cao cấp, đặc biệt là lý thuyết vành.[10] Ước chung lớn nhất g của hai số a và b khác không là tổ hợp tuyến tính tích phân nhỏ nhất, tức là số nhỏ nhất với dạng ua + vb với u và v là số nguyên. Tập hợp tất cả các tổ hợp tuyến tính tích phân của a và b thực chất giống với tập hợp tất cả các bội của g (mg với m là số nguyên). Trong ngôn ngữ toán học hiện đại, ideal tạo bởi a và b chính là ideal tạo bởi g (một ideal tạo bởi một phần tử duy nhất được gọi là ideal chủ yếu và tất cả ideal của số nguyên đều là ideal chủ yếu). Từ đó, một số tính chất của ƯCLN có thể được nhận ra dễ dàng hơn, ví dụ như bất kỳ ước chung nào của a và b cũng chia được bởi ƯCLN (cả hai số hạng trong ua + vb). Tính thống nhất của định nghĩa này với các định nghĩa khác được mô tả dưới đây.

ƯCLN của ba số trở lên bằng tích của các thừa số nguyên tố chung của cả ba số đã cho,[11] nhưng nó cũng có thể được tính bằng cách tìm ƯCLN của từng cặp số trong ba số đó.[12] Chẳng hạn,

ƯCLN(a, b, c) = ƯCLN(a, ƯCLN(b, c)) = ƯCLN(ƯCLN(a, b), c) = ƯCLN(ƯCLN(a, c), b).

Vì vậy, giải thuật Euclid, vốn dùng để tính ƯCLN của hai số nguyên cũng có thể được áp dụng để tính ƯCLN của một số lượng số nguyên bất kỳ.

Mô tả

sửa

Thuật toán

sửa

Giải thuật Euclid gồm một dãy các bước mà trong đó, đầu ra của mỗi bước là đầu vào của bước kế tiếp. Gọi k là số nguyên dùng để đếm số bước của thuật toán, bắt đầu từ số không (khi đó bước đầu tiên tương ứng với k = 0, bước tiếp theo là k = 1,...)

Mỗi bước bắt đầu với hai số dư không âm rk−1 và rk−2. Vì thuật toán giúp đảm bảo số dư luôn giảm dần theo từng bước nên rk−1 nhỏ hơn rk−2. Mục tiêu của bước thứ k là tìm thương qk và số dư rk thỏa mãn phương trình

 

và 0 ≤ rk < rk−1. Nói cách khác, từ số lớn hơn rk−2, trừ đi bội của số nhỏ hơn rk−1 đến khi phần dư rk nhỏ hơn rk−1.

Ở bước đầu tiên (k = 0), số dư r−2 và r−1 bằng a và b, hai số cần tìm ƯCLN. Đến bước kế tiếp (k = 1), hai số dư lần lượt bằng b và số dư r0 ở bước đầu tiên,... Do đó, thuật toán có thể được viết thành một dãy các phương trình

 

Nếu a nhỏ hơn b thì thuật toán đảo ngược vị trí của hai số. Chẳng hạn, nếu a < b thì thương q0 bằng không và số dư r0 bằng a. Do đó, rk luôn nhỏ hơn rk−1 với mọi k ≥ 0.

Vì các số dư luôn giảm dần theo từng bước nhưng không thể là số âm nên số dư sau cùng rN phải bằng không và thuật toán dừng lại tại đó.[13] Số dư khác không cuối cùng rN−1 chính là ước chung lớn nhất của a và b. Số N không thể là vô hạn vì chỉ có một số lượng hữu hạn các số nguyên dương nằm giữa số dư ban đầu r0 và số không.

Chứng minh tính đúng đắn

sửa

Tính đúng đắn của giải thuật Euclid có thể được chứng minh qua hai bước lập luận.[14] Bước thứ nhất, cần chứng minh số dư khác không cuối cùng rN−1 chia được cả a và b. Vì rN−1 là một ước chung nên nó phải nhỏ hơn hoặc bằng với ước chung lớn nhất g. Bước thứ hai, cần chứng minh rằng bất kỳ ước chung nào của a và b, trong đó có g cần phải chia được rN−1; từ đó, g phải nhỏ hơn hoặc bằng rN−1. Hai kết luận trên là mâu thuẫn trừ khi rN−1 = g.

Để chứng tỏ rN−1 chia được cả a và b, cần biết rN−1 chia được số dư liền trước rN−2:

rN−2 = qN rN−1

vì số dư cuối cùng rN bằng không. rN−1 cũng chia được số dư rN−3:

rN−3 = qN−1 rN−2 + rN−1

vì nó chia được cả hai số hạng trong vế phải của phương trình. Chứng minh tương tự, rN−1 cũng chia được tất cả số dư liền trước nó kể cả a và b. Không có số dư liền trước rN−2, rN−3,... chia bởi a và b cho số dư bằng không. Vì rN−1 là ước chung của a và b nên rN−1 ≤ g.

Trong bước thứ hai, một số tự nhiên c bất kỳ chia được cả a và b (là ước chung của a và b) cũng chia được số dư rk. Theo định nghĩa thì a và b có thể được viết thành bội của c: a = mc và b = nc với m và n là các số tự nhiên. Ta có r0 = a − q0b = mc − q0nc = (m − q0n)c nên c là một ước của số dư ban đầu r0. Chứng minh như bước thứ nhất, ta thấy c cũng là ước của các số dư liền sau r1, r2,... Từ đó, ước chung lớn nhất g là ước của rN−1 hay g ≤ rN−1. Kết hợp hai kết luận thu được, ta có g = rN−1. Vậy g là ước chung lớn nhất của tất cả cặp số liền sau:[15][16]

g = ƯCLN(a, b) = ƯCLN(b, r0) = ƯCLN(r0, r1) = … = ƯCLN(rN−2, rN−1) = rN−1.

Ví dụ

sửa
 
Hình ảnh động minh họa giải thuật Euclid qua phép trừ. Hình chữ nhật ban đầu có hai cạnh a = 1071 và b = 462. Đặt vào đó các hình vuông kích thước 462 × 462 thì còn lại hình chữ nhật 462 × 147. Tiếp tục đặt vào hình chữ nhật đó các hình vuông 147 × 147 đến khi còn lại hình chữ nhật 21 × 147. Cuối cùng, đặt vào phần hình còn lại đó các hình vuông 21 × 21 thì không còn chỗ trống nào. Cạnh của hình vuông nhỏ nhất, 21, chính là ƯCLN của 1071 và 462.

Áp dụng giải thuật Euclid để tính ƯCLN của a = 1071 và b = 462. Đầu tiên, ta trừ bội của 462 từ 1071 thì được thương q0 = 2 và số dư là 147:

1071 = 2 × 462 + 147.

Tiếp tục trừ bội của 147 từ 462 thì được thương q1 = 3 và số dư là 21:

462 = 3 × 147 + 21.

Tiếp tục trừ bội của 21 từ 147 thì được thương q2 = 7 và số dư là 0:

147 = 7 × 21 + 0.

Vì số dư cuối cùng bằng 0 nên thuật toán kết thúc với 21 là ƯCLN của 1071 và 462, bằng với ƯCLN có được từ phép phân tích ra thừa số nguyên tố như trên. Các bước được tóm tắt thành bảng sau:

Bước k Phương trình Thương và số dư
0 1071 = q0 462 + r0 q0 = 2 và r0 = 147
1 462 = q1 147 + r1 q1 = 3 và r1 = 21
2 147 = q2 21 + r2 q2 = 7 và r2 = 0; kết thúc

Minh họa

sửa

Giải thuật Euclid có thể được minh họa dựa vào bài toán hình chữ nhật tương tự như trên.[17] Giả sử ta cần dùng hình vuông để lấp đầy một hình chữ nhật có kích thước là a × b với a là số lớn hơn. Đầu tiên, ta đặt các hình vuông b × b lên trên đó thì còn lại phần hình trống là một hình chữ nhật b × r0 với r0 < b. Tiếp theo, ta đặt các hình vuông r0 × r0 lên phần hình trống đó thì còn lại phần hình trống thứ hai r1 × r0 mà ta cần phải đặt lên đó các hình vuông r1 × r1,... Toàn bộ quá trình chỉ kết thúc khi không còn phần hình trống nào, và khi đó, độ dài cạnh hình vuông nhỏ nhất chính là ƯCLN của độ dài hai cạnh hình chữ nhật ban đầu. Chẳng hạn, hình vuông nhỏ nhất trong hình bên là 21 × 21 (màu đỏ), và 21 là ƯCLN của 1071 và 462, độ dài hai cạnh của hình chữ nhật ban đầu (màu xanh lá).

Phép chia có dư

sửa
Bài chi tiết: Phép chia có dư

Tại mỗi bước k, giải thuật Euclid tính một thương qk và số dư rk từ hai số rk−1 và rk−2:

rk−2 = qk rk−1 + rk

trong đó rk không âm và nhỏ hơn giá trị tuyệt đối của rk−1. Định lý làm nền tảng cho phép chia có dư cho thấy luôn tồn tại duy nhất một thương và số dư như vậy.[18]

Trong dạng ban đầu của giải thuật, thương và số dư được tìm bằng cách lặp lại phép trừ, nghĩa là trừ rk−1 từ rk−2 và lặp lại đến khi phần dư rk nhỏ hơn rk−1, sau đó hoán đổi chúng cho nhau rồi lại lặp lại quá trình này. Phép chia có dư hiệu quả hơn nhiều khi giảm đi số bước giữa hai hoán đổi còn một bước duy nhất. Hơn nữa, ta còn có thể thay phép chia có dư bằng phép toán modulo, vốn chỉ cho kết quả số dư. Như vậy, dạng lặp của giải thuật Euclid trở thành

rk = rk−2 mod rk−1.

Chương trình

sửa

Giải thuật Euclid có thể được biểu diễn bằng mã giả. Chẳng hạn, dạng phép chia của nó có thể được lập trình thành[19] 

function gcd(a, b)
    while b ≠ 0
        t:= b
        b:= a mod b
        a:= t
    return a

Ở đầu vòng lặp k, biến b mang giá trị số dư rk−1, trong khi biến a mang giá trị số dư liền trước rk−2. Bước b := a mod b giống với công thức đệ quy như trên rk ≡ rk−2 mod rk−1. Biến tạm thời t mang giá trị rk−1 khi tính số dư liền sau rk. Cuối vòng lặp, biến b mang giá trị rk, trong khi biến a mang giá trị số dư liền trước rk−1.

Trong dạng phép trừ (dạng ban đầu của thuật toán), bước b := a mod b được thay bằng phép trừ lặp lại.[20] Trái ngược với dạng phép chia cho phép đầu vào là một số nguyên bất kỳ, dạng phép trừ chỉ cho phép đầu vào là một số nguyên dương và dừng lại khi a = b: 

function gcd(a, b)
    while a ≠ b 
        if a > b
            a:= a − b
        else
            b:= b − a
    return a

Biến a và b luân phiên mang giá trị của các số dư liền trước rk−1 và rk−2. Giả sử a > b ở đầu một vòng lặp thì a bằng rk−2 vì rk−2 > rk−1. Trong vòng lặp, a được trừ đi bởi bội của số dư liền trước b đến khi a nhỏ hơn b, khi đó a trở thành số dư liền sau rk. Sau đó, b được trừ đi bởi bội của a đến khi nó nhỏ hơn a và phần còn lại trở thành số dư rk+1,...

Dạng đệ quy dựa trên tính chất ƯCLN của các cặp số dư liên tiếp là bằng nhau và điều kiện dừng lại là ƯCLN(rN−1, 0) = rN−1.[21] 

function gcd(a, b)
    if b = 0
        return a
    else
        return gcd(b, a mod b)

Sử dụng dạng này, ƯCLN(1071, 462) được tính từ ƯCLN(462, 1071 mod 462) = ƯCLN(462, 147). ƯCLN sau cùng được tính từ ƯCLN(147, 462 mod 147) = ƯCLN(147, 21), vốn được tính từ ƯCLN(21, 147 mod 21) = ƯCLN(21, 0) = 21.

Phương pháp số dư tuyệt đối nhỏ nhất

sửa

Trong một dạng khác của giải thuật Euclid, thương thu được qua mỗi bước được tăng thêm 1 đơn vị nếu giá trị tuyệt đối của phần dư âm nhỏ hơn so với giá trị tuyệt đối của phần dư dương.[22][23] Điều kiện của phương trình

rk−2 = qk rk−1 + rk

là |rk−1| > rk > 0. Tuy nhiên, có thể tính số dư âm ek bởi

rk−2 = (qk + 1) rk−1 + ek

nếu rk−1 > 0 hoặc

rk−2 = (qk − 1) rk−1 + ek

nếu rk−1 < 0.

Nếu thay rk bằng ek với |ek| < |rk| thì ta có một dạng khác của giải thuật Euclid sao cho trong mỗi bước,

|rk| ≤ |rk−1| / 2.

Leopold Kronecker chứng minh được rằng dạng này tốn số bước ít nhất trong tất cả các dạng của giải thuật Euclid.[22][23] Tổng quát hơn, người ta chứng minh được rằng với mọi số đầu vào a và b, số bước tính ƯCLN là nhỏ nhất khi và chỉ khi qk được chọn sao cho   với   là tỷ lệ vàng.[24]

Lịch sử phát triển

sửa
 
Giải thuật Euclid có thể đã xuất hiện từ trước thời của Euclid, người đang cầm com-pa trong một tranh vẽ khoảng năm 1474.

Giải thuật Euclid là một trong những thuật toán lâu đời nhất được sử dụng rộng rãi.[25] Nó xuất hiện trong bộ Cơ sở của Euclid (khoảng 300 TCN), đặc biệt là ở cuốn 7 (mệnh đề 1–2) và cuốn 10 (mệnh đề 2–3). Trong cuốn 7, thuật toán được phát biểu cho số nguyên, còn trong cuốn 10, nó được phát biểu cho độ dài của đoạn thẳng. (Ngày nay, ta có thể nói thuật toán được phát biểu cho số thực. Nhưng độ dài, diện tích và thể tích, vốn được đo bằng số thực trong thời kỳ hiện đại, lại không có cùng đơn vị đo và cũng không có đơn vị đo tự nhiên nào cho chúng; người xưa lúc bấy giờ vẫn chưa hiểu rõ khái niệm số thực.) Thuật toán trong cuốn 10 mang tính hình học: ƯCLN của hai độ dài a và b là độ dài lớn nhất g có thể làm đơn vị đo chung cho a và b; nói cách khác, độ dài a và b là bội số của độ dài g.

Có lẽ giải thuật trên không phải do Euclid trực tiếp tìm ra (ông là người đã sưu tầm các công trình của các nhà toán học khác và tổng hợp lại trong bộ Cơ sở).[26][27] Nhà toán học và sử học B. L. van der Waerden cho rằng cuốn 7 xuất phát từ một cuốn sách giáo khoa về lý thuyết số được viết bởi các nhà toán học trong trường của Pythagoras.[28] Giải thuật có thể đã được biết bởi Eudoxus của Cnidus (khoảng 375 TCN),[25][29] hoặc thậm chí có thể đã có từ trước thời của ông,[30][31] dựa trên thuật ngữ ἀνθυφαίρεσις (anthyphairesis, phép trừ nghịch đảo) trong một số công trình của Euclid và Aristotle.[32]

Nhiều thế kỷ sau, giải thuật Euclid được tìm ra một cách độc lập tại Ấn Độ và Trung Quốc,[33] chủ yếu để giải phương trình Diophantine vốn nảy sinh trong thiên văn học và làm lịch chính xác. Vào cuối thế kỷ 5, nhà toán học và thiên văn người Ấn Độ Aryabhata đã gọi giải thuật là một "máy nghiền",[34] có thể là vì tính hiệu quả của nó trong việc giải phương trình Diophantine.[35] Mặc dù một trường hợp đặc biệt của định lý số dư Trung Quốc đã được mô tả trong cuốn Sunzi Suanjing,[36] lời giải tổng quát được Tần Cửu Thiều xuất bản trong cuốn Shushu Jiuzhang (數書九章, Giáo trình Toán học trong 9 chương) năm 1247.[37] Giải thuật Euclid lần đầu tiên được mô tả và truyền bá tại châu Âu trong cuốn Problèmes plaisants et délectables (ấn bản thứ hai) của Bachet năm 1624.[34] Tại châu Âu, nó cũng được sử dụng để giải phương trình Diophantine và lập liên phân số. Giải thuật Euclid mở rộng được cho là do Roger Cotes tìm ra và được Nicholas Saunderson xuất bản như là một cách để tính nhanh liên phân số.[38][39]

Đến thế kỷ 19, giải thuật Euclid đã dẫn đến sự ra đời và phát triển của các hệ thống số học mới, chẳng hạn như số nguyên Gauss và số nguyên Eisenstein. Năm 1815, Carl Gauss sử dụng giải thuật này để chứng minh tính duy nhất của sự phân tích các số nguyên Gauss, mặc dù công trình của ông chỉ được xuất bản lần đầu năm 1832.[40] Gauss trước đó cũng từng nhắc đến giải thuật trong cuốn Disquisitiones Arithmeticae (xuất bản 1801) liên quan đến liên phân số.[33] Peter Gustav Lejeune Dirichlet có thể là người đầu tiên mô tả giải thuật như là một cơ sở của phần lớn lý thuyết số.[41] Lejeune Dirichlet nhận thấy rằng nhiều hệ quả của lý thuyết số là đúng với bất kỳ hệ thống số học nào mà giải thuật Euclid có thể áp dụng được.[42] Những bài giảng của Dirichlet về lý thuyết số đã được biên tập và mở rộng bởi Richard Dedekind, người đã ứng dụng giải thuật để nghiên cứu số đại số nguyên, một dạng số tổng quát mới. Chẳng hạn, Dedekind là người đầu tiên chứng minh được định lý Fermat về tổng của hai số chính phương qua sự phân tích duy nhất số nguyên Gauss.[43] Ông cũng định nghĩa khái niệm miền Euclid, một hệ thống số mà trong đó một dạng tổng quát của giải thuật Euclid có thể được xác định. Những năm cuối thế kỷ 19, giải thuật Euclid dần bị lu mờ bởi lý thuyết tổng quát của Dedekind về ideal.[44]

"[Giải thuật Euclid] là cha đẻ của thuật toán, vì nó là thuật toán không tầm thường lâu đời nhất vẫn còn trụ lại được đến ngày nay."

Donald Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, ấn bản 2 (1981), tr. 318.

Nhiều ứng dụng khác của giải thuật Euclid cũng đã được phát triển trong thế kỷ 19. Năm 1829, Charles Sturm cho thấy rằng giải thuật này có ích trong phương pháp chuỗi Sturm dùng để đếm số nghiệm thực của đa thức trong một khoảng bất kỳ.[45]

Giải thuật Euclid là thuật toán liên hệ số nguyên đầu tiên dùng để tìm mối liên hệ số nguyên giữa các số thực tương xứng. Nhiều thuật toán khác như vậy cũng đã được phát triển, chẳng hạn như thuật toán của Helaman Ferguson và R.W. Forcade (1979)[46] hay thuật toán LLL.[47][48]

Năm 1969, Cole và Davie đã tạo ra một trò chơi hai người dựa trên giải thuật Euclid có tên là The Game of Euclid.[49] Trò chơi này có một chiến lược chơi tối ưu.[50] Mỗi người chơi bắt đầu với hai đống đá chứa a và b viên đá, lần lượt loại bỏ m bội của đống nhỏ hơn so với đống lớn hơn. Như vậy, khi a lớn hơn b thì người tiếp theo có thể giảm số lượng viên đá trong đống lớn từ a xuống a − mb viên. Người chiến thắng là người đầu tiên có một đống không còn viên đá nào.[51][52]

Xem thêm

sửa

Ghi chú

sửa
  1. ^ Một số sách giáo khoa như Topics in Algebra của I. N. Herstein và Algebra của Serge Lang sử dụng thuật ngữ "giải thuật Euclid" để liên hệ với phép chia có dư

Chú thích

sửa
  1. ^ Stark 1978, tr. 16
  2. ^ Stark 1978, tr. 21
  3. ^ LeVeque 1996, tr. 32
  4. ^ LeVeque 1996, tr. 31
  5. ^ Grossman, J. W. (1990). Discrete Mathematics. New York: Macmillan. tr. 213. ISBN 0-02-348331-8.
  6. ^ Schroeder 2005, tr. 21–22
  7. ^ Schroeder 2005, tr. 19
  8. ^ Ogilvy, C. S.; Anderson, J. T. (1966). Excursions in number theory. New York: Oxford University Press. tr. 27–29.
  9. ^ Schroeder 2005, tr. 216–219
  10. ^ LeVeque 1996, tr. 33
  11. ^ Stark 1978, tr. 25
  12. ^ Ore 1948, tr. 47–48
  13. ^ Stark 1978, tr. 18
  14. ^ Stark 1978, tr. 16–20
  15. ^ Knuth 1997, tr. 320
  16. ^ Lovász, L.; Pelikán, J.; Vesztergombi, K. (2003). Discrete Mathematics: Elementary and Beyond. New York: Springer-Verlag. tr. 100–101. ISBN 0-387-95584-4.
  17. ^ Kimberling, C. (1983). “A Visual Euclidean Algorithm”. Mathematics Teacher. 76: 108–109.
  18. ^ Dummit, David S.; Foote, Richard M. (2004). Abstract Algebra. John Wiley & Sons, Inc. tr. 270-271. ISBN 978-0-471-43334-7.
  19. ^ Knuth 1997, tr. 319–320
  20. ^ Knuth 1997, tr. 318–319
  21. ^ Stillwell 1997, tr. 14
  22. ^ a b Ore 1948, tr. 43
  23. ^ a b Stewart, B. M. (1964). Theory of Numbers (ấn bản thứ 2). New York: Macmillan. tr. 43–44. LCCN 64010964.
  24. ^ Lazard, D. (1977). “Le meilleur algorithme d'Euclide pour K[X] et Z”. Comptes rendus de l'Académie des Sciences (bằng tiếng Pháp). 284: 1–4.
  25. ^ a b Knuth 1997, tr. 318
  26. ^ Weil, A. (1983). Number Theory. Boston: Birkhäuser. tr. 4–6. ISBN 0-8176-3141-0.
  27. ^ Jones, A. (1994). “Greek mathematics to AD 300”. Companion encyclopedia of the history and philosophy of the mathematical sciences. New York: Routledge. tr. 46–48. ISBN 0-415-09238-8.
  28. ^ van der Waerden, B. L. (1954). Science Awakening. Arnold Dresden dịch. Groningen: P. Noordhoff Ltd. tr. 114–115.
  29. ^ von Fritz, K. (1945). “The Discovery of Incommensurability by Hippasus of Metapontum”. Annals of Mathematics. 46 (2): 242–264. doi:10.2307/1969021. JSTOR 1969021.
  30. ^ Heath, T. L. (1949). Mathematics in Aristotle. Oxford Press. tr. 80–83.
  31. ^ Fowler, D. H. (1987). The Mathematics of Plato's Academy: A New Reconstruction. Oxford: Oxford University Press. tr. 31–66. ISBN 0-19-853912-6.
  32. ^ Becker, O. (1933). “Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid”. Quellen und Studien zur Geschichte der Mathematik B. 2: 311–333.
  33. ^ a b Stillwell 1997, tr. 31
  34. ^ a b Tattersall 2005, tr. 70
  35. ^ Rosen 2000, tr. 86–87
  36. ^ Ore 1948, tr. 247–248
  37. ^ Tattersall 2005, tr. 72, 184–185
  38. ^ Saunderson, Nicholas (1740). The Elements of Algebra in Ten Books. University of Cambridge Press. Truy cập ngày 6 tháng 7 năm 2020.
  39. ^ Tattersall 2005, tr. 72–76
  40. ^ Gauss, C. F. (1832). “Theoria residuorum biquadraticorum”. Comm. Soc. Reg. Sci. Gött. Rec. 4. In lại trong Gauss, C. F. (2011). “Theoria residuorum biquadraticorum commentatio prima”. Werke. 2. Cambridge Univ. Press. tr. 65–92. doi:10.1017/CBO9781139058230.004. và Gauss, C. F. (2011). “Theoria residuorum biquadraticorum commentatio secunda”. Werke. 2. Cambridge Univ. Press. tr. 93–148. doi:10.1017/CBO9781139058230.005.
  41. ^ Stillwell 1997, tr. 31–32
  42. ^ Lejeune Dirichlet 1894, tr. 29–31
  43. ^ Richard Dedekind trong Lejeune Dirichlet 1894, phụ lục XI
  44. ^ Stillwell 2003, tr. 41–42
  45. ^ Sturm, C. (1829). “Mémoire sur la résolution des équations numériques”. Bull. des sciences de Férussac (bằng tiếng Pháp). 11: 419–422.
  46. ^ Weisstein, Eric W., "Integer Relation" từ MathWorld.
  47. ^ Peterson, I. (ngày 12 tháng 8 năm 2002). “Jazzing Up Euclid's Algorithm”. ScienceNews.
  48. ^ Cipra, Barry Arthur (ngày 16 tháng 5 năm 2000). “The Best of the 20th Century: Editors Name Top 10 Algorithms” (PDF). SIAM News. Society for Industrial and Applied Mathematics. 33 (4). Bản gốc (PDF) lưu trữ ngày 22 tháng 9 năm 2016. Truy cập ngày 6 tháng 7 năm 2020.
  49. ^ Cole, A. J.; Davie, A. J. T. (1969). “A game based on the Euclidean algorithm and a winning strategy for it”. Math. Gaz. 53 (386): 354–357. doi:10.2307/3612461. JSTOR 3612461.
  50. ^ Spitznagel, E. L. (1973). “Properties of a game based on Euclid's algorithm”. Math. Mag. 46 (2): 87–92. doi:10.2307/2689037. JSTOR 2689037.
  51. ^ Rosen 2000, tr. 95
  52. ^ Roberts, J. (1977). Elementary Number Theory: A Problem Oriented Approach. Cambridge, MA: MIT Press. tr. 1–8. ISBN 0-262-68028-9.

Tham khảo

sửa

Liên kết ngoài

sửa
 
Wikimedia Commons có thêm hình ảnh và phương tiện truyền tải về Giải thuật Euclid.
Lấy từ “https://vi.wikipedia.org/w/index.php?title=Giải_thuật_Euclid&oldid=72048049”