tailieunhanh - Bài giảng Toán rời rạc: Chương 4 - Lê Văn Luyện

Bài giảng "Toán rời rạc - Chương 4: Số nguyên" cung cấp cho người học các kiến thức: Phép chia, ước chung lớn nhất và bội chung nhỏ nhất, nguyên tố cùng nhau. Bài giảng hữu ích dành cho các bạn sinh viên đang theo học môn này và những ai quan tâm dùng làm tài liệu học tập và nghiên cứu. | TOÁN RỜI RẠC - HK1 - NĂM 2015 -2016 Chương 4 SỐ NGUYÊN lvluyen@ ∼luyen/trr FB: Trường Đại Học Khoa học Tự nhiên TP Hồ Chí Minh lvluyen@ Chương 3. Số nguyên 14/12/2015 1/15 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@ Chương 3. Số nguyên 14/12/2015 2/15 . 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@ Chương 3. Số nguyên 14/12/2015 3/15 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, lvluyen@ − 23 div 5 = −5, − 23 mod 5 = 2. Chương 3. Số nguyên 14/12/2015 4/15 Đồ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