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


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ê

ấn độ vào Thế kỷ 5 sau công nguyên. Đến năm 1202 nhờ tác phẩm Liber
thì hệ
Abacci của L. Fibonacci (một nhà toán học và thơng gia ngời Y),
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

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

(111010, 01)2 = 1.25 + 1.24 + 1.23 + 0.22 + 1.21 + 0.20 + 0.21 + 1.22 .
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.81 + 8.82 .
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.161 + A.162
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 = 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 = 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