Chuyên đề Đại số Lớp 6 - 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 (Có lời giải chi tiết)

Nội dung text: Chuyên đề Đại số Lớp 6 - 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 (Có lời giải chi tiết)

1. Đ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 abMc và (b, c) 1 thì aMc . 3. Nếu aMm và aMn thì aMBCNN(m,n) . Đặc biệt, nếu aMm,aMn và (m,n) 1 thì aMmn 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 . + Nếu a chia hết cho b thì ƯCLN (a,b) b .
2. 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 4Md và 5n 1Md nên 5(3n 4) 3(5n 1)Md , tức là 17Md Suy ra d {1;17} . Để 3n 4 và 5n 1 có ước chung khác 1 , ta phải có 3n 4M17 tức là 3n 4 34M17 hay 3(n 10)M17 Ta lại có (3,17) 1 nên n 10M17 . 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. Bài 4: Có ba đèn tín hiệu, chúng phát sáng cùng một lúc vào 8 giờ sáng. Đèn thứ nhất cứ 4 phút phát sáng một lần, đèn thứ hai cứ 6 phút phát sáng một lấn, đèn thứ ba cứ 7 phút phát sáng một lần. Thời gian đầu tiên để cả ba đèn cùng phát sáng sau 12 giờ trưa là lúc mấy giờ? Lời giải: Gọi thời gian ít nhất để sau đó, cả ba đèn lại cùng phát sáng là a (phút).
3. 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ì nM45;nM40 n BC(40,45) n B(BCNN(40,45)) Ta có: 40 23.5;45 32.5 BCNN(40,45) 23.32.5 360 n B(360) n 700 700 n 800 Vậy Số học sinh là 700 . Dạng 2: Thuật toán EUCLID để tìm ƯCLN Trong toán học, giải thuật Euclid (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.
4. 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 rk 2 qk rk 1 rk 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ư rk 2 và rk 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 bước: a q0b r0 b q1r0 r1 r0 q2r1 r2 r1 q3r2 r3 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 .
5. 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 Vậy ƯCLN 1575,343 7 14 7 4 Bài 2: Tìm ƯCLN 58005,2835 bằng thuật toán 0Euclide2 Lời giải: Ta có: 58005 20.2835 1305 (58005, 2835) (2835,1305); 2835 2.1305 225;1305 5.225 180 225 1.180 45;180 4.45 ƯCLN 45 . Bài 3: Chứng minh rằng ƯCLN (n 1,3n 4) 1, n ¥ . Lời giải: Cách 1: 3n 4Md Gọi d UCLN(n 1,3n 4),d ¥ * (3n 4) 3(n 1)Md 1Md d 1 . n 1Md Vậy ƯCLN (n 1,3n 4) 1, n ¥ .
6. Theo đầu bài ta có: 239 14 225Mn 2 2 2  n UC(225,350) n U (UCLN(225,350));225 3 .5 ;350 2.5 .7 373 23 350Mn Ư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)M10,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ả Bài 9: Một trường học có số lượng học sinh không quá 1000 . Khi xếp hàng 20,25,30 thì đều dư 15 . Nhưng khi xếp hàng 41 thì vừa đủ. Tính số học sinh của trường? Lời giải: Gọi số học sinh của trường là: n ( n N * ) Theo bài ra ta có: n 1000 Lại có: n 15M20,25,30;nM41;n 15 BC(20,25,30) B(BCNN(20,25,30) 300 n 15 B(300) n 315,615,915 Mà n 15 1000 15 985 n 1 300,600,900 n 615 nM41 Vậy số học sinh của trường là 615 (học sinh). Bài 10: Tìm số tự nhiên nhỏ nhất, biết rằng khi chia số đó cho 12,18,23 thì số dư lần lượt là 11,17,9 Lời giải: Gọi số tự nhiên cần tìm là: a ( a N ) Theo bài ta có: a 12k 1 18q 17 2.3.p 9(k, p, q N ) Ta tìm số b sao cho: a bM12,18,23 Nhận thấy: a 37 12k 48M12;a 37 18q 54M18;a 37 23p 46M23 a 37 BC(12,18,23) Vì a nhỏ nhất a 37 BCNN(12,18,23);12 22.3;18 2.32 ;23 23 BCNN(12,18,23) 22.32.23 828
7. Theo đề khi chia 355 cho a ta được số dư là 13 nên ta có 355 a.m 13 với m N * và a 13 hay a.m 342 18.19 (1) và khi chia 836 cho a có số dư là 8 836 a.n 8 a.n 828 18.46 với n N * (2). Từ (1) và (2) suy ra a 18 là số tự nhiên cần tìm. Bài 15: Một số chia cho 7 dư 3 , chia cho 17 dư 12 , chia cho 23 dư 7 . Hỏi số đó chia cho 2737 dư bao nhiêu? Lời giải: Gọi số đã cho là A . Theo bài ra ta có: A 7a 3 17b 12 23c 7 Mặt khác: A 39 7a 3 39 17b 12 39 23c 7 39 7 a 6 17 b 3 23 c 2 Như vậy A 39 đồng thời chia hết cho 7,17 và 23 . Nhưng ƯCLN 7,17,23 1 A 39 M7.17.23 A 39 M2737 A 39 2737.k A 2737k 39 2737 k 1 2698 Do 2698 2737 nên 2698 là số dư của phép chia số A cho 2737 . Bài 16: Tìm số tự nhiên lớn nhất có 3 chữ số, sao cho chia nó cho 8 thì dư 7 và chia nó cho 31 thì dư 28 . Lời giải: Gọi số cần tìm là a ( a N ,100 a 999 ) Vì a chia cho 8 thì dư 7 và chia nó cho 31 thì dư 28 nên: a 7M8 a 7 8M8 a 1M8 a 1 64M8 a 65M8 a 28M31 a 28 31M31 a 3M31 a 3 62M31 a 65M31 Vì 8,31 1 a 65 M248 a 248k 65 k N * Vì a là số có 3 chữ số lớn nhất nên k 4 , khi đó a 248.4 65 927 Vậy số cần tìm là 927 . Bài 17: Tìm số tự nhiên nhỏ nhất có 3 chữ số biết rằng số đó chia cho 4,6,7 đều dư 3 . Lời giải: Gọi số cần tìm là a . điều kiện a N , a 100 Vì a chia cho 4,6,7 đều dư 3 a 3 M4,6,7 Mà a nhỏ nhất nên a 3 nhỏ nhất a 3 BCNN 4,6,7 Mà ƯCLN 4,6,7 1 BCNN 4,6,7 4.6.7 168 a 3 168 a 171 Vậy số cần tìm là 171 .
8. Vì 3 n 1 M n 1 nên để 3n 14 M n 1 thì 7M n 1 n 1 phải là ước của 7 n 1 7; 1;1;7 n 6;0;2;8 Mà n N , nên n 0;2;8 Vậy n 0;2;8 thì 3n 14 chia hết cho n 1 . n 15 Bài 3: Tìm số tự nhiên n biết là số tự nhiên. n 3 Lời giải: n 15 Để là số tự nhiên thì n 15 chia hết cho n 3 n 3 n 15 n 3 chia hết cho n 3 12 chia hết cho n 3 Mà n N nên n 3 phải là số tự nhiên lớn hơn hoặc bằng 3 và đồng thời là ước của 12 n 3 3;4;6;12 n 0;1;3;9 n 15 Vậy n 0;1;3;9 thì là số tự nhiên. n 3 Bài 4: Tìm số tự nhiên n biết n2 3n 6 M n 3 Lời giải: Ta có n2 3n 6 n n 3 6 Vì n n 3 M n 3 , nên để n2 3n 6 M n 3 thì 6M n 3 Mà n N , nên n 3 phải là số tự nhiên lớn hơn hoặc bằng 3 và đồng thời là ước của 6 n 3 3;6 n 0;3 Vậy n 0;3 thì n2 3n 6 M n 3 n 1 Bài 5: Tìm số tự nhiên n biết có giá trị là một số nguyên n 2 Lời giải: n 1 Ta có là một số nguyên khi n 1 M n 2 n 2 Ta có n 1 n 2 3, do đó n 1 M n 2 khi 3M n 2 n 2 là ước của 3
9. Lời giải: Gọi ƯCLN 9n 24;3n 4 d d N* 9n 24Md 9n 24Md Khi đó ta có: 9n 24 9n 12 d 12Md 3n 4Md 9n 12Md d U 12 1; 2; 3; 4; 6; 12 Do 3n 4 Md, mà 3n 4 không chia hết cho 3 , nên d 3;6;13 (loại) Do đó d 1;2;4 - Để d 2 thì n phải chẵn - Để d 4 thì n phải chia hết cho 4 - Để d 1 thì n là số lẻ Vậy n 4k 2 k N thì ƯCLN 9n 24;3n 4 2 n 4k k N thì ƯCLN 9n 24;3n 4 4 n 2k 1 k N thì ƯCLN 9n 24;3n 4 1 . Bài 10: Biết a,b 95 . Tìm a b,a b Lời giải: Gọi ƯCLN a b,a b d d N* a bMd 2bMd d U 2 hoặc d U b a bMd a bMd và 2aMd hoặc d U 2 hoặc d U a a bMd mà ƯCLN a,b 95, nên d 95 hoặc d 2 Vậy ƯCLN a b,a b 2 hoặc d 95 . Bài 11: Học sinh khối 6 khi xếp hàng; nếu xếp hàng 10 , hàng 12 , hàng 15 đều dư 3 học sinh. Nhưng khi xếp hàng 11 thì vừa đủ. Biết số học sinh khối 6 chưa đến 400 học sinh. Tính số học sinh khối 6? Lời giải: Gọi số học sinh khối 6 là a 3 a 400 Vì khi xếp hàng 10 , hàng 12 , hàng 15 đều dư 3 học sinh a 3M10;12;15
10. Lời giải: Gọi số học sinh là a a N * Vì số học sinh khi xếp hàng 10;12;15 đều dư 3 a 3 BC 10;12;15 Mà BCNN 10;12;15 60 a 3 60k k N * a 6kk 3 Ta có bảng sau: k 1 2 3 4 5 6 7 a 63 123 183 243 303 363 423 Vì số học sinh chưa đến 400 bạn và khi xếp hàng 11 thì không dư nên a 400 và aM11 Trong các giá trị trên, chỉ có a 363 thỏa mãn bài toán Vậy số học sinh cần tìm là 363 học sinh. Bài 15: Một đơn vị bộ đội khi xếp hàng, mỗi hàng có 20 người, hoặc 25 người, hoặc 30 người đều thừa 15 người. Nếu xếp mỗi hàng 41 người thì vừa đủ (không có hàng nào thiếu, không có ai ở ngoài hàng). Hỏi đơn vị có bao nhiêu người, biết rằng số người của đơn vị chưa đến 1000 ? Lời giải: Gọi số người của đơn vị bộ đội là x x N *;41 x 100 Ta có a : 20 dư 15 x 15 M20 a : 25 dư 15 x 15 M25 a :30 dư 15 x 15 M30 x 15 BC 20,25,35 Ta có 20 22.5;25 52;30 2.3.5 BCNN 20,25,30 22.52.3 300 BC 20,25,35 300k k N x 15 300k x 300k 15 Mà x 1000 nên chỉ xét k 1;2;3, khi đó x 315;615;915 Vì số bộ đội khi xếp mỗi hàng 41 người thì vừa đủ tức là: xM41, do đó có x 615 thỏa mãn bài toán Vậy đơn vị bộ đội có 615 người. Bài 16: Cho m,n là hai số tự nhiên. Gọi A là tập hợp các ước chung của m và n . B là tập hợp các ước số chung của 11m 5n và 9m 4n . Chứng minh rằng A B. Lời giải: