Chuyên đề HSG Toán đại 6 (Cánh diều) - Chuyên đề 4, Chủ đề 3: Các phương pháp tìm ƯCLN và BCNN

 ĐS6. CHUYÊN ĐỀ 4- ƯỚC CHUNG LỚN NHẤT VÀ BỘI CHUNG NHỎ NHẤT
 CHỦ ĐỀ 3: CÁC PHƯƠNG PHÁP TÌM ƯCLN, BCNN
PHẦN I. TÓM TẮT LÝ THUYẾT
1. Kiến thức cần nhớ
1. Ước chung của hai hay nhiều số là ước của tất cả các số đó. 
2. Ước chung lớn nhất (ƯCLN) của hai hay nhiếu số là số lớn nhất trong các ước chung của các số đó. 
3. Muốn tìm ƯCLN của hai hay nhiếu số lớn hơn 1 , ta thực hiện ba bước sau: 
- Phân tích mổi số ra thừa số nguyên tố. 
- Chọn ra các thừa số nguyên tố chung. 
- Lập tích các thừa số đã chọn, mỗi thừa số lấy với số mũ nhỏ nhất của nó. Tích đó là ƯCLN phải tìm. 
4. Để tìm ước chung của nhiều số, ta có thể tìm ƯCLN của các số đó rồi tìm ước của ƯCLN đó. 
5. Bội chung của hai hay nhiều số là bội của tất cả các số đó. 
6. Bội chung nhỏ nhất (BCNN) của hai hay nhiều số là số nhỏ nhất khác 0 trong các bội chung của các số đó. 
7. Muốn tìm BCNN của hai hay nhiều số lớn hơn 1 , ta thực hiện ba bước sau: 
- Phân tích mỗi số ra thừa số nguyên tố. 
- Chọn ra các thừa sổ nguyên tố chung và riêng. 
- Lập tích các thừa số đã chọn, mỗi thừa số lấy với số mũ lớn nhất của nó. Tích đó là BCNN phải tìm. 
8. Để tìm bội chung của nhiều số, ta có thể tìm BCNN của các số đó rồi nhân BCNN đó lần lượt với 0,1, 2,3, 
2. Các tính chất
1. Khi cần kí hiệu gọn, ta có thể viết ƯCLN (a,b) là (a,b) , viết BCNN (a,b) là [a,b] 
2. Nếu abc và (b, c) 1 thì ac . 
3. Nếu am và an thì aBCNN(m,n) . Đặc biệt, nếu am,an và (m,n) 1 thì amn 
4. Nếu ƯCLN (a,b) d thì a dm,b dn với (m,n) 1 . 
5. Nếu BCNN (a,b) c thì c am,c bn với (m,n) 1 . 
6. ƯCLN (a,b) BCNN(a,b) a.b . 
7. Người ta chứng minh được rằng: 
Cho hai số tự nhiên a và b trong dó a b . 50 52.2 
ƯCLN (125, 175, 50) 52 25 
Vậy n 25 
Bài 2: Tìm số tự nhiên n nhỏ hơn 30 để các số 3n 4 và 5n 1 có ước chung khác 1 . 
Lời giải: 
Gọi d là một ước chung của 3n 4 và 5n 1 . 
Ta có 3n 4d và 5n 1d nên 5(3n 4) 3(5n 1)d , tức là 17d 
Suy ra d {1;17} . 
Để 3n 4 và 5n 1 có ước chung khác 1 , ta phải có 3n 417 tức là 3n 4 3417 hay 3(n 10)17 
Ta lại có (3,17) 1 nên n 1017 . 
Do n 30 nên n 10 hoặc n 27 . 
Thử lại n 10 , n 27 thỏa mãn. Vậy n 10 ,
Bài 3: Tổng của năm số tự nhiên bằng 156 . Ước chung lớn nhất của chúng có thể nhận giá trị lớn nhất bằng 
bao nhiêu?
Lời giải: 
Gọi năm số tự nhiên đã cho là a1,a2 ,a3 ,a4 ,a5 , ước chung lớn nhất của chúng là d . 
Ta có: a1 dk1,a2 dk2 ,a3 dk3 ,a4 dk4 ,a5 dk5 
nên a1 a2 a3 a4 a5 d k1 k2 k3 k4 k5 
do đó 156 d k1 k2 k3 k4 k5 
Suy ra d là ước của 156 . 
Ta lại có k1 k2 k3 k4 k5 5 nên 5 d 156 , suy ra d 31 . 
Phân tích ra thừa số nguyên tố: 156 22.3.13 . 
Ước lớn nhất của 156 không vượt quá 31 là 26 . 
Giá trị lớn nhất của d là 26 , xảy ra khi chẳng hạn a1 a2 a3 a4 26 và a5 52 hoặc các hoán vị của 
chúng. a 12 48 
 b 60 
 240 
