ĐẠ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 HC THI NGUYấN
TRNG I HC KHOA HC

MAI HUY NGHị


Hệ GHI CƠ Số Và MộT Số ứng dụng



Chuyờn ngnh: Phng phỏp Toỏn s cp
Mó s: 60.46.01.13

LUN VN THC S TON HC



Ngi hng dn khoa hc: PGS.TS. Lờ Th Thanh Nhn



THI 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 nhng Cô vẫn dành
thời gian và tâm huyết trong v iệ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ự g iú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ữn g 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 độn g 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à h oà 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 c uộc sống, có thể nói hệ gh i cơ số là một trong
những lí th uyế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 t r ong số học và có nhiều ứng dụng khác nhau t r ong khoa
học và thực tiễn. Lí thuyết hệ ghi cơ số liên quan đến nhiều lĩn h 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 ệ t hập phân, xuất hiện đầu tiên ở
ấn độ vào Thế kỷ 5 sau công n guyê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

Y), thì hệ
ghi thập phân mới đợc truyền bá vào châu Âu. Hệ n hị 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ĩn h vực kh oa 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 c hơng. Trong
Chơng 1, chúng tôi trình bày khái niệm hệ gh i 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 p
t
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ệ gh i cơ số p với p nguyên tố,
chúng ta có thể tính đợc số t lớn nhấ t sao cho p
t
là ớc củ a C
a

a+b
, trong
đó C
a
a+b
là số tổ hợp chập a của a + b p hầ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 = (a
n
. . . a
1
a
0
)
b
là biểu diễn của p trong hệ
ghi cơ số b thì đa t hức f(x) = a
n
x
n
+ . . . + a
1
x + a
0
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ệ gh i 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
Wikipe dia, 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 Anth ony Santos, Number Theory for Mathematical Contests,
GNU Free Documentation Licen se, October 31, 2007.
3. J. Stillwell, Elements of Number Theory, Springer, 2003.
4. M. R am Murty, Prime numbers an d 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 Ab acci của L. Fibonacci
(một nhà toán học đồng thời là thơng gia ngời

Y) thì hệ thập phân mới
đợc truyền bá vào Châu Âu. Với sự phát minh ra n ghề 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í d o cho rằn g do hai bàn tay có 10 ngó n và dễ dàng
đếm trên 10 n g ó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ụn g. 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ả thu y ế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 t hự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 t hủ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ụn g. 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ệ gh i 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ừ xa, 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 qu an 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 = a
n
b
n
+ a
n1
b
n1
+ . . . + a
1
b + a
0
b
0
+ a
1
b
1
+ a
2
b
2
+ . . . + a
m
b
m

,
trong đó n, m N, a
n
, . . . , a
0
, a
1
, . . . , a
m
{0, 1, . . . , b 1} và a
n
= 0.
Khi đó ta nói a = (a
n
. . . a
0
, 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ố t hờ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.10

4
+ 2.10
3
+ 5.10
2
+ 6.10
1
+ 8.10
0
+ 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.2
5
+ 1.2
4
+ 1.2
3
+ 0.2
2
+ 1.2
1
+ 0.2
0

+ 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.8
4
+ 0.8
3
+ 3.8
2
+ 6.8
1
+ 5.8
0
+ 6.8
1
+ 8.8
2
.
Hệ thậ p lục p h â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.16
5
+ A.16

4
+ 0.16
3
+ B.16
2
+ 1.16
1
+ F.16
0
+ 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à p hần lẻ), giữa hai phần ấy đợc n găn
8
cách với n h au 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 = 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 = a
n
b

n
+ . . . + a
1
b + a
0
, với n là số tự nhiên, a
0
, a
1
, . . . , a
n

{0, 1, . . . , b 1} và a
n
= 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ó b iểu diễn c = c
k
b
k
+ . . . + c
1
.b + c
0
, với k là số tự nhiên,
c
0

, c
1
, . . . , c
k
{0, 1, . . . , b 1} và c
k
= 0. Suy ra
a = c
k
b
k+1
+ . . . + c
1
.b
2
+ c
0
b + r.
Chọn n = k + 1, a
i+1
= c
i
với i = 0, 1, . . . , k và a
0
= 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 = a
n
b

n
+ . . . + a
1
b + a
0
= a

m
b
m
+ . . . + a

1
b + a

0
với n m là hai b iểu diễn của a trong hệ g hi cơ số b. Nếu a < b thì
m = n = 0 và a = a
0
= 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ì
a
0
, a

0
{0, 1, . . . , b 1} nên a

0
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ó a
0
= a

