BỘ GIÁO DỤC VÀ ĐÀO TẠO UBND TỈNH THANH HÓA
TRƯỜNG ĐẠI HỌC HỒNG ĐỨC

NGUYỄN MẠNH HUY

CÁC KẾT QUẢ VỀ VIỆC XÁC ĐỊNH SỐ
FROBENIUS CỦA TẬP CÁC SỐ CHO TRƯỚC
VÀ CÁC ỨNG DỤNG CỦA NĨ

LUẬN VĂN THẠC SĨ TỐN HỌC

THANH HĨA - Năm 2020


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC HỒNG ĐỨC

NGUYỄN MẠNH HUY

CÁC KẾT QUẢ VỀ VIỆC XÁC ĐỊNH SỐ
FROBENIUS CỦA TẬP CÁC SỐ CHO TRƯỚC
VÀ CÁC ỨNG DỤNG CỦA NÓ

Chuyên ngành : Đại số và lí thuyết số
Mã số : 8. 46. 01. 04

Người hướng dẫn : TS. ĐINH THÀNH TRUNG


Mục lục
Lời cam đoan

Lời cảm ơn
Một số ký hiệu
Mở đầu

i
ii
iii
1

Chương 1. TỔNG QUAN VỀ BÀI TOÁN FROBENIUS
1.1 Sự tồn tại của số Frobenius . . . . . . . . . . . . . . . . . .
1.2 Công thức của số Frobenius khi k = 2 . . . . . . . . . . . .
1.3 Số Frobenius trong trường hợp tổng quát . . . . . . . . . .
1.3.1 Tính chất và các chặn cho số Frobenius . . . . . . .
1.3.2 Công thức số Frobenius của cấp số cộng . . . . . . .
1.4 Số Frobenius khi k = 3 . . . . . . . . . . . . . . . . . . . . .
Chương 2. Thuật tốn tính s Frobenius v ng dng
2.1 Thut toỏn Răodseth . . . . . . . . . . . . . . . . . . . . . . .
2.2 Số Frobenius của 3 số chính phương liên tiếp . . . . . . . .
Kết luận
Tài liệu tham khảo

3
3
4
5
5
11
12
15

15
19
23
24

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

. . .
. . .



Lời cam đoan
Tôi xin cam đoan bản luận văn này là kết quả nghiên cứu của cá nhân tôi.
Các số liệu và tài liệu được trích dẫn trong luận văn là trung thực. Kết quả
nghiên cứu này không trùng với bất cứ cơng trình nào đã được cơng bố trước
đó.
Trong quá trình nghiên cứu và thực hiện luận văn, tác giả đã kế thừa những
kết quả của các nhà khoa học với sự trân trọng và biết ơn.
Tôi chịu trách nhiệm với lời cam đoan của mình.

Thanh Hóa ngày 07 tháng 11 năm 2020
Học viên

Nguyễn Mạnh Huy

i


Lời cảm ơn
Luận văn được thực hiện và hoàn thành tại trường Đại học Hồng Đức dưới
sự hướng dẫn của TS. Đinh Thành Trung. Nhân đây tôi xin được bày tỏ lòng
biết ơn sâu sắc đến thầy người đã tận tình chỉ dẫn và truyền dạy cho tơi những
kinh nghiệm quý báu trong học tập và trong nghiên cứu suốt thời gian vừa qua.
Đồng thời tôi cũng xin gửi lời cảm ơn tới các thầy cô trong Bộ môn Đại số, khoa
Khoa Học Tự Nhiên, trường Đại học Hồng Đức đã tạo mọi điều kiện thuận lợi
để tơi có thể hồn thành tốt luận văn này.
Cuối cùng tơi xin bày tỏ lịng tri ân sâu sắc tới gia đình, bạn bè đã ln ở
bên động viên, khích lệ, giúp đỡ tơi trong suốt q trình học tập và nghiên cứu.
Tơi xin chân thành cảm ơn.

Thanh Hóa ngày 07 tháng 11 năm 2020

Học viên

Nguyễn Mạnh Huy

ii


Một số ký hiệu
Tập hợp các số tự nhiên
Tập hợp các số nguyên
g(a1 , . . . , ak )
Số Frobenius của dãy số a1 , . . . , ak
(a1 , . . . , ak ) = 1 Ước chung lớn nhất của a1 , . . . , ak
N
Z

iii


Mở đầu
Cho a1 , a2 , . . . , ak là các số nguyên dương sao cho ước chung lớn nhất của
chúng bằng 1. Khi đó tồn tại số N sao cho mọi số nguyên dương n ≥ N ln có
thể biểu diễn được dưới dạng n = c1 a1 + c2 a2 + · · · + ck ak , trong đó c1 , c2 , . . . , ck là
các số nguyên không âm. Số nguyên lớn nhất không biểu diễn được dưới dạng
trên được gọi là số Frobenius, ký hiệu là g (a1 , a2 , . . . , ak ).
Ví dụ: g (4, 5) = 11, vì mọi số nguyên n ≥ 12 đều biểu diễn được dưới dạng
n = 4a + 5b với a, b ∈ N, nhưng 11 không biểu diễn được.
Một vấn đề trung tâm trong lý thuyết nửa nhóm số là hãy xác định số
Frobenius của tập các số nguyên dương nguyên tố cùng nhau, gọi là bài toán
Frobenius. Bài tốn Frobenius có những ứng dụng quan trọng trong nhiều lĩnh

vực khác nhau của toán học như Lý thuyết số, Lý thuyết tự động và Tổ hợp.
Đặc biệt, bài tốn Frobenius có những ứng dụng để phân tích các mạng Petri,
để nghiên cứu bài tốn phân loại các khơng gian véc tơ, các nhóm Aben, nghiên
cứu các mật mã hình học đại số thơng qua tính chất của các nửa nhóm đặc biệt,
để nghiên cứu các bài tốn xếp hình.
Từ những năm 1890 người ta đã biết cơng thức tường minh tính số Frobenius của hai số tự nhiên a, b nguyên tố cùng nhau. Tuy nhiên việc tìm công thức
tường minh cho số Frobenius của 3 số trở lên chưa có lời giải trọn vẹn. Vì vậy,
vấn đề nghiên cứu bài toán Frobenius cho trường hợp từ 3 số trở lên là một
trong các vấn đề trung tâm hiện nay trong lý thuyết nửa nhóm số. Các kết quả
đạt được về hướng nghiên cứu này cho đến nay chủ yếu là cung cấp các chặn
cho số Frobenius, chứng minh công thức tường minh của số Frobenius cho tập
các số có dạng đặc biệt, và các thuật tốn tính số Frobenius.
Mục đích của luận văn và trình bày tổng quan các kết quả quan trong về
bài tốn Frobenius. Ngồi phần mở đầu, kết luận và tài liệu tham khảo, luận
văn gồm 2 chương. Trong Chương 1, luận văn trình bày lại chứng minh của công
thức tường minh cho số Frobenius của 2 số. Tiếp theo, luận văn trình bày một số
kết quả tổng quát về số Frobenius cho k tùy ý. Phần cuối cùng trong Chương 1
luận văn thảo luận về một vài kết quả đã biết cho số Frobenius ca 3 s nguyờn
dng.
ă
Chng 2 ca trỡnh by mt thut toỏn tớnh s Frobenius ca Oystein
J.
ă
ROdseth, v mt ng dụng của thuật tốn này trong việc tìm ra được cơng thức
tính số Frobenius của 3 số chính phương liên tiếp, được đưa ra bởi M.Lepilov,
J. O’Rourke, and I. Swanson.
Các kết quả cũng như định lý ở trong luận văn được viết chủ yếu dựa vào

1



cuốn sách của J. L. Ramirez Alfosin "The Diophantine Frobenius Problem" xuất
bản năm 2005 và hai bài báo được nêu ra ở Chương 2.

2


Chương 1

TỔNG QUAN VỀ BÀI
TOÁN FROBENIUS
Trong chương này chúng ta sẽ trình bày khái qt về bài tốn Frobenius.
Cụ thể, sau khi phát biểu biểu bài tốn và trình bày chứng minh sự tồn tại,
luận văn sẽ điểm lại một vài kết quả đáng chú ý cho số Frobenius của tập hai
số, tập ba số cũng như trong trường hợp tổng quát.

1.1

Sự tồn tại của số Frobenius

Định lý dưới đây là một kết quả cổ điển trong lý thuyết nửa nhóm số.
Định lý 1.1.1. Cho a1 , a2 , . . . , ak là các số nguyên dương với (a1 , a2 , . . . , ak ) = 1.
Khi đó tồn tại số N sao cho mọi số ngun dương n ≥ N ln có thể biểu diễn
được dưới dạng
n = c 1 a1 + c 2 a2 + . . . + c k ak ,

với c1 , c2 , . . . , ck là các số nguyên không âm.
Số nguyên lớn nhất không biểu diễn được dưới dạng trong kết luận của định
lý trên được gọi là số Frobenius của a1 , a2 , . . . , ak , ký hiệu là g (a1 , a2 , . . . , ak ).
Chứng minh. Ta sẽ trình bày 2 chứng minh cho định lý này.

Chứng minh thứ nhất:
Vì (a1 , . . . , ak ) = 1 nên ta có thể viết m1 a1 + m2 a2 + . . . + mk ak = 1 với số
nguyên mi . Kí hiệu P và −Q là tổng các số hạng dương và tổng các số hạng âm ở
trong tổ hợp trên, vì vậy P và Q thuộc vào nửa nhóm W tạo ra bởi a1 , a2 , . . . , ak
và P − Q = 1. Mọi số nguyên l ≥ 0 được viết dưới dạng ha1 + l0 với h ≥ 0 và
0 ≤ l0 < a1 . Khi đó


0
0
(a1 − 1) Q + l = ha1 + a1 − 1 − l Q + l P ∈ W.

3


Do đó tất cả các số nguyên lớn hơn hoặc bằng (a1 − 1) Q đều thuộc W. Điều đó
có nghĩa là, bất kỳ số nguyên t ≥ (a1 − 1) Q đều có thể viết được dưới dạng tổ
hợp nguyên không âm của a1 , a2 , . . . , ak−1 .
Chứng minh thứ hai:
Nếu k = 2 ta đã biết theo kết quả sẽ được chứng minh g (a1 , a2 ) = a1 a2 −
a1 − a2 (theo định lý 1.2.1). Giả sử rằng k ≥ 3. Nếu (a1 , . . . , ak−1 ) = 1, khẳng định
là đúng theo quy nạp, thậm chí không cần ak trong biểu diễn của các số nguyên
đủ lớn. Do vậy ta chỉ cần xét (a1 , . . . , ak−1 ) = d > 1.
Cho ai = a0i d với mỗi i = 1, . . . , k − 1. Vì (d, ak ) = 1 nên phương trình
k
k−1
P
P 0
m − ak b k
(1.0.2) trong đó 0 ≤ bk ≤ d − 1
ai xi = m (1.0.1) trở thành

ai x i =
d
là số nguyên duy

nhất sao cho ak bk ≡ m mod d. Theo quy nạp, tồn tại số nguyên
M a01 , . . . , a0k−1 sao cho (1.0.2) có nghiệm ngun khơng âm xi = bi , 1 ≤ i ≤ k − 1
i=1

