Giáo án Tự chọn Chủ đề 3: Số nguyên tố - ƯCLN– BCNN

Chủ đề 3: SỐ NGUYÊN TỐ - ƯCLN– BCNN 1.Số nguyên tố: số nguyên tố là số tự nhiên lớn hơn 1, chỉ có 2 ước là 1 và chính nó. VD: các số nguyên tố là: 2,3,5,7,11,13,vì chúng chỉ có 2 ước là 1 và chính nó. *Kiểm tra 1 số là số nguyên tố: Để kết luận số a là số nguyên tố (a>1) , chỉ cần chứng tỏ rằng nó không chia hết cho mọi số nguyên tố mà bình phương không vượt quá a. Như vậy: 29 là số nguyên tố vì nó không chia hết cho 2,3,5. 67 là số nguyên tố vì nó không chia hết cho 2, 3, 5, 7. 127 là số nguyên tố vì nó không chia hết cho 2,3,5,7,11. 173 là số nguyên tố vì nó không chia hết cho 2,3,5,7,11,13. * Phân tích 1 số tự nhiên lớn hơn 1 ra thừa số nguyên tố là viết số đó dưới dạng một tích các thừa số nguyên tố. VD: Chú ý: Trong cách phân tích 1 số ra thừa số nguyên tố, ta thường viết các ước nguyên tố theo thứ tự từ nhỏ đến lớn. 2.Cách xác định số lượng các ước của 1 số Để tính số lượng các ước của số m (m>1) ta xét dạng phân tích của số m ra thừa số nguyên tố: Nếu thì m có x+1 ước. Nếu thì m có (x+1)(y+1) ước. Nếu thì m có (x+1)(y+1)(z+1) ước. VD: *Số nên số 32 có 5 +1 = 6 (ước) là: 1,2,4,8,16,32. *Số nên số 63 có (2+1)(1+1) = 6 (ước) *Số nên số 60 có (2+1)(1+1)(1+1) = 12 (ước). 3. Ước chung lớn nhất (ƯCLN ) -Ước chung lớn nhất của hai hay nhiều số là số lớn nhất trong tập hợp các ước chung của các số đó. -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: .B1: Phân tích mỗi số ra thừa số nguyên tố. .B2: Chọn ra các thừa số nguyên tố chung. .B3: 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. VD: Chọn ra các thừa số chung, đó là 2 và 3. Số mũ nhỏ nhất của 2 là 2, của 3 là 1. Do đó nên: ƯCLN(36,84,168) = **Để tìm ước chung của các số đã cho, ta có thể tìm các ước của ƯCLN của các số đó. VD: ƯCLN (12,30) =6 , Do 6 có các ước là: 1; 2 ;3; 6 nên ƯC(12,30) = {1; 2; 3; 6}. 4.Bội chung nhỏ nhất (BCNN) -Bội chung nhỏ nhất của hai hay nhiều số là số nhỏ nhất khác 0 trong tập hợp các bội chung của các số đó. - 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: .B1: Phân tích mỗi số ra thừa số nguyên tố. .B2: Chọn ra các thừa số nguyên tố chung và riêng. .B3: 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. VD: Chọn ra các thừa số nguyên tố chung và riêng là 2, 3 và 5 ; số mũ lớn nhất của 2 là 3, của 3 là 2 và của 5 là 1. Vậy khi đó ta có: BCNN(8,18,30) = *Để tìm bội chung của các số đã cho, ta có thể tìm các bội của BCNN của các số đó. VD: Cho . Viết tập hợp A bằng cách liệt kê các phần tử. Giải: Ta phải tìm xBC(8,18,30) và x< 1000 Ta có :BCNN(8,18,30) = 360 Bây giờ lần lượt nhân 360 với 0,1,2,3 ta được: 0, 360, 720, 1080. So sánh với điều kiện bài toán, suy ra: A = {0; 360; 720} MỘT DẠNG TOÁN VỀ ƯCLN VÀ BCNN Trong chương trình số học lớp 6, sau khi học các khái niệm ước chung lớn nhất (ƯCLN) và bội chung nhỏ nhất (BCNN), các bạn sẽ gặp dạng toán tìm hai số nguyên dương khi biết một số yếu tố trong đó có các dữ kiện về ƯCLN và BCNN. Phương pháp chung để giải : 1/ Dựa vào định nghĩa ƯCLN để biểu diễn hai số phải tìm, liên hệ với các yếu tố đã cho để tìm hai số. 2/ Trong một số trường hợp, có thể sử dụng mối quan hệ đặc biệt giữa ƯCLN, BCNN và tích của hai số nguyên dương a, b, đó là : ab = (a, b).[a, b], trong đó (a, b) là ƯCLN và [a, b] là BCNN của a và b. Việc chứng minh hệ thức này không khó : Theo định nghĩa ƯCLN, gọi d = (a, b) => a = md ; b = nd với m, n thuộc Z+ ; (m, n) = 1 (*) Từ (*) => ab = mnd2 ; [a, b] = mnd => (a, b).[a, b] = d.(mnd) = mnd2 = ab => ab = (a, b).[a, b] . (**) Chúng ta hãy xét một số ví dụ minh họa. Ví dụ 1 : Tìm hai số nguyên dương a, b biết [a, b] = 240 và (a, b) = 16. Lời giải : Do vai trò của a, b là như nhau, không mất tính tổng quát, giả sử a ≤ b. Từ (*), do (a, b) = 16 nên a = 16m ; b = 16n (m ≤ n do a ≤ b) với m, n thuộc Z+ ; (m, n) = 1. Theo định nghĩa BCNN : [a, b] = mnd = mn.16 = 240 => mn = 15 => m = 1 , n = 15 hoặc m = 3, n = 5 => a = 16, b = 240 hoặc a = 48, b = 80. Chú ý : Ta có thể áp dụng công thức (**) để giải bài toán này : ab = (a, b).[a, b] => mn.162 = 240.16 suyy ra mn = 15. Ví dụ 2 : Tìm hai số nguyên dương a, b biết ab = 216 và (a, b) = 6. Lời giải : Lập luận như bài 1, giả sử a ≤ b. Do (a, b) = 6 => a = 6m ; b = 6n với m, n thuộc Z+ ; (m, n) = 1 ; m ≤ n. Vì vậy : ab = 6m.6n = 36mn => ab = 216 tương đương mn = 6 tương đương m = 1, n = 6 hoặc m = 2, n = 3 tương đương với a = 6, b = 36 hoặcc là a = 12, b = 18. Ví dụ 3 : Tìm hai số nguyên dương a, b biết ab = 180, [a, b] = 60. Lời giải : Từ (**) => (a, b) = ab/[a, b] = 180/60 = 3. Tìm được (a, b) = 3, bài toán được đưa về dạng bài toán 2. Kết quả : a = 3, b = 60 hoặc a = 12, b = 15. Chú ý : Ta có thể tính (a, b) một cách trực tiếp từ định nghĩa ƯCLN, BCNN : Theo (*) ta có ab = mnd2 = 180 ; [a, b] = mnd = 60 => d = (a, b) = 3. Bài tập tự giải : 1) Tìm hai số nguyên dương a, b biết a/b = 2,6 và (a, b) = 5. ( a = 65 và b = 25). Chú ý : phân số tương ứng với 2,6 phải chọn là phân số tối giản do (m, n) = 1. 2) Tìm a, b biết a/b = 4/5 và [a, b] = 140. (a = 28 ; b = 35). 3) Tìm hai số nguyên dương a, b biết a + b = 128 và (a, b) = 16. ( a = 16, b = 112 hoặc a = 48, b = 80 ) 4)Tìm a, b biết a + b = 42 và [a, b] = 72. (a = 3.6 = 18 , b = 4.6 = 24) 5)Tìm a, b biết a - b = 7, [a, b] = 140. ( a = 5.7 = 35 ; b = 4.7 = 28 ). 6) Tìm hai số a, b biết 7a = 11b và (a, b) = 45. 7) Tìm hai số biết tổng của chúng bằng 448, ƯCLN của chúng bằng 16 và chúng có các chữ số hàng đơn vị giống nhau. 8) Cho hai số tự nhiên a và b. Tìm tất cả các số tự nhiên c sao cho trong ba số, tích của hai số luôn chia hết cho số còn lại. I/ Ghi số tự nhiên. - Hệ thập phân: Ví dụ 1: Tìm số tự nhiên có số tận cùng là 3, nếu xoá số tận cùng thì ta được số mới nhỏ hơn số ban đầu 2010 Giải: Gọi: Số cần tìm là: (); Số sau khi xoá đi số tận cùng là x: Theo bài ra ta có phương trình: 10x + 3 – x = 2010 Vậy số cần tìm là: 2233 Ví dụ 2: Tìm số tự nhiên có , biết Giải: Ta có Từ đã: , vì ƯCLN(3,5) = 1 (ƯCLN(11,15) =1) Do Vậy số cần tìm là 78; 87; 69; 96 II/ Các phép tính trong N; phép chia có dư. 1/ Phép tính(+; -; x; :) Phép tính luỹ thừa: + + + + Quy ước: + Lưu ý: + Những số có số tận cùng là 4, nếu luỹ thừa chẵn thì số tận cùng là 6; nếu luỹ thừa lẻ thì số tận cùng là 4 ; + Những số có số tận cùng là 9, nếu luỹ thừa chẵn thì số tận cùng là 1; nếu luỹ thừa lẻ thì số tận cùng là 4 ; Ví dụ 1: So sánh và Giải: Ta có: Do 9 < 10, nên 9100< 10100 Vậy< Ví dụ 2: Ta có 24 = 16 có số tận cùng là 6. 122004 =(10 + 2)2004 = (102004 + 2004.2.102003+....+ 2004.10.22003+ 22004) Mà 102004 + 2.102003+....+ 10.22003 Vây xét 22004 = (24)501 có số tận cùng là 6, nên 122004có số tận cùng là 6. B/ Phép chia hết trong tập hợp các số nguyên. I/ Một số phương pháp chứng minh chia hết. Tính chất: + Sử dụng tính chất “ Trong n số tự nhiên có một và chỉ một số chia hết cho n”. + Tích của hai số tự nhiên liên tiếp chia hết cho 2. + Tích của ba số tự nhiên liên tiếp chia hết cho 6. + Tích của hai số tự nhiên chẵn liên tiếp chia hết cho 8. + Tích của 5 số tự nhiên liên tiếp chia hết cho 120. Các dấu hiệu chia hết Dấu hiệu chia hết cho 11 Cho A = ... a5 a4 a3 a2 a1 a0. A 11 [(a0 + a2 + a4 +...) – (a1 + a3 + a5 + ... )] 11. Chứng minh: A = (a0 + 102a2 + 104a4 + ... ) + (10a1 + 103a3 + 105a5 + ... ) Chú ý rằng : 102 = 99 + 1, 104 = 9999 + 1,..., tổng quát : 102k = bội 11 + 1 , còn 10 = 11 – 1, 103 = 1001 – 1, 105 = 100001 – 1,... Tổng quát 102k + 1 = bội 11 – 1 . Do đã : A = ( bội 11 + a0 + a2 + a4 + ...) + + (bội 11 – a1 – a3 – a5 - ... ) = béi 11 + ( a0 + a2 + a4 + ...) – (a1 + a3 + a5 +...) Như vậy điều kiện cần và đủ đó một số chia hết cho 11 là : Tổng các chữ số hàng lẻ và tổng các chữ số hàng chẵn của số đã có hiệu chia hết cho 11 Ví dụ 1: Chứng minh: n3 + 11n6 Ví dụ 2: Cho 717 + 17.3 - 1 9. Chứng minh: 718 + 18.3 - 1 9 (Đề thi chọn HSG lớp 9 huyện Văn Bàn năm học 2009 - 2010) Giải: Ta có: 717 + 17.3 - 1 9, Đặt: 717 + 17.3 - 1 = 9k. Mặt khác: 718 + 18.3 – 1 = 7.(717 + 17.3 – 1) + [18.3 – 1 - 7.(17.3 - 1)] = 7.9k – 33.9 = 9.(7k - 33) 9 Vậy: 718 + 18.3 - 1 9. Ví dụ3: Cho 717 + 17.3 - 1 3. Chứng minh: 718 + 18.3 - 1 3 (Đề thi chọn HSG líp 9, cấp trường năm học 2010 - 2011) Sử dụng định lý mở rộng. Các ví dụ: Ví dụ1: Chứng minhrằng 20n + 16n - 3n + 1 323 3. Một số phương pháp chứng minh khác. Chứng minh quy nặp: Nguyên tắc chứng minh + Xét vì n = n0 đúng. + Gỉa sử vì n = k đúng. + Biến đổi chứng minh vì n = k + 1 đúng Từ đã được điều phải chứng minh. Bài tập vận dụng: Chứng minhrằng c) Giải: + Vì n = 1; 0 hiển nhiên đúng, + Gỉa sử, n = k đúng, tức là:. Đặt: . + Xét vì n = k + 1,ta có Vậy n = k + 1 đúng, Kết luận: b) Làm tương tự: c) Giải: + Vì n = 0 hiển nhiên đúng, vì 100 + 18.0 – 1 = 027 + Gỉa sử n = k đúng, tức là , Đặt: + Xét vì n = k +1 ta có: Vậy n = k + 1 đúng, Kết luận: Các bài tập vận dụng dấu hiệu chia hết Ví dụ 1: Tìm chữ số x,y đó Ví dụ 2: Tìm chữ số x,y đó (Đề thi chọn HSG lớp 9 huyện Văn Bàn năm học 2009 - 2009) Bài 3: Cho S=21 + 22 + 23 + ... + 2100 . a/ Chứng minh S chia hết cho 3. b/ Chứng minh S chia hết cho 15. c/ S tận cùng là chữ số nào? Lời giải a/ S = 21 + 22 + 23 + ... + 2100 =(21 + 22 )+ (23 + 24)+ ... +(299+ 2100) = 2(1 + 2) + 23(1 + 2) + + 299(1 +2). = 3.(2 + 23 ++ 299) 3 Vậy S 3 b/ Nhóm 4 số hạng một của S ta được:S = 15.(2 + 25 + 29 ++ 227) 15 . c/ S 15 và S là số chẵn nên S tận cùng là 0 3.Các dạng bài tập khác sử dụng. Tìm số tận cùng. Sử dụng phép chia có dư. Sử dụng nguyên tắc De-rich-ne. Sử dụng đồng dư thức. C/ Số nguyên tố. I/ Số nguyên tố, hợp số. 1. Bài tập liên quan đến số nguyên tố. Ngoài các kiến thức về số nguyên tố , số nguyên tố cùng nhau. ƯCLN, BCNN, ta có thêm một số tính chất về chia hết. 1) Nếu một tích chia hết cho số nguyên tố p thì tồn tại một thừa số của tích chia hết cho p. Hệ quả: Nếu an chia hết cho số nguyên tố p thì a chia hết cho p . 2) Nếu tích a.b chia hết cho m trong đó b và m là hai số nguyên tố cùng nhau thì a chia hết cho m. Thật vậy, phân tích m ra Theo số nguyên tố : m = a1k1a2k2 ...an kn (1) Vì a.b chia hết cho m nên a.b chứa tất cả các thừa số nguyên tố a1, a2,...an vì số mò lớn hơn hoặc bằng số mò của các thừa số nguyên tố đó trong (1). Nhưng b và m nguyên tố cùng nhau nên b không chứa thừa số nguyên tố nào trong các thừa số a1 , a2, ..., an. Do đó a chứa tất cả các thừa số a1 , a2 , ... an tức là a chia hết cho m. 3) Nếu a chia hết cho m và n thì a chia hết cho BCNN của m và n. Thật vậy, a chia hết cho m và n nên a là bội chung của m và n so đó chia hết cho BCNN ( m,n). Hệ quả: Nếu a chia hết cho hai số nguyên tố cùng nhau m và n thì a chia hết cho tích m.n. II. Những ví dụ Ví dụ 1 . Tìm số tự nhiên n sao cho 18n + 3 chia hết cho 7. Giải : Cách 1: 18n + 3 7 14n + 4n + 3 7 4n + 3 7 4n + 3 – 7 7 4n – 4 7 4(n – 1) 7 Ta lại có (4,7) = 1 nên n – 1 7 Vậy n = 7k + 1 ( k N). Cách 2: 18n + 3 7 18 n + 3 – 21 7 18n - 18 7 18(n – 1) 7 Ta lại có (18,7) = 1 nên n – 1 7 Vậy n = 7k + 1 ( k N) Nhận xét: Việc thêm bớt các bội của 7 trong hai cách giải trên nhằm đi đến một biểu thức chia hết cho 7 mà ở đó hệ số của n bằng 1. Ví dụ: 2. Cho biết a + 4b chia hết cho 13 (a, b N) . Chứng minh rằng 10a + b chia hết cho 13. Giải : Đặt a + 4b = x ; 10a + b = y . Ta biết x 13, cần chứng minh y 13. Cách 1: xét biểu thức: 10x – y = 10 (a + 4b) – (10a + b) = 10a + 40b – 10a – b = 39b Như vậy 10x – y 13 Do x 13 nên 4y 13. Suy ra y 13 Cách 2: Xét Biểu thức: 4y – x = 4 (10a + b) – (a + 4b) = 40a + 4b – A – 4b = 39a Như vậy 4y – x 13 Do x 13 nên 4y 13. Ta lại có ( 4,13) = 1 nên y 13 Cách 3 : Xét biểu thức: 3x + y = 3 (a + 4b) + (10a + b) = 3a + 12b + 10a + b = 13a + 13b. Như vậy 3x + y 13 Do x 13 nên 3x 13 . Suy ra y 13 Cách 4: Xét biểu thức: x + 9y = a + 4b + 9 (10a + b) = a + 4b + 90a + 9b = 91a + 13b Như vậy x + 9y 13 Do x 13 nên 9y 13 . Ta lại có (9,13) – 1, nên y 13 Nhận xét: Trong các cách giải trên, ta đã đưa ra các biểu thức mà sau khi rút gọn có một số hạng là bội của 13, khi đó số hạng thứ hai (nếu có) còng là bội của 13. Hệ số của a ở x là 4, hệ số của a ở y là 1 nên xét biểu thức 10x – y nhằm khử a (tức là làm cho hệ số của bằng 0) , xét biểu thức 3x + y nhằm tạo ra hệ số của a bằng 13. Hệ số của b ở x là 4, hệ số của b ở y là 1 nên xét biểu thức 4y – x nhằm khử b, xét biểu thức x + 9y nhằm tạo ra hệ số của b bằng 13. Ví dụ 3. Chứng minh rằng nếu p là số nguyên tố lớn hơn 3 thì (p – 1)(p + 1) chia hết cho 24. Giải . Ta có (p – 1)p(p + 1) 3 mà (p,3) = 1 nên (p – 1)(p + 1) 3 (1) p là số nguyên tố lớn hơn 3 nên p là số lẻ, p – 1 và p + 1 là hai số chẵn liên tiếp. Trong hai số chẵn liên tiếp, có một số là béi của 4 nên tích của chúng chia hết cho 8 (2). Từ (1) và (2) suy ra (p – 1)(p + 1) chia hết cho hai số nguyên tố cùng nhau 3 và 8. Vậy (p – 1)(p + 1) 24. III. Tìm số bị chia biết các số chia và số dư trong hai phép chia Ví dụ 1. Tìm số tự nhiên nhỏ nhất khi chia cho 5 thì dư 1, chia cho 7 thì dư 5. Giải : Gọi n là số chia cho 5 dư 1, chia cho 7 dư 5 Cách 1: Vì n khằngchia hết cho 35 nên n có dạng 35k + r ( k, r N, r < 35), trong đó r chia 5 dư 1, chia 7 dư 5. Số nhỏ hơn 35 chia cho 7 dư 5 là 5, 12, 19, 26, 33 trong đó chỉ có 26 chia cho 5 dư 1, vậy r = 26. Số nhỏ nhBất có dạng 35k + 26 là 26. Cách 2: Ta có n – 1 5 n – 1 + 10 5 n + 9 (1) . Ta có n – 5 7 n – 5 + 14 7 n + 9 7 (2) . Từ (1) và (2) suy ra n + 9 35 số n nhỏ nhBất có tính chBất trên là n = 26 Cách 3: n = 5x + 1 = 7y + 5 Þ 5x = 5y + 2y + 4 Þ 2(y + 2) 5 Þ y + 2 5 Giá trị nhỏ nhBất của y bằng 3, giá trị nhỏ nhất của n bằng 7.3 + 5 = 26. Ví dụ 2: . Tìm số tự nhiên n có bội chữ số sao cho chia n cho 131 thì dư 112, chia n cho 132 thì dư 98. Giải : Cách 1: Ta có 131x + 112 = 132y + 98 131x = 131y + y – 14 y – 14 131 y = 131k + 14 ( k N) n = 132.(131k + 14) + 98 = 132.131k + 1946 Do n có bội chữ số nên k = 0 , n = 1946 Cách 2: Từ 131x = 131y + y – 14 suy ra 131(x – y) = y – 14 . Nếu x > y thì y – 14 ³ 131 y ³ 145 n có nhiều hơn bội chữ số. Vậy x = y, do đó y = 14, n = 1946, Cách 3. Ta có n = 131x + 112 nên 132 n = 131.132x + 14784 (1) Mặt khác n = 132y + 98 nên 131n = 131.132y + 12838 (2) Từ (1) và (2) suy ra 132n – 131 n = 131.132(x – y) + 1946 n = 131.132(x – y) + 1946. Vì n có bội chữ số nên n = 1946. III/ ƯCLN, BCNN. 1) Tìm hai số trong đó biết ƯCLN của chúng. Ví dụ 1. Tìm hai số tự nhiên, biết rằng tổng của chúng bằng 84, ƯCLN của chúng bằng 6. Giải : Gọi hai số phải tìm là a và b ( a £ b) . Ta có (a,b) = 6 nên a = 6a’; b = 6b’ trong đó (a’, b’) = 1 (a, b, a’, b; N) Do a + b = 84 nên 6 (a’ + b”) = 84 suy ra a’ + b’ = 14 Chọn cặp số a’, b’ nguyên tố cùng nhau có tổng bằng 14 (a’ £ b’), ta được: a’ 1 3 5 Do đó a 6 18 30 b’ 13 11 9 b 78 66 54 Ví dụ 2: Tìm hai số tự nhiên có tích bằng 300. ƯCLN bằng 5. Giải : Gọi hai số phải tìm là a và b ( a £ b). Ta có (a,b) = 5 nên a = 5a’, b = 5b’ trong đó (a’, b’) = 1 Do ab = 300 nên 25a’b’ = 300 suy ra a’b’ = 12 = 4.3 Chọn cặp số a’, b’ nguyên tố cùng nhau có tích bằng 12 (a’ £ b’) ta được: a’ 1 3 Do đó a 5 15 b’ 12 4 b 60 20 2) Các bài toán phối hợp giữa BCNN của các số vì ƯCLN của chúng. Ví dụ 3 . Tìm hai số tự nhiên biết rằng ƯCLN của chúng bằng 10, BCNN của chúng bằng 900. Giải : Gọi các số phải tìm là a và b, giả sử a £ b . Ta có (a,b) = 10 nên a = 10a’, b = 10b’, (a’,b’) = 1; a’ £ b. Do đó ab = 100 a’b’(1). Mặt khác ab = [a,b].(a,b) = 900.10 = 9000 (2) Từ (1) và (2) suy ra a’b’ = 90. Ta có các trường hợp: a’ 1 2 5 9 Do đó a 10 20 50 90 b’ 90 45 18 10 b 900 450 180 100 3) Tìm ƯCLN của hai số bằng thuật toán Ơ clit Ví dụ 4 . Cho hai số tự nhiên a và b (a > b) a) Chứng minh rằng nếu a chia hết cho b thì (a,b) = b b) Chứng minh rằng nếu a không chia hết cho b thì ƯCLN của hai số bằng ƯCLN của số nhỏ và số dư trong phép chia số lớn cho số nhỏ. c) Dùng các nhận xét trên đó tìm ƯCLN (72,56). Giải : a) Mọi ước chung của a và b hiểnn nhiên là ước của b. Đảo lại,do a chia hết cho b nên b là ước chung của a và b. Vậy (a,b) = b. b) Gọi r là số dư trong phép chia a cho b (a > b) . Ta có a = bk + r (k N), cần chứng minh rằng (a, b) = (b,r) Thật vậy, nếu a và b cùng chia hết cho d thì r chia hết cho d, do đó ước chúng của a và b còng là ước chung của b và r (1). Đảo lại nếu b và r cùng chia hết cho d thì a chia hết cho d, do đó ước chung của b và r còng là ước chung của a và b (2). Từ (1) và (2) suy ra tập hợp các ước chung của a và b và tập hợp các chung của b và r bằng nhau. Do đó hai số lớn nhất trong hai tập hợp đó còng bằng nhau, tức là (a, b) = (b,r) c) 72 chia 56 dư 16 nên 972,56) = ( 56,16) 56 chia 16 dư 8 nên (56,16) = (16,8); 16 chia hết cho 8 nên (16,8) = 8 . Vậy (72,56) = 8 Nhận xét : Giả sử a khôngchia hết cho b và a chia hết cho b dư r1, b chia cho r1 dư r2, r1 chia cho r2 dư r3... , rn – 2 chia cho rn-1 dư rn’ rn-1 chia cho rn dư 0. (dãy số b, r1 , r2 ,...,rn là dãy số tự nhiên giảm dần nên số phép chia là hữu hạn do đó quá trình trên phải kết thúc vì một số dư bằng 0). Theo chứng minh ở ví dụ trên ta có (a, b) = (b,r1) = (r1,r2) =... =(rn-1’rn)= rn (vì rn-1 chia hết cho rn). Như vậy ƯCLN (a,b) là số chia cuối cùng trong dãy các phép chia liên tiếp a cho b; b cho r1; r1 cho r2;... trong đó r1,r2,... là số dư trong các phép chia theo thứ tự trên. Trong thực hành ngưêi ta đặt tính như sau: 72 56 56 16 1 16 8 3 0 2 Việc thực hiện một dãy phép chia liên tiếp như trên được gọi là thuật toán Ơ–clit. Trường hợp tìm ƯCLN của ba số, ta tìm ƯCLN của hai số rồi tìm ƯCLN của kết quả vì số thứ ba. 4) Hai số nguyên tố cùng nhau: Hai số nguyên tố cùng nhau là hai số có ƯCLN bằng 1. Nói cách khác, chúng chỉ có ước chung duy nhất là 1. Ví dụ 1. Chứng minh rằng a) Hai số tự nhiên liên tiếp (khác 0) là hai số nguyên tố cùng nhau. b) Hai số lẻ liên tiếp là hai số nguyên tố cùng nhau. c) 2n + 1 và 3n + 1 ( n N) là hai số nguyên tố cùng nhau. Giải: a) Gọi d ƯC (2n + 1,2n + 3) (2n + 3) – (2n + 1) d 2 d d {1; 2} Nhưng d ¹ 2 vì d là ước của số lẻ. Vậy d = 1 c) Gọi d ƯC (2n + 1, 3n + 1) 3 (2n + 1) – 2 (3n + 1) d 1 d d=1 Ví dụ 2. Tìm số tự nhiên n đó các số 9n + 24 và 3n + 4 là các số nguyên tố cùng nhau. Giải : Giả sử 9n + 24 và 3n + 4 cùng chia hết cho số nguyên tố d thì 9n + 24 – 3 (3n + 4) d 12 d d { 2 ; 3} Điều kiện đề (9n + 24, 3n + 4) = 1 là d ¹ 2 và d ¹ 3. Hiển nhiên d ¹ 3 vì 3n + 4 không chia hết cho 3. Muốn d ¹ 2 phải có ít nhất một trong hai số 9n + 24 và 3n + 4 không chia hết cho 2. Ta thấy: 9n + 24 là số lẻ 9n lẻ n lẻ 3n + 4 là số lẻ 3n lẻ n lẻ Vậy điều kiện đó (9n + 24,3n + 4) = 1 là n lẻ. 5) Tìm ƯCLN của các biểu thức số Ví dụ 1. Tìm ƯCLN của 2n - 1 và 9n + 4 (n N) Giải : Gọi d ƯC (2n – 1, 9n + 4) 2(9n + 4) - 9(2n – 1) d 17 d d { 1 ; 17 } Ta có 2n – 1 17 2n – 18 17 2(n – 9) 17 n – 9 17 n = 17k + 9 ( k N) Nếu n = 17k + 9 thì 2n – 1 17 và 9n + 4 = 9.(17k + 9) + 4 = 17.9k + 85 17, do đó (2n – 1, 9n + 4) = 17 Nếu n ¹ 17k + 9 thì 2n – 1 không chia hết cho 17, do đó (2n – 1, 9n + 4) = 1 Ví dụ 2. Tìm ƯCLN của và 2n + 1 (n Î N *) Giải : Gọi d Î ƯC thì n(n + 1) d và 2n + 1 d Suy ra n(2n + 1) – n(n + 1) d tức là n2 d Từ n(n+1) d và n2 d suy ra n d . Ta lại có 2n + 1 d, do đó 1d, nên d = 1 Vậy ƯCLN của và 2n + 1 bằng 1 V. Số lượng các ước của một số (*) Nếu dạng phân tích ra thừa số nguyên tố của một số tự nhiên A = ax.by.cz... thì số lượng các ước của A bằng (x + 1)(y + 1)(z + 1)... Thật vậy, ước của A là số có dạng m.n.p... trong đó m có x + 1 cách chọn ( là 1, a, a2 ,... ax), n có y + 1 cách chọn (là 1, b , b2, ..., by), p có z + 1 cách chọn (là 1, c, c2,... cz),... Do đó số lượng các ước của A bằng (x + 1)(y + 1)(z + 1)... Ví dụ 1. Tìm số nhỏ nhất có 12 ước. Giải : Phân tích số phải tìm ra theo số nguyên tố : N = ax.by.cz... ta có (x + 1)(y + 1)(z + 1) ... = 12. ( x ³ y ³ z ³ ... ³ 1). Số 12 có bội, cách viết thành một tích của một hay nhiều theo số lớn hơn 1 là: 12 =12.1 = 6.2 = 4.3 = 3.2.2. Xét các trường hợp sau: a) n chứa một theo số nguyên tố : Khi đó x + 1 = 12 nên x = 11. Chọn theo số nguyên tố nhỏ nhất là 2, ta có số nhỏ nhất trong trường hợp này là 211. b) n chứa hai thừa số nguyên tố: Khi đó (x + 1)(y + 1) = 6.2 hoặc (x + 1)(y + 1) = 4.3, do đó x = 5, y = 1 hoặc x = 3 , y = 2. Để n nhỏ nhất ta chọn thứa số nguyên tố nhỏ ứng vì số m lớn, ta có n = 25.3 = 96 hoặc n = 23.32 = 72 . Số nhỏ nhất trong trường hợp này là 72. c) n chứa ba thừa số nguyên tố : Khi đó (x + 1)(y + 1)(z + 1) = 3.2.2 nên x = 2,y = z = 1 . Số nhỏ nhất là 22.3.5 = 60 So sánh ba số 211, 72, 60 trong ba trường hợp, ta thấy số nhỏ nhất có 12 ước là 60