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.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Chương 4 - Lê Văn LuyệnTOÁN RỜI RẠC - HK1 - NĂM 2015 -2016Chương 4SỐ NGUYÊNlvluyen@hcmus.edu.vnhttp://www.math.hcmus.edu.vn/∼luyen/trrFB: fb.com/trr2015Trường Đại Học Khoa học Tự nhiên TP Hồ Chí Minhlvluyen@hcmus.edu.vnChương 3. Số nguyên14/12/20151/15Nội dungChương 4. SỐ NGUYÊN1. Phép chia2. Ước chung lớn nhất và bội chung nhỏ nhất3. Nguyên tố cùng nhaulvluyen@hcmus.edu.vnChương 3. Số nguyên14/12/20152/154.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.vnChương 3. Số nguyên14/12/20153/15Bổ đề. Cho hai số nguyên a và b với b > 0. Khi đó tồn tại duy nhấtcặp q, r ∈ Z sao choa = qb + r với 0 ≤ r < b.Ví dụ. Cho a = −102 và b = 23. Khi đó −102 = −5 × 23 + 13Ví 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 đượcgọ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@hcmus.edu.vn− 23 div 5 = −5, − 23 mod 5 = 2.Chương 3. Số nguyên14/12/20154/15Đồng dưĐịnh nghĩa. Cho m là số nguyên dương. Hai số nguyên a và b đượcgọi đồng dư với nhau theo modulo m, nếu a và b chia m có cùng phầndư. 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.vnChương 3. Số nguyên14/12/20155/15