i=1

bất cứ khi nào
m − ak (d − 1)
m − ak b k
≥
> M (a1 , . . . , ak−1 ) .
d
d

Vì vậy (1.0.1) có nghiệm ngun khơng âm xi = bi , 1 ≤ i ≤ k bất cứ khi nào
m > ak (d − 1) + dM (a1 , . . . , ak−1 ) .
Bài toán Frobenius. Cho a1 , a2 , . . . , ak là các số nguyên dương nguyên tố
cùng nhau. Tính số Frobenius g(a1 , a2 , . . . , ak ).

1.2

Công thức của số Frobenius khi k = 2

Chúng ta có một cơng thức rất gọn gàng và đẹp cho số Frobenius của hai
số nguyên dương.
Định lý 1.2.1. Cho a1 , a2 là các số nguyên dương nguyên tố cùng nhau. Khi đó
g (a1 , a2 ) = a1 a2 − a1 − a2 .


Ta sẽ trình bày hai cách chứng minh khác nhau cho Định lý 1.2.1. Chứng
minh đầu tiên dựa theo Nijenhuis và Wilf [14], thứ hai là chứng minh số học.
Chứng minh. Chứng minh thứ nhất:
Vì (a1 , a2 ) = 1 nên bất kì số nguyên n nào cũng có thể biểu diễn được dưới
dạng n = xa1 + ya2 trong đó x, y ∈ Z.
Lưu ý rằng n có thể biểu diễn được theo nhiều cách khác nhau nhưng biểu
diễn là duy nhất nếu ta yêu cầu 0 ≤ x < a2 . Trong trường hợp này, nếu y ≥ 0 thì
rõ ràng n biểu diễn được như là môt tổ hợp tuyến tính với hệ số ngun khơng
âm của a1 và a2 , cịn nếu y < 0 thì n khơng thể biểu diễn được như vậy. Do đó,

4


giá trị n lớn nhất không thể biểu diễn được như là một tổ hợp tuyến tính với hệ
số nguyên không âm của a1 và a2 tương ứng với x = a2 − 1 và y = −1. Vì vậy
g (a1 , a2 ) = (a2 − 1) a1 + (−1)a2 = a1 a2 − a1 − a2 .

Chứng minh thứ hai:
Cho T = a1 N +a2 N = {xa1 + ya2 |x, y ∈ N }. Giả sử a1 a2 −a1 −a2 = r1 a1 +r2 a2
với r1 , r2 ∈ N. Vì vậy a1 (a2 − r1 − 1) = a2 (r2 + 1) và vì (a1 , a2 ) = 1 nên a2 − r1 − 1 =
sa2 ≥ a2 đó là vơ lý. Như vậy a1 a2 − a1 − a2 ∈
/ T.
Bây giờ đặt c = a1 a2 − a1 − a2 , ta có thể chỉ ra rằng c + i ∈ T với bất kì số
nguyên i ≥ 1. Do (a1 , a2 ) = 1, theo định lý Bézout, luôn tồn tại các số nguyên r1
và r2 với 0 ≤ r1 < a2 sao cho a1 r1 + a2 r2 = 1. Khi đó
c + i = (a2 − 1 + ir1 ) a1 + (ir2 − 1) a2 .

(1.1)


Ta có thể viết (1.1) dưới dạng c + i = v1 a1 + v2 a2 với 0 ≤ v2 < a1 . Vì
−i = c−v1 a1 −v2 a2 = (−v1 −1)a1 +(a1 −1−v2 )a2 không thuộc T , và do a1 −1−v2 ≥ 0
nên ta phải có −v1 − 1 < 0 dẫn đến v1 > −1, do đó v1 ≥ 0. Vì vậy c + i ∈ T .

1.3

Số Frobenius trong trường hợp tổng
quát

Trong Chương này luận văn trình bày một số kết quả về chặn trên và chặn
dưới cho số Frobenius của tập các số nguyên dương tùy ý, và công thức tường
minh cho số Frobenius của một cấp số cộng các số nguyên dương.

1.3.1

Tính chất và các chặn cho số Frobenius

Schur (1935) chứng minh một chặn trên đơn giản cho số Frobenius của tập
các số nguyên dương tùy ý. Kết quả này được đề câp đến trong [3].
Định lý 1.3.1. [3] Giả sử (a1 , . . . , ak ) = 1. Khi đó
g (a1 , . . . , ak ) ≤ (a1 − 1) (ak − 1) − 1

.
Cũng trong [3] Brauer chứng minh được kết quả tốt hơn như trong định lý
dưới đây.
Định lý 1.3.2. [3] Ký hiệu di = (a1 , . . . , ai ). Khi đó
g (a1 , . . . , ak ) ≤

k−1
X


ai+1 di /di+1 −

i=1

k
X
i=1

5

ai .


Để chứng minh Định lý 1.3.2 ta cần các bổ đề quan trọng dưới đây.
Bổ đề 1.3.3. [4] Ta luôn có
g (a1 , . . . , ak ) =

max

l∈{1,2,...ak −1}

{tl } − ak ,

trong đó tl là số nguyên dương bé nhất đồng dư với l modulo ak , đồng thời biểu
diễn được dưới dạng tổ hợp của a1 , . . . , ak với các hệ số không âm.
Chứng minh. Chứng minh khá là đơn giản. Cho L là một số nguyên dương. Nếu
L ≡ 0 mod ak thì L là tổ hợp của ak với hệ số ngun khơng âm.
Nếu L ≡ l mod ak thì L là tổ hợp số nguyên không âm của a1 , . . . , ak khi và
chỉ khi L ≥ tl .

Bổ đề 1.3.4. [4] Ký hiệu d = (a1 , . . . , ak−1 ), khi đó

