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

TOÁN RỜI RẠC - HK1 - NĂM 2015 -2016<br /> <br /> Chương 4<br /> <br /> SỐ NGUYÊN<br /> lvluyen@hcmus.edu.vn<br /> http://www.math.hcmus.edu.vn/∼luyen/trr<br /> FB: fb.com/trr2015<br /> Trường Đại Học Khoa học Tự nhiên TP Hồ Chí Minh<br /> <br /> lvluyen@hcmus.edu.vn<br /> <br /> Chương 3. Số nguyên<br /> <br /> 14/12/2015<br /> <br /> 1/15<br /> <br /> Nội dung<br /> Chương 4. SỐ NGUYÊN<br /> 1. Phép chia<br /> 2. Ước chung lớn nhất và bội chung nhỏ nhất<br /> 3. Nguyên tố cùng nhau<br /> <br /> lvluyen@hcmus.edu.vn<br /> <br /> Chương 3. Số nguyên<br /> <br /> 14/12/2015<br /> <br /> 2/15<br /> <br /> 4.1. Phép chia<br /> Định nghĩa. Cho hai số nguyên a và b 6= 0. Ta gọi a chia hết cho b<br /> .<br /> nếu tồn tại số nguyên m sao cho a = mb, ký hiệu a .. b. Khi đó<br /> a được gọi là bội của b,<br /> b được gọi là ước của a, ký hiệu b | a<br /> .<br /> Ví dụ. 12 .. 3,<br /> <br /> .<br /> 156 .. 2,<br /> <br /> 4 | 20,<br /> <br /> 56 | 21.<br /> <br /> Định lý. Cho a 6= 0, b và c là các số nguyên. Khi đó<br /> (i) Nếu a | b và a | c, thì a | (b + c);<br /> (ii) Nếu a | b, thì a | bc;<br /> (iii) Nếu a | b và b | c, thì a | c.<br /> Hệ quả. Cho a 6= 0, b và c là các số nguyên thỏa a | b và a | c. Khi đó<br /> a | mb + nc với m, n là số nguyên.<br /> lvluyen@hcmus.edu.vn<br /> <br /> Chương 3. Số nguyên<br /> <br /> 14/12/2015<br /> <br /> 3/15<br /> <br /> Bổ đề. Cho hai số nguyên a và b với b > 0. Khi đó tồn tại duy nhất<br /> cặp q, r ∈ Z sao cho<br /> a = qb + r với 0 ≤ r < b.<br /> Ví dụ. Cho a = −102 và b = 23. Khi đó −102 = −5 × 23 + 13<br /> Ví dụ.(tự làm) Làm tương tự như ví dụ trên trong trường hợp:<br /> a = 121; b = 15.<br /> a = 214; b = 23<br /> Định nghĩa. Trong bổ đề trên, q được gọi là phần thương , r được<br /> gọi là phần dư. Ký hiệu q = a div b, r = a mod b.<br /> Ví dụ.<br /> 13 ÷ 4 = 3, 13 mod 4 = 1,<br /> lvluyen@hcmus.edu.vn<br /> <br /> − 23 div 5 = −5, − 23 mod 5 = 2.<br /> <br /> Chương 3. Số nguyên<br /> <br /> 14/12/2015<br /> <br /> 4/15<br /> <br /> Đồng dư<br /> Định nghĩa. Cho m là số nguyên dương. Hai số nguyên a và b được<br /> gọi đồng dư với nhau theo modulo m, nếu a và b chia m có cùng phần<br /> dư. Ký hiệu a ≡ b (mod m)<br /> Ví dụ. 27 ≡ 43 (mod 4);<br /> <br /> 47 ≡ 92 (mod 5);<br /> <br /> 124 ≡ 58 (mod 6).<br /> <br /> Bổ đề. a ≡ b (mod m) khi và chỉ khi a − b chia hết cho m.<br /> Tính chất.<br /> (i) Với mọi số nguyên a, ta có a ≡ a (mod m)<br /> (ii) Nếu a ≡ b (mod m) thì b ≡ a (mod m)<br /> (iii) Nếu a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m)<br /> Tính chất. Nếu a ≡ b (mod m) và c ≡ d (mod m) thì<br /> a + c ≡ b + d (mod m) và ac ≡ bd (mod m)<br /> lvluyen@hcmus.edu.vn<br /> <br /> Chương 3. Số nguyên<br /> <br /> 14/12/2015<br /> <br /> 5/15<br /> <br />