Bài giảng Toán rời rạc - Chương 5: Số nguyên - Nguyễn Anh Thi

Bài giảng môn
học Toán rời
rạc
Nguyễn Anh
Thi
Bài giảng môn học Toán rời rạc
Nguyễn Anh Thi
Trường Đại học Khoa học Tự nhiên, Tp Hồ Chí Minh
2017
Nguyễn Anh Thi Bài giảng môn học Toán rời rạc
Bài giảng môn
học Toán rời
rạc
Nguyễn Anh
Thi
SỐ NGUYÊN
Nguyễn Anh Thi Bài giảng môn học Toán rời rạc
Bài giảng môn
học Toán rời
rạc
Nguyễn Anh
Thi
Biểu diễn số nguyên
Định lý
Cho b là số nguyên lớn hơn 1. Khi đó mọi số nguyên dương n
đều được biểu diễn duy nhất dưới dạng
n = akbk + ak−1bk−1 + · · ·+ a1b + a0
trong đó k là số nguyên không âm và ai là số nguyên thỏa
0 ≤ ai < b. Dạng biểu diễn này được gọi là dạng biểu diễn
theo cơ số b của n, và được ký hiệu n = (akak−1 . . . a1a0)b.
Ta có một số dạng biểu diễn thường gặp: nhị phân (b = 2),
bát phân (b = 8), thập phân (b = 10), thập lục phân
(b = 16),...
Nguyễn Anh Thi Bài giảng môn học Toán rời rạc
Bài giảng môn
học Toán rời
rạc
Nguyễn Anh
Thi
Ví dụ
Tìm dạng thập phân của số nguyên có dạng nhị phân là
1011111?
Hướng dẫn.
1011111 = 1.26 + 0.25 + 1.24 + 1.23 + 1.22 + 1.21 + 1.20 = 95.
Ví dụ
Tìm dạng thập phân của số nguyên có dạng bát phân là 7016?
Hướng dẫn. 3598
Chú ý
Đối với hệ thập lục phân, chữ A đến F dùng thay thế cho 10
đến 15.
Ví dụ
Tìm dạng thập phân của số nguyên có dạng thập lục phân là
2AE0B?
Hướng dẫn.
2AE0B = 2.164 + 10.163 + 14.162 + 0.16 + 11 = 175627.
Nguyễn Anh Thi Bài giảng môn học Toán rời rạc
Bài giảng môn
học Toán rời
rạc
Nguyễn Anh
Thi
Tìm dạng biểu diễn theo cơ số b
của n
• Chia n cho b ta được
n = q0b + a0.
• Khi đó số dư a0 chính là ký tự cuối cùng trong dạng biểu
diễn. Ta tiếp tục chia q0 cho b, ta được q0 = q1b + a1.
• Tiếp tục thực hiện quá trình này cho đến khi phần thương
bằng 0, qk−1 = 0.b + ak.
• Khi đó (akak−1 . . . a1a0)b là dạng biểu diễn theo cơ số b
của n.
Ví dụ
• Tìm dạng biểu diễn bát phân của 12345?
(30071)8
• Tìm dạng biểu diễn thập lục phân của 177130? (2B3EA)16
Nguyễn Anh Thi Bài giảng môn học Toán rời rạc
Bài giảng môn
học Toán rời
rạc
Nguyễn Anh
Thi
Tìm dạng biểu diễn theo cơ số b
của n
• Chia n cho b ta được
n = q0b + a0.
• Khi đó số dư a0 chính là ký tự cuối cùng trong dạng biểu
diễn. Ta tiếp tục chia q0 cho b, ta được q0 = q1b + a1.
• Tiếp tục thực hiện quá trình này cho đến khi phần thương
bằng 0, qk−1 = 0.b + ak.
• Khi đó (akak−1 . . . a1a0)b là dạng biểu diễn theo cơ số b
của n.
Ví dụ
• Tìm dạng biểu diễn bát phân của 12345? (30071)8
• Tìm dạng biểu diễn thập lục phân của 177130?
(2B3EA)16
Nguyễn Anh Thi Bài giảng môn học Toán rời rạc
Bài giảng môn
học Toán rời
rạc
Nguyễn Anh
Thi
Tìm dạng biểu diễn theo cơ số b
của n
• Chia n cho b ta được
n = q0b + a0.
• Khi đó số dư a0 chính là ký tự cuối cùng trong dạng biểu
diễn. Ta tiếp tục chia q0 cho b, ta được q0 = q1b + a1.
• Tiếp tục thực hiện quá trình này cho đến khi phần thương
bằng 0, qk−1 = 0.b + ak.
• Khi đó (akak−1 . . . a1a0)b là dạng biểu diễn theo cơ số b
của n.
Ví dụ
• Tìm dạng biểu diễn bát phân của 12345? (30071)8
• Tìm dạng biểu diễn thập lục phân của 177130? (2B3EA)16
Nguyễn Anh Thi Bài giảng môn học Toán rời rạc
Bài giảng môn
học Toán rời
rạc
Nguyễn Anh
Thi
Đồng dư
Định nghĩa
Cho n là số nguyên dương. Hai số nguyên a và b được gọi là
đồng dư với nhau theo modulo n, nếu a và b chia n có cùng số
dư. Ký hiệu a ≡ b(mod n).
Tính chất
i. Với mọi số nguyên a, ta có a ≡ a(mod n);
ii. Nếu a ≡ b(mod n) thì b ≡ a(mod n);
iii. Nếu a ≡ b(mod n) và b ≡ c(mod n), thì a ≡ c(mod n).
Nguyễn Anh Thi Bài giảng môn học Toán rời rạc
Bài giảng môn
học Toán rời
rạc
Nguyễn Anh
Thi
Tính chất
Cho a ≡ b(mod n) và c ≡ d(mod n). Khi đó
a + c ≡ b + d(mod n) và ac ≡ bd(mod n).
Ví dụ
Tìm số nguyên a sao cho
a. a ≡ 43(mod 23) và −22 ≤ a ≤ 0
b. a ≡ 17(mod 23) và −14 ≤ a ≤ 14
c. a ≡ −11(mod 23) và 90 ≤ a ≤ 110
Ví dụ
Cho a và b là hai số nguyên và a ≡ 4(mod 13) và
b ≡ 9(mod 13). Tìm số nguyên c với 0 ≤ c ≤ 12 sao cho
a. c ≡ 9a(mod 13)
b. c ≡ 11b(mod 13)
c. c ≡ a + b(mod 13)
Nguyễn Anh Thi Bài giảng môn học Toán rời rạc
Bài giảng môn
học Toán rời
rạc
Nguyễn Anh
Thi
Phép chia Euclide trên Z, ước số
chung lớn nhất, bội số chung nhỏ
nhất
Định nghĩa
a. Số nguyên U > 0 được gọi là ước số chung lớn nhất (ký
hiệu USCLN) của hai số nguyên a, b khi và chỉ khi U là một
ước chung của a, b (nghĩa là U|a, U|b) và nếu số nguyên V
là một ước chung của a, b thì V|U.
b. Số nguyên B > 0 được gọi là bội số chung nhỏ nhất (ký
hiệu BSCNN) của hai số nguyên a, b khi và chỉ khi B là một
bội chung của a, b (nghĩa là a|B và b|B) và nếu số nguyên
A là một bội chung của a, b thì B|A.
Nguyễn Anh Thi Bài giảng môn học Toán rời rạc
Bài giảng môn
học Toán rời
rạc
Nguyễn Anh
Thi
Ví dụ
USCLN của 15 và 25 là 5, BSCNN của chúng là 75.
Định lý
Ước số chung lớn nhất (tương ứng bội số chung nhỏ nhất) của
a, b là duy nhất, ký hiệu (a; b), (tương ứng [a; b]).
Nguyễn Anh Thi Bài giảng môn học Toán rời rạc
Bài giảng môn
học Toán rời
rạc
Nguyễn Anh
Thi
Thuật toán tìm USCLN 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 < b
b = q2r1 + r2 , 0 ≤ r2 < r1
r1 = q3r2 + r3 , 0 ≤ r3 < r2
. . .
Do b > r1 > r2 > · · · ≥ 0, phép chia như trên sẽ ngư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à USCLN của a và b.
Nguyễn Anh Thi Bài giảng môn học Toán rời rạc
Bài giảng môn
học Toán rời
rạc
Nguyễn Anh
Thi
Định lý
Giả sử d là USCLN của a và b. Khi đó tồn tại m,n ∈ Z sao cho:
d = ma + nb
Đị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.
Hệ quả
Cho a, b > 0. Ta có (a, b) = 1 ⇔ ∃m,n ∈ Z : ma + nb = 1.
Định lý
Giả sử a, b ∈ Z+, d = (a, b). Khi đó, BSCNN của a, b là abd .
Nguyễn Anh Thi Bài giảng môn học Toán rời rạc
Bài giảng môn
học Toán rời
rạc
Nguyễn Anh
Thi
Đị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ụ
48 = 24.3; 60 = 22.3.5.
Nhận xét
Nếu x = pt11 p
t2
2 . . . p
tn
n , y = pu11 p
u2
2 . . . p
un
n thì x|y khi và chỉ khi
ti ≤ ui, i = 1 . . .n.
Nguyễn Anh Thi Bài giảng môn học Toán rời rạc
Bài giảng môn
học Toán rời
rạc
Nguyễn Anh
Thi
Định lý
Cho hai số tự nhiên a, b với a = pr11 p
r2
2 . . . p
rn
n và
b = ps11 p
s2
2 . . . p
sn
n , ri, si ≥ 0, i = 1, . . . ,n. Ta có
(a, b) = pt11 p
t2
2 . . . p
tn
n với ti = min{ri, si}, i = 1, . . . ,n;
[a, b] = pu11 p
u2
2 . . . p
un
n với ui = max{ri, si}, i = 1, . . . ,n.
Nguyễn Anh Thi Bài giảng môn học Toán rời rạc