a
a
g (a1 , . . . , ak ) = dg

1

d

,...,

k−1

d

, ak + (d − 1) ak .

(1.2.2)

Chứng minh. Ký hiệu
G (a1 , . . . , ak ) = g (a1 , . . . , ak ) +

k
X

ai ,

i=1


tức là G là số nguyên lớn nhất không thể biểu diễn dưới dạng tổ hợp tuyến tính
của a1 , . . . , ak với các hệ số nguyên dương. Khi đó đẳng thức (1.2.2) đúng khi và
chỉ khi
G (a1 , . . . , ak )

k
X

ai = dG

a

k−1

X ai
ak−1
,...,
, ak − d
− dak + (d − 1) ak ,
d
d
d

i=1



1

i=1


tức là khi và chỉ khi
ak−1
, ak + ak − dak + (d − 1) ak
d
d

a
ak−1
1
= dG
,...,
, ak .
d
d

G (a1 , . . . , ak ) = dG

Lưu ý rằng G (a1 , . . . , ak ) =

a

k
P

1



,...,


ai xi , xi > 0 (ta có thể viết

i=1

ak + G (a1 , . . . , ak ) =

k
X
i=1

6

ai xi , xi + ak xk , xk > 0


, do đó G (a1 , . . . , ak ) =

k
P

ai xi + ak (xk − 1) như vậy mâu thuẫn với định nghĩa

i=1

của G trừ khi xk = 1).
Cho ai = dai , i = 1, . . . , k − 1. Do đó G =

k−1
P


ai x i = d

i=1

k−1
P

ai xi và G chia hết

i=1

cho d.
Giả sử G = dG0 (1.2.3), rõ ràng rằng G0 không thể biểu diễn được dưới
dạng tổ hợp tuyến tính a1 , . . . , ak−1 , ak với các hệ số ngun dương (nếu khơng
k−1
k−1
P
P
thì G0 = yk ak +
ai yi với yi > 0 và G = G0 d = y1 da1 +
ai yi là mâu thuẫn).
i=1

i=1

Bây giờ nếu h > G thì h có thể biễu diễn được dưới dạng tổ hợp tuyến tính
của a1 , . . . , ak−1 , ak với hệ số nguyên dương.
k
k−1

P
P
Vì hd > G0 d = G nên hd =
ai zi = zk ak + d
ai zi , zi > 0. Do đó d phải
i=1

i=1

chia hết zk , giả sử z1 = dz1 và h = zk ak +

k−1
P

ai zi . Vì vậy G0 = G (a1 , . . . , ak−1 , ak )

i=1

và theo (1.2.3) ta được
G (a1 , . . . , ak ) = dG

a

1

d

,...,

ak−1

, ak .
d



Chứng minh. (của Định lý 1.3.2) Chú ý rằng




g

ai ai+1
a1
,..., ,
di
di di+1

dấu bằng xảy ra khi

≤g

ai
a1
,...,
di
di

,


(1.2.1)

ai+1
a
a
phụ thuộc vào 1 , . . . , i . Do
di+1
di
di
di
=
di+1



a1
ai
,...,
di+1
di+1


,

khi đó lặp lại liên tiếp ứng dụng của Bổ đề 1.3.4 và áp dụng (1.2.1) ta sẽ có điều
cần chứng minh.
Wilf [24] đưa ra một thuật tốn để tính số Frobenius, và một hệ quả của
thuật toán này là một chặn trên gọn gàng cho số Frobenius.
Định lý 1.3.5. [24] Cho các số nguyên dương a1 , a2 , . . . , ak với (a1 , a2 , . . . , ak ) = 1.
Ta ln có

g (a1 , . . . , ak ) ≤ a2k .

M. Beck, R. Diaz and S. Robins [1] sử dụng các kết quả về phân hoạch của
các số nguyên chứng minh được chặn trên sau.

7


Định lý 1.3.6. [1] Cho a1 ≤ · · · ≤ ak với (a1 , . . . , ak ) = 1. Khi đó


1 p
g (a1 , . . . , ak ) ≤

a1 a2 a3 (a1 + a2 + a3 ) − a1 − a2 − a3

2

.

Định lý 1.3.7 (Selmer [21]). Cho a1 , . . . , ak là các số nguyên dương và (a1 , . . . , ak ) =
1. Khi đó
ja k
1

g (a1 , . . . , ak ) ≤ 2ak

− a1 .

k


Chặn trên trong Định lý 1.3.7 đôi khi nhỏ hơn chn trờn trong nh lý sau.
nh lý 1.3.8 (Erdăos v Graham [8]). Cho a1 , . . . , ak là các số nguyên dương
và (a1 , . . . , ak ) = 1. Khi đó
ja k
k

g (a1 , . . . , ak ) ≤ 2ak−1

− ak .

k

Chứng minh. Gọi A = (0, a1 , . . . , ak−1 ) là tập các phần dư modulo ak và đặt
C = |A + .{z
. . + A} = A = { b1 + . . . + bm | bi ∈ A} mod ak ,
m

ja k
ở đó m = k . Theo một định lý của Kenser [12] tồn tại một ước g 0 (nhỏ nhất)
k

của ak mà

0

0

(g )
C=A

+ .{z
. . + A(g }) mod ak
|
m

ở đó

0

A(g ) =



a + rg 0
0 ≤ r < ak /g 0 .a ∈ A mod ak ,






và sao cho
|C|
mk m − 1
≥
−
.
ak
ak
g0


(1.2.4)