Bài 7: Cho a 24,b 70, c 112. Tìm a,b ; a,b,c ;a,b;a,b,c. Từ đó kiểm tra công thức
ƯCLN (a,b,c) ƯCLN(ƯCLN (a,b), c); BCNN (a,b, c) BCNN (BCNN (a,b), c) 
Lời giải: 
Ta có: a 24 23.3;b 70 2.5.7;c 112 24.7;(a,b) 2;(a,b,c) 2;a,b 23.35.7 840 
a,b,c 24.3.5.7 1680 
ƯCLN (a,b,c) 2; ƯCLN (a,b) 2 ƯCLN(ƯCLN (a,b),c) ƯCLN (2,112) 2 
BCNN (a,b, c) 1680; BCNN (BCNC(a,b), c) BCNN (840,112) 1680 
Bài 8: Tìm ƯCLN, BCNN của các số sau
a) 793016,308,3136 
b) 1323,19845,1287,315 
Lời giải: 
a) Ta có: 793016 23.73.172 ; 308 22.7.11 ; 3136 26.72 
 ƯCLN 793016,308,3136 22.7 28; BCNN 26.73.11 172 
b) Ta có
1323 33.72 ; 19845 34.5.72 ; 1287 32.11.13 ; 315 32.5.7 
 ƯCLN 1323,19845,1287,315 32 9; BCNN 34.5.72.11.13 
Bài 9: Một trường tổ chức cho khoảng 700 và 800 học sinh đi tham quan. Tính số học sinh biết rằng nếu xếp 
40 người hoặc 50 người lên xe ô tô thì vừa đủ. 
Lời giải: 
Gọi số học sinh của trường là: n n N * 
Theo bài ta có: 700 n 800 
Vì n45;n40 n BC(40,45) n B(BCNN(40,45)) 
Ta có: 40 23.5;45 32.5 
BCNN(40,45) 23.32.5 360 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. 
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ì có thể phân tích bất kỳ thừa số chung nào 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ỳ. 
ƯCLN có thể được minh họa như sau: 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à 
 24
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 ( 2 ) và năm hình vuông nằm trên 
 12
 60
cạnh còn lại ( 5 ). 
 12
Ướ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 . 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ố. 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. 
Ư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, 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ố đó. 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ỳ.
 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 g ¦CLN a,b ¦CLN b,r0 ¦CLN r0 ,r1  ¦CLN rn 2 ,rn 1 rn 1. 
I. Phương pháp giải
Muốn tìm ƯCLN của a và b (giả sử a b) 
Bước 1: Chia a cho b có số dư là r 
Bước 2: 
 + Nếu r 0 thì ƯCLN a,b b . Việc tìm ƯCLN dừng lại.
 + Nếu r 0 , ta chia tiếp b cho r , được số dư r1 
 - Nếu r1 0 thì r1 ¦CLN a,b . Dừng lại việc tìm ƯCLN
 - Nếu r1 0 thì ta thực hiện phép chia r cho r1 và lập lại quá trình như trên. 
 ƯCLN a,b là số dư khác 0 nhỏ nhất trong dãy phép chia nói trên.
II. Bài toán
Bài 1: Hãy tìm ƯCLN 1575,343 bằng thuật toán Ơclide
Lời giải:
 Ta có: 1575 343.4 203 
 343 203.1 140 
 203 140.1 63 
 140 63.2 14 
 63 14.4 7 
 14 7.2 0 (chia hết)
 Vậy ƯCLN 1575,343 7 
 Trong thực hành làm như sau:
 1575 343
 343 203 4
 203 140 1
 140 63 1
 63 14 2
 14 7 4
 0 2 Bài 5: Biết số A gồm 2015 chữ số 2 và B gồm 8 chữ số 2 . Hãy tìm ƯCLN A, B 
Lời giải:
Ta có A 2 2...2 2.2.....20 ....0 2.2......2 
 2015 2008 7 7.chu.so.2
Vì 2.2.....20 ....02.2.....2 (A, B) (2.2.....2,2.2.....2) 
 2008 7 8 8 7
Ta có: 2.2.....2 2.2.....20 2 (2.2.....2,2.2.....2) (2.2.....2,2) 2 (A, B) 2 
 8 7 8 7 7
Bài 6: Số X gồm 2002 chữ số 9 , Y gồm 9 chữ số 9 . Tìm ƯCLN X,Y 
Lời giải:
Có: 2002 222.9 4; X 99....9 99....90 000 9 999; X BS(Y ) 9999(1) 
 2002 1998 4 4
Y 9999....9 9999....90 9 Y BS(9999) 9(2);9999 BS(9)(3) 
 9 8 1
Từ (1)(2)(3) ƯCLN (X ,Y ) 9 
Bài 7: Tìm số tự nhiên n , biết rằng khi chia 239 và 373 cho n thì số dư lần lượt là 14 và 23 
Lời giải:
Theo đầu bài ta có: 
239 14 225n 2 2 2
  n UC(225,350) n U (UCLN(225,350));225 3 .5 ;350 2.5 .7 
373 23 350n
ƯCLN (225,350) 25 n UC(25) 
 n 23
Vì 373 chia cho n dư 23 n 25 
 n U (25)
Vậy n 25 
Bài 8: Người ta đếm số trứng trog một rổ. Nếu đếm theo từng chục cũng như theo tá hoặc theo từng 15 quả 
thì lần nào cũng dư 1 quả. Tính số trứng trong rổ, biết rằng số trứng đó lớn hơn 150 và nhỏ hơn 200 quả.
Lời giải:
Gọi số trứng trong rổ là n ( n N * )
Ta có: 150 n 200(1);(n 1)10,12,15 (n 1) BC(10,12,15) n 1 B(60) 
Theo 1 149 n 1 199 n 1 180 n 181 
Vạy số trứng trong rổ là 181 quả