Số Học - Bà Chúa Của Toán Học: Khám Phá Từ Cổ Điển Đến Hiện Đại

Khám phá Số học, "bà chúa của toán học": từ những con số đơn giản đến những bí ẩn sâu sắc. Tìm hiểu về vẻ đẹp và ứng dụng của số học.

• Tác giả: Hoàng Chúng
• Trường học: Nhà xuất bản Giáo dục
• Chuyên ngành: Toán học
• Đề tài: Số học - bà chúa của toán học
• Loại tài liệu: Sách giáo khoa
• Năm xuất bản: 1998
• Địa điểm: Thành phố Hồ Chí Minh

Mục lục chi tiết

• LỜI NÓI ĐẦU
• 1. CHƯƠNG 1: PHÉP CHIA CÓ DƯ. ĐỒNG DƯ THỨC VÀ PHƯƠNG TRÌNH ĐỒNG DƯ
• 1.1. Phép chia hết và phép chia có dư
• 1.2. Ước chung lớn nhất và bội chung nhỏ nhất
• 1.3. Thuật toán Euclide (Oclit)
• 1.4. Định lí về phép chia có dư
• 1.5. Các bài toán về chia hết và phương hướng tìm lời giải

Tóm tắt

I. Giới thiệu Số học bà chúa của Toán học hiện đại

Số học, ngành lâu đời nhất và đầy hấp dẫn của toán học, đã từng được một nhà toán học nổi tiếng gọi là ” bà chúa của toán học ”. Các bài toán số học đã làm say mê nhiều người, từ những nhà toán học lỗi lạc của mọi thời đại đến đông đảo các bạn yêu toán. Thế giới các con số, rất quen thuộc với chúng ta trong cuộc sống hàng ngày, là một thế giới hết sức kì lạ, đầy bí ẩn: loài người đã phát hiện trong đó biết bao tính chất rất hay, nhiều quy luật rất đẹp và có khi rất bất ngờ, đồng thời cũng đang chịu bó tay trước nhiều sự hiện, nhiều dự đoán. Điều lí thú là nhiều mệnh đề khó nhất của số học được phát biểu rất đơn giản, ai cũng hiểu được; nhiều bài toán khó có thể giải rất sáng tạo với những kiến thức số học phổ thông. Không ở đâu như trong số học, chúng ta lại có thể lần theo được dấu vết của những bài toán cổ xưa để đến được với những vấn đề mới đang chờ người giải. Chính vì các lẽ trên đây mà môn số học tuy chỉ được học ở 6~ 7 năm đầu của trường phổ thông, nhưng các bài toán số học luôn có mặt trong các đề thì chọn học sinh giỏi toán ở tất cả các cấp học và ở hầu hết các nước trên thế giới. Cuốn sách này trình bày một số vấn đề cơ bản của số học phù hợp với trình độ học sinh khá giỏi toán cấp 2 và 3. Sách gồm có 4 chương và một phụ lục; sau mỗi chương (hoặc phần của chương) có nhiều bài tập từ dễ đến tương đối khó. Các chương độc lập với nhau, bạn có thể đọc chương nào trước cũng được (bỏ qua các chỗ in chữ nhỏ). Phần “Gợi ý giải bài tập” chỉ giúp bạn khi gặp khó khăn, và tác giả luôn hi vọng rằng bạn đọc sẽ có những ý hay hơn, sáng tạo hơn. So với bản in lần thứ nhất (1991), bản in lần thứ hai này có một số sa chữa nhỏ, đặc biệt là 66 di Phu luc 2 ( Hdon vi va tổ hợp, công thức Neuton) vì nội dung này đã được trình bày đầy đủ trong sách gióo khoa Giải tích 12, kể từ nănt học 1992-93. Tác giả xin chân thành cắm ơn những nhậm xét quý báu cua ban doc.Thanh phé Hd Chi Minh, tháng 6 năm 1998 HGÀNG CHÚNG.

1.1. Lý thuyết số Vai trò của Số học trong Toán học

Số học không chỉ là nền tảng cơ bản mà còn là nguồn cảm hứng cho nhiều lĩnh vực khác của toán học. Những khái niệm và định lý trong lý thuyết số thường xuyên được sử dụng trong đại số, hình học và giải tích. Sự hiểu biết sâu sắc về số học giúp chúng ta tiếp cận các vấn đề phức tạp một cách sáng tạo và hiệu quả hơn.

1.2. Ứng dụng số học trong cuộc sống thường nhật

Mặc dù trừu tượng, số học có nhiều ứng dụng thực tế trong cuộc sống hàng ngày. Từ việc tính toán đơn giản đến mã hóa thông tin, số học đóng vai trò quan trọng trong nhiều lĩnh vực. Đặc biệt, trong mật mã học, các khái niệm như số nguyên tố và số học module được sử dụng rộng rãi để bảo vệ thông tin.

1.3. Các nhánh chính của Số học

Số học không phải là một khối thống nhất mà bao gồm nhiều nhánh khác nhau. Các nhánh chính bao gồm lý thuyết số, số học module, phương trình Diophantine, và số học giải tích. Mỗi nhánh có một tập hợp các vấn đề và phương pháp riêng, nhưng tất cả đều dựa trên nền tảng của số học cơ bản.

II. Thách thức trong Số học Bài toán Nghiên cứu hiện nay

Số học không chỉ là những kiến thức đã được chứng minh mà còn là một lĩnh vực nghiên cứu đầy thách thức. Nhiều bài toán cổ điển vẫn chưa có lời giải hoàn chỉnh, và các nhà toán học tiếp tục khám phá những bí ẩn của các con số. Các vấn đề như giả thuyết Riemann và bài toán Goldbach-Euler là những ví dụ điển hình về những thách thức lớn trong số học.

2.1. Các bài toán số học cổ điển chưa có lời giải

Nhiều bài toán số học đã được đặt ra từ hàng trăm năm trước nhưng vẫn chưa có lời giải hoàn chỉnh. Ví dụ, bài toán về sự tồn tại vô hạn của các cặp số nguyên tố sinh đôi vẫn là một thách thức lớn. Giải quyết những bài toán này đòi hỏi sự sáng tạo và kiến thức sâu rộng về số học.

2.2. Hướng nghiên cứu Số học trong tương lai

Các nhà toán học hiện đại đang tập trung vào việc phát triển các phương pháp mới để giải quyết các bài toán số học khó. Một trong những hướng nghiên cứu quan trọng là sử dụng các công cụ từ đại số, hình học, và giải tích để tiếp cận các vấn đề số học. Sự kết hợp giữa các lĩnh vực khác nhau của toán học có thể mở ra những con đường mới để khám phá những bí ẩn của các con số.

2.3. Ứng dụng số học trong bảo mật thông tin

Sự phát triển của công nghệ thông tin đã tạo ra nhu cầu lớn về bảo mật thông tin. Số học, đặc biệt là lý thuyết số, đóng vai trò quan trọng trong việc phát triển các thuật toán mã hóa mạnh mẽ. Các thuật toán như RSA dựa trên sự khó khăn của việc phân tích một số lớn thành các thừa số nguyên tố.

III. Phép chia hết và đồng dư thức Phương pháp giải toán

Phép chia hết và đồng dư thức là hai khái niệm cơ bản trong số học, và chúng cung cấp những công cụ mạnh mẽ để giải quyết nhiều bài toán. Hiểu rõ về các tính chất của phép chia hết và đồng dư thức giúp chúng ta tiếp cận các vấn đề một cách có hệ thống và hiệu quả hơn. Phép chia có dư, đồng dư thức và các phương trình đồng dư là các yếu tố cốt lõi để hiểu sâu sắc hơn về Số học

3.1. Định nghĩa và tính chất của Phép chia hết

Phép chia hết xảy ra khi một số nguyên chia hết cho một số nguyên khác mà không có số dư. Các tính chất cơ bản của phép chia hết bao gồm tính chất bắc cầu, tính chất phân phối, và tính chất chia hết cho tích của hai số nguyên tố cùng nhau. Nắm vững những tính chất này giúp chúng ta giải quyết các bài toán liên quan đến ước số và bội số.

3.2. Ứng dụng của đồng dư thức trong Toán học

Đồng dư thức là một công cụ mạnh mẽ để giải quyết các bài toán liên quan đến chia hết và số dư. Các tính chất của đồng dư thức cho phép chúng ta đơn giản hóa các biểu thức và tìm ra các quy luật. Đồng dư thức được sử dụng rộng rãi trong lý thuyết số và mật mã học.

3.3. Phương trình đồng dư Các bước giải cơ bản