Giả sử rằng C không chứa một hệ thặng dư đầy đủ modulo ak . Vì (a1 , . . . , ak ) = 1
0
nên A(g ) phải bao gồm nhiều hơn một modulo lớp g 0 . Theo Định lý Kenser và
tính nhỏ nhất của g 0 thì C phải chứa ít nhất m+1 lớp thặng dư phân biệt modulo
g 0 . Vì vậy
|C|
m+1
≥
.
ak
g0

Lưu ý rằng ak ≥ k và m =

ja k
k

k

, suy ra


m+1>

(1.2.5)




1 m−1 

.
2 mk 1
−
ak
2

8

(1.2.6)


1
2

Bây giờ giả sử |C| ≤ ak . Theo (1.2.4) và (1.2.6) ta có
mk m − 1
1
−
≤ ,
0
ak
g
2

g0 ≤

m−1

< 2 (ak + 1) .
mk 1
−
m
2

Do đó theo (1.2.5) ta lại có
1
|C|
m+1
m+1
= ,
≥
>
0
ak
g
2 (m + 1)
2
1
2

đó là một mâu thuẫn. Do đó, ta có thể giả định rằng |C| > ak . Nhưng trong
trường hợp này dễ dàng có thể thấy rằng C + C chứa một hệ thặng dư đầy đủ
modulo ak . Theo đó, số nguyên bé nhất có thể viết được dưới dạng
x1 b1 + . . . + x2m b2m + xak

, với xi ≥ 0, x ≥ 0 và bi ∈ A cho bởi
2m.max a − ak = 2ak1
aA


ja k
n

n

an .

Răodseth [20] chng minh kt qu tt hn kt qu ca Erdăos and Graham
khi n là số lẻ.
Định lý 1.3.9. [20] Cho k là số nguyên lẻ, khi đó
ja + 2k
1

g (a1 , . . . , ak ) ≤ 2ak

k+1

− a1 .

Dãy a1 , a2 , . . . , ak được gọi là dãy độc lập nếu khơng có phần tử nào được
biểu diễn như là tổ hợp với hệ số không âm của các phần tử còn lại.
Định lý 1.3.10 (Vitek [22]). Cho a1 < . . . < ak là một dãy độc lập với k ≥ 2 thì
ja k
1

g (a1 , . . . , ak ) <

2


(ak − k) .

Chứng minh. Ta chứng minh bằng phương pháp quy nạp theo k . Với k = 2, Định
lý 1.3.10 luôn đúng. Ta giả sử nó đúng với k = l − 1 và chứng minh nó đúng với
k = l.
a

al−1
1
Đặt (a1 , . . . , al ) = d, thì rõ ràng (d, al ) = 1 và
,...,
= 1 nên theo
d

giả thiết quy nạp ta có
a
g

1

d

,...,

al−1
d



<


ja k a
1
l−1
2d

9

d

d



−l+1 .


Tất cả các bội số của d bắt đầu từ

ja k a
1
l−1
2d

d



− l + 1 d đều biểu diễn được như


là tổ hợp tuyến tính với hệ số ngun khơng âm a1 , . . . , al−1 .
Mặt khác, trên tất cả các số từ g (d, al ) + 1 = (d − 1) (al − 1) trở đi là có thể
biểu diễn dưới dạng αal + hd với 0 ≤ α < d, h ≥ 0. Như vậy

ja k a
1

l−1

− l + 1 d + (d − 1) (al − 1)
j a2d k  a d

1
l−1
<
− l + 1 + (d − 1) (al − 1) .
2
d

g (a1 , . . . , al ) <

Vì tập hợp là độc lập nên 1 ≤ d ≤
ta có
g (a1 , . . . , al ) <

và nếu d =

ja k
1


2

ja k
1

2

ja k
1

2

ja k
(thực tế là d ≤ 1 ). Do đó, nếu d = 1
l

(al − l + 1) ≤

ja k
1

2

(al − l) ,

thì

g (a1 , . . . , al ) < al−1 −

ja k

1

l+

ja k
1

+

ja k
1

2
2
j a2 k
1
≤ al−1 +
(al − l) − al + 1
2
ja k
1
(al − l) .
≤
2

Khi đó dẫn đến g (a1 , . . . , al ) <

ja k
1


2

al −

ja k
1

2

− al + 1

ja k
1
(al − l) với bất kỳ 1 ≤ d ≤
.
2

Ngoài các kết quả về chặn trên cho số Frobenius cịn có một số kết quả về
chặn dưới. Chúng tôi phát biểu dưới đây một số kết quả như vậy.
Định lý 1.3.11 (Hujter [10]). Cho k là số nguyên cố định. Ta có các bất đẳng
thức sau
1 ≥ lim inf

g (a1 , a2 , . . . , ak )

min

t→∞ a1 ,...,ak ≥t

1+


(k − 1) (min aj )

>

1
(k − 1)

k−1
.
ke

Định lý 1.3.12 (Hujter [10]). Cho a1 , . . . , ak là các số nguyên sao cho (a1 , . . . , ak ) =
1. Khi đó


k
X
g (a1 , . . . , ak ) ≥

k−1
k

1

((k − 1)!a1 a2 . . . ak ) k−1 −

ai .

i=1


Định lý 1.3.13 (Killingbergtrø [11]). Cho a1 , . . . , ak là các số nguyên sao cho
(a1 , . . . , ak ) = 1. Khi đó
g (a1 , . . . , ak ) ≥ ((k

1
− 1)!a1 a2 . . . ak ) k−1

−

k
X
i=1

10

ai .


Định lý 1.3.14 (Vizvári [23]). Cho a1 < aj với j = 2, . . . , k và cho cj , dj là các
số tự nhiên sao cho aj = cj a1 + dj , trong đó 1 ≤ dj ≤ a1 và
g (a1 , . . . , ak ) ≥

