Bài tập Tìm ước chung lớn nhất (ƯCLN) và bội chung nhỏ nhất (BCNN)

3. Tìm ước chung lớn nhất (UCLN) và bội chung nhỏ nhất (BCNN):
Bổ đề (cơ sở của thuật toán Euclide)
Nếu a = bq + r thì (a, b) = (b, r)
Từ bổ đề trên, ta có thuật toán Euclide như sau (với hai số nguyên dương a, b):
- Chia a cho b, ta được thương q1 và dư r1: a = bq1 + r1
- Chia b cho r1, ta được thương q2 và dư r2: b = r1q2 + r2
- Chia r1 cho r2, ta được thương q3 và dư r3: r1 = r2q3 + r3 
....
Tiếp tục quá trình trên, ta được một dãy giảm: b, r1, r2, r3... dãy này dần đến 0, và đó là các số tự nhiên nên ta se thực hiện không quá b phép chia. Thuật toán kết thúc sau một số hữu hạn bước và bổ đề trên cho ta:
(a, b) = (b, r1) = ... rn
Định lí: Nếu x, y là hai số nguyên khác 0, BCNN của chúng luôn luôn tồn tại và bằng:
Bài 8: Tìm UCLN của hai số:
a = 24614205, b = 10719433
Giải:
* Thực hiện trên máy thuật toán tìm số dư trong phép chia số a cho số b, ta được:
- Chia a cho b được: 24614205 = 10719433 x 2 + 3175339
- Chia 10719433 cho 3175339 được: 10719433 = 3175339 x 3 + 1193416
- Chia 3175339 cho 1193416 được: 3175339 = 1193416 x 2 + 788507
- Chia 1193416 cho 788507 được: 1193416 = 788507 x 1 + 404909
- Chia 788507 cho 404909 được: 788507 = 404909 x 1 + 383598
- Chia 404909 cho 383598 được: 404909 = 383598 x 1 + 21311
- Chia 383598 cho 21311 được: 383598 = 21311 x 18 + 0
Þ UCLN(a, b) = 21311
Bài 9: (Thi giải Toán trên MTBT lớp 10 + 11 tỉnh Thái Nguyên - Năm học 2003-2004)
Tìm ước chung lớn nhất và bội chung nhỏ nhất của: 
a = 75125232 và b = 175429800
Đáp số: UCLN(a, b) = ; BCNN(a, b) = 
II. ƯCLN; BCNN: 
1. Lí thuyết: Để tìm ƯCLN, BCNN của hai số A và B ta rút gọn phân số 
 Từ đó : ƯCLN (A; B) 
2. Ví dụ: Cho hai số A = 1234566 và B = 9876546
 a) Tìm ƯCLN(A, B) và BCNN(A,B) ?
Gọi D = BCNN(A,B) Tính giá trị đúng của D3 ? Tính và ghi kết quả vào ô vuông. 
ƯCLN(A, B) = 
BCNN(A,B) = 
D3 = 
a) Ví dụ 1: Tìm ƯCLN; BCNN của A = 209865 và B = 283935
Giải:
 Ta có: 
 ƯCLN (A; B) = 209865: 17 = 12345
 BCNN (A; B) = 209865.23 = 4826895.
Đáp số: ; 
Ta có Gọi D = BCNN(A,B)= 
Đặt 
b) Ví dụ 2: Tìm UCLN của 40096920, 9474372 và 51135438
Giải:
 (Nêu được cơ sở lý thuyết và cách giải 2 điểm; Kết quả 3 điểm)
Do máy cài sẵn chương trình đơn giản phân số nên ta dùng chương trình này
 để tìm Ước số chung lớn nhất (ƯSCLN)
