Bài giảng Toán rời rạc - Chương 4: Số nguyên

Nội dung text: Bài giảng Toán rời rạc - Chương 4: Số nguyên

1. TOÁN RỜI RẠC - HK1 - NĂM 2015 -2016 Chương 4 SỐ NGUYÊN lvluyen@hcmus.edu.vn ∼luyen/trr FB: fb.com/trr2015 Trường Đại Học Khoa học Tự nhiên TP Hồ Chí Minh lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 1/15
2. Nội dung Chương 4. SỐ NGUYÊN 1. Phép chia 2. Ước chung lớn nhất và bội chung nhỏ nhất 3. Nguyên tố cùng nhau lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 2/15
3. 4.1. Phép chia Định nghĩa. Cho hai số nguyên a và b 6= 0. Ta gọi a chia hết cho b . nếu tồn tại số nguyên m sao cho a = mb, ký hiệu a . b. Khi đó a được gọi là bội của b, b được gọi là ước của a, ký hiệu b | a . . Ví dụ. 12 . 3, 156 . 2, 4 | 20, 56 | 21. Định lý. Cho a 6= 0, b và c là các số nguyên. Khi đó (i) Nếu a | b và a | c, thì a | (b + c); (ii) Nếu a | b, thì a | bc; (iii) Nếu a | b và b | c, thì a | c. Hệ quả. Cho a 6= 0, b và c là các số nguyên thỏa a | b và a | c. Khi đó a | mb + nc với m, n là số nguyên. lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 3/15
4. Bổ đề. Cho hai số nguyên a và b với b > 0. Khi đó tồn tại duy nhất cặp q, r ∈ Z sao cho a = qb + r với 0 ≤ r < b. Ví dụ. Cho a = −102 và b = 23. Khi đó −102 = −5 × 23 + 13 Ví dụ.(tự làm) Làm tương tự như ví dụ trên trong trường hợp: a = 121; b = 15. a = 214; b = 23 Định nghĩa. Trong bổ đề trên, q được gọi là phần thương, r được gọi là phần dư. Ký hiệu q = a div b, r = a mod b. Ví dụ. 13 ÷ 4 = 3, 13 mod 4 = 1, − 23 div 5 = −5, − 23 mod 5 = 2. lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 4/15
5. Đồng dư Định nghĩa. Cho m là số nguyên dương. Hai số nguyên a và b được gọi đồng dư với nhau theo modulo m, nếu a và b chia m có cùng phần dư. Ký hiệu a ≡ b (mod m) Ví dụ. 27 ≡ 43 (mod 4); 47 ≡ 92 (mod 5); 124 ≡ 58 (mod 6). Bổ đề. a ≡ b (mod m) khi và chỉ khi a − b chia hết cho m. Tính chất. (i) Với mọi số nguyên a, ta có a ≡ a (mod m) (ii) Nếu a ≡ b (mod m) thì b ≡ a (mod m) (iii) Nếu a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m) Tính chất. Nếu a ≡ b (mod m) và c ≡ d (mod m) thì a + c ≡ b + d (mod m) và ac ≡ bd (mod m) lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 5/15
6. 4.2. Ước chung lớn nhất và bội chung nhỏ nhất Định nghĩa. Số nguyên U > 0 được gọi là ước chung lớn nhất (ký hiệu UCLN) của hai số nguyên a, b nếu thỏa hai điều kiện sau: 1 U là một ước chung của a, b 2 Nếu số nguyên V là một ước chung của a, b thì V là ước của U. Định nghĩa. Số nguyên B > 0 được gọi là bội chung nhỏ nhất (ký hiệu BCNN) của hai số nguyên a, b nếu thỏa hai điều kiện sau: 1 U là một bội chung của a, b 2 Nếu số nguyên V là một bội chung của a, b thì V là bội của B. Ví dụ. UCLN của 15 và 25 là 5, BCNN của chúng là 75. Định lý. Ước chung lớn nhất (tương ứng bội chung nhỏ nhất) của a, b là duy nhất, ký hiệu (a; b), (tương ứng [a; b]). lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 6/15
7. Mệnh đề. Với mọi số tự nhiên m, n ta có mn = (m; n)[m; n] Nhận xét. 1 (a; b) = (±a; ±b) và [a; b] = [±a; ±b]. Do đó, từ đây về sau ta giả sử a, b ≥ 0. 2 Nếu a | b thì (a; b) = a và [a; b] = b. Ví dụ. (15; 20) = (−15; 20) = (−15; −20) = (15, −20) = 5 [15; 20] = [−15; 20] = [−15; −20] = [15, −20] = 60 (15, 60) = 15; [15, 60] = 60 lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 7/15
8. Thuật toán Euclide tìm UCLN d của a, b Nếu b là ước của a, thì d = b; Nếu không, ta lần lượt thực hiện các phép chia: a = q1b + r1 0 ≤ r1 r1 > r2 > · · · ≥ 0 nên phép chia như trên sẽ dừng sau một số hữu hạn bước. Gọi rn+1 là số dư đầu tiên bằng 0. Ta có rn−2 = qnrn−1 + rn 0 ≤ rn < rn−1 rn−1 = qn+1rn + 0 Khi đó rn là UCLN của a và b. lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 8/15
9. Ví dụ. Tìm UCLN và BCNN của a = 2322, b = 654. Giải. Ta có 2322 = 3 × 654 + 360 654 = 1 × 360 + 294 360 = 1 × 294 + 66 294 = 4 × 66 + 30 66 = 2 × 30 + 6 30 = 5 × 6 2322 × 654 Như vậy (2322; 654) = 6 và [2322; 654] = = 253098. 6 Ví dụ.(tự làm) Tìm UCLN và BCNN 1638 và 16457? Đáp án. (1638; 16457) = 7 và [1638; 16457] = 3850938. lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 9/15
10. Định lý. Giả sử d là UCLN của a và b. Khi đó tồn tại m, n ∈ Z sao cho: d = ma + nb. Ví dụ. Tìm UCLN d và BCNN e của a = 114 và b = 51? Từ đó tìm: a) hai số m, n ∈ Z sao cho d = ma + nb? 1 u v b) hai số u, v ∈ sao cho = + ? Z e a b Giải. Ta có 114 = 2 × 51 + 12 51 = 4 × 12 + 3 12 = 4 × 3. Suy ra (114; 51) = 3. Hơn nữa 3 = 51 − 4 × 12 = 51 − 4 × (114 − 2 × 51) = −4 × 114 + 9 × 51. lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 10/15
11. ab Ta có e = = 1938. Như vậy d a) m = −4, n = 9 b) Ta có d = ma + nb. Chia 2 vế cho ab, ta được d m n 1 n m = + ⇔ = + (vì ab = de). ab b a e a b Như vậy u = 9, v = −4. Ví dụ.(tự làm) Tìm UCLN d và BCNN e của a = 1638 và b = 16457? Từ đó tìm: a) hai số m, n ∈ Z sao cho d = ma + nb? 1 u v b) hai số u, v ∈ sao cho = + ? Z e a b lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 11/15
12. 4.3. Nguyên tố cùng nhau Định nghĩa. Hai số nguyên dương a, b được gọi là nguyên tố cùng nhau khi và chỉ khi (a; b) = 1. Mệnh đề. Cho a, b, c là số nguyên dương sao cho a | bc và (a; b) = 1. Khi đó a | c. Mệnh đề. Cho a, b, c là số nguyên dương sao cho (a; b) = 1 và (a; c) = 1. Khi đó (a; bc) = 1 Định lý. [Định lý căn bản của số học] Mọi số nguyên dương đều được phân tích thành tích hữu hạn những thừa số nguyên tố. Hơn nữa, cách phân tích này là duy nhất, sai khác một phép hoán vị các thừa số nguyên tố. Ví dụ. 72600 = 23 × 3 × 52 × 112. lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 12/15
13. t1 t2 tn Mệnh đề. Cho a = p1 p2 . . . pn . Khi đó ước của a có dạng s1 s2 sn d = p1 p2 . . . pn với 0 ≤ si ≤ ti. Do đó số ước của a là (t1 + 1)(t2 + 1) (tn + 1). Ví dụ. Tìm số ước của 72600? Giải. Ta có 72600 = 23 × 3 × 52 × 112 nên số ước của 72600 là (3 + 1)(1 + 1)(2 + 1)(2 + 1) = 72. Ví dụ.(tự làm) Phân tích các số sau ra thừa số nguyên tố và tìm số ước của chúng 84500; 664048; 743091250. lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 13/15
14. t1 t2 tn s1 s2 sn Mệnh đề. Cho a = p1 p2 . . . pn và b = p1 p2 . . . pn , ri, si ≥ 0. Khi đó i) a | b ⇔ ti ≤ si, ∀i = 1 . . . n l1 l2 ln ii) (a; b) = p1 p2 . . . pn với li = min{ti, si} h1 h2 hn iii) [a; b] = p1 p2 . . . pn với hi = max{ti, si} Ví dụ. Cho a = 1815000 và b = 234000. Hãy tìm (a; b) và [a; b]? Giải. Ta có 1815000 = 23 × 3 × 54 × 112. 234000 = 24 × 32 × 53 × 13. Khi đó (1815000; 234000) = 23 × 3 × 53. [1815000; 234000] = 24 × 32 × 54 × 11 × 13. lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 14/15
15. Ví dụ. Dùng thuật chia Euclid, tìm d = (a; b) và m; n ∈ Z sao cho 1 u v d = ma + nb. Sau đó ìm e = [a; b] và u, v ∈ sao cho = + ? Z e a b a) a = 116; b = −84. b) a = 72; b = 26. c) a = 414; b = 662. d) a = 123; b = 277. Ví dụ. Phân tích các số sau thành tích các số nguyên tố 36, 120, 720, 5040. Ví dụ. Tìm ước chung lớn nhất và ước chung nhỏ nhất bằng phương pháp phân tích ra thừa số nguyên tố của 12250 và 1575; 794750 và 19550 lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 15/15