cj
c∗
. Khi đó
=
min
d∗ 2≤j≤k dj


c∗ 2 c∗
a − a1 − 1.
d∗ 1 d∗

Định lý 1.3.15 (Boros [2]). Cho aj , cj , c∗ và d∗ với aj = cj a1 + dj , trong đó
1 ≤ dj ≤ a1 và

cj
c∗
. Khi đó
=
min
d∗ 2≤j≤k dj


g (a1 , . . . , ak ) ≥

d (a1 − 1) c∗
a1 + a1 d − a1 − d
d∗



trong đó d = (d2 , . . . , dk ) .

1.3.2

Công thức số Frobenius của cấp số cộng

Trong mục này luận văn sẽ trình bày một số cơng thức tường minh cho số

Frobenius của một cấp số cộng tùy ý. Trước hết là công thức của số Frobenius
cho các số nguyên dương liên tiếp.
Định lý 1.3.16 (Brauer [3]). Cho a là số nguyên dương. Khi đó
j a − 2 k

g (a, a + 1, . . . , a + l − 1) =

l−1

+ 1 a − 1.

Dãy số a1 , . . . , ak được gọi là cấp số cộng nếu ai+1 = ai + d với i = 1, . . . , k − 1
với d là số nguyên dương.
Định lý 1.3.16 được mở rộng cho cấp số cộng tổng quát bởi Roberts [17].
Định lý 1.3.17. [17] Cho a, d và s là các số nguyên dương với (a, d) = 1, ta có

j a − 2 k
g (a, a + d, . . . , a + sd) =

Chứng minh. Cho yi =

s
P

s

+ 1 a + (d − 1) (a − 1) − 1.

xj với i = 0, . . . , s. Rõ ràng rằng số nguyên L được


j=i

biểu diễn bởi

s
P

(a + id)xi nếu và chỉ nếu

i=a

L = ay0 + d (y1 + · · · + ys ) ,

với y0 ≥ ... ≥ ys ≥ 0. Bây giờ với một y0 cho trước, các số nguyên có thể biểu
diễn được dưới dạng y1 + ... + ys , với y0 ≥ ... ≥ ys ≥ 0 chính là các số nguyên z
sao cho 0 ≤ z ≤ sy0 . Vì vậy L có thể biểu diễn bởi a, a + d, ..., a + sd khi và chỉ
khi L = ay + dz với 0 ≤ z ≤ sy .

11


Selmer mở rộng Định lý 1.3.17 như sau.
Định lý 1.3.18 (Selmer [21]). Cho a, h, d và m là các số nguyên dương với
(a, d) = 1 ta có
ja − 2k
g (a, ha + d, ha + 2d, . . . , ha + md) = ha

1.4

+ a (h − 1) + d (a − 1) .


m

Số Frobenius khi k = 3

Trái ngược với trường hợp k = 2, việc tính tốn cơng thức cho g (a1 , a2 , a3 )
hóa ra khó hơn nhiều. Curtis [6] chứng minh rằng, theo một nghĩa nào đó, khơng
thể tìm được một công thức tường minh dạng đa thức cho số Frobenius của tập
3 số.
Định lý 1.4.1. [6] Không tồn tại tập hữu hạn các đa thức 3 biến h1 , h2 , h3 có
tính chất: với mỗi bộ giá trị của a1 , a2 , a3 tồn tại chỉ số i sao cho g(a1 , a2 , a3 ) =
hi (a1 , a2 , a3 ).
Áp dụng các định lý về chặn cho các số Frobenius trong trường hợp tổng
quát trong Mục 1.2 tất nhiên chúng ta sẽ thu được các chặn cho số Frobenius
của tập 3 số. Trong phần còn lại của Mục này luận văn tập trung vào việc giới
thiệu một số kết quả cho phép tính số Frobenius cho các bộ 3 số cụ thể.
Định lý 1.4.2 (Oiu và Niu [15]). Cho (a1 , a2 ) = d, a1 = a01 d, a2 = a02 d sao cho tồn
tại các số nguyên x1 , x2 ≥ 0 với a3 = x1 a01 + x2 a02 . Khi đó
g (a1 , a2 , a3 ) =

a1 a2
− a1 − a2 + (d − 1) a3 .
d

Ví dụ. Cho các số 10, 15, 17 khi đó ta có (10, 15) = 5, 10 = 2.5, 15 = 3.5 và
tồn tại cặp số 1, 5 để cho 17 = 1.2 + 5.3 khi đó ta được:
g (10, 15, 17) =

Định lý 1.4.3 (Roberts [18]).


g (a1 , a2 , a3 ) ≤a1

10.15
− 10 − 15 + (5 − 1).17 = 73.
5

a) Nếu (a3 − a1 , a2 − a1 ) = 1 thì



a3 − a2 − 2 +

a1
a3 − a1

+ (a2 − a1 − 1) (a3 − a1 − 1)

+ a1 + a2 + a3 ;

b) Nếu a, j > 2 là các số nguyên thì
 j k
a+1

a + (j − 3)a
a ≡ −1 mod j; a ≥ j 2 − 5j + 3
j
j k
.
g (a, a + 1, a + j) =
a+1


(a + j) + (j − 3)a a ≡ −1 mod j; a ≥ j 2 − 4j + 2
j

12


c) 0 < a < b và m là các số nguyên sao cho (a, b) = 1, m ≥ 2 thì

j m k
g (m.m + a, m + b) ≤ m b − 2 +

b

+ (a − 1) (b − 1) .

Định lý 1.4.4 (Byrnes [5]). Cho a1 < a2 < a3 với a2 ≡ 1 mod a1 . Khi đó

a1 a2 − (a1 +a2 ) a3 ≤ ja2




a1 − m