Phương trình đồng dư là một phương trình mà chúng ta cần tìm các nghiệm nguyên thỏa mãn một điều kiện đồng dư. Để giải phương trình đồng dư, chúng ta có thể sử dụng các tính chất của đồng dư thức, thuật toán Euclid mở rộng, và định lý Trung Hoa về số dư. Các bài toán về phương trình đồng dư thường xuất hiện trong các kỳ thi toán học và có nhiều ứng dụng thực tế.

IV. Định lý Fermat và Euler Công cụ mạnh mẽ trong Số học

Định lý Fermat nhỏ và định lý Euler là hai kết quả quan trọng trong lý thuyết số, và chúng cung cấp những công cụ mạnh mẽ để giải quyết nhiều bài toán. Hiểu rõ về các điều kiện áp dụng và cách sử dụng của hai định lý này giúp chúng ta tiếp cận các vấn đề một cách sáng tạo và hiệu quả hơn. Các nhà toán học thường xuyên sử dụng hai định lý này

4.1. Phát biểu và chứng minh Định lý Fermat

Định lý Fermat nhỏ phát biểu rằng nếu p là một số nguyên tố và a là một số nguyên không chia hết cho p, thì a^(p-1) đồng dư với 1 modulo p. Chứng minh định lý Fermat nhỏ có thể được thực hiện bằng nhiều phương pháp khác nhau, bao gồm sử dụng nguyên lý quy nạp và lý thuyết nhóm.

4.2. Tổng quan về Định lý Euler ứng dụng

Định lý Euler mở rộng định lý Fermat nhỏ cho trường hợp các số nguyên tố cùng nhau. Định lý Euler phát biểu rằng nếu a và n là hai số nguyên tố cùng nhau, thì a^phi(n) đồng dư với 1 modulo n, trong đó phi(n) là hàm Euler. Định lý Euler có nhiều ứng dụng trong lý thuyết số và mật mã học.

4.3. Mối liên hệ giữa Fermat và Euler

Định lý Fermat nhỏ là một trường hợp đặc biệt của định lý Euler. Khi n là một số nguyên tố p, hàm Euler phi(p) bằng p-1, và định lý Euler trở thành định lý Fermat nhỏ. Như vậy, định lý Euler có thể được xem như là một sự tổng quát hóa của định lý Fermat nhỏ.

V. Số nguyên tố Khám phá bí ẩn của những con số

Số nguyên tố là những số tự nhiên chỉ có hai ước số là 1 và chính nó. Chúng đóng vai trò quan trọng trong số học và có nhiều ứng dụng thực tế. Tuy nhiên, vẫn còn nhiều bí ẩn xung quanh các số nguyên tố, và các nhà toán học tiếp tục khám phá những tính chất của chúng. Phân bố, sự xuất hiện ngẫu nhiên, và các dạng đặc biệt là các chủ đề nghiên cứu chính.

5.1. Số nguyên tố và Định lý cơ bản của Số học

Định lý cơ bản của số học phát biểu rằng mọi số tự nhiên lớn hơn 1 đều có thể được phân tích thành một tích duy nhất của các số nguyên tố. Như vậy, số nguyên tố là những viên gạch xây dựng cơ bản của các số tự nhiên. Việc tìm ra các số nguyên tố lớn và phân tích một số thành các thừa số nguyên tố là những vấn đề quan trọng trong số học.

5.2. Phương pháp tìm kiếm và kiểm tra số nguyên tố

Có nhiều phương pháp khác nhau để tìm kiếm và kiểm tra số nguyên tố. Phương pháp đơn giản nhất là thử chia số cần kiểm tra cho tất cả các số tự nhiên nhỏ hơn căn bậc hai của nó. Tuy nhiên, phương pháp này trở nên kém hiệu quả khi số cần kiểm tra lớn. Các thuật toán phức tạp hơn, như thuật toán Miller-Rabin, cho phép kiểm tra số nguyên tố lớn một cách nhanh chóng.

5.3. Các dạng số nguyên tố đặc biệt ứng dụng

Ngoài các số nguyên tố thông thường, còn có nhiều dạng số nguyên tố đặc biệt, như số nguyên tố Mersenne và số nguyên tố Fermat. Các số nguyên tố đặc biệt này có những tính chất riêng biệt và được sử dụng trong nhiều ứng dụng, bao gồm mật mã học và kiểm tra phần cứng máy tính.

VI. Phương trình Diophantine Giải nghiệm nguyên bài toán khó

Phương trình Diophantine là một phương trình mà chúng ta cần tìm các nghiệm nguyên thỏa mãn. Các phương trình Diophantine thường rất khó giải và đòi hỏi sự sáng tạo và kiến thức sâu rộng về số học. Việc tìm ra các nghiệm nguyên của phương trình Diophantine có thể dẫn đến những khám phá mới trong lý thuyết số.

6.1. Khái niệm và các loại phương trình Diophantine

Các phương trình Diophantine có thể có nhiều dạng khác nhau, từ các phương trình bậc nhất đến các phương trình bậc cao. Một số loại phương trình Diophantine nổi tiếng bao gồm phương trình Pell và phương trình elliptic. Mỗi loại phương trình đòi hỏi một phương pháp giải riêng.

6.2. Phương pháp giải phương trình Diophantine cơ bản

Có nhiều phương pháp khác nhau để giải phương trình Diophantine, bao gồm sử dụng đồng dư thức, thuật toán Euclid mở rộng, và phương pháp lùi vô hạn. Lựa chọn phương pháp phù hợp phụ thuộc vào dạng của phương trình và các ràng buộc của bài toán.

6.3. Ứng dụng của phương trình Diophantine

Mặc dù trừu tượng, các phương trình Diophantine có nhiều ứng dụng thực tế. Chúng được sử dụng trong mật mã học, lý thuyết mã, và vật lý lý thuyết. Việc nghiên cứu các phương trình Diophantine không chỉ là một bài tập toán học mà còn có thể dẫn đến những khám phá mới trong các lĩnh vực khoa học khác.

Trích đoạn nội dung tài liệu

Mở đầu phép chứng minh một định lí, lời giải một bài toán oO Kết thúc chứng minh một định lí, lời giải một bài toán Các số nói đến trong sách này, nếu không ghi chu gi khác, đều là số nguyên ( thuộc Z2 ). Riêng trong chương 2 và chương 4 chỉ xét các số tự nhiên ( thuộc N ). Trong LẦN XUẤT BẢN THỨ NĂM trang 88 được viết lại cho phù hợp với thành tựu mới ; một số sai sót do chế bản in đã được sủa. CHUONG 1 PHEP CHIA CO DU.

DONG DU THUC VA PHUONG TRINH DONG DU Tw Han Tin dén Gauss Trong ruột cuốn sách toán của Trung Quốc cách đây khoảng 1500 năm, có giải một bài toán gọi là Hàn Tín điểm binh như sau : Bảo lính sắp hàng 3, hàng ð rồi hàng 7, mỗi lần sắp thì đếm số lẻ ở hàng cuối cùng. Nhân số lẻ hàng 3 cho 70, số lẻ hàng õð cho 31, số lẻ hàng 7 cho lỗ rồi cộng lại. Lấy số thành thêm một bội cúa 105 thì được số lính. Thí dụ: nếu sắp hàng 3 lẻ 2,hàng ð lễ 3, hàng 7 lẻ 4 thì số lính là x = 2.

Nếu biết chừng số lính từ 800 đến 900 thì có x = 893 (lấy k = 6). “Qui tác điểm binh” trên đây được tóm tắt cho dễ nhớ trong bốn câu thơ. Đến thế kỉ thứ 13, nhà toán học Trung Quốc Tần Cửu Thiều đã trình bày đây đủ hơn phương pháp giải những bài toán tương tự bài toán Hàn Tín điểm binh, thí dụ bài toán Mấy? trộm gao sau day: Có một nhà mất trộn: gạo. Nhà đó có ba thùng gạo đầy oà bằng nhau, nhưng không biết là bao nhiêu.