Ta có : ( tối giản)
ƯSCLN(A;B) = A ÷ a
Ấn 
Ta được: 6987 29570
ƯSCLN của 9474372 và 40096920 là 9474372 ÷ 6987 = 1356
Ta đã biết : ƯSCLN(a ; b ; c ) = ƯSCLN(ƯSCLN( a ; b ) ; c )
Do đó chỉ cần tìm ƯSCLN(1356 ; 51135438 )
Ấn 1356 51135438 = Ta được: 2 75421
Kết luận : ƯSCLN của 9474372 ; 40096920 và 51135438
là : 1356 ÷ 2 = 678
ĐS : 678 
c) Ví dụ 3: Cho ba số A = 1193984 ; B = 157993 ; C = 38743
Tìm UCLN của A , B , C
Tìm BCNN của A , B , C với kết quả đúng.
Giải:
Đáp số: D = UCLN(A,B) = 583 ; UCLN(A,B,C) = UCLN(D,C) = 53
Bài tập áp dụng:
1. Bài 1: Tìm ƯCLN và BCNN của hai số A = 1234566 và B = 9876546
 (ƯCLN = 18; BCNN = 677402660502)
2. Bài 2: Tìm ƯCLN và BCNN của các cặp số sau:
 a) 12356 và 546738	b) 20062007 và 121007 c) 2007 và 2008 và 20072008.
3. Bài 3: 
 Tìm UCLN, BCNN của A = 45563, B = 21791, C = 182252 .
Giải
A : B = 23 : 11 UCLN(A,B) = A : 23 = D
 UCLN( C,D) = 1981
 BCNN(A,B) = 45563x11 = E
 BCNN(C,E) = 46109756
UCLN(A,B,C) = 1981
BCNN(A,B,C) = 46109756
4. Bài 4: 
Tìm ƯCLN và BCNN của các cặp số sau:
 a)12356 và 546738	b)20062007 và 121007 	c)2007 và 2008 và 20072008.
5. Bài 5: Cho hai số A = 2419580247 và B = 3802197531
Tìm ƯCLN(A, B) ?
Tìm BCNN(A,B) ? 
	Tính và ghi kết quả vào ô vuông . 
ƯCLN(A, B) = . . . . . . . .. .. . . . .. 
BCNN(A,B) = . . . .. . .. . .. . . .. . . 
6. Bài 6: Tìm ƯSCLN của 40096920 , 9474372 và 51135438. 
Giải
Do máy cài sẵn chương trình đơn giản phân số nên ta dùng chương trình này để tìm 
 Ước số chung lớn nhất (ƯSCLN) Ta tinh : ( tối giản) ƯSCLN : A a
 Ấn 9474372 40096920 = Ta được: 6987 29570
 ƯSCLN (9474372; 40096920) = 9474372 ÷ 6987 = 1356
 Ta đã biết : ƯSCLN(a ; b ; c ) = ƯSCLN(ƯSCLN( a ; b ) ; c )
 Do đó chỉ cần tìm ƯSCLN(1356 ; 51135438 )
 Aán: 1356 51135438 = 2 75421
 Kết luận: ƯSCLN ( 9474372 ; 40096920 ; 51135438 )= 1356 2 = 678
 ĐS : 678 
7. Bài 7: 
a) Tìm tổng các ước số lẻ của số 7677583
b) Tìm ước số chung lớn nhất và Bội số chung nhỏ nhất của hai số 12705, 26565.
 USCLN: 1155 BSCNN: 292215
c) Tìm ước số chung lớn nhất và Bội số chung nhỏ nhất của hai số 82467, 2119887.
 USCLN: 4851 BSCNN: 36.038.079
Giải:
a) Ta có Ư(7677583) = 
 Tổng các ước dương của số 7677583 là: 83 + 92501 = 92584
b) Ta có: ƯSCLN(12705; 26565) = 12705 ÷ 11 = 1155
 Vậy USCLN: 1155 
 Ta có 
 Vậy BSCNN: 292215
c) Ta có: ƯSCLN(82467, 2119887) = 82467÷ 17 = 4851
 Vậy USCLN: 4851 
 Ta có 
 Vậy BSCNN: 36.038.079
4. ƯỚC VÀ BỘI:
a) Lí thuyết: 
b) Ví dụ: Tìm tất cả các ước của 120 
+) Sử dụng máy tính CASIO 500MS
 Ta ấn các phím sau: 
 / / /= / = / . . . 
 chọn các kết quả là số nguyên Kết quả: Ư(120) =
Giải:
Quy trình tìm các ước của 60 trên máy tính Casio 570 Esv là 
 Ghi lên màn hình sau đó ấn ấn dấu liên tiếp để chọn kết quả là số nguyên
Kết quả: Ư (60) = 
Thuật toán tìm ƯCLN, BCNN:
Giả sử cần tìm UCLN và BCNN của 2 số A,B 
Cách đơn giản ai cũng biết đó là ấn A/B rồi tối giản nó 
Trong một số trường hợp vì A,B khá lớn và dạng tối giản của A/B không đủ màn hình để chứa thì sẽ ra dạng số thập phân. Với trường hợp này các bạn nên dùng phương pháp phân tích ra thừa số nguyên tố bằng cách kiểm tra số nguyên tố để phân tích A,B ra dạng cơ sở. 
Trường hợp tìm UCLN,BCNN của A,B,C thì sao? 
Rất đơn giản (A,B,C)= ((A,B),C) và [A,B,C]=[[A,B],C] 
Tuy nhiên có một số trường hợp tìm BCNN bằng cách trên sẽ khó khăn vì số tràn màn hình, để xử lý thì nên dùng công thức 
[A,B,C]=ABC(A,B,C)/{(A,B).(B,C).(C,A)}
VD: tìm ƯCLN() ta làm như sau 
(không ra phân số) 
bạn bấm vào phím replay thì con trỏ xuất hiện trên màn hình sửa thành 
ta lại lập PS 
lại làm lại 
thì 
ta có thể gán các số vào trong máy sau đó kết quả phép tính thưc ba lại gán vô cho số lớn trong hai số cần tìm 
ta dùng kiến thức này là với 
Nếu dùng mà ko được: 
------------ Đối với loại máy ms : 
số A [shift] [sto] A [=] 
số B [shift] [sto] B [=] 
[mode]...fix 0 
a[=] 
nhập vào biểu thức: 
10^(log Ans)-0.5:Ans/b[=] : 10^(log Ans) -0.5: b/Ans[shift][sto] B 
rồi thực hiện dãy lặp: [shift][rnd][=]... đến khi có lỗi... 
Hình như vậy là tính được UCLN còn BCNN thi lấy tích A và B chia cho UCLN là xong.
III. TÌM BCNN, UCLN
Máy tính cài sẵn chương trình rút gọn phân số thành phân số tối giản 
Tá áp dụng chương trình này để tìm UCLN, BCNN như sau:
 + UCLN (A; B) = A : a
 + BCNN (A; B) = A . b
Ví dụ 1: Tìm UCLN và BCNN của 2419580247 và 3802197531
HD: Ghi vào màn hình : và ấn =, màn hình hiện 
UCLN: 2419580247 : 7 = 345654321
BCNN: 2419580247 . 11 = 2.661538272 . 1010 (tràn màn hình)
Cách tính đúng: Đưa con trỏ lên dòng biểu thức xoá số 2 để chỉ còn 419580247 . 11
Kết quả : BCNN: 4615382717 + 2.109 . 11 = 26615382717
Ví dụ 2: Tìm UCLN của 40096920 ; 9474372 và 51135438
Giải: Ấn 9474372 ¿ 40096920 = ta được : 6987¿ 29570.
UCLN của 9474372 và 40096920 là 9474372 : 6987 = 1356.
Ta đã biết UCLN(a; b; c) = UCLN(UCLN(a ; b); c)
Do đó chỉ cần tìm UCLN(1356 ; 51135438).
Thực hiện như trên ta tìm được: 
UCLN của 40096920 ; 9474372 và 51135438 là : 678
Bài tập:
Cho 3 số 1939938; 68102034; 510510.
Hãy tìm UCLN của 1939938; 68102034.
Hãy tìm BCNN của 68102034; 510510.
Gọi B là BCNN của 1939938 và 68102034. Tính giá trị đúng của B2.
Câu 6(5đ) Cho a=1 092 609; b= 277 263; c = 9153
Tìm ƯCLN(a;b;c).
Tìm BCNN(a;b;c) với kết quả đúng