g (a1 , a2 , a3 ) =

a3






a3



+ (m − 1)a2 − a1 (j − m)a2 < a3 ≤ ja2
j



j
a1 − m − j
+ (j − 1)a2 − a1 a2
(j − m) ≤ a3 < (j − m)a2
j
a1 − m + j

Trong đó j và m thõa mãn a3 ≡ j mod a1 ; 0 ≤ j < a1 và (nếu j 6= 0)
a1 ≡ m mod j; 1 ≤ m ≤ j .
Định lý 1.4.5 (Selmer [21]). Nếu a1 , a2 , a3 là độc lập và đôi một nguyên tố cùng
nhau thì
g (a1 , a2 , a3 ) ≤ max {(s − 1) a2 + (q − 1) a3 , (r − 1) a2 + qa3 } − a1 ,

trong đó s được xác định bởi a3 ≡ sa2 mod a1 ; 1 < s < a1 , q và r được xác định bởi
a1 = qs + r, 0 < r < s. Hơn nữa, nếu a2 ≥ t (q + 1) trong đó a3 = sa2 − ta1 , t > 0
thì
g (a1 , a2 , a3 ) = max {(s − 1) a2 + (q − 1) a3 , (r − 1) a2 + qa3 } − a1 .


Định lý 1.4.6 (Alfonsín [16]). Cho 0 < w1 < a3 và 0 < w2 < a3 là số nguyên
duy nhất sao cho a1 w1 ≡ a2 mod a3 và a2 w2 ≡ −a1 mod a3 . Gọi r1 , r2 là các số
nguyên dương lớn nhất sao cho −a3 + r1 w1 < 0 và a3 − w2 r2 > 0.
(a) g (a1 , a2 , a3 ) ≤ max {a1 (a3 − r1 w1 ) + a2 (r1 + 1) , a1 w1 + a2 r1 }
− a1 − a2 − a3 .
(b) g (a1 , a2 , a3 ) ≤ max {a1 + a2 (a3 + (1 − r2 ) w2 ) , a1 r2 + a2 w2 }
− a1 − a2 − a3 .

