ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
MAI HUY NGHÞ
HÖ GHI C¥ Sè Vµ MéT Sè øng dông
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2015
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
MAI HUY NGHÞ
HÖ GHI C¥ Sè Vµ MéT Sè øng dông
Chuyên ngành: Phương pháp Toán sơ cấp
Mã số: 60.46.01.13
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học: PGS.TS. Lê Thị Thanh Nhàn
THÁI NGUYÊN - 2015
Môc lôc
Môc lôc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
Lêi nãi ®Çu . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1 HÖ ghi c¬ sè
5
1.1
Kh¸i niÖm hÖ ghi c¬ sè . . . . . . . . . . . . . . . . . . . .
6
1.2
C¸c phÐp to¸n vµ vÊn ®Ò ®æi c¬ sè . . . . . . . . . . . . .
9
2 Mét sè øng dông cña hÖ ghi c¬ sè
16
2.1
§Þnh lý cña Legendre vµ §Þnh lý cña Kummer . . . . . . .
16
2.2
X©y dùng ®a thøc bÊt kh¶ quy tõ sè nguyªn tè . . . . . . .
21
2.3
Mét sè øng dông cña hÖ ghi c¬ sè trong to¸n s¬ cÊp . . . .
28
KÕt luËn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
Tµi liÖu tham kh¶o . . . . . . . . . . . . . . . . . . . . . . . .
40
1
2
Lêi c¶m ¬n
Tr−íc hÕt, xin ®−îc tá lßng biÕt ¬n ch©n thµnh vµ s©u s¾c ®Õn PGS.TS Lª
ThÞ Thanh Nhµn. MÆc dï rÊt bËn rén trong c«ng viÖc nh−ng C« vÉn dµnh
thêi gian vµ t©m huyÕt trong viÖc h−íng dÉn. Cho ®Õn h«m nay, luËn v¨n
th¹c sÜ cña t«i ®· ®−îc hoµn thµnh còng chÝnh lµ nhê sù sù gióp ®ì nhiÖt
t×nh cña C«.
T«i xin c¶m ¬n ch©n thµnh tíi Tr−êng §¹i häc Khoa häc Th¸i Nguyªn,
n¬i t«i ®· nhËn ®−îc mét häc vÊn sau ®¹i häc c¨n b¶n vµ xin tr©n träng
c¶m ¬n Ban Gi¸m hiÖu nhµ tr−êng, Khoa To¸n - Tin vµ Phßng §µo t¹o cña
tr−êng §¹i häc Khoa häc - §¹i häc Th¸i Nguyªn. T«i xin tr©n träng c¶m
¬n c¸c ThÇy C« ®· tËn t×nh truyÒn ®¹t nh÷ng kiÕn thøc quý b¸u còng nh−
t¹o mäi ®iÒu kiÖn thuËn lîi nhÊt ®Ó t«i hoµn thµnh luËn v¨n nµy.
Cuèi cïng, t«i xin ch©n thµnh bµy tá lßng biÕt ¬n ®Õn gia ®×nh, b¹n bÌ,
nh÷ng ng−êi ®· kh«ng ngõng ®éng viªn, hç trî vµ t¹o mäi ®iÒu kiÖn tèt
nhÊt cho t«i trong suèt thêi gian häc tËp vµ thùc hiÖn luËn v¨n. LuËn v¨n
nµy ®−îc thùc hiÖn vµ hoµn thµnh t¹i Tr−êng §¹i häc Khoa häc - §¹i häc
Th¸i Nguyªn.
3
Lêi nãi ®Çu
Do nhu cÇu thùc tiÔn cña cuéc sèng, cã thÓ nãi hÖ ghi c¬ sè lµ mét trong
nh÷ng lÝ thuyÕt to¸n häc ®Çu tiªn xuÊt hiÖn, ®−îc h×nh thµnh vµ ph¸t triÓn
song hµnh víi sù ph¸t triÓn cña v¨n minh nh©n lo¹i. HÖ ghi c¬ sè lµ mét néi
dung quan träng trong sè häc vµ cã nhiÒu øng dông kh¸c nhau trong khoa
häc vµ thùc tiÔn. LÝ thuyÕt hÖ ghi c¬ sè liªn quan ®Õn nhiÒu lÜnh vùc kh¸c
cña to¸n häc nh− LÝ thuyÕt sè; To¸n rêi r¹c; Ph−¬ng tr×nh nghiÖm nguyªn
vµ ph−¬ng tr×nh hµm; §a thøc; Qui n¹p to¸n häc; C¸c bµi to¸n trß ch¬i v.v.
Mét sè hÖ ghi c¬ sè quan träng lµ hÖ thËp ph©n (c¬ sè 10), hÖ nhÞ ph©n
(c¬ sè 2), hÖ b¸t ph©n (c¬ sè 8), hÖ thËp lôc ph©n (c¬ sè 16). HÖ ghi c¬ sè
®−îc sö dông phæ biÕn nhÊt hiÖn nay lµ hÖ thËp ph©n, xuÊt hiÖn ®Çu tiªn ë
Ên ®é vµo ThÕ kû 5 sau c«ng nguyªn. §Õn n¨m 1202 nhê t¸c phÈm Liber
Abacci cña L. Fibonacci (mét nhµ to¸n häc vµ th−¬ng gia ng−êi Ý), th× hÖ
ghi thËp ph©n míi ®−îc truyÒn b¸ vµo ch©u ¢u. HÖ nhÞ ph©n ®−îc sö dông
bëi ng−êi Babylon (kho¶ng ThÕ kØ 5 ®Õn ThÕ kØ 3 r−íc C«ng Nguyªn), ngµy
nay hÖ nhÞ ph©n, hÖ b¸t ph©n vµ hÖ thËp lôc ph©n ®ang ®−îc sö dông réng
r·i trong lÜnh vùc khoa häc m¸y tÝnh vµ b¶o mËt th«ng tin. NhiÒu hÖ ghi
c¬ sè kh¸c nh− c¬ sè 12, c¬ sè 7, c¬ sè 3, v.v. ®Õn nµy vÉn ®−îc quan t©m
vµ sö dông.
LuËn v¨n nµy quan t©m ®Õn vÊn ®Ò biÓu diÔn trong c¸c hÖ ghi c¬ sè
vµ mét sè øng dông trong to¸n s¬ cÊp. LuËn v¨n gåm 2 ch−¬ng. Trong
Ch−¬ng 1, chóng t«i tr×nh bµy kh¸i niÖm hÖ ghi c¬ sè, mét sè tÝnh chÊt c¬
së, c¸c phÐp to¸n vµ bµi to¸n ®æi c¬ sè. Ch−¬ng 2 tr×nh bµy mét sè øng
dông cña hÖ ghi c¬ sè. Tr−íc hÕt, th«ng qua mét biÓu diÔn cña sè n trong
hÖ ghi c¬ sè p víi p lµ sè nguyªn tè, chóng ta cã thÓ tÝnh ®−îc sè tù nhiªn
t lín nhÊt sao cho pt lµ −íc cña n! (§Þnh lÝ cña Legendre). Còng th«ng qua
4
biÓu diÔn cña hai sè tù nhiªn a vµ b trong hÖ ghi c¬ sè p víi p nguyªn tè,
a
chóng ta cã thÓ tÝnh ®−îc sè t lín nhÊt sao cho pt lµ −íc cña Ca+b
, trong
a
®ã Ca+b
lµ sè tæ hîp chËp a cña a + b phÇn tö (§Þnh lÝ Kummer). Hai ®Þnh
lÝ nµy ®−îc tr×nh bµy trong TiÕt 2.1 cña luËn v¨n. Trong TiÕt 2.2, chóng t«i
tr×nh bµy mét øng dông n÷a cña hÖ ghi c¬ sè trong vÊn ®Ò x©y dùng c¸c ®a
thøc (víi hÖ sè nguyªn) bÊt kh¶ quy trªn Q. Khi p lµ mét sè nguyªn tè vµ
b > 2 lµ mét sè tù nhiªn, nÕu p = (an . . . a1a0 )b lµ biÓu diÔn cña p trong hÖ
ghi c¬ sè b th× ®a thøc f (x) = an xn + . . . + a1 x + a0 lµ bÊt kh¶ quy trªn
Q (§Þnh lÝ cña Murty). TiÕt 2.3 quan t©m ®Õn øng dông cña hÖ ghi c¬ sè
®Ó gi¶i mét sè d¹ng to¸n sè häc s¬ cÊp, ®Æc biÖt lµ nh÷ng bµi to¸n thi häc
sinh giái bËc phæ th«ng trung häc.
Ngoµi mét sè th«ng tin vÒ hÖ ghi c¬ sè ®−îc tham kh¶o trªn trang
Wikipedia, luËn v¨n ®−îc viÕt dùa trªn 4 tµi liÖu sau ®©y
1. Lª Thanh Nhµn, LÝ thuyÕt ®a thøc (Gi¸o tr×nh sau ®¹i häc), NXB
§HQGHN, 2015.
2. David Anthony Santos, Number Theory for Mathematical Contests,
GNU Free Documentation License, October 31, 2007.
3. J. Stillwell, Elements of Number Theory, Springer, 2003.
4. M. Ram Murty, Prime numbers and irreducible polynomials, The
American Math. Monthly, 109 (2002), 452-458.
Ch−¬ng 1
HÖ ghi c¬ sè
HÖ thËp ph©n xuÊt hiÖn ®Çu tiªn ë ¢́n ®é vµo ThÕ kû 5 (sau C«ng
Nguyªn). §Õn n¨m 1202, nhê t¸c phÈm Liber Abacci cña L. Fibonacci
(mét nhµ to¸n häc ®ång thêi lµ th−¬ng gia ng−êi Ý) th× hÖ thËp ph©n míi
®−îc truyÒn b¸ vµo Ch©u ¢u. Víi sù ph¸t minh ra nghÒ in vµo ThÕ kØ 15
th× 10 ch÷ sè míi cã h×nh d¹ng cè ®Þnh nh− hiÖn nay. Ng−êi ta còng cè lý
gi¶i t¹i sao hÖ ghi thËp ph©n l¹i ®−îc ®a sè c¸c n−íc trªn thÕ giíi sö dông
®Õn nh− vËy. Cã nhiÒu lÝ do cho r»ng do hai bµn tay cã 10 ngãn vµ dÔ dµng
®Õm trªn 10 ngãn tay.
Ngoµi hÖ ghi thËp ph©n chóng ta cã hÖ ghi c¬ sè kh¸c nhau mµ c¸c n−íc,
c¸c d©n téc trªn thÕ giíi ®· sö dông. HÖ ghi c¬ sè 60 cña ng−êi Babilon
(kho¶ng ThÕ kØ thø 5 ®Õn ThÕ kØ thø 3 tr−íc C«ng Nguyªn), hÖ ghi c¬ sè
60 cho ®Õn ngµy nay vÉn ®−îc dïng ®Ó ®o gãc vµ thêi gian. Cã gi¶ thuyÕt
cho r»ng v× 60 cã nhiÒu −íc sè (2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60) nªn
khi thùc hiÖn phÐp chia th× sÏ thu ®−îc nhiÒu sè ch½n (tøc lµ sè nguyªn).
Cßn sè 10 chØ cã 2 −íc lµ 2 vµ 5 nªn khi thùc hiÖn phÐp chia sÏ thu ®−îc
nhiÒu sè lÎ (ph©n sè). Thêi cæ ®¹i, c¸c bé téc nguyªn thñy th−êng dïng hÖ
ghi c¬ sè 5, nã t−¬ng øng víi viÖc ®Õm trªn n¨m ngãn tay. HiÖn nay ng−êi
Trung Quèc vµ ng−êi NhËt B¶n vÉn cßn dïng c¸c bµn tÝnh gÈy dùa trªn hÖ
ghi c¬ sè 5. Víi hÖ ghi c¬ sè 20, cã nh÷ng d©n téc dïng c¶ 10 ngãn ch©n
5
6
vµ 10 ngãn tay ®Ó ®Õm. HÖ ghi nµy ®−îc ng−êi Maya cæ sö dông. Cho
®Õn ngµy nay ë §an M¹ch vµ ë Ph¸p ng−êi ta vÉn sö dông hÖ ghi c¬ sè
20. Trong ®o l−êng ng−êi ta cßn sö dông nhiÒu hÖ ghi kh¸c n÷a. HÖ ghi
c¬ sè 12 ®−îc sö dông ë nhiÒu n−íc trªn thÕ giíi vµ cho ®Õn ngµy nay vÉn
®−îc sö dông nhiÒu ë Anh (mét th−íc Anh kh«ng ph¶i b»ng 10 tÊc Anh,
mµ b»ng 12 tÊc Anh). Chóng ta vÉn hay dïng ®¬n vÞ inch, 18 inch kh«ng
ph¶i lµ mét th−íc vµ 8 tÊc mµ lµ mét th−íc Anh vµ 6 tÊc Anh. Ng−êi ta
cßn dïng ®¬n vÞ “t¸”, mét t¸ b»ng 12 chiÕc. Cã lÏ ng−êi Trung Quèc còng
®· sö dông hÖ ghi c¬ sè 12 (chu k× cña 12 con gi¸p). Tïy theo yªu cÇu
thùc tÕ mµ ng−êi ta l¹i dïng c¸c hÖ ghi víi c¬ sè míi. HÖ ghi c¬ sè 2 hay
hÖ ghi nhÞ ph©n ®−îc cµi trªn c¸c m¸y tÝnh. PhÐp ®Õm nhÞ ph©n cïng víi
phÐp to¸n logic lµ c¬ së ho¹t ®éng cña m¸y tÝnh. Do chØ cã hai ký tù nªn
viÖc biÓu diÔn cña mét sè trong hÖ ghi c¬ sè 2 rÊt dµi, v× vËy trong m¸y
tÝnh cßn sö dông hÖ ghi c¬ sè 8 vµ hÖ ghi c¬ sè 16, rÊt thuËn tiÖn trong
biÓu diÔn c¸c sè, v× 2 lµ −íc cña 8 vµ 16. Thùc ra th× hÖ ghi c¬ sè 16 còng
®· cã ë Trung Quèc tõ x−a, v× thêi tr−íc 1 c©n cña Trung Quèc cã tíi 16
l¹ng. HÖ ghi c¬ sè 24 dïng ®Õm sè giê trong 1 ngµy. HÖ ghi c¬ sè 30 ®Õm
sè ngµy trong th¸ng. HÖ ghi c¬ sè 3 dïng ®Ó ®Õm sè th¸ng trong quÝ. HÖ
ghi c¬ sè 7 ®Õm sè ngµy trong tuÇn, v.v.
Môc ®Ých cña ch−¬ng nµy lµ tr×nh bµy kh¸i niÖm c¬ b¶n vÒ hÖ ghi c¬
sè, c¸c tÝnh chÊt, c¸c phÐp to¸n vµ vÊn ®Ò ®æi c¬ sè.
1.1 Kh¸i niÖm hÖ ghi c¬ sè
TiÕt nµy tr×nh bµy mét sè kh¸i niÖm vµ tÝnh chÊt c¬ së cña hÖ ghi c¬
sè. LuËn v¨n quan t©m ®Õn nh÷ng hÖ ghi c¬ sè th−êng gÆp nh−: HÖ thËp
ph©n, hÖ nhÞ ph©n, hÖ b¸t ph©n, hÖ thËp lôc ph©n.
1.1.1 §Þnh nghÜa. Cho a > 0 lµ mét sè h÷u tû, b > 1 lµ mét sè tù nhiªn.
7
Gi¶ sö
a = an bn + an−1 bn−1 + . . . + a1 b + a0 b0 + a−1 b−1 + a−2 b−2 + . . . + a−mb−m ,
trong ®ã n, m ∈ N, an , . . . , a0 , a−1 , . . . , a−m ∈ {0, 1, . . . , b − 1} vµ an 6= 0.
Khi ®ã ta nãi a = (an . . . a0, a−1 . . . a−m )b lµ biÓu diÔn cña a trong hÖ ghi
c¬ sè b.
1.1.2 VÝ dô. Mét sè hÖ ghi c¬ sè th−êng gÆp nh−
HÖ thËp ph©n: Chóng ta dïng c¸c ch÷ sè 0, 1, . . . , 9 ®Ó biÓu diÔn c¸c sè
trong hÖ thËp ph©n. Ch¼ng h¹n
(12568, 36)10 = 1.104 + 2.103 + 5.102 + 6.101 + 8.100 + 3.10−1 + 6.10−2 .
HÖ nhÞ ph©n: Chóng ta dïng c¸c ch÷ sè 0 vµ 1 ®Ó biÓu diÔn c¸c sè trong
hÖ nhÞ ph©n. Ch¼ng h¹n
(111010, 01)2 = 1.25 + 1.24 + 1.23 + 0.22 + 1.21 + 0.20 + 0.2−1 + 1.2−2 .
HÖ b¸t ph©n: Chóng ta dïng c¸c ch÷ sè 0, 1, . . . , 7 ®Ó biÓu diÔn c¸c sè trong
hÖ b¸t ph©n. Ch¼ng h¹n
(20365, 68)8 = 2.84 + 0.83 + 3.82 + 6.81 + 5.80 + 6.8−1 + 8.8−2 .
HÖ thËp lôc ph©n: Chóng ta dïng c¸c sè 0, 1, . . . , 9 vµ c¸c ch÷ A, B, C,
D, E, F ®Ó biÓu diÔn c¸c sè trong hÖ ghi c¬ sè thËp lôc ph©n, trong ®ã
A = 10, B = 11, C = 12, D = 13, E = 14, F = 15. Ch¼ng h¹n
3.165 + A.164 + 0.163 + B.162 + 1.161 + F.160 + 3.16−1 + A.16−2
cã biÓu diÔn trong hÖ thËp lôc ph©n lµ (3A0B1F, 3A)16 .
Nh− vËy dï ë hÖ ghi c¬ sè b nµo th× nã còng bao gåm hai phÇn: phÇn
nguyªn vµ phÇn b-ph©n (hay cßn gäi lµ phÇn lÎ), gi÷a hai phÇn Êy ®−îc ng¨n
8
c¸ch víi nhau bëi dÊu phÈy. PhÇn ®øng bªn tr¸i cña dÊu phÈy ®−îc gäi lµ
phÇn nguyªn, phÇn ®øng bªn ph¶i cña dÊu phÈy ®−îc gäi lµ phÇn b-ph©n
hay phÇn lÎ. NÕu sè cã phÇn lÎ b»ng 0 th× kh«ng cÇn dïng dÊu phÈy, vµ sè
®ã gäi lµ sè nguyªn. NÕu sè viÕt trong hÖ b 6= 10 th× b¾t buéc ta ph¶i biÕt
c¬ sè b kÌm theo, trong khi ®ã nÕu viÕt trong hÖ thËp ph©n, tøc lµ b = 10,
th× ta kh«ng cÇn viÕt c¬ sè kÌm theo.
1.1.3 §Þnh lý. Cho sè tù nhiªn b > 1. Khi ®ã mäi sè tù nhiªn a > 0 ®Òu
cã duy nhÊt mét biÓu diÔn trong hÖ ghi c¬ sè b, tøc lµ tån t¹i duy nhÊt mét
biÓu diÔn a = anbn + . . . + a1 b + a0 , víi n lµ sè tù nhiªn, a0, a1 , . . . , an ∈
{0, 1, . . . , b − 1} vµ an 6= 0.
Chøng minh. Ta chøng minh sù tån t¹i biÓu diÔn b»ng quy n¹p theo a. NÕu
a < b th× a = a lµ biÓu diÔn cÇn t×m. Cho a ≥ b vµ gi¶ thiÕt r»ng c¸c sè tù
nhiªn nhá h¬n a ®Òu cã biÓu diÔn nh− trong ®Þnh lý. Chia a cho b ta ®−îc
a = cb + r víi c, r ∈ N vµ r < b. Do b > 1 nªn c < a. Do ®ã theo gi¶ thiÕt
quy n¹p ta cã biÓu diÔn c = ck bk + . . . + c1 .b + c0 , víi k lµ sè tù nhiªn,
c0 , c1 , . . . , ck ∈ {0, 1, . . . , b − 1} vµ ck 6= 0. Suy ra
a = ck bk+1 + . . . + c1 .b2 + c0 b + r.
Chän n = k + 1, ai+1 = ci víi i = 0, 1, . . . , k vµ a0 = r ta cã kÕt qu¶.
TiÕp theo, ta chøng minh tÝnh duy nhÊt cña biÓu diÔn b»ng quy n¹p theo
a. Gi¶ sö
a = an bn + . . . + a1b + a0 = a′mbm + . . . + a′1 b + a′0
víi n ≥ m lµ hai biÓu diÔn cña a trong hÖ ghi c¬ sè b. NÕu a < b th×
m = n = 0 vµ a = a0 = a′0, do ®ã biÓu diÔn lµ duy nhÊt. Cho a ≥ b
vµ gi¶ thiÕt r»ng kÕt qu¶ ®· ®óng cho c¸c sè tù nhiªn nhá h¬n a. V×
a0, a′0 ∈ {0, 1, . . . , b − 1} nªn a0 vµ a′0 ®Òu lµ d− cña phÐp chia a cho b. Do
9
tÝnh duy nhÊt cña th−¬ng vµ d− trong phÐp chia a cho b nªn ta cã a0 = a′0.
Suy ra
b(anbn−1 + . . . + a1) = b(a′mbm−1 + . . . + a′1 ).
Gi¶n −íc c¶ hai vÕ cho b ta ®−îc an bn−1 + . . . + a1 = a′mbm−1 + . . . + a′1.
§©y lµ hai biÓu diÔn cña cïng mét sè c = an bn−1 + . . . + a1 trong hÖ ghi
c¬ sè b. V× b > 1 nªn c < a. Do ®ã theo gi¶ thiÕt quy n¹p ta suy ra
m − 1 = n − 1 vµ a1 = a′1, . . . , am = bm. Suy ra m = n vµ ai = a′i víi mäi
i = 0, 1, . . . , n.
1.2 C¸c phÐp to¸n vµ vÊn ®Ò ®æi c¬ sè
TiÕt nµy tr×nh bµy c¸c phÐp to¸n sè häc (céng, trõ, nh©n, chia) trªn hÖ
ghi c¬ sè bÊt kú vµ vÊn ®Ò ®æi mét sè trong hÖ ghi c¬ sè tïy ý sang hÖ ghi
c¬ sè kh¸c. Tr−íc hÕt chóng ta quan t©m ®Õn c¸c phÐp to¸n trong hÖ ghi
c¬ sè b bÊt k×.
1.2.1 Chó ý. Trªn mét hÖ ghi c¬ sè bÊt kú, ta vÉn thùc hiÖn c¸c phÐp to¸n
céng, trõ, nh©n, chia nh− trªn hÖ thËp ph©n nh−ng dùa trªn b¶ng céng vµ
b¶ng nh©n cña hÖ ghi c¬ sè ®ã.
Ch¼ng h¹n ta cã b¶ng céng cña hÖ ghi c¬ sè 8 (b¸t ph©n).
+
0
1
2
3
4
5
6
7
0
0
1
2
3
4
5
6
7
1
1
2
3
4
5
6
7
10
2
2
3
4
5
6
7
10
11
3
3
4
5
6
7
10
11
12
4
4
5
6
7
10
11
12
13
5
5
6
7
10
11
12
13
14
6
6
7
10
11
12
13
14
15
7
7
10
11
12
14
14
15
16
10
D−íi ®©y lµ b¶ng nh©n cña hÖ ghi c¬ sè 8 (b¸t ph©n).
.
0
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
0
1
0
1
2
3
4
5
6
7
2
0
2
4
6
10
12
14
16
3
0
3
6
11
14
17
22
25
4
0
4
10
14
20
24
30
34
5
0
5
12
17
24
31
36
43
6
0
6
14
22
30
36
44
52
7
0
7
16
25
34
43
52
61
D−íi ®©y lµ b¶ng c«ng trong hÖ ghi c¬ sè 5 (ngò ph©n)
+
0
1
2
3
4
0
0
1
2
3
4
1
1
2
3
4
10
2
2
3
4
10
11
3
3
4
10
11
12
4
4
10
11
12
13
B¶ng nh©n trong hÖ ghi c¬ sè 5
.
0
1
2
3
4
0
0
0
0
0
0
1
0
1
2
3
4
2
0
2
4
11
13
3
0
3
11
14
22
4
0
4
13
22
31
Dùa trªn 2 b¶ng céng vµ b¶ng nh©n nµy, ta cã thÓ thùc hiÖn c¸c phÐp
to¸n céng, trõ, nh©n vµ chia cña hÖ ghi c¬ sè ®ã.
1.2.2 VÝ dô. §Ó thùc hiÖn phÐp céng (234, 32)5 + (1021, 32)5 , ta tiÕn hµnh
nh− sau
+
2 3 4, 3 2
1 0 2 1, 3 2
1 3 1 1, 1 4
11
VËy, (234, 32)5 + (1021, 32)5 = (1311, 14)5 .
1.2.3 VÝ dô. §Ó thùc hiÖn phÐp trõ (2014, 23)5 − (123, 12)5 , ta lµm nh− sau
2 0 1 4, 2 3
−
1 2 3, 1 2
1 3 4 1, 1 1
VËy (2014, 23)5 − (123, 12)5 = (1341, 11)5 .
1.2.4 VÝ dô. §Ó thùc hiÖn phÐp nh©n ta tiÕn hµnh gièng nh− trong hÖ thËp
ph©n. Ta ®Æt sè thø hai d−íi sè thø nhÊt, dïng b¶ng nh©n ®Ó nh©n tõng ch÷
sè cña sè thø hai víi sè thø nhÊt, kÕt qu¶ cña mçi phÐp nh©n ®−îc viÕt theo
mét hµng, hµng sau lïi sang bªn tr¸i 1 ch÷ sè so víi hµng ®øng tr−íc, sau
®ã céng tÊt c¶ c¸c hµng l¹i ta ®−îc kÕt qu¶. Ch¼ng h¹n, ®Ó nh©n (201, 13)5
víi (13, 12)5 , ta lµm nh− sau
+
2 0
x
1
4
2 0
1 1 0 3
2 0 1 1
3 1 3 4,
1,
3,
0
1
4
3
4
1
1
2
1
4
3
2
3 1
3
1 1 1
VËy (201, 13)5 x (13, 12)5 = (3144, 4311)5 .
1.2.5 VÝ dô. §Ó thùc hiÖn phÐp chia trong hÖ ngò ph©n, ta lµm t−¬ng tù nh−
phÐp chia trong hÖ thËp ph©n, tøc lµ chia tõ tr¸i qua ph¶i, sau mçi phÐp chia
ta h¹ ch÷ sè tiÕp theo cña sè bÞ chia xuèng bªn ph¶i cña phÇn d− råi chia
tiÕp cho ®Õn khi hoµn thµnh. Ch¼ng h¹n, chia (31344123)5 cho (20223)5 ta
®−îc th−¬ng lµ (1244)5 vµ d− lµ (14001)5 .
TiÕp theo chóng ta quan t©m ®Õn vÊn ®Ò ®æi c¬ sè. VÊn ®Ò ®Æt ra lµ nÕu
ta cã sè a viÕt trong hÖ ghi c¬ sè b th× ta cã thÓ chuyÓn nã sang c¸c hÖ ghi
12
c¬ sè kh¸c ®−îc kh«ng? Lµm thÕ nµo ®Ó ®æi biÓu diÔn cña nã tõ hÖ ghi
c¬ sè nµy sang hÖ ghi c¬ sè kh¸c? Ta tr¶ lêi cÊu hái nµy b»ng c¸ch ph©n
thµnh c¸c tr−êng hîp sau
- §æi mét sè trong hÖ ghi c¬ sè b sang hÖ thËp ph©n. Ta cã 2 c¸ch ®Ó
gi¶i quyÕt bµi to¸n nµy. C¸ch thø nhÊt lµ tÝnh to¸n theo ®Þnh nghÜa. Cô thÓ,
a = (an an−1 . . . a1 a0)b = anbn + an−1 bn−1 + . . . + a1b + a0 .
KÕt qu¶ thu ®−îc ë vÕ ph¶i chÝnh lµ biÓu diÔn cña a trong hÖ thËp ph©n. Ta
minh häa ®iÒu nµy b»ng vÝ dô sau (chó ý r»ng ®èi víi hÖ thËp ph©n chóng
ta kh«ng ghi c¬ sè 10 ë trong biÓu diÔn).
1.2.6 VÝ dô. Cho a = (111010, 01)2 , a′ = (245)6 , a′′ = (20365, 68)8 vµ
a′′′ = (3A0B1F, 3A)16 . Khi ®ã
a = (111010, 01)2
= 1.25 + 1.24 + 1.23 + 0.22 + 1.21 + 0.20 + 0.2−1 + 1.2−2 = 58, 25;
a′ = (245)6 = 2.62 + 4.6 + 5 = 101;
a′′ = (20365, 68)8
= 2.84 + 0.83 + 3.82 + 6.81 + 5.80 + 6.8−1 + 8.8−2 = 84378, 75;
a′′′ = (3A0B1F, 3A)16
= 3.165 + 11.164 + 0.163 + 12.162 + 1.161 + 15.160 + 3.16−1 + 11.16−2
= 3869727, 23.
C¸ch thø hai ®Ó biÓu diÔn mét sè a trong hÖ ghi c¬ sè b sang hÖ thËp
ph©n lµ sö dông phÐp chia liªn tiÕp. Tr−íc hÕt ta biÓu diÔn sè 10 trong
hÖ ghi c¬ sè b, ch¼ng h¹n 10 = (c)b. Sau ®ã trong hÖ ghi c¬ sè b ta thùc
hiÖn phÐp chia liªn tiÕp cho c. Cô thÓ, b−íc ®Çu tiªn lµ chia a cho c ®−îc
th−¬ng lµ q1 vµ d− lµ r1 . B−íc tiÕp theo ta chia q1 cho c ta ®−îc th−¬ng q2
vµ d− r2 . Cø tiÕp tôc chia th−¬ng cho c ®Õn b−íc thø k ta thu ®−îc th−¬ng
13
qk = 0. Ta biÓu diÔn c¸c sè d− r1 , . . . , rk cña c¸c phÐp chia trong hÖ ghi
c¬ sè b sang hÖ thËp ph©n råi viÕt c¸c sè d− nµy theo thø tù tõ hµng ®¬n vÞ
®Õn hang chôc, hµng tr¨m, v.v. Tõ ®ã ta cã kÕt qu¶. Ta minh häa c¸ch lµm
nµy b»ng vÝ dô sau.
1.2.7 VÝ dô. §Ó biÓu diÔn (234765003)8 trong hÖ thËp ph©n, ta ®æi 10 =
(12)8 , sau ®ã thùc hiÖn c¸c phÐp chia liªn tiÕp trong hÖ ghi c¬ sè 8, råi
chuyÓn phÇn d− sang hÖ thËp ph©n, cô thÓ:
Thùc hiÖn phÐp chia 234765003 : 12, th−¬ng lµ 17545231 vµ d− 118 = 9;
thùc hiÖn phÐp chia 17545231 : 12, th−¬ng lµ 1443565 vµ d− 78 = 7;
thùc hiÖn phÐp chia 1443565 : 12 ta ®−îc th−¬ng 120276 vµ d− 118 = 9;
thùc hiÖn phÐp chia 120276 : 12 ta ®−îc th−¬ng 10023 vµ d− 08 = 0;
thùc hiÖn phÐp chia 10023 : 12 ta ®−îc th−¬ng 633 vµ d− 58 = 5;
thùc hiÖn phÐp chia 633 : 12 ta ®−îc th−¬ng 51 vµ d− 18 = 1;
thùc hiÖn phÐp chia 51 : 12 ta ®−îc th−¬ng 4 vµ d− 18 = 1;
thùc hiÖn phÐp chia 4 : 12 ta ®−îc th−¬ng 0 vµ d− 48 = 4.
Suy ra (234765003)8 = 41150979.
- Bµi to¸n thø hai lµ ®æi mét sè trong hÖ thËp ph©n sang hÖ ghi c¬ sè
b. Trong hÖ thËp ph©n ta chia liªn tiÕp cho b. B−íc ®Çu tiªn ta chia a cho
b ®−îc th−¬ng q1 vµ d− r1 . B−íc tiÕp theo lµ chia th−¬ng q1 cho b ta ®−îc
th−¬ng q2 vµ d− r2 . Cø tiÕp tôc chia th−¬ng thu ®−îc cho b, ®Õn khi th−¬ng
thu ®−îc b»ng 0 th× ta dõng l¹i. ViÕt c¸c sè d− theo thø tù tõ hµng ®¬n vÞ
sang hµng chôc, hµng tr¨m, vv, ta cã kÕt qu¶.
1.2.8 VÝ dô. BiÓu diÔn sè 118 trong hÖ thËp ph©n sang hÖ nhÞ ph©n (hÖ ghi
14
c¬ sè 2). Ta cã (trong hÖ thËp ph©n)
Thùc hiÖn phÐp chia 118 : 2, th−¬ng lµ 59 vµ d− 0;
thùc hiÖn phÐp chia 59 : 2 ta ®−îc th−¬ng 29 vµ d− 1;
thùc hiÖn phÐp chia 29 : 2 ta ®−îc th−¬ng 14 vµ d− 1;
thùc hiÖn phÐp chia 14 : 2 ta ®−îc th−¬ng 7 vµ d− 0;
thùc hiÖn phÐp chia 7 : 2 ta ®−îc th−¬ng 3 vµ d− 1;
thùc hiÖn phÐp chia 3 : 2 ta ®−îc th−¬ng 1 vµ d− 1;
thùc hiÖn phÐp chia 1 : 2 ta ®−îc th−¬ng 0 vµ d− 1.
VËy, 118 = (1110110)2 .
- Bµi to¸n ®æi c¬ sè tæng qu¸t lµ biÓu diÔn mét sè a trong hÖ ghi c¬ sè
b sang hÖ sè ghi c¬ sè b′. C¸ch thø nhÊt lµ lÊy c¬ sè 10 lµm trung gian,
chuyÓn sè a tõ hÖ ghi c¬ sè b sang hÖ thËp ph©n, råi chuyÓn tiÕp tù hÖ thËp
ph©n sang hÖ ghi c¬ sè b′ . Ta minh häa ®iÒu nµy b»ng vÝ dô sau.
1.2.9 VÝ dô. BiÓu diÔn sè (1551)6 trong hÖ b¸t ph©n. Ta cã (1551)6 = 427.
Suy ra 427 = (653)8 . Do ®ã (1551)6 = (653)8 .
§Ó biÓu diÔn sè (a)b sang hÖ ghi c¬ sè b′ , c¸ch thø hai lµ ®æi sè b′ sang
hÖ ghi c¬ sè b. Ch¼ng h¹n b′ = (c)b . Sau ®ã, trong hÖ ghi c¬ sè b, chóng ta
thùc hiÖn chia liªn tiÕp cho c. Cô thÓ, b−íc ®Çu tiªn lµ chia a cho c ®−îc
th−¬ng lµ q1 vµ d− lµ r1 . B−íc tiÕp theo ta chia th−¬ng q1 cho c vµ thu ®−îc
th−¬ng q2 vµ d− r2 . Cø tiÕp tôc chia th−¬ng cho c, cho ®Õn khi ta thu ®−îc
th−¬ng b»ng 0. §æi c¸c sè d− tõ hÖ ghi c¬ sè b sang hÖ ghi c¬ sè b′ råi viÕt
chóng theo thø tù tõ hµng ®¬n vÞ sang hµng chôc, hµng tr¨m, vv. Khi ®ã ta
®−îc kÕt qu¶. Sau ®©y lµ mét vÝ dô minh häa.
1.2.10 VÝ dô. ChuyÓn sè (2347603)8 sang hÖ ghi c¬ sè 12. Tr−íc hÕt ta
biÓu diÔn 12 trong hÖ ghi c¬ sè 8. Ta cã 12 = (14)8 . B©y giê, trong hÖ ghi
15
c¬ sè 8 ta thøc hiÖn c¸c phÐp chia liªn tiÕp
Thùc hiÖn phÐp chia 2347603 : 14, th−¬ng lµ 150512 vµ d− 138 = 1112 ;
thùc hiÖn phÐp chia 15052 : 14 ta ®−îc th−¬ng 10560 vµ d− 128 = 1012 ;
thùc hiÖn phÐp chia 15060 : 14 ta ®−îc th−¬ng 564 vµ d− 08 = 012 ;
thùc hiÖn phÐp chia 564 : 14 ta ®−îc th−¬ng 37 vµ d− 08 = 012 ;
thùc hiÖn phÐp chia 37 : 14 ta ®−îc th−¬ng 2 vµ d− 78 = 712;
thùc hiÖn phÐp chia 2 : 14 ta ®−îc th−¬ng 0 vµ d− 28 = 212 .
Chó ý r»ng chóng ta dïng c¸c sè tõ 1 ®Õn 9 vµ c¸c ch÷ A = 10, B = 11
®Ó biÓu diÔn c¸c sè trong hÖ ghi c¬ sè 12. V× thÕ ta cã
(2347603)8 = (2700AB)12 .
Ch−¬ng 2
Mét sè øng dông cña hÖ ghi c¬ sè
2.1 §Þnh lý cña Legendre vµ §Þnh lý cña Kummer
Trong tiÕt nµy, chóng ta chøng minh hai ®Þnh lý cña Legendre vµ Kummer liªn quan ®Õn biÓu diÔn c¸c sè tù nhiªn trong c¸c hÖ ghi c¬ sè. Tr−íc
hÕt chóng ta chøng minh §Þnh lý Legendre. Cho n lµ mét sè tù nhiªn vµ p
lµ mét sè nguyªn tè. §Þnh lý Legendre gióp ta tÝnh sè tù nhiªn t sao cho
pt lµ −íc cña n! vµ pt+1 kh«ng lµ −íc cña n!.
2.1.1 KÝ hiÖu. Cho p lµ mét sè nguyªn tè vµ n > 1 lµ mét sè tù nhiªn.
Gi¶ sö n = pt11 . . . ptkk lµ ph©n tÝch tiªu chuÈn cña n thµnh tÝch c¸c thõa
sè nguyªn tè. NÕu p = pi víi i ∈ {1, . . . , k} th× ta ®Æt vp (n) = ti. NÕu
p∈
/ {1, . . . , k} th× ta ®Æt vp (n) = 0. Nh− vËy, vp (n) chÝnh lµ sè mò lín nhÊt
t sao cho pt lµ −íc cña n. Ch¼ng h¹n, ta cã 100 = 22 52 nªn v2 (100) = 2,
v5 (100) = 2 vµ vp (100) = 0 víi mäi sè nguyªn tè p kh¸c 2 vµ 5.
Môc tiªu ®Çu tiªn cña tiÕt nµy lµ chøng minh mét c«ng thøc tÝnh vp (n!)
th«ng qua biÓu diÔn cña sè n trong hÖ ghi c¬ sè p. §©y lµ mét kÕt qu¶
quan träng trong lý thuyÕt sè, ®−îc ph¸t hiÖn bëi Legendre n¨m 1808.
2.1.2 §Þnh lý (Legendre, 1808). Cho p lµ mét sè nguyªn tè vµ n > 1 lµ
mét sè tù nhiªn. Gi¶ sö
n = a0 pk + a1 pk−1 + . . . + ak−1 p + ak
16
17
lµ biÓu diÔn cña sè n trong hÖ ghi c¬ sè p. Khi ®ã ta cã
vp (n!) =
n − (a0 + a1 + . . . + ak )
.
p−1
Chøng minh. Víi mçi sè thùc a > 0, ta kÝ hiÖu [a] lµ sè nguyªn b lín
nhÊt sao cho b 6 a. Ta gäi [a] lµ phÇn nguyªn cña a. Theo C«ng thøc De
Polignac (c«ng thøc nµy cßn cã tªn lµ C«ng thøc Legendre, xuÊt hiÖn trong
mét cuèn s¸ch t¸i b¶n lÇn hai n¨m 1808).
∞
X
n
vp (n!) =
.
pk
k=1
n
ak
ak
= a0pk−1 +a1pk−2 +. . .+ak−2p+ak−1 + . Chó ý r»ng 0 6
< 1,
p
p
p
do ®ã
n
= a0 pk−1 + a1 pk−2 + . . . + ak−2 p + ak−1 .
p
Víi i 6 k ta cã
Ta cã
n
ak−i+1
ak−1 ak
k−i
k−i−1
=
a
p
+
a
p
+
.
.
.
+
a
+
+ i.
+
.
.
.
+
0
1
k−i
pi
p
pi−1
p
Chó ý r»ng
06
Do ®ã
ak−i+1
ak−1 ak
p−1
p−1 p−1
+ . . . + i−1 + i 6
+ . . . + i−1 +
p
p
p
p
p
pi
pi − 1
=
< 1.
pi
n
= a0 pk−i + a1pk−i−1 + . . . + ak−i.
i
p
- Xem thêm -