Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Toán rời rạc: Chương 1.8 - Dr. Ngô Hữu Phúc

Bài giảng Toán rời rạc: Chương 1.7 Khái niệm cơ bản Lý thuyết số và hệ đếm, cung cấp cho người đọc những kiến thức như: Các phép toán trên số nguyên; Biểu diễn các số nguyên; Định lý về số dư Trung Quốc và ứng dụng; Các hệ đếm. Mời các bạn cùng tham khảo! | TOÁN RỜI RẠC CHƯƠNG 1 KHÁI NIỆM CƠ BẢN Lý thuyết số và hệ đếm Lecturer PhD. Ngo Huu Phuc Tel 0438 326 077 Mob 098 5696 580 Email ngohuuphuc76@gmail.com 1 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University NỘI DUNG 1. Các phép toán trên số nguyên. 2. Biểu diễn các số nguyên. 3. Định lý về số dư Trung Quốc và ứng dụng. 4. Các hệ đếm. 2 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University 1. Các phép toán trên số nguyên 1 5 1.1. Phép chia nguyên. Cho hai số nguyên n và m ta nói n chia hết cho m nếu tồn tại số nguyên k sao cho n k.m và ký hiệu là m n. Định lý 1. Cho n m và k là các số nguyên. Khi đó a- Nếu k n và k m thì k n m . b- Nếu k n thì k n m với mọi số nguyên m . c- Nếu k n và n m thì k m. 3 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University 1. Các phép toán trên số nguyên 2 5 1.1. Phép chia nguyên tiếp Định lý 2. Mọi số nguyên dương đều có thể được viết duy nhất dưới dạng tích của các số nguyên tố. Định lý 3. Cho a là một số nguyên và d là số nguyên dương. Khi đó tồn tại các số q và r duy nhất với 0 r lt d sao cho a dq r. Hai số nguyên n và m gọi là nguyên tố cùng nhau nếu USCLN n m 1. Các số nguyên a1 a2 . . . an được gọi là đôi một nguyên tố cùng nhau nếu USCLN ai aj 1 với mọi 1 i j n. 4 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University 1. Các phép toán trên số nguyên 3 5 1.1. Phép chia nguyên tiếp Định lý 4. Cho n m là hai số nguyên dương. Khi đó ab USCLN n m BSCNN n m Hai số nguyên n và m gọi là đồng dư theo modulo k nếu n mod k m mod k ta ký hiệu n m mod k . Định lý 5. Nếu n m mod k và p q mod k . Khi đó a n p m q mod k b np m q mod k Phần tử b được gọi là phần tử nghịch đảo của a theo modulo m nếu ab 1 mod m và ký hiệu là a -1 khi đó aa -1 1 mod m . 5 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University 1. Các phép toán trên số nguyên 4 5 1.2. Thuật toán Euclid. Bổ đề Cho a b q r trong đó a b q r là các số nguyên dương. Khi đó USCLN a b USCLN b r Chứng minh. Với mọi ước số chung d của a và b