Các chặn trên trong Định lý 1.4.6 nói chung khơng chặt nhưng có những
trường hợp một trong số chúng (hoặc cả hai) đưa ra được giá trị gần đúng với
g (a1 , a2 , a3 ). Điều này được minh họa ở hai ví dụ sau.
Ví dụ 1.4.7. Cho a1 = 4, a2 = 7, a3 = 9. Ta có w1 = 4, w2 = 2, r1 = 2 và r2 = 4
Khi đó
(
g (4, 7, 9) ≤

max {25, 30} − 20
= 10.
max {18, 30} − 20

13


Ví dụ 1.4.8. Cho a1 = 5, a2 = 14, a3 = 31. Ta có w1 = 11, w2 = 2, r1 = 2 và r2 = 15
Khi đó
(
g (5, 14, 31) ≤

max {87, 83} − 50 = 37 = g (5, 14, 31)

.
max {47, 103} − 50 = 87

Định lý 1.4.9 (Hofmeister [9]). Cho a1 , a2 , a3 là các số nguyên dương đôi một
nguyên tố cùng nhau với a1 ≥ 4 và a1 < a2 , a3 . Gọi j, k, m là các số nguyên dương
được xác định bởi a3 ≡ ja2 mod a1 , a1 = kj + m. Khi đó
(
g (a1 , a2 , a3 ) = −a1 +

(m − 1) a2 + ka3

(j − m) a2 ≤ a3

(j − 1) a2 + (k − 1) a3

(j − m) a2 > a3 ≥ a2

Lưu ý rằng định lí trên khơng xét trường hợp a3 < a2

j − m

j − m
k+1

.

k+1

.


Định lý dưới đây được chứng minh sử dụng các kết quả sâu sắc về chuỗi
Hilbert trong Đại số giao hoán.
Định lý 1.4.10. [7, 16] Cho a1 , a2 , a3 là các số nguyên dương đôi một nguyên
tố cùng nhau và {i, j, q} = {1, 2, 3}. Khi đó

3
X




max {Li ai + xjq aq , Lj aj + xiq aq } −
ak
nếu xij > 0, ∀i, j


k=1

g (a1 , a2 , a3 ) =






Lj aj + Li ai −

3
X


ak

nếu xij = 0

k=1

trong đó L1 , L2 , L3 là các số nguyên dương nhỏ nhất sao cho tồn tại các số nguyên
xij ≥ 0, 1 ≤ i, j ≤ 3, i 6= j với tính chất
L1 a1 = x12 a2 + x13 a3 ,
L2 a2 = x21 a1 + x23 a3 ,
L3 a3 = x31 a1 + x32 a2 .

14


Chương 2

Thuật tốn tính số Frobenius
và ứng dụng
Trong chương này ta tìm hiểu về một thuật tốn để tính số Frobenius
c a ra bi J. Răodseth [19]. õy l mt thuật tốn rất hiệu quả để tính
số Frobenius của 3 số nguyên dương. Dựa trên thuật toán này, các tác giả M.
Lepilov, J. O’Rourke, and I. Swanson [13] đã tìm được công thức tường minh
cho số Frobenius của 3 số chính phương liên tiếp cũng như là của 3 số lập phương
liên tiếp. Sau khi trình bày thuật tốn của Răodseth, lun vn s trỡnh by chng
minh ca M. Lepilov, J. O’Rourke, and I. Swanson cho số Frobenius của 3 s
chớnh phng liờn tip.

2.1


Thut toỏn Ră
odseth

Cho a, b, c l các số nguyên dương nguyên tố cùng nhau. Nhắc lại ký hiệu
số Frobenius g(a, b, c) là số nguyên dương lớn nhất không biểu diễn được như
một tổ hợp của a, b, c với các hệ số khơng âm. Ngồi ra ta cũng quan tâm đến
số n(a, b, c) là số các số nguyên không âm không biểu diễn được như là một tổ
hợp của a, b, c.
Đối với thừa số chung dương d của a và b chúng ta có cơng thức truy hồi
của Johnson:


a b
, , c + c (d − 1) .
(2.2)
g (a, b, c) = d.g
d d

Tương tự ta có cơng thức truy hồi cho n(a, b, c)


n (a, b, c) = d.n

a b
, ,c
d d

+

1

(c − 1) (d − 1) .
2

(2.3)

Do vậy sẽ khơng có vấn đề gì xảy ra khi ta coi a và b là hai nguyên tố cùng
nhau.

15


Thut toỏn Răodseth c bt u nh sau. Cho s0 được xác định bởi công
thức
bs0 ≡ c (moda) , 0 ≤ s0 < a.

(2.4)

Nếu s0 = 0 thì c sẽ phụ thuộc vào a nên ta có thể bỏ qua trường hợp này.
Giả sử s0 6= 0. Ta sử dụng thuật toán Euclid
a =s−1 = q1 s0 − s1 , 0 ≤ s1 < s0
s0 = q2 s1 − s2 , 0 ≤ s2 < s1
s1 = q3 s2 − s3 , 0 ≤ s3 < s2
...
sm−2 = qm sm−1 − sm , 0 ≤ sm < sm−1
sm−1 = qm+1 sm , 0 = sm+1 < sm

(2.5)

Nếu s0 = 0, ta đặt m = −1. Ta cũng xác định số nguyên Pi bởi P−1 = 0, P0 =
1 và

Pi+1 = qi+1 Pi − Pi−1 , i = 0, 1, . . . , m.

(2.6)

s−1
= ∞ và coi bất đẳng thức x < ∞ có nghĩa. Từ
P−1
qi ≥ 2 sử dụng quy nạp và (2.6) ta chứng minh được Pi+1 > Pi . Do đó

Ta viết theo quy ước

0=

sm
s0
s−1
sm+1
<
< ··· <
<
= ∞,
Pm+1
Pm
P0
P−1

và sẽ có một số nguyên duy nhất v, −1 ≤ v ≤ m thõa mãn
sv+1
c
sv

≤ <
.
Pv+1
b
Pv

(2.7)

Cơng thức tính g(a, b, c) được đưa ra ở Định lý 2.1.1 dưới đây. Trong trường
hợp v = 0 công thức (2.8) được đưa ra bởi Hofmeister:
Định lý 2.1.1. [19] Cho a, b, c là các số nguyên dương, trong đó a và b là các
số nguyên tố cùng nhau. Khi đó
g (a, b, c) = −a + b (sv − 1) + c (Pv+1 − 1) − min {bsv+1 , cPv } ,

(2.8)

trong đó v là số nguyên duy nhất được xác nh (2.7).
Vớ d 2.1.2. S dng thut toỏn Răodseth tim số Frobenius cho ba số 121, 144, 169
Ta có s0 = 81 và
a = q1 s0 − s1 , 0 ≤ s1 < s0 ⇔ 121 = 81q1 − s1 ⇒ q1 = 2, s1 = 41
s0 = q2 s1 − s2 , 0 ≤ s2 < s1 ⇔ 81 = 41q2 − s2 ⇒ q2 = 2, s2 = 1

16


sau đó ta có
p−1 = 0, p0 = 1
p1 = q1 p0 − p−1 = 2.1 − 0 = 2
p2 = q2 p1 − p0 = 2.2 − 1 = 3


và

s2
1
169
41
s1
= ≤
<
= .
p2
3
144
3
p1

Khi đó thì
g (121, 144, 169) = −121 + 144 (41 − 1) + 169 (3 − 1) − min {144.1, 169.2}
= −121 + 5760 + 338 − 144 = 5833

Vậy g (121, 144, 169) = 5833.
Ngoài ra, thuật tốn trên cũng giúp tính được số n(a, b, c) như trong Định lý
2.1.3 dưới đây. Trong trường hợp v = 0 công thức (2.9) được đưa ra bởi Selmer:
Định lý 2.1.3. [19] Với các kí hiệu như ở Định lý 2.1.1, ta có
n
1

1
n(a, b, c) =
1 − a + b(sv − sv+1 − 1) + c(Pv+1 − 1) + sv+1 (Pv+1 − Pv ) (bsv − cPv ) .

2
a

o

(2.9)
Theo thảo luận phía trên, khơng làm mất tính tổng qt ta hồn tồn có
thể giả sử a, b, c là độc lập và là đôi một nguyên tố cùng nhau. Trong trường hợp
này 0 ≤ v < m và đẳng thức (2.7) không thể xảy ra.
Chứng minh. Ta đặt
Ri =

1
(bsi − cPi ) ,
a

i = −1, . . . , m.

(2.10)

Theo (2.5) và (2.6), Ri thõa mãn phương trình tuyến tính sau:
Ri+1 = qi+1 Ri − Ri−1 ,

i = 0, . . . , m.

(2.11)

R−1 = b.

(2.12)


với các điều kiện ban đầu là
R0 =

1
(bs0 − c) ,
a

Do (2.4) nên R0 là số nguyên, và cũng vì R−1 là số nguyên nên (2.11) cho
thấy rằng tất cả các Ri là số nguyên. Hơn nữa, vì Pi − Pi+1 < 0 < si − si+1 và ta
sử dụng (2.7) nên ta có:
Rm+1 < Rm < · · · < Rv+1 ≤ 0 < Rv < · · · < R−1 .

17

(2.13)