Sau khi médt thi thay thùng bên trái còn niột hộc, thùng giữa còn 1 thăng 4 héc, thang bên phải còn một hộc.Về sau bắt được ba tên trộm Giáp, At, Bính. Giáp khơi rằng ban đêm sờ được cói góo cho uòo đong guo thùng bên trái đồ uào túi, At khai rằng đá phải chiếc giầy gỗ cho 0uào thùng gia đong gạo, Bính khai rằng sờ được cói bát son cho 0uào thiing/phdi đong gạo; lay vé an lau ngay, quén mat không biết là bao nhiéu.Tim tang vat thì thấy: gáo đựng 1 thăng 9 hộc, giầy gỗ đựng 1 thăng 7 hộc, bát son 1 thờng 2 hộc. Theo tang vat, tim xem mỗi tên lấy trộm bao nhiêu ? (1 thăng bằng 10 hộc ) Để giải bài toán Hàn Tín điểm binh ta phải tìm x sao cho x chia cho 3, dư 2 x— 2 chia hết cho 3 x chia cho 5, dư 3 hay là x — 3 chia hét cho 5 x chia cho 7, du 4 x - 4 chia hết cho 7 Tương tự như vậy với bài toán Mất trộn: gạo. Với phương pháp giải các bài toán này, các nhà toán học Trung Quốc thời ấy đã biết sử dụng các định lí về chia hết, sớm có khái niệm về đông dư thức, về giải phương trình đồng dư mà mãi đến đầu thế kỉ thứ 19, nhà toán học Đức lỗi lạc C.Gauss (Gau-xơ, 1777-1855) mới xây dựng thành một lí thuyết tương đối hoàn chỉnh.

m1 - Phép chỉa hết và phép chia có dư 1-1-Cho hai số nguyên a và b (bồ > 0). Chia a cho b, ta có: a chia hết cho b hoặc a không chia hết cho b. 1) a chia hết cho b hay a là bội của b, được kí hiệu là a : b. Ta cũng nói: b chia hết œ hay b là ước của q và kí hiệu là bla.

a :b (hay bịa ) khi và chỉ khi có số nguyên q sao cho a = bq. 2) a không chia hết cho b.Trong trường hợp này, khi chia cho b, ta được thương gần đúng là q và số dư là r (0<r<b) Ta viết được: a = bq + r với <r<b Thí dụ:- Với a = 19, b = 3 ta có 19 = 3. Chia 19 cho 3 được thương gần đúng là 6 và số dư là 1. Chia -25 cho 7 được thương gần đúng là-4 và dư là 3.