0
.
Suy ra
b(a
n
b
n1
+ . . . + a
1
) = b(a

m
b
m1
+ . . . + a

1
).
Giản ớc c ả hai vế cho b ta đợc a
n

b
n1
+ . . . + a
1
= a

m
b
m1
+ . . . + a

1
.
Đây là hai biểu diễn của cùng một số c = a
n
b
n1
+ . . . + a
1
trong hệ g hi
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à a
1
= a

1
, . . . , a
m
= b
m

. Suy ra m = n và a
i
= 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 ý san g 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 nhng 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 14
5 5 6 7 10 11 12 13 14
6 6 7 10 11 12 13 14 15
7 7 10 11 12 13 14 15 16
10
D−íi ®©y lµ b¶ng nh©n cña hÖ ghi c¬ sè 8 (b¸t p h ©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 c hữ
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 1, 1 3
x 1 3, 1 2
4 0 2 3 1
2 0 1 1 3
+ 1 1 0 3 4 4
2 0 1 1 3
3 1 3 4, 4 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 c ho đ ến khi hoàn thành. Chẳng hạn, chi a (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àn h 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 t hứ nhất là tính toán theo định nghĩ a. Cụ thể,
a = (a
n
a
n1
. . . a
1
a
0
)
b
= a
n
b
n
+ a
n1
b
n1
+ . . . + a
1
b + a
0

.
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 ở t r ong biểu diễn).
1.2.6 Ví dụ. Ch o a = (111010, 01)
2
, a

= (245)
6
, a

= (20365, 68)
8
và
a

= (3A0B1F, 3A)
16
. Khi đó
a = (111010, 01)
2
= 1.2
5
+ 1.2
4
+ 1.2
3
+ 0.2
2

+ 1.2
1
+ 0.2
0
+ 0.2
1
+ 1.2
2
= 58, 25;
a

= (245)
6
= 2.6
2
+ 4.6 + 5 = 101;
a

= (20365, 68)
8
= 2.8
4
+ 0.8
3
+ 3.8
2
+ 6.8
1
+ 5.8
0

+ 6.8
1
+ 8.8
2
= 84378, 75;
a

= (3A0B1F, 3A)
16
= 3.16
5
+ 11.16
4
+ 0.16
3
+ 12.16
2
+ 1.16
1
+ 15.16
0
+ 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 t iế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 c ho c. Cụ thể, bớc đầu tiên là chia a cho c đợc
thơng là q
1
và d là r
1
. Bớc tiếp theo ta chia q
1
cho c ta đợc thơn g q
2
và d r
2
. Cứ tiếp tục chia thơng cho c đến bớc thứ k ta thu đợc th ơng
13
q
k
= 0. Ta biểu diễn các số d r
1
, . . . , r
k
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 min h họa các h 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 11
8
= 9;
thực hiện phép chia 17545231 : 12, thơng là 1443565 và d 7
8
= 7;
thực hiện phép chia 1443565 : 12 ta đợc th ơng 120276 và d 11
8
= 9;
thực hiện phép chia 120276 : 12 ta đợc thơng 10023 và d 0
8
= 0;
thực hiện phép chia 10023 : 12 ta đợc thơng 633 và d 5
8
= 5;
thực hiện phép chia 633 : 12 t a đợc t hơng 51 và d 1
8
= 1;
thực hiện phép chia 51 : 12 ta đợc thơng 4 và d 1
8
= 1;
thực hiện phép chia 4 : 12 ta đợc thơng 0 và d 4
8
= 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 c ho

b đợc thơng q
1
và d r
1
. Bớc tiếp theo là chia th ơng q
1
cho b ta đợc
thơng q
2
và d r
2
. Cứ t iế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à q
1
và d là r
1
. Bớc tiếp theo ta chia thơng q
1
cho c và thu đợc
thơng q
2
và d r
2
. Cứ tiếp tục chia thơng cho c, cho đến khi ta thu đợc
thơng bằn g 0. Đổi các số d từ hệ ghi cơ số b sa n g hệ ghi cơ số b

rồi viết
chúng theo thứ tự từ hàn g đơn vị san g 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ệ gh i 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 c hia liên tiếp
Thực hiện phép chia 2347603 : 14, thơ ng là 150512 và d 13
8
= 11
12
;

thực hiện phép chia 15052 : 14 ta đợc thơng 10560 và d 12
8
= 10
12
;
thực hiện phép chia 15060 : 14 ta đợc thơng 564 và d 0
8
= 0
12
;
thực hiện phép chia 564 : 14 ta đợc t hơng 37 và d 0
8
= 0
12
;
thực hiện phép chia 37 : 14 ta đợc thơng 2 và d 7
8
= 7
12
;
thực hiện phép chia 2 : 14 ta đợc thơng 0 và d 2
8
= 2
12
.
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ún g ta chứng minh hai định lý của Legendre v à Kum-
mer 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 ý Legend r e giúp ta tính số tự nhiên t sao cho
p
t
là ớc của n! và p
t+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 = p
t
1
1
. . . p
t
k
k
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 = p
i
với i {1, . . . , k} thì ta đặt v
p
(n) = t
i

. Nếu
p / {1, . . . , k} thì ta đặt v
p
(n) = 0. Nh vậy, v
p
(n) chính là số mũ lớn nhất
t sao cho p
t
là ớc của n. Chẳng hạn, ta có 100 = 2
2
5
2
nên v
2
(100) = 2,
v
5
(100) = 2 và v
p
(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 v
p
(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 = a
0
p

k
+ a
1
p
k1
+ . . . + a
k1
p + a
k
16
17
là biểu diễn của số n trong hệ ghi cơ số p. Khi đó ta có
v
p
(n!) =
n (a
0
+ a
1
+ . . . + a
k
)
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 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).
v
p

(n!) =


k=1

n
p
k

.
Ta có
n
p
= a
0
p
k1
+a
1
p
k2
+. . .+a
k2
p+a
k1
+
a
k
p
. Chú ý rằng 0

a
k
p
< 1,
do đó

n
p

= a
0
p
k1
+ a
1
p
k2
+ . . . + a
k2
p + a
k1
.
Với i k ta có
n
p
i
= a
0
p
ki

+ a
1
p
ki1
+ . . . + a
ki
+
a
ki+1
p
+ . . . +
a
k1
p
i1
+
a
k
p
i
.
Chú ý rằng
0
a
ki+1
p
+ . . . +
a
k1
p

i1
+
a
k
p
i

p 1
p
+ . . . +
p 1
p
i1
+
p 1
p
i
=
p
i
1
p
i
< 1.
Do đó

n
p
i


= a
0
p
ki
+ a
1
p
ki1
+ . . . + a
ki
.
18
Tơng tự ta suy ra

n
p
i

= 0 với mọi i > k. Do đó ta có


k=1

n
p
k

= a
0
(1 + p + p

2
+ . . . + p
k1
) + a
1
(1 + p + p
2
+ . . . + p
k2
)
+ . . . + a
k1
(1 + p) + a
k
= a
0
p
k
1
p 1
+ a
1
p
k1
1
p 1
+ . . . + a
k1
p
2

1
p 1
+ a
k
p 1
p 1
=
a
0
p
k
+ a
1
p
k1
+ . . . + a
k
(a
0
+ a
1
+ . . . + a
k
)
p 1
=
n (a
0
+ a
1

+ . . . + a
k
)
p 1
.
Từ đây ta có điều phải c hứng minh.
Mục tiêu thứ hai của tiết này là chứng minh Định lý của Kummer. Với
k n là hai số tự nhiên, kí hiệu C
k
n
=
n!
k!(n k)!
là số tổ hợp chập k của
n phần tử. Với m, n là hai số tự nhiê n biểu diễn trong hệ ghi cơ số b. Số
lần nhớ khi cộng m với n t rong hệ ghi cơ số b đợc hiểu là số lần cộng
hai chữ số ở cùng một v ị tr í của m và n (cộng từ v ị trí phía bên phải sang)
và cộng t hêm với p hần nhớ ở lần cộng trớc (nếu có) lớn hơn hay bằng b.
Chẳng hạn, cho m = (23432)
5
và n = (102132)
5
. Thự c hi ện phép c ộng m
và n
+ 2 3 4 3 2
1 0 2 1 3 2
1 3 1 1 1 4
Trong phép c ộng này, lần n hớ thứ nhất xuất hiện khi ta cộng 3 với 3 (ở vị
trí thứ hai của m và n), đợc số nhớ là 1. Lần nhớ th ứ hai xuất hiện k hi t a
cộng 4 với 1 (ở vị trí thứ ba củ a m và n) và cộng thêm với 1 (số nhớ của

lần cộng trớc), đợc số nhớ là 1. Lần nhớ th ứ ba xuất hiện khi ta cộng 3
với 2 (ở vị trí thứ t của m và n) và cộng thêm với 1 (số nhớ của lần cộng
19
trớc), đợc số d là 1. Nh vậy, khi cộng m và n trong hệ ghi cơ số 5, số
lần nhớ là 3. Mục tiêu thứ hai của tiết này là chứng minh một kết quả của
Kummer trong lý thuyết số, cho ta côn g thức tính v
p
(C
m
n+m
) thông qua số
lần nhớ khi cộ ng m với n trong hệ ghi cơ số p.
2.1.3 Định lý (Kummer, 1852). Cho a và b là hai số tự nhiên và p là một
số nguyên tố. Khi đó v
p
(C
m
n+m
) là số lần nhớ khi thực hiện phép cộng m
với n trong hệ ghi cơ số p.
Chứng minh. Viết
a = a
0
+ a
1
p + . . . + a
k
p
k
;

b = b
0
+ b
1
p + . . . + b
t
p
t
là hai biểu diễn của a và b trong hệ g hi cơ số p. Khi đó 0 a
j
, b
j
p 1
và a
k
, b
t
> 0. Không mất tính tổng quát, ta giả th iết t k. Nếu t < k thì
ta đặt b
t+1
= . . . = b
k
= 0. Khi đó ta có
b = b
0
+ b
1
p + . . . + b
k
p

k
với a
k
+ b
k
> 0. Đặt S
a
=
k

j=0
a
j
, S
b
=
k

j=0
b
j
. Chú ý rằng a
0
+ b
0

(p 1) + (p 1) = p + (p 2). Do đó khi chi a a
0
+ a
1

cho p ta đ ợc
a
0
+ b
0
=
0
p + c
0
với 0 c
0
< p và
0
= 0 hoặc
0
= 1. Tơng tự, vì

0
{0, 1} nên
0
+ a
1
+ b
1
1 + (p 1) + (p 1) = p + (p 1). Do đó
khi chia
0
+ a
1
+ b

1
cho p ta đợc
0
+ a
1
+ b
1
=
1
p + c
1
với 0 c
1
< p
và
1
= 0 hoặc
1
= 1. C ứ tiếp tục lập luận trên, tồn tại các số tự nhiê n
20
c
i
< p và các số
i
bằng 0 hoặc bằng 1 sao cho
a
0
+ b
0
=

0
p + c
0
,

0
+ a
1
+ b
1
=
1
p + c
1
,

1
+ a
2
+ b
2
=
2
p + c
2
,
.
.
.


k1
+ a
k
+ b
k
=
k
p + c
k
.
Với i = 0, . . . , k, nhân cả hai vế của đ ẳng thức thứ i với p
i1
(tức là nhân
đẳng thức thứ nhất với 1, đẳng thức thứ hai với p, . . ., đẳng thức thứ k + 1
với p
k
) rồi cộng vế v ới vế của tất cả các đẳng thức đó ta đợc
a + b +
0
p +
1
p
2
+ . . . +
k1
p
k
=
0
p +

1
p
2
+ . . . +
k1
p
k
+
k
p
k+1
+ c
0
+ c
1
p + . . . + c
k
p
k
.
Ta suy ra a + b = c
0
+ c
1
p + . . . + c
k
p
k
+
k

p
k+1
. Suy ra
S
a
+ S
b
+ (
0
+
1
+ . . . +
k1
) = (
0
+
1
+ . . . +
k
)p + S
a+b

k
.
Theo Định lý Leg endre ta suy ra
(p1)v
p
(C
m
n+m

= (a+b)S
a+b
a+S
a
b+S
b
= (p1)(
0
+
1
+. . .+
k
).
Chú ý rằng
0
+
1
+ . . . +
k
là số lần nhớ khi thự c hiện phép cộng a với
b trọng hệ ghi cơ số p. Từ đó ta có điều phải chứng minh.
Ta minh họa Định lý Kummer thông qua ví dụ sau.
2.1.4 Ví dụ. Cho a = 23 và b = 32. Trong hệ ghi cơ số 5, ta có 23 = (43)
5
và 32 = (112)
5
. Phép c ộng (43)
5
+ (112)
5

= (210)
5
trong hệ gh i cơ số 5
có 2 lần nhớ, lần nhớ thứ nhất là cộng 3 với 2 (ở vị trí đầu tiên từ bên phải
sang), số nh ớ là 1, lần nhớ thứ hai là c ộng 4 với 1 (ở vị trí thứ hai từ phải
sang) cộng thêm số nhớ 1, ta đợc số nhớ bằng 1.
21
Mặt khác, ta có
C
32
23+32
= C
32
55
=
33.34. . . . 54.55
1.2 . . . 22.23
.
Trong biểu thức ở tử, các thừa số chia hết cho 5 là 35 = 5.7, 40 = 5.8,
45 = 5.9, 50 = 5
2
.2, 55 = 5.11. Do đó biểu thức ở tử có thể viết dới dạng
5
6
c, trong đó c là số tự nhiên không là bội của 5. Các thừa số ở mẫu số
chia hế t ch o 5 là 5 = 5.1, 10 = 5.2, 15 = 5.3, 20 = 5.4. Do đó biểu thức
mẫu đợc viết dới dạng 5
4
d, trong đó d là một số tự nhiên không chia hết
cho 5. Suy ra C

32
55
= 5
2
n, trong đ ó n là số tự nhiên không là bội của 5. Vì
thế v
5
(C
32
55
) = 2. Chú ý rằng 2 cũng là số lần nhớ khi cộng a và b trong hệ
ghi cơ số 5 nh đã phân tích ở trên.
Khi a, b lớn, việc tìm v
p
(C
b
a+b
) một cách trực ti ếp là vô cùng khó khăn.
Nhờ Định lý Kummmer, chúng ta có thể tính đợc giá trị n ày một cách
nhanh chóng. Sau đây là một ví dụ.
2.1.5 Ví dụ. Cho a = 1742 và b = 3417. Trong hệ ghi cơ số 5 ta có biểu
diễn a = (23432)
5
và b = (102132)
5
. Nh đã tính trong ví dụ trên, số lần
nhớ khi cộng a với b là 3. Do đó theo Định lý Kumme r ta có
C
a
a+b

= C
1742
5159
= 5
3
c,
trong đó c là số tự nhiên không chia hết c ho 5. Vì thế v
5
(C
1742
5159
) = 3.
2.2 Xây dựng đa thức bất khả quy từ số nguyên tố
Mục tiêu của tiết này là sử dụng hệ ghi cơ số để xây dựng các đa thức bất
khả quy. Cụ thể, chúng ta sẽ chứng minh rằ ng nếu n là một số nguyên tố
và n có biểu diễn trong hệ ghi cơ số b là n = (a
m
. . . a
1
a
0
)
b
thì đa thức
f(x) = a
m
x
m
+ . . . + a
1

x + a
0
là bất khả quy trên Q với mọi số tự n h iên
22
b > 1. Để chứng mi nh kết quả này, chúng ta cần nhắc lại khái niệm đa thức
bất khả quy, một số tính chất của đa thức bất khả quy. Đồng thời chún g ta
cũng cần đến Định lý cơ bản của Đại số. Trong suốt tiết này ta g iả thiết
K C là một trờng. Ta thờng xét trong trờn g hợp K là một trong các
trờng Q, R, C.
2.2.1 Định nghĩa. Đa thức f(x) với hệ số trên một trờng K là bất khả
quy nếu và chỉ nếu deg f(x) > 0 và f(x) không phân tích đợc thành tích
của hai đa thức có bậc bé hơn.
Chẳng hạn, đa thức bậc nhất luôn bất khả quy vì đa thức bậc nhất
không thể là tích của h ai đa thức bậc thấp hơn. Đa thức b ậc 2 và bậc 3
là bất khả quy nếu và chỉ nếu nó không có nghiệm trong K. Thật vậy,
nếu f(x) có nghiệm x = a K thì f = (x a)g(x) với g(x) K[x] và
deg g(x) = deg f(x) 1 1. Ngợc lại, nếu f(x) khả quy thì bậc 2 hoặc
3 thì f(x) là tích của một đa thức bậc 1 và một đa thức bậc hai hoặc bậc
ba, do đó nó có nghiệm trong K. Đa thức (x
2
+ 1)
2
không có nghiệm trong
R nhng rõ ràng nó khôn g bất khả quy trên R.
Chúng ta trình bày một số tính chất của đa thức bất khả quy tơng tự
nh tính chất của số nguyên tố. Trớc hết, Bổ đề Euclid phát biểu rằng số
tự nhiên p > 1 là số nguyên tố nếu và chỉ nếu p là ớc của ab kéo the o p
là ớc của a hoặc p là ớc của b với mọi a, b N. T ính chất sau đây là
điều tơng tự cho đa thức bất khả quy.
2.2.2 Mệnh đề. Nếu p(x) K[x] là bất khả quy và p(x)|a(x)b(x) thì

p(x)|a(x) hoặc p(x)|b(x) với mọi a(x), b(x) K[x].
Chứng minh. Cho p(x) bất khả quy. Giả sử p(x)|a(x)b(x) và a(x), b(x) đều
không là bội của p(x). Do p(x) bất khả quy nên gcd(p(x), a(x)) = 1 và
gcd(p(x), b(x)) = 1. Do đó tồn tại s(x), r(x), e(x), f(x) K[x] sao cho