Bài giảng Toán rời rạc - Chương 5: Số nguyên
Baøi giaûng moân
raïc
Bieåu dieãn soá nguyeân
Nguyeãn Anh
Thi
Ñònh lyù
Cho b laø soá nguyeân lôùn hôn 1. Khi ñoù moïi soá nguyeân döông n
ñeàu ñöôïc bieåu dieãn duy nhaát döôùi daïng
n = akbk + ak−1bk−1 + · · · + a1b + a0
trong ñoù k laø soá nguyeân khoâng aâm vaø ai laø soá nguyeân thoûa
0 ≤ ai < b. Daïng bieåu dieãn naøy ñöôïc goïi laø daïng bieåu dieãn
theo cô soá b cuûa n, vaø ñöôïc kyù hieäu n = (akak−1 . . . a1a0)b.
Ta coù moät soá daïng bieåu dieãn thöôøng gaëp: nhò phaân (b = 2),
baùt phaân (b = 8), thaäp phaân (b = 10), thaäp luïc phaân
(b = 16),...
Nguyeãn Anh Thi
Baøi giaûng moân
raïc
Ví duï
Tìm daïng thaäp phaân cuûa soá nguyeân coù daïng nhò phaân laø
Nguyeãn Anh
Thi
1011111?
Höôùng daãn.
1011111 = 1.26 + 0.25 + 1.24 + 1.23 + 1.22 + 1.21 + 1.20 = 95.
Ví duï
Tìm daïng thaäp phaân cuûa soá nguyeân coù daïng baùt phaân laø 7016?
Höôùng daãn. 3598
Chuù yù
Ñoái vôùi heä thaäp luïc phaân, chöõ A ñeán F duøng thay theá cho 10
ñeán 15.
Ví duï
Tìm daïng thaäp phaân cuûa soá nguyeân coù daïng thaäp luïc phaân laø
2AE0B?
Höôùng daãn.
Nguyeãn Anh Thi
Baøi giaûng moân
raïc
Tìm daïng bieåu dieãn theo cô soá b
cuûa n
Chia n cho b ta ñöôïc
Nguyeãn Anh
Thi
•
n = q0b + a0.
•
•
•
Khi ñoù soá dö a0 chính laø kyù töï cuoái cuøng trong daïng bieåu
dieãn. Ta tieáp tuïc chia q0 cho b, ta ñöôïc q0 = q1b + a1.
Tieáp tuïc thöïc hieän quaù trình naøy cho ñeán khi phaàn thöông
baèng 0, qk−1 = 0.b + ak.
Khi ñoù (akak−1 . . . a1a0)b laø daïng bieåu dieãn theo cô soá b
cuûa n.
Ví duï
•
Tìm daïng bieåu dieãn baùt phaân cuûa 12345?
Nguyeãn Anh Thi
Baøi giaûng moân
raïc
Tìm daïng bieåu dieãn theo cô soá b
cuûa n
Chia n cho b ta ñöôïc
Nguyeãn Anh
Thi
•
n = q0b + a0.
•
•
•
Khi ñoù soá dö a0 chính laø kyù töï cuoái cuøng trong daïng bieåu
dieãn. Ta tieáp tuïc chia q0 cho b, ta ñöôïc q0 = q1b + a1.
Tieáp tuïc thöïc hieän quaù trình naøy cho ñeán khi phaàn thöông
baèng 0, qk−1 = 0.b + ak.
Khi ñoù (akak−1 . . . a1a0)b laø daïng bieåu dieãn theo cô soá b
cuûa n.
Ví duï
•
•
Tìm daïng bieåu dieãn baùt phaân cuûa 12345? (30071)8
Tìm daïng bieåu dieãn thaäp luïc phaân cuûa 177130?
Nguyeãn Anh Thi
Baøi giaûng moân
raïc
Tìm daïng bieåu dieãn theo cô soá b
cuûa n
Chia n cho b ta ñöôïc
Nguyeãn Anh
Thi
•
n = q0b + a0.
•
•
•
Khi ñoù soá dö a0 chính laø kyù töï cuoái cuøng trong daïng bieåu
dieãn. Ta tieáp tuïc chia q0 cho b, ta ñöôïc q0 = q1b + a1.
Tieáp tuïc thöïc hieän quaù trình naøy cho ñeán khi phaàn thöông
baèng 0, qk−1 = 0.b + ak.
Khi ñoù (akak−1 . . . a1a0)b laø daïng bieåu dieãn theo cô soá b
cuûa n.
Ví duï
•
•
Tìm daïng bieåu dieãn baùt phaân cuûa 12345? (30071)8
Tìm daïng bieåu dieãn thaäp luïc phaân cuûa 177130? (2B3EA)16
Nguyeãn Anh Thi
Baøi giaûng moân
raïc
Ñoàng dö
Nguyeãn Anh
Thi
Ñònh nghóa
Cho n laø soá nguyeân döông. Hai soá nguyeân a vaø b ñöôïc goïi laø
ñoàng dö vôùi nhau theo modulo n, neáu a vaø b chia n coù cuøng soá
dö. Kyù hieäu a ≡ b(mod n).
Tính chaát
i. Vôùi moïi soá nguyeân a, ta coù a ≡ a(mod n);
ii. Neáu a ≡ b(mod n) thì b ≡ a(mod n);
iii. Neáu a ≡ b(mod n) vaø b ≡ c(mod n), thì a ≡ c(mod n).
Nguyeãn Anh Thi
Baøi giaûng moân
raïc
Tính chaát
Cho a ≡ b(mod n) vaø c ≡ d(mod n). Khi ñoù
Nguyeãn Anh
Thi
a + c ≡ b + d(mod n) vaø ac ≡ bd(mod n).
Ví duï
Tìm soá nguyeân a sao cho
a. a ≡ 43(mod 23) vaø −22 ≤ a ≤ 0
b. a ≡ 17(mod 23) vaø −14 ≤ a ≤ 14
c. a ≡ −11(mod 23) vaø 90 ≤ a ≤ 110
Ví duï
Cho a vaø b laø hai soá nguyeân vaø a ≡ 4(mod 13) vaø
b ≡ 9(mod 13). Tìm soá nguyeâ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)
Nguyeãn Anh Thi
Baøi giaûng moân
raïc
Pheùp chia Euclide treân Z, öôùc soá
chung lôùn nhaát, boäi soá chung nhoû
nhaát
Nguyeãn Anh
Thi
Ñònh nghóa
a. Soá nguyeân U > 0 ñöôïc goïi laø öôùc soá chung lôùn nhaát (kyù
hieäu USCLN) cuûa hai soá nguyeân a, b khi vaø chæ khi U laø moät
öôùc chung cuûa a, b (nghóa laø U|a, U|b) vaø neáu soá nguyeân V
laø moät öôùc chung cuûa a, b thì V|U.
b. Soá nguyeân B > 0 ñöôïc goïi laø boäi soá chung nhoû nhaát (kyù
hieäu BSCNN) cuûa hai soá nguyeân a, b khi vaø chæ khi B laø moät
boäi chung cuûa a, b (nghóa laø a|B vaø b|B) vaø neáu soá nguyeân
A laø moät boäi chung cuûa a, b thì B|A.
Nguyeãn Anh Thi
Baøi giaûng moân
raïc
Thuaät toaùn tìm USCLN d cuûa a, b:
Nguyeãn Anh
Thi
•
•
Neáu b laø öôùc cuûa a, thì d = b;
Neáu khoâng, ta laàn löôït thöïc hieän caùc pheùp chia:
a = q1b + r1
, 0 ≤ r1 < b
b = q2r1 + r2
r1 = q3r2 + r3
, 0 ≤ r2 < r1
, 0 ≤ r3 < r2
. . .
Do b > r1 > r2 > · · · ≥ 0, pheùp chia nhö treân seõ ngöng
sau moät soá höõu haïn böôùc. Goïi rn+1 laø soá dö ñaàu tieân baèng
0. Ta coù rn−2 = qnrn−1 + rn
rn−1 = qn+1rn + 0.
Khi ñoù rn laø USCLN cuûa a vaø b.
, 0 ≤ rn < rn−1
,
Nguyeãn Anh Thi
Baøi giaûng moân
raïc
Ñònh lyù
Nguyeãn Anh
Thi
Giaû söû d laø USCLN cuûa a vaø b. Khi ñoù toàn taïi m, n ∈ Z sao cho:
d = ma + nb
Ñònh nghóa
Hai soá nguyeân döông a, b ñöôïc goïi laø nguyeân toá cuøng nhau
khi vaø chæ khi (a, b) = 1.
Heä quaû
Cho a, b > 0. Ta coù (a, b) = 1 ⇔ ∃m, n ∈ Z : ma + nb = 1.
Ñònh lyù
ab
Giaû söû a, b ∈ Z+, d = (a, b). Khi ñoù, BSCNN cuûa a, b laø
.
d
Nguyeãn Anh Thi
Baøi giaûng moân
raïc
Nguyeãn Anh
Thi
Ñònh lyù (Ñònh lyù caên baûn cuûa soá hoïc)
Moïi soá nguyeân döông ñeàu ñöôïc phaân tích thaønh tích höõu haïn
nhöõng thöøa soá nguyeân toá. Hôn nöõa, caùch phaân tích naøy laø duy
nhaát, sai khaùc moät pheùp hoaùn vò caùc thöøa soá nguyeân toá.
Ví duï
48 = 24.3; 60 = 22.3.5.
Nhaän xeùt
Neáu x = pt11 pt2 . . . pntn , y = p1u1 pu22 . . . pnun thì x|y khi vaø chæ khi
ti ≤ ui, i = 12. . . n.
Nguyeãn Anh Thi
Baøi giaûng moân
raïc
Nguyeãn Anh
Thi
Ñònh lyù
Cho hai soá töï nhieân a, b vôùi a = pr11 p2r2 . . . pnrn vaø
b = ps1 ps2 . . . psnn , ri, si ≥ 0, i = 1, . . . , n. Ta coù
1
2
(a, b) = pt11 pt22 . . . pntn vôùi ti = min{ri, si}, i = 1, . . . , n;
[a, b] = pu11 pu22 . . . pnun vôùi ui = max{ri, si}, i = 1, . . . , n.
Nguyeãn Anh Thi
15 trang
15/01/2024
6780
Free
Bạn đang xem tài liệu "Bài giảng Toán rời rạc - Chương 5: Số nguyên", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_chuong_5_so_nguyen.pdf