Chia 5 cho 11 được thương gần đúng là 0 và số dư là ð. Một cách tổng quái, có thể nói rằng: Khi chia một số nguyên a cho một số nguyên b> 0, ta luôn có một số dư duy nhất là r với 0< r<b (a chia hết cho b nếu r= 0,a không chia hết cho b nếu r # 0). Số dư r luôn nhỏ hơn b, tức là lớn nhất chỉ bằng b— 1. Khi chia một số nguyên qa cho một số nguyên b>0 thì số dự là một trong b số từ 0 đến b — 1.

Thí dụ:- Chia một số cho 2 thì số dư là một trong hai số: 0 hoặc 1. - Chia một số cho 3 thì số dư là một trong ba số: 0,1 hoặc 2. - Chia một số cho 5 thi số dư là một trong năm số: 0,1,2,3 hoặc 4.2 - Trong trường hợp a không chia hết cho b (số dư r z 0), thay vì lấy r > 0 (từ 1 đến b~ 1 ), để tiện lợi trong chứng minh và giải toán, nhiều khi người ta cúng lấy số dư là sé 4m r’vdi r’= r— b (do đó |rˆ|<b ). Thí dụ:- Chia 23 cho 3, được số dư là 2: 23 = 3.

Ta gọi 7 là (hương gần đúng thiéu, vi 3. Cũng có thể viết: 23 = 3. Ta gọi 8 là (hương gần đúng thừa, vì 3.8 = 24 > 23, và sé du la-- 1. - Chia B2 cho 6,lấy thương gần đúng thiếu là 8, ta có số dư là 4: 52 = 68+ 4.

Nếu lấy thương gần đúng thừa là 9 thì có số dư là 4 ~ 6 =~2: 52 = 6. - Chia -36 cho 5, ta viết được: -36 = 5-8) + 4 hoặc là ~—36 = ð. Số~8 là thương gần đúng thiếu, vì 5. (-8) = -40 <-36, và ta có số dư là 4.

Số ~7 là thương gần đúng thừa, vì 5.(-7 ) = -35 >-~36, và ta có số dư là -— 1. Coi số dư có thể là số âm như trên, ta có: - Khi chia một số cho 2 thì số dư là 0 hoặc 1, do đó mọi số nguyên đều có dạng 2k (bội của 2, số chắn) hoặc 2k + 1 (số lễ), trong đó k là một số nguyên. Nếu số dư trong phép chia cho 2 là 1 thì có thể coi số dư la 1-2 =-1, do đó có thể nói: mọi số nguyên đều có dạng 2k hoặc 2k — 1. - Khi chia một số nguyên cho 3 thì số dư là 0,1 hoặc 2, do đó mọi số nguyên đều có dạng 3k (bội của 3 ) hoặc 3k + 1 (bội của 3 cộng 1) hoặc 3k + 2 (bội của 3 cộng 2 ).

Với số dư là 2 thì có thể coi số du là—1, vì vậy có thể nói mọi số nguyên đều có dạng 3k hoặc 3k+1. Tương tự như vậy, nếu xét phép chia cho 4 thì ta có: mọi số nguyên đêu có dạng 4k, 4k + 1 hoặc 4k + 2 (hay la 4k, 4k + 1 hoặc 4k~ 2); nếu xét phép chia cho 5 thì có: mọi số nguyên đều có dạng 5k, 5k + 1 hoặc ðk + 2;v. Ta có kết quả tổng quát như sau: a =bq +r(b>0) r là số dư khi chia a cho b> 0: - b b chẳn > r = 0,£1,+2,.3 - Ước chung lớn nhất và bội chung nhỏ nhất Cho hai số nguyên dương a và b. Ước chung lớn nhất của œ 0à b được kí hiệu là ƯCLN (a,b) hay là (a,b).Một số d là ước chung của a và b khi và chỉ khi d là ước của ƯCLN (a,b); dla va d|b « d] (a,b).

Bội chung nhỏ nhất của a va b được ki hiéu 1A BCNN (ab) hay là [a,b]. Một số m là bội chung của a và b khi và chỉ khi m là bội của BƠNN (ab) : m : a và m : b œ© m : [a,b] Hai số a và b được gọi là ñguyên tố càng nhau khi và chỉ khi (a,b) = 1. Ta đã biết cách tìm (a,b) va [a,b] dựa vào sự phân tích a và b ra thừa số nguyên tố. Có thể chứng minh được rằng: 8, “lam Từ đó: [a,b] = ab néu (a,b) = 1.4 - Thuật toán Euclide (Oclit) Có thể tìm ƯCLN của hai số, dựa vào định lí về phép chia có dư, mà không cần đến việc phân tích các số đã cho thành thừa số nguyên tố, Cho hai số nguyên dương a,b và giả sử a>b.

Trước hết, ta chú ý rằng nếu b là ước của a thì (a,b) = b, Thí dụ: 80 = 16. Xét trường hợp b không phải là ước của a. Thí dụ: a = 702, b = 306, và phải tìm (702,306). Ta chia 702 cho 306, được thương là 2 và số dư là 90 : 702 = 306.2 + 90 Vận dụng tính chất: nếu một số là ước của mỗi số hạng của một tổng (hiệu) thì nó là ước cuả tổng (hiệu) ấy, ta có: mọi ước chung của 702 và 306 cúng là ước của 702 — 306.2 = 90, do đó cũng là ước chung của 306 và 90.

Ngược lai, mọi ước chung của 306 và 90 cũng là ước của 306.2 + 90 = 702, do đó cũng là ước chung của 702 và 306, vì vậy (702,306) = (306,90) và ta đã đưa việc tìm ƯCLN của hai số đã cho về việc tim UCLN 10 của hai số tương ứng bé hơn. Tiếp tục nhiều lần như vậy, cuối cùng ta đi đến việc tìm ƯCLN của hai số mà số này là ước của số kia và có ngay được ƯCLN. Ta viết được: 702 = 306.2 + 90 => (702,306) = (306,90) 306 = 903 +36 = (306,90) = (90,36) 90 =362 +18 + (90,36) = (36,18) 36 = 182 > (36,18) = l8 Vay (720,306) = 18 Trong thực hành,người ta đặt phép tính như sau: 702 | 306 306} 90 | 2 90; 36 | 3 36 | 181 2 0 Ì 3 | Việc thực hiện một dãy phép chia liên tiếp như trên để tìm ƯCLN của hai số được gọi là thudt todn Euclide. Nhu da thay qua thí dụ ở trên, thuật toán Buclide dựa vào hai mệnh đề sau đây: 1) a = bq => (a,b) = b 2) a = bq + r (r#0) > (a,b) = (b,r) Có thể lặp lại các lập luận trong thí dụ đã xét (với a = 702, b = 306) để chứng minh mệnh đề 2.