TRONG N
THUẬT CHIA EUCLIDE
PHẦN A

I- Số nguyên tố - Hợp số


( Cho p(N, p > 1
p là số nguyên tố ( Ư(p) = {1, p}
p là hợp số ( Ư(p) có nhiều hơn 2 phần tử.
Số 2 là số nguyên tố nhỏ nhất và là số nguyên tố chẵn duy nhất. Từ đây, ta có nhận xét rằng các số nguyên tố lớn hơn 2 là số lẻ.
Biểu diễn tập N theo sơ đồ Venn
( Hai hay nhiều số nguyên tố cùng nhau
Hai số a, b được gọi là nguyên tố cùng nhau khi ƯCLN(a,b) = 1

Ví dụ1 15 và 26 là hai số nguyên tố cùng nhau vì ƯCLN(15, 26) = 1
Chú ý Hai số nguyên tố cùng nhau không có nghĩa là cả 2 số là số nguyên tố.
Hai số nguyên tố khác nhau hiển nhiên chúng là hai số nguyên tố cùng nhau
Hai số nguyên tố cùng nhau không nhất thiết mỗi số là số nguyên ( như ví dụ trên )
Ví dụ 2 Các cặp số sau : (12, 55) ; (13, 18) ; (17, 19) là các cặp số nguyên tố cùng nhau.
Ví dụ 3 Tìm các cặp số nguyên tố cùng nhau thỏa :
a + b = 20
( để ý rằng a và b phải là hai số cùng lẻ .
a. b = 240
( phân tích 240 ra thừa số nguyên tố .


Qui ước ƯCLN (a,b) = (a,b) và BCNN(a,b) = [a,b]

II- Thuật toán EUCLIDE
( Vài dòng Tiểu sử :
Euclide, nhà Toán học lỗi lạc thời cổ Hy Lạp, sống vào thế kỷ thứ III trước Công nguyên. Toàn bộ kiến thức hình học sơ cấp ở mấy năm đầu ở trường THCS hiện nay đều đã được nói đến một cách khá hệ thống, chính xác qua bộ sách “ CƠ BẢN “ do Euclide viết ra. Bộ sách đó vẫn còn giữ nguyên giá trị sau hơn 2000 năm .
Ngoài Toán học, Ông còn nghiên cứu về Quang học, âm nhạc. Có thể nói rằng tất cả những người học toán trên hành tinh này đều là học trò của Euclide .
( Thuật toán :
Thuật toán EUCLIDE là một phương pháp tìm ƯCLN của hai số khác 0 mà không cần phân tích chúng ra thừa số nguyên tố .
Thuật toán EUCLIDE dựa vào tính chất sau :

Nếu a = b.q + r với 0 ( r < b thì (a, b) = (b, r)
{ Bạn có thể dễ dàng chứng minh tính chất này – Nguyên tắc chứng minh như sau : “ Chứng minh ƯC(a , b) = ƯC(b , r). Từ đó suy ra (a , b) = (b , r) }

Ví dụ minh họa :
Ví dụ1 Tìm ( 702, 306 ) ?
Trong thực hành, ta có thể đặt phép tính như sau :



306 90 2

90 36 3

36 18 2

0 2 Số dư cuối cùng khác 0

Vậy 
( Lấy số chia, chia cho số dư… . Dư cuối cùng khác 0 chính là ƯCLN của hai số đã cho )
Ví dụ2 Tìm

Nhận xét
Phép chia này thực tế thực hiện dựa vào số chữ số của hai số
Dùng thuật toán Euclide, ta tìm được : (100, 24) = (24, 4) = (4, 0) = 4
Vậy :

III- Chia có dư liên hệ ước - bội
Một trong các ứng dụng của Lý thuyết Ước và Bội đó là việc giải một số bài toán khó. Thực tế cho thấy nếu không vận dụng lý thuyết này để giải quyết thì các bài toán đó quá khó đối với chương trình phổ thông (cho dù có giải bằng cách đặt phương trình). Để có một hình ảnh về việc ứng dụng này, trước tiên các bạn nên làm quen với một số khái niệm, tính chất sau :
( Phép chia có dư :
“ Với hai số tự nhiên a, b  N (b ( 0), luôn có hai số q, r  N thỏa a = b.q + r , trong đó 0 ( r < b “. ( ta gọi a = b.q + r , trong đó 0 ( r < b là hệ thức chia có dư )
Từ đây, ta có nhận xét sau :
( Hai phương án cơ bản đưa bài toán chia