Đăng ký Đăng nhập
Trang chủ Hệ ghi cơ số và một số ứng dụng...

Tài liệu Hệ ghi cơ số và một số ứng dụng

.PDF
43
252
125

Mô tả:

ĐẠ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 -

Tài liệu liên quan