Luận văn Thạc sĩ Toán học: Định lí không điểm tổ hợp và một vài vận dụng

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

VŨ LAN DUNG

ĐỊNH LÍ KHÔNG ĐIỂM TỔ HỢP

VÀ MỘT VÀI VẬN 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

Thái Nguyên - 2015

Mục lục

Lời cảm ơn 3

Lời nói đầu 4

6 1 Định lý không điểm tổ hợp

6 1.1 Định lý không điểm tổ hợp . . . . . . . . . . . . . . . . .

6 1.1.1 Định lý không điểm Hilbert . . . . . . . . . . . .

8 1.1.2 Định lý không điểm tổ hợp . . . . . . . . . . . . .

11 1.1.3 Vận dụng . . . . . . . . . . . . . . . . . . . . . .

13 1.2 Khái niệm đồ thị . . . . . . . . . . . . . . . . . . . . . .

13 1.2.1 Đồ thị và đồ thị con . . . . . . . . . . . . . . . .

17 1.2.2 Bài toán tô màu . . . . . . . . . . . . . . . . . .

22 2 Tổng thu hẹp-phương pháp đa thức

22 2.1 Phương pháp đa thức . . . . . . . . . . . . . . . . . . . .

24 2.2 Một vài ví dụ liên quan . . . . . . . . . . . . . . . . . . .

28 2.3 Điều kiện |A + B| = |A| + |B| − 1 . . . . . . . . . . . . .

30 3 Vận dụng

30 3.1 Chứng minh Định lý Fermat, Định lý Wilson . . . . . . .

1

3.2 Vận dụng tổng tập hợp trong phương trình nghiệm nguyên 33

3.2.1 Một vài phương trình vô nghiệm . . . . . . . . . . 34

3.2.2 Phương trình có nghiệm . . . . . . . . . . . . . . 36

3.2.3 Điều kiện tham số của phương trình . . . . . . . 36

3.3 Phương pháp đa thức qua nghiệm . . . . . . . . . . . . . 39

3.3.1 Chứng minh số vô tỷ . . . . . . . . . . . . . . . . 39

3.3.2 Bài toán Waring về đa thức . . . . . . . . . . . . 43

3.4 Phương pháp đa thức trong bất đẳng thức . . . . . . . . 46

Kết luận 50

2

Tài liệu tham khảo 51

Lời cảm ơn

Luận văn này được hoàn thành tại trường Đại học Khoa học - Đại

học Thái Nguyên. Tác giả xin bày tỏ lòng biết ơn sâu sắc với PGS.TS

Đàm Văn Nhỉ, người thầy đã trực tiếp hướng dẫn tận tình và động viên

tác giả trong suốt thời gian nghiên cứu vừa qua.

Xin chân thành cảm ơn tới các thầy, cô giáo trong Bộ môn Toán -

Tin, Phòng Đào tạo Khoa học và Quan hệ quốc tế, các bạn học viên lớp

Cao học Toán K7D trường Đại học Khoa học - Đại học Thái Nguyên, và

các bạn đồng nghiệp đã tạo điều kiện thuận lợi, động viên tác giả trong

quá trình học tập và nghiên cứu tại trường.

Tác giả cũng xin bày tỏ lòng biết ơn sâu sắc tới gia đình và người

thân luôn khuyến khích, động viên tác giả trong suốt quá trình học tập

và làm luận văn.

Mặc dù có nhiều cố gắng nhưng luận văn khó tránh khỏi những thiếu

sót và hạn chế. Tác giả mong nhận được những ý kiến đóng góp quý báu

của các thầy cô và bạn đọc để luận văn được hoàn thiện hơn.

Xin chân thành cảm ơn!

Thái Nguyên, 2015 Vũ Lan Dung

Học viên Cao học Toán K7D,

3

Trường ĐH Khoa học - ĐH Thái Nguyên

Lời nói đầu

Mục đích của luận văn là chứng minh lại một số định lí nổi tiếng về

đa thức nhiều biến với hệ số trên một trường như Định lý không điểm

của Hilbert, Định lý không điểm tổ hợp của Noga Alon và một số vận

dụng phương pháp đa thức, đồng thời vận dụng các định lí này để nghiên

cứu một số vấn đề trong tổ hợp và trong số học. Đây là kết quả mới còn

có thể tiếp tục phát triển thêm theo hướng nghiên cứu này. Luận văn

được chia thành ba chương với những nội dung chính sau đây:

Chương 1 của luận văn trình bày chứng minh Định lý không điểm

của Hilbert, Định lý không điểm tổ hợp. Thực chất định lí không điểm

tổ hợp là một dạng mở rộng của định lí không điểm Hilbert, định lí này

cho một mô tả các đa thức triệt tiêu trên một tập điểm có dạng tích

Descartes. Phần cuối chương I trình bày ứng dụng của định lí này vào

các bài toán tô màu đồ thị.

Chương 2 của luận văn trình bày phương pháp đa thức, tổng thu

hẹp các thặng dư và một vài ví dụ liên quan.

Chương 3 tập trung trình bày một số vận dụng các kết quả đạt

được trong toán sơ cấp như chứng minh các kết quả cổ điển của số học

đó là định lí Fecmat, Wilson, bài toán Waring (cho đa thức), giải một

số phương trình nghiệm nguyên, chứng minh số vô tỉ, chứng minh một

số bất đẳng thức trong toán phổ thông.

Để hoàn thành luận văn này, em xin bày tỏ lòng biết ơn chân

4

thành tới PGS.TS. Đàm Văn Nhỉ đã hướng dẫn, chỉ bảo tận tình em

trong suốt quá trình thực hiện luận văn này. Cuối cùng em xin bày tỏ

lòng biết ơn sâu sắc tới các thầy cô trong Khoa Toán, Trường Đại học

Khoa học, Đại học Thái Nguyên cùng toàn thể bạn bè trong lớp đã giúp

đỡ, đóng góp ý kiến trong quá trình nghiên cứu, học tập và hoàn thành

luận văn.

Hải Dương, ngày 25 tháng 5 năm 2015

5

Học viên: Vũ Lan Dung

Chương 1

Định lý không điểm tổ hợp

1.1 Định lý không điểm tổ hợp

1.1.1 Định lý không điểm Hilbert

Khái niệm vành đa thức nhiều biến trên trường K đã được trình bày

trong nhiều giáo trình đại số, chẳng hạn [1]. Do vậy, chúng tôi không

nhắc lại ở đây. Một trường K thỏa mãn điều kiện mọi đa thức một biến

bậc dương trên K đều có nghiệm trong K được gọi là trường đóng đại số, chẳng hạn trường số phức C là trường đóng đại số, còn trường số thực R không là trường đóng đại số.

Để trình bày Định lý Hilbert về không điểm, ta sẽ vận dụng kết quả,

không chứng minh, sau đây.

gi(x1, . . . , xn) = 0   không Bổ đề 1.1.1. Nếu hệ phương trình đa thức

 i = 1, 2, . . . , r

r (cid:88)

có nghiệm thì tồn tại các đa thức ai(x1, . . . , xn) ∈ C[x1, . . . , xn] thỏa mãn

i=1

ai(x1, . . . , xn)gi(x1, . . . , xn) = 1.

fi(x1, . . . , xn) = 0   Xét hệ các phương trình đa thức Giả sử đa thức

6

 i = 1, 2, . . . , r.

g(x1, . . . , xn) (cid:54)= 0 thỏa mãn g(ξ1, ξ2, . . . , ξn) = 0 khi (ξ1, ξ2, . . . , ξn) là

fi(x1, . . . , xn) = 0   nghiệm của hệ Khi đó ta có kết quả sau:

 i = 1, 2, . . . , r.

Định lý 1.1.2. [Hilbert’s zero-theorem] Giả sử g(x1, . . . , xn) (cid:54)= 0 thỏa mãn g(ξ1, ξ2, . . . , ξn) = 0 khi (ξ1, ξ2, . . . , ξn) là nghiệm của hệ

fi(x1, . . . , xn) = 0  

 i = 1, 2, . . . , r.

r (cid:80) i=1

Khi đó có các đa thức bi(x1, . . . , xn) ∈ C[x1, . . . , xn] và số nguyên dương s thỏa mãn g(x1, . . . , xn)s = bi(x1, . . . , xn)fi(x1, . . . , xn).

Chứng minh. Ký hiệu z là biến mới. Coi các đa thức fi(x1, . . . , xn) như là các phần tử thuộc vành đa thức C[x1, . . . , xn, z]. Xét hệ phương trình đa thức 

fi(x) = fi(x1, . . . , xn) = 0

i = 1, 2, . . . , r

zg(x) − 1 = zg(x1, . . . , xn) − 1 = 0.  

r (cid:88)

Hệ này vô nghiệm. Theo Bổ đề 1.1.1, tồn tại các ai(x1, . . . , xn, z) và b(x1, . . . , xn, z) thuộc vành C[x1, . . . , xn, z] để

i=1

ai(x1, . . . , xn, z)fi(x) + b(x1, . . . , xn, z)(zg(x) − 1) = 1.

r (cid:88)

Đồng nhất thức này vẫn đúng khi ta thay z qua . Từ đây suy ra 1 g(x)

i=1

(cid:1)fi(x) = 1. (cid:0)x1, . . . , xn, ai 1 g(x)

r (cid:80) i=1

7

bi(x1, . . . , xn)fi(x1, . . . , xn). Nhân hai vế với một lũy thừa thích hợp của g(x) ta nhận được hệ thức g(x1, . . . , xn)s =

1.1.2 Định lý không điểm tổ hợp

Chúng ta sẽ chứng minh hai định lý của Noga Alon, giáo sư tại Tel

Aviv University, gọi là Combinatorial Nullstellensatz, được sử dụng nhiều

trong Tổ hợp, Lý thuyết số, Đồ thị và Tô màu.

Bổ đề 1.1.3. Giả thiết trường K có char(K) = 0. Cho đa thức khác

không g(x) = g(x1, . . . , xn) ∈ K[x] ta ký hiệu ti = degi g(x) là bậc của g(x) theo biến xi, i = 1, . . . , n. Ký hiệu các tập con Si ⊂ K thỏa mãn |Si| (cid:62) ti + 1 với i = 1, . . . , n. Nếu g(α) = 0 thỏa mãn cho mọi (α) = (α1, . . . , αn) ∈ S1 × S2 × · · · × Sn thì g(x) ≡ 0.

Chứng minh. Ta chứng minh kết luận bằng phương pháp quy nạp theo

n. Với n = 1, ta có đa thức một biến g(x1) bậc t1 triệt tiêu trên tập S1 với nhiều hơn t1 phần tử. Do vậy g(x1) ≡ 0 theo Định lý Bezout. Giả sử kết luận đúng cho tất cả các đa thức ít hơn n biến. Biểu diễn lại đa

tn(cid:88)

thức g(x) thành đa thức của biến xn như sau:

n ∈ K[x1, . . . , xn−1][xn].

j=1

g(x1, . . . , xn) = gj(x1, . . . , xn−1)xj

Với mỗi bộ (γ) = (γ1, . . . , γn−1) ∈ S1 × S2 × · · · × Sn−1 cố định ta có

n ≡ 0 trên tập Sn. Từ đó suy ra gj(γ) = 0 với mọi

tn(cid:80) j=0

g(γ, xn) = gj(γ)xj

j = 0, 1, . . . , tn và mọi (γ) ∈ S1 × S2 × · · · × Sn−1. Theo giả thiết quy nạp ta có gj(x1, . . . , xn−1) ≡ 0 với mọi j = 0, 1, . . . , tn. Như vậy g(x) ≡ 0. Bổ đề đã được chứng minh.

Định lý 1.1.4. [Noga Alon] Giả thiết trường K có char(K) = 0. Cho

đa thức khác không g(x) = g(x1, . . . , xn) ∈ K[x]. Ký hiệu các tập con Si ⊂ K thỏa mãn |Si| (cid:62) 1 và pi(xi) = (cid:81) (xi − s) với i = 1, . . . , n. Nếu s∈Si

8

g(x) triệt tiêu tại mọi nghiệm chung của p1, . . . , pn thì tồn tại đa thức

n (cid:88)

q1, . . . , qn ∈ K[x1, . . . , xn] thỏa mãn deg qi (cid:54) deg g − deg pi để

i=1

g = qipi.

Chứng minh. Đặt ti = |Si| − 1 với i = 1, . . . , n. Theo giả thiết ta có g(α) = 0 với mọi (α) ∈ S1 × S2 × · · · × Sn. Biểu diễn lại đa thức

ti(cid:88)

i , aij ∈ Si, i = 1, . . . , n.

i −

j=0

s∈Si

(cid:89) pi(xi) = (xi − s) = xti+1 aijxj

i =

ti(cid:80) j=0

Do pi(s) = 0 nên sti+1 = aijsj, aij ∈ Si, i = 1, . . . , n. Như vậy xti+1

i trên Si với i = 1, . . . , n. Ký hiệu đa thức g∗(x) là đa thức nhận

ti(cid:80) j=0 được từ g(x) qua việc biểu diễn g(x) như là tổ hợp của các đơn thức

aijxj

i

i . Như vậy, đa thức nhận được sau khi

ti(cid:80) j=0

và lần lượt thay xti+1 bởi aijxj

n (cid:81) i=1

thay g∗(x) có bậc không quá ti đối với mỗi biến xi với i = 1, . . . , n và nhận được từ g(x) bởi việc trừ đi các tích dạng qipi, trong đó đa thức qi ∈ K[x1, . . . , xn] với deg qi (cid:54) deg g − deg pi. Qua những lần biến đổi, ta vẫn luôn luôn có g∗(α) = g(α) = 0 với mọi α ∈ Si. Theo Bổ đề 1.1.3,

n (cid:80) i=1

g∗ ≡ 0 và suy ra g = qipi.

Định lý 1.1.5. [Noga Alon] Giả thiết trường K có char(K) = 0. Cho

n (cid:81) i=1

ti, ti ∈ N. Giả thiết hệ số của đơn thức

đa thức khác không g(x) = g(x1, . . . , xn) ∈ K[x] với bậc deg g(x) = n (cid:80) xti i khác 0. Khi đó, nếu các i=1 tập con Si ⊂ K thỏa mãn |Si| (cid:62) ti + 1 với i = 1, 2, . . . , n, thì tồn tại α1 ∈ S1, . . . , αn ∈ Sn để g(α) (cid:54)= 0.

9

(xi − s), i = 1, . . . , n. Theo Định lý 1.1.4, tồn tại các đa thức Chứng minh. Ta chỉ cần chứng minh định lý cho trường hợp |Si| = ti + 1 với i = 1, 2, . . . , n. Giả sử kết luận trên không đúng. Xét các đa thức pi(xi) = (cid:81) s∈Si

n (cid:80) i=1

n (cid:80) i=1

q1, . . . , qn ∈ K[x1, . . . , xn] thỏa mãn deg qi (cid:54) ti −deg pi để g = qipi.

n (cid:81) i=1

Theo giả thiết, hệ số của xti i ở trong g(x) là khác 0 và kéo theo hệ

số của đơn thức như thế ở bên phải cũng khác 0. Hơn nữa, bậc của

qipi = qi (xi − s) không lớn hơn bậc của đa thức g(x). Nếu có một (cid:81) s∈Si

n (cid:80) i=1

đơn thức nào ở bên phải hệ thức g = qipi với bậc deg(g) thì đơn thức

i

n (cid:81) i=1

n (cid:80) i=1

đó phải chia hết cho xti+1 . Điều này kéo theo hệ số của qipi xti i ở

phải bằng 0. Điều mâu thuẫn này chỉ ra điều giả sử là sai. Định lý đã

được chứng minh.

n (cid:80) i=0

Giả thiết K = Zp với số nguyên tố p và các tập con khác rỗng S0, S1, . . . , Sn ⊂ K. Cho đa thức g(x) = g(x0, x1, . . . , xn) ∈ K[x]. Định nghĩa (cid:76) Si = {s0 + s1 + · · · + sn|si ∈ Si, g(s0, s1, . . . , sn) (cid:54)= 0}.

n (cid:80) i=0

n (cid:81) i=0

ti − deg(g). Nếu hệ số của đơn thức Định lý 1.1.6. [Noga Alon] Giả sử |Si| = ti + 1 với i = 0, 1, . . . , n và xti định nghĩa m = i trong đa

n (cid:80) i=0

Si| =

thức (x0 + x1 + · · · + xn)mg(x0, x1, . . . , xn) mà khác 0 thì | (cid:76) |{s0 + s1 + · · · + sn|si ∈ Si, g(s0, s1, . . . , sn) (cid:54)= 0}| (cid:62) m + 1.

n (cid:80) i=0

Chứng minh. Giả sử kết luận là sai và ký hiệu E là một tập gồm m phần tử (không nhất thiết phải phân biệt) thuộc Zp sao cho E chứa tập (cid:76) Si = {s0 + s1 + · · · + sn|si ∈ Si, g(s0, s1, . . . , sn) (cid:54)= 0}. Giả sử đa

thức h = h(x0, x1, . . . , xn) được định nghĩa như sau:

e∈E

(cid:89) h(x0, x1, . . . , xn) = (x0 + x1 + · · · + xn − e)g(x0, x1, . . . , xn).

10

Theo định nghĩa h(s0, s1, . . . , sn) = 0 thỏa mãn với mọi (s0, s1, . . . , sn) ∈ (S0, S1, . . . , Sn) do bởi hoặc g(s0, s1, . . . , sn) = 0 hoặc (s0 + s1 + · · · + sn − e) = 0 với mọi (s0, s1, . . . , sn) ∈ (S0, S1, . . . , Sn). Vì deg(h) = m +

n thuộc h(x) cũng chính là

0 . . . xtn

n (cid:80) i=0

deg(g) = ti nên hệ số của đơn thức xt0

hệ số của đơn thức ấy thuộc đa thức (x0 +x1 +· · ·+xn)mg(x0, x1, . . . , xn) khác không theo giả thiết. Theo Định lý 1.1.5, tồn tại s0 ∈ S0, . . . , sn ∈ Sn để h(s0, s1, . . . , sn) (cid:54)= 0 mâu thuẫn với kết quả h(s0, s1, . . . , sn) = 0 thỏa mãn với mọi (s0, s1, . . . , sn) ∈ (S0, S1, . . . , Sn). Như vậy, điều giả sử là sai.

1.1.3 Vận dụng

Vận dụng đầu tiên là việc chứng minh phỏng đoán của Artin vào năm

1934 và được giải quyết bởi Chevalley và được Waring mở rộng đều vào

năm 1935.

m (cid:80) i=1

Định lý 1.1.7. Giả sử p là số nguyên tố và các đa thức Pi thuộc vành Zp[x] = Zp[x1, . . . , xn] với i = 1, . . . , m. Nếu n > deg Pi và các đa

thức Pi có chung một không điểm (α) thì chúng còn có chung một không điểm khác nữa.

m (cid:89)

n (cid:89)

Chứng minh. Giả sử kết luận trên không đúng. Xét đa thức

i

i=1

j=1

a∈Zp,a(cid:54)=αj

(cid:89) g = g(x) = [1 − P p−1 ] − δ (xj − a)

m (cid:81) i=1

n (cid:81) j=1

với δ được chọn để g(α) = 0. Chú ý rằng, g(α) = 0 khi và chỉ khi 1 0 = [1 − 0] − δ . Ta (αj − a) hay δ = (cid:81) a∈Zp,a(cid:54)=αj (αj − a)

p và (γ) (cid:54)= (α) có

n (cid:81) j=1 m (cid:81) i=1

cũng chú ý rằng, khi (γ) ∈ Zn (cid:81) a∈Zp,a(cid:54)=αj [1 − Pi(γ)p−1] = 0 và

p . Lấy

n (cid:81) j=1

δ (γj − a) = 0 và như vậy g(γ) = 0, (∗), với mọi (γ) ∈ Zn (cid:81) a∈Zp

n (cid:81) i=1

ti = p−1 với mọi i và chú ý rằng, hệ số của xti i trong g(x) bằng −δ (cid:54)= 0

m (cid:80) i=1

m (cid:81) i=1

11

] bằng (p−1) vì bậc toàn thể của đa thức deg Pi < (p−1)n. [1−P p−1 i

Như vậy, theo Định lý 1.1.5 với việc chọn Sj = Zp, j = 1, 2, . . . , n, có b1, . . . , bn ∈ Zp để g(b1, . . . , bn) (cid:54)= 0, mâu thuẫn với (∗). Điều mâu thuẫn này chỉ ra điều giả sử là sai. Định lý đã được chứng minh.

Định lý dưới đây được Cauchy chứng minh vào năm 1813 và áp dụng

nó để đưa ra một chứng minh mới cho một kết quả của Lagrange vào

năm 1770 về biểu diễn mỗi số tự nhiên thành tổng bốn số chính phương.

Davenport phát biểu lại kết quả như một tương tự mới của phỏng đoán

Khintchine.

Định lý 1.1.8. [Cauchy-Davenport] Với số nguyên tố p và hai tập con khác rỗng của Zp ta luôn luôn có bất đẳng thức

|A + B| (cid:62) min{p, |A| + |B| − 1}.

Chứng minh: Nếu A ∩ B = ∅ thì kết quả đúng. Xét A ∩ B (cid:54)= ∅. Nếu |A| + |B| > p thì giao giữa A và x \ B luôn khác rỗng cho mọi x ∈ Zp. Từ đây suy ra A + B = Zp và kết quả đúng. Xét trường hợp |A| + |B| (cid:54) p. Giả sử kết luận của định lý là sai. Khi đó |A + B| (cid:54) |A| + |B| − 2. Giả sử C là một tập con của Zp thỏa mãn A + B ⊂ C và |C| = |A| + |B| − 2. Định nghĩa đa thức g = g(x, y) = (cid:81) (x + y − c). Theo định nghĩa của c∈C C ta có g(a, b) = 0, (∗∗), với mọi a ∈ A, b ∈ B. Đặt t1 = |A| − 1 và t2 = |B| − 1. Chú ý rằng, hệ số của xt1yt2 trong đa thức g đúng bằng (cid:1) là khác 0 trong Zp vì |A| + |B| − 2 < p. Bởi vậy, theo Định (cid:0)|A|+|B|−2 |A|−1 lý 1.1.5 với n = 2, S1 = A, S2 = B có a ∈ A và b ∈ B để g(a, b) (cid:54)= 0, mâu thuẫn (∗∗). Điều mâu thuẫn này chỉ ra điều giả sử là sai. Định lý

12

đã được chứng minh.

1.2 Khái niệm đồ thị

1.2.1 Đồ thị và đồ thị con

Trước hết ta trình bày một số khái niệm cơ bản về lý thuyết đồ thị:

Đồ thị G là một tập gồm các đỉnh và các cạnh nối các đỉnh đó. Ta

thường kí hiệu G = (V, E), trong đó V là tập các đỉnh và E là tập các

cạnh.

Đồ thị G = (V, E) được gọi là đơn đồ thị vô hướng bao gồm V là

tập các đỉnh và E là tập các cặp không có thứ tự gồm hai phần tử khác

nhau của V gọi là các cạnh.

Đồ thị G = (V, E) được gọi là đa đồ thị vô hướng bao gồm V là tập

các đỉnh và E là họ các cặp không có thứ tự gồm hai phần tử khác nhau

của V gọi là các cạnh. Hai cạnh e1, e2 gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh.

Đồ thị G = (V, E) được gọi là đơn đồ thị có hướng bao gồm V là tập

các đỉnh và E là tập các cặp có thứ tự gồm hai phần tử khác nhau của

V gọi là các cung.

Đồ thị G = (V, E) được gọi là đa đồ thị có hướng bao gồm V là tập

các đỉnh và E là họ các cặp có thứ tự gồm hai phần tử khác nhau của

V gọi là các cung. Hai cung e1, e2 được gọi là cung lặp nếu chúng cùng tương ứng với một cặp đỉnh.

Giả sử u và v là hai đỉnh của đồ thị vô hướng G và e = (u, v) là cạnh

của đồ thị. Khi đó ta nói u và v kề nhau và e liên thuộc với u và v; u

và v là các đỉnh đầu của cạnh e.

Bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó.

Kí hiệu deg(v).

Giả sử u và v là hai đỉnh của đồ thị có hướng G và e = (u, v) là cung

13

của đồ thị. Khi đó ta nói u và v kề nhau và e đi ra khỏi u và đi vào v;

u là đỉnh đầu, v là đỉnh cuối của cạnh e.

Bán bậc ra (bán bậc vào) của đỉnh v trong đồ thị có hướng là số cung

ra khỏi nó (đi vào nó). Kí hiệu deg+(v), deg−(v).

Đường đi độ dài n từ đỉnh u đến đỉnh v trên đồ thị vô hướng G =

(V, E) là dãy x0, x1, . . . , xn. Trong đó u = x0, v = xn, (xi, xi+1) inE. Hay theo cạnh (x0, x1), (x1, x2), . . . , (xn−1, xn). Khi đó u gọi là đỉnh đầu, v gọi là đỉnh cuối của đường đi.

Đường đi có đỉnh đầu và đỉnh cuối trùng nhau gọi là chu trình. Đường

đi (hay chu trình) được gọi là đơn nếu nó không đi qua một cạnh nào

quá một lần.

Đường đi độ dài n từ đỉnh u đến đỉnh v trên đồ thị có hướng G =

(V, E) là dãy x0, x1, . . . , xn. Trong đó u = x0, v = xn, (xi, xi+1) inE. Hay theo cung (x0, x1), (x1, x2), . . . , (xn−1, xn).

Đồ thị vô hướng G = (V, E) được gọi là liên thông nếu luôn tìm được

đường đi giữa hai đỉnh bất kì của nó.

Đồ thị H = (W, F ) được gọi là đồ thị con của đồ thị G = (V, E) nếu

W ⊆ V và F ⊆ E.

Đồ thị đơn vô hướng n đỉnh được gọi là đồ thị đầy đủ nếu hai đỉnh

bất kì đều được nối với nhau bằng 1 cạnh. Kí hiệu Kn.

Đồ thị đơn vô hướng n đỉnh được gọi là đồ thị vòng nếu nó có duy

nhất một chu trình đơn đi qua tất cả các đỉnh. Kí hiệu Cn.

Đồ thị được gọi là đồ thị phẳng nếu ta có thể vẽ nó trên một mặt

phẳng mà các cạnh không giao nhau.

Một giả thuyết nổi tiếng của Berge và Sauer, được chứng minh bởi

Taskinov, khẳng định rằng mọi đồ thị đơn, chính quy bậc 4 đều chứa

một đồ thị con chính quy bậc 3. Khẳng định này dễ thấy là sai lầm cho

các đồ thị với nhiều cạnh, nhưng như trong [2] một cạnh bổ sung đủ để

14

đảm bảo một đồ thị con chính quy bậc 3 trong trường hợp tổng quát

hơn này là đúng. Điều sau từ trường hợp p = 3 như chỉ ra dưới đây, có

thể suy ra một cách nhanh chóng từ định lý 1.1.5.

Định lý 1.2.1. Cho p là một số nguyên tố bất kỳ, đồ thị vòng G = (V, E)

bất kì với bậc trung bình lớn hơn 2p − 2 và bậc cực đại lớn nhất 2p − 1

chứa một đồ thị con chính quy bậc p.

Chứng minh. Cho (av,e)v∈V,e∈E kí hiệu là ma trận liên thuộc của G được định nghĩa bởi av,e = 1 nếu v ∈ e và nếu không thì av,e = 0. Kết hợp mỗi cạnh e của G với một biến xe và xét đa thức

e∈E

v∈V

e∈E

 (cid:32) (cid:33)p−1 (cid:88) (cid:89) (cid:89) F = av,exe (1 − se),  − 1 −

trên GF (p). Lưu ý rằng bậc của F là |E|, vì bậc của tích đầu tiên nhiều

nhất là (p − 1)|V | < |E|, bởi giả thiết trên bậc trung bình của G. Ngoài ra, hệ số của (cid:81) xe trong F là (−1)|E|+1 (cid:54)= 0. Do đó, theo định lý 1.1.5, e∈E

có các giá trị xe ∈ {0, 1} sao cho F (xe : e ∈ E) (cid:54)= 0. Theo định nghĩa của F , véctơ trên (xe : e ∈ E) là khác véctơ không, vì đối với vector này F = 0. Ngoài ra (cid:80) av,exe bằng không mod p với mọi v vì nếu không F e∈E

sẽ triệt tiêu tại điểm này. Do đó, trong đồ thị con bao gồm tất cả các

cạnh e ∈ E mà xe = 1 các bậc chia hết p và vì bậc cực đại nhỏ hơn 2p tất cả các bậc dương chính xác bằng p.

Erdos và Sauer đã phát triển bài toán ước lượng số lượng tối đa các

cạnh trong một đơn đồ thị trên n đỉnh mà không chứa đồ thị con chính

quy bậc 3. Họ phỏng đoán rằng, với mọi số dương (cid:15) không vượt quá n1+(cid:15), với điều kiện n đủ lớn như một hàm của (cid:15). Điều này đã được chứng

minh bởi Pyber, bằng cách sử dụng Định lý 1.2.1. Ông đã chứng minh

rằng với đồ thị đơn bất kì bất kì n đỉnh với ít nhất 200n log n cạnh chứa

một đồ thị con với bậc cực đại là 5 và bậc trung bình nhỏ hơn 4. Theo

15

định lý 1.2.1, đồ thị con này chứa một đồ thị con chính quy bậc 3. Mặt

khác, Pyber , Rodl và Szemeredi đã chứng minh bằng lập luận xác suất

rằng có một đồ thị đơn n đỉnh với ít nhất Ω(n log log n) cạnh mà không

chứa đồ thị con chính quy bậc 3. Do đó, đánh giá của Pyber không phải

là tốt nhất.

Vận dụng Định lý 1.1.5 ta chứng minh các kết quả sau đây:

Mệnh đề 1.2.2. Cho p là một số nguyên tố và cho G = (V, E) là một

đồ thị trên tập |V | > d(p − 1) đỉnh. Khi đó, có một tập con khác rỗng U

của các đỉnh của G sao cho chỉ số clique của d đỉnh của G mà giao U

bằng 0 mod p.

Chứng minh. Với mỗi tập con I các đỉnh của G, cho K(I) kí hiệu là số

bản sao của Kd trong G mà chứa I. Kết hợp mỗi đỉnh v ∈ V với một biến xv và xét đa thức

v∈V

(cid:89) F = (1 − xv) − 1 + G,

p−1

trong đó  

i∈I

∅(cid:54)=I⊂V

(cid:88) (cid:89) G = (−1)|I|+1K(I) xi  

trên GF (p). Vì K(I) bằng không với mọi bản số I lớn hơn d, bậc của

(cid:54)= 0. Do đó, theo Định lý 1.1.5 xv trong F là (−1)|V | đa thức này là |V |, như bậc của G nhiều nhất là d(p − 1) < |V |. Ngoài ra, hệ số của (cid:81) v∈V

tồn tại xv ∈ {0, 1} sao cho F (xv : v ∈ V ) (cid:54)= 0. Vì F triệt tiêu trên tất cả các véctơ 0, suy ra không phải tất cả các số xv bằng không và do đó G(xv : v ∈ V ) (cid:54)= 1, theo Định lý nhỏ của Fermat suy ra

i∈I

∅(cid:54)=I⊂V

(cid:88) (cid:89) (−1)|I|+1K(I) xi ≡ 0( mod p)

16

Tuy nhiên, vế trái của đồng dư trên bằng số bản sao của Kd mà giao với tập U = {v : xv = 1}. Vì U khác rỗng nên mệnh đề đúng.

Ta kết thúc phần này với một kết quả hình học đơn giản, đã được

chứng minh để trả lời câu hỏi của Komjath. Kết quả này cũng là một

hệ quả đơn giản của Định lý 1.1.5.

Định lý 1.2.3. Cho H1, H2, . . . , Hm là họ các siêu phẳng trong Rn mà phủ tất cả các đỉnh của hình lập phương đơn vị {0, 1}n. Khi đó m (cid:62) n.

Chứng minh. Rõ ràng, ta có thể giả sử rằng các đỉnh không phủ là các

m (cid:89)

n (cid:89)

m (cid:89)

véctơ không. Đặt (ai, x) = bi là phương trình xác định Hi, trong đó x = (x1, x2, . . . , xn) và (a, b) là tích trong của hai véctơ a và b. Lưu ý rằng với mọi i, bi (cid:54)= 0 vì Hi không phủ gốc tọa độ. Giả sử khẳng định là sai và m < n, xét đa thức

j=1

i=1

i=1

P (x) = (−1)n+m+1 (xi − 1) − bj [(ai, x) − bi].

n (cid:81) i=1

Bậc của đa thức này rõ ràng bằng n và hệ số của trong đó là

m (cid:81) j=1

(−1)n+m+1 bj (cid:54)= 0. Do đó, theo Định lí 1.1.5 tồn tại điểm x ∈ {0, 1}n

sao cho P (x) (cid:54)= 0. Điểm này không phải tất cả là các véctơ không, như P

triệt tiêu trên nó và do đó nó là một vài đỉnh khác của hình lập phương.

Nhưng trong trường hợp này (ai, x) − bi = 0 với một vài i, suy ra P không triệt tiêu trên điểm này, mâu thuẫn.

1.2.2 Bài toán tô màu

Trước hết ta bắt đầu với một vài khái niệm cơ bản về tô màu đồ thị.

Tô màu đồ thị (graph coloring) là trường hợp đặc biệt của gán nhãn đồ

thị, mà trong đó mỗi đỉnh hay mỗi cạnh hay mỗi miền của đồ thị có thể

được gán bởi một màu hay một tập hợp các màu nào đó. Tô màu đồ thị

có thể là:

Tô màu đỉnh (vertex coloring) là gán cho mỗi đỉnh của đồ thị một

17

màu nào đó sao cho không có hai đỉnh nào liền kề lại trùng màu nhau;

Tô màu cạnh (edge coloring) là gán cho mỗi cạnh của đồ thị một màu

nào đó sao cho sao cho không có 2 cạnh nào trùng màu;

Tô màu miền (face coloring) là gán cho mỗi miền của đồ thị phẳng

một màu sao cho không có 2 miền có chung đường biên lại cùng màu.

Sắc số (chromatic number) của một đồ thị là số màu ít nhất để tô

các đỉnh. Sắc số của đồ thị G được kí hiệu là χ(G).

Số màu cạnh (chromatic index) của một đồ thị là số màu ít nhất dùng để tô các cạnh. Số màu cạnh của đồ thị G được kí hiệu là χ(cid:48)(G).

Rõ ràng số màu cạnh bằng sắc số của đồ thị đường của G.

Nếu G = (V, E) là một đồ thị (hữu hạn, có hướng hoặc vô hướng)

và f là một hàm gán mỗi đỉnh v của G với một số nguyên dương f (v),

ta nói rằng G là f - chọn nếu với mọi phép gán các tập các số nguyên S(v) ⊂ Z với các đỉnh v ∈ V , trong đó |S(v)| = f (v) với mọi v đều tồn tại một phép tô màu đỉnh thích hợp c : V (cid:55)→ Z sao cho c(v) ∈ S(v) với

mọi v ∈ V . Đồ thị G là k - chọn nếu nó f - chọn với hàm hằng f (v) ≡ k.

Số lựa chọn của G, kí hiệu là ch(G) là số nguyên k nhỏ nhất sao cho G

là k - chọn. Hiển nhiên, số này số nhỏ nhất của sắc số χ(G) của G. Số lựa chọn của đồ thị đường của G, kí hiệu là ch(cid:48)(G) và thường được gọi là bảng số màu cạnh của G và rõ ràng nó ít nhất bằng số màu cạnh χ(cid:48)(G)

của G.

Theo quan sát của các nhà nghiên cứu khác nhau, có nhiều đồ thị

G mà số lựa chọn ch(G) là lớn hơn sắc số χ(G). Một ví dụ đơn giản

chứng minh thực tế này là đồ thị hai phía đầy đủ K3,3. Nếu {u1, u2, u3} và {v1, v2, v3} là hai lớp các đỉnh đại diện của nó và S(ui) = S(vi) = {1, 2, 3}\{i} thì không có phép tô màu đỉnh thích hợp cho mỗi đỉnh ω

với một màu từ tập S(ω) của nó. Do đó, số lựa chọn của đồ thị này vượt

quá sắc số của nó. Trong thực tế, không khó để chứng minh rằng, với

18

k ≥ 2 bất kì, tồn tại đồ thị hai phía có số lựa chọn vượt quá k. Ngoài

ra, bằng cách sử dụng lập luận xác suất, ta chứng minh được rằng với

mọi k tồn tại một vài c(k) hữu hạn sao cho số lựa chọn của mọi đồ thị

đơn với bậc nhỏ nhất vượt quá k.

Theo quan điểm này, phỏng đoán sau được đề xuất độc lập bởi các

nhà nghiên cứu khác nhau bao gồm Vizing, Albertson, Collins, Tucker

và Gupta.

Phỏng đoán (Danh sách phỏng đoán màu). Với mọi đồ thị G thì ch(cid:48)(G) = χ(cid:48)(G).

Phỏng đoán này khẳng định rằng với đồ thị đường thì số lựa chọn

bằng sắc số. Nhiều kết quả thú vị trong phần này là chứng minh trường

hợp đặc biệt của phỏng đoán này mà vẫn còn mở rộng. Một phiên bản

tiệm cận của nó đã được chứng minh bởi Kahn bằng cách sử dụng lập luận xác suất: Với bậc cực đại của đồ thị đơn d thì ch(cid:48)(G) = (1 + o(1))d

trong đó o(1) tiến tới không như d tiến tới vô cùng. Trong trường hợp này χ(cid:48)(G) bằng d hoặc d + 1 theo định lý Vizing, điều này chứng tỏ rằng

bảng phỏng đoán màu là gần đúng.

Đa đồ thị fG = fG{x1, x2, . . . , xn} của đồ thị có hướng hoặc không có hướng G = (V, E) trên tập V = {v1, v2, . . . , vn} có n đỉnh được định nghĩa bởi fG(x1, x2, . . . , xn) = (cid:81){(xi − xj) : i < j, {vi, vj} ∈ E}. Đa thức này được nghiên cứu bởi các nhà nghiên cứu khác nhau, bắt đầu

là Petersen năm 1891.

Đồ thị con có hướng H của một đồ thị có hướng D được gọi là

H(v) của mọi đỉnh v của H bằng với bán H(v). Lưu ý ta không giả sử rằng H là liên thông. H là chẵn nếu nó có số cạnh chẵn, nếu không thì gọi là lẻ. Cho EE(D) và

Eulerian nếu bán bậc ra deg− bậc vào deg+

EO(D) lần lượt kí hiệu là số chẵn hoặc lẻ các đồ thị con Eulerian của

D. Để thuận tiện, ta đồng ý rằng đồ thị con khác rỗng là một đồ thị con

19

Eulerian chẵn.

Định lý 1.2.4. Cho D = (V, E) là một định hướng của một đồ thị vô

hướng G, kí hiệu V = {1, 2, . . . , n} và định nghĩa f : V (cid:55)→ Z bởi f (i) =

di + 1, trong đó di là bán bậc vào của i trong D. Nếu EE(D) (cid:54)= EO(D) thì D là f -chọn.

Chứng minh. Cho 1 ≤ i ≤ n, đặt Si ⊂ Z là tập của di + 1 số nguyên khác nhau. Sự tồn tại một phép tô màu thích hợp của D để gán mỗi

n (cid:81) i=1

di, nó đủ chứng tỏ rằng hệ số của

đỉnh i một màu từ bảng màu Si của nó là tương đương với sự tồn tại của các màu ci ∈ Si sao cho fG(c1, c2, . . . , cn) (cid:54)= 0. Vì bậc của fG bằng n (cid:80) xdi i trong fG là khác không để i=1 suy ra sự tồn tại của các màu ci theo Định lý 1.1.5.

Không khó để thấy rằng các hệ số của các đơn thức xuất hiện trong phép

biểu diễn chuẩn của fG như một tổ hợp tuyến tính của các đơn thức có thể được biểu diễn theo định hướng của G như sau. Gọi một định hướng

D của G là chẵn nếu số cạnh có hướng (i, j) với i > j của nó là chẵn,

nếu không gọi là lẻ. Cho d1, d2, . . . , dn là các số nguyên không âm, đặt DE(d1, . . . , dn) và DO(d1, . . . , dn) lần lượt kí hiệu là tập các định hướng chẵn và lẻ của G trong đó bán bậc vào của đỉnh vi là di với 1 ≤ i ≤ n. Trong ký hiệu này, người ta có thể kiểm tra rằng

n (cid:89)

i=1

d1,...,dn≥0

(cid:88) fG(x1, . . . , xn) = (|DE(d1, . . . , dn)| − |DO(d1, . . . , dn)|) xdi i .

20

Bây giờ xét định hướng D mà nằm trong DE(d1, . . . , dn)∪DO(d1, . . . , dn). Với định hướng D2 ∈ DE(d1, . . . , dn) ∪ DO(d1, . . . , dn) bất kì, kí hiệu D ⊕ D2 là tập tất cả các cạnh định hướng của D mà định hướng trong D2 theo hướng ngược lại. Vì bán bậc ra của mọi đỉnh trong D là bằng với bán bậc ra của nó trong D2, suy ra D ⊕D2 là một đồ thị con Eulerian của D. Hơn nữa D ⊕ D2 chẵn như là một đồ thị con Eulerian nếu và chỉ nếu cả D và D2 cùng chẵn hoặc lẻ. Ánh xạ D2 → D ⊕ D2 rõ ràng là một song ánh giữa DE(d1, . . . , dn) ∪ DO(d1, . . . , dn) và tập tất cả các đồ

thị con Eulerian của D. Trong trường hợp D chẵn, ánh xạ từ các định

hướng chẵn tới các đồ thị con chẵn và từ các định hướng lẻ tới các đồ

thị con lẻ. Nếu không thì ánh xạ từ các định hướng chẵn tới các đồ thị

con lẻ và ánh xạ từ các định hướng lẻ tới các đồ thị con chẵn. Trong

trường hợp bất kì

(cid:12) (cid:12) (cid:12) (cid:12) (cid:12) = |EE(D) − EO(D)|. (cid:12)|DE(d1, . . . , dn)| − |DO(d1, . . . , dn)|

n (cid:81) i=1

Do đó, giá trị tuyệt đối của hệ số của đơn thức xdi i trong phép biểu

diễn chuẩn của fG = fG(x1, . . . , xn) là một tổ hợp tuyến tính các đơn thức là |EE(D) − EO(D)|. Thực tế, nếu EE(D) (cid:54)= EO(D) thì các hệ

21

số này khác không và kết quả ước muốn sau từ Định lý 1.1.5.

Chương 2

Tổng thu hẹp-phương pháp đa thức

Chương này dành để trình bày phương pháp đa thức và việc sử

dụng các kết quả đạt được trong lý thuyết cộng các số, mở rộng của

Định lý Cauchy-Davenport. Đặc biệt ta thu được kết quả về chặn cho

lực lượng tập

{a0 + a1 + · · · + ak|ai ∈ Ai, ai (cid:54)= aj, 0 (cid:54) i < j (cid:54) k}

bởi một hàm các lực lượng của các tập con A0, A1, A2, . . . , Ak ⊂ Zp.

2.1 Phương pháp đa thức

Tiếp theo, để chứng minh mệnh đề ngay dưới đây chúng ta cần biết hệ

số đơn thức qua bổ đề sau:

2

n (cid:80) i=0

Bổ đề 2.1.1. Giả sử ti với i = 0, 1, . . . , n là những số nguyên không (cid:1), trong đó m là một số nguyên không âm. Khi âm và ti − m + (cid:0)n+1

n (cid:81) i=0

xti i xuất hiện trong đa thức (x0 + x1 + · · · +

0(cid:54)j

đó, hệ số của đơn thức xn)m (cid:81) (xi − xj) đúng bằng

0(cid:54)j

22

(cid:89) (ti − tj). m! t0!t1! . . . tn!

0(cid:54)j

Chứng minh: Tích (cid:81) (xi −xj) đúng bằng định thức Vandermonde

i )| với 0 (cid:54) i, j (cid:54) n. Đó là tổng (cid:80)

n (cid:81) i=0

δ∈Sn+1 là nhóm của tất cả các hoán vị của n + 1 ký hiệu 0, 1, 2, . . . , n. Ký hiệu

|(xj (−1)sign(δ) , trong đó Sn+1 xδ(i) i

xti i xuất hiện trong đa thức (x0 + x1 + · · · +

n (cid:81) i=0 (xi − xj) qua C. Khi đó

0(cid:54)j

hệ số của đơn thức xn)m (cid:81)

δ∈Sn+1

(cid:88) . C = (−1)sign(δ) m! (t0 − δ(0))!(t1 − δ(1))! . . . (tn − δ(n))!

i )|

0(cid:54)j

Tương tự, tích (cid:81) (ti − tj) đúng bằng định thức Vandermonde |(tj

với 0 (cid:54) i, j (cid:54) n. Với số nguyên dương r và số nguyên s ta đặt (s)r = s(s − 1) · · · (s − r + 1) và (s)0 = 1 cho mọi s. Qua phép biến đổi tuyến tính ta sẽ suy ra được ma trận ((ti)j)0(cid:54)i,j(cid:54)n từ ma trận (tj i )0(cid:54)i,j(cid:54)n. Như vậy hai định thức của hai ma trận này bằng nhau và ta nhận được

C = (ti − tj). m! t0!t1! . . . tn! (cid:81) 0(cid:54)j

Định lý 2.1.2. Giả sử p là một số nguyên tố và A0, A1, . . . , Ak là các tập con khác rỗng của nhóm cyclic Zp. Nếu |Ai| (cid:54)= |Aj| với mọi 0 (cid:54) i < j (cid:54) k

2

k (cid:80) i=0

và (cid:1) − 1 thì ta luôn có bất đẳng thức |Ai| (cid:54) p + (cid:0)k+2

k (cid:88)

i=0

(cid:19) + 1. |{a0 + · · · + ak|ai ∈ Ai, ai (cid:54)= aj, ∀i (cid:54)= j}| (cid:62) |Ai| − (cid:18)k + 2 2

Chứng minh. Định nghĩa h(x0, . . . , xk) = (cid:81) (xi − xj). Chú ý rằng,

i=0Ai = ⊕

0(cid:54)j

cho đa thức h(x0, . . . , xk) tổng ⊕k Ai. Giả sử |Ai| = ti + 1

2

2

k (cid:80) i=0

k (cid:80) i=0

(cid:1). Theo giả thiết (cid:1). Khi đó m = và đặt m = |Ai| − (cid:0)k+2 ti − (cid:0)k+1

k (cid:81) i=0

m < p. Theo Bổ đề 2.1.1, hệ số của đơn thức xti i thuộc đa thức

23

(ti − tj). Hệ h(x0, . . . , xk).(x0 + · · · + xk)m đúng bằng m! t0!t1! . . . tn! (cid:81) 0(cid:54)j

k (cid:80) i=0

số này khác 0 theo modulo p do m < p và ti (cid:54)= tj. Do m = ti + deg h

.. os-Heilbronn’s Conjecture] Nếu p là một số

nên mệnh đề được chứng minh theo Định lý 1.1.6.

Hệ quả 2.1.3. [Erd nguyên tố và A là tập con khác rỗng của Zp thì

|{a + a(cid:48)|a, a(cid:48) ∈ A, a (cid:54)= a(cid:48)}| (cid:62) min{p, 2|A| − 3}.

Chứng minh. Với k = 1, A0 = A và A1 = A \ {a} cho bất kỳ a ∈ A ta có kết quả: Khi A ⊂ Zp và 2|A| − 1 (cid:54) p + 2 thì số các tổng a + a(cid:48) với a, a(cid:48) ∈ A và a (cid:54)= a(cid:48) nhỏ nhất là bằng 2|A| − 3 theo Định lý 2.1.2. Do vậy,

ta có kết quả cần chứng minh.

Hệ quả 2.1.4. [Erdos-Heibronn’s Conjecture] Nếu p là một số nguyên tố và A, B là hai tập con khác rỗng của Zp thì

|{a + b|a ∈ A, b ∈ B, ab (cid:54)= 1}| (cid:62) min{p, |A| + |B| − 3}.

Chứng minh. Với k = 1, A0 = A, A1 = B, h = x0x1 − 1 và m = |A| + |B| − 4 ta có |{a + b|a ∈ A, b ∈ B, ab (cid:54)= 1}| (cid:62) m + 1 theo Định lý 2.1.2.

Do vậy, ta có kết quả cần chứng minh.

2.2 Một vài ví dụ liên quan

k (cid:89)

k (cid:88)

Mệnh đề 2.2.1. Nếu p là số nguyên tố và A0, A1, . . . , Ak là các tập con khác rỗng của Zp thì với mỗi g ∈ Zp ta luôn có

i=0

i=0

|{a0 + · · · + ak|ai ∈ Ai, ai (cid:54)= g}| (cid:62) min{p, |Ai| − 2k − 1}.

Chứng minh. Nếu g = 0 thì kết quả được suy ra ngay từ Định lý Cauchy

Davenport. Ta xét trường hợp g (cid:54)= 0. Đầu tiên, giả sử rằng |Ai| > 1

k (cid:80) i=0

24

với mọi i. Nếu |Ai| − 2k − 2 < p thì ta sử dụng Định lý 1.1.5 với

k (cid:81) i=0

k (cid:80) i=0

h = xi − g và m = |Ai| − 2k − 2. Ở đây ci = |Ai| − 1 và hệ số của

mà khác không mod m, suy xci i trong h.(x0 + · · · + xk)m là m! (cid:81)(ci − 1)!

k (cid:81) i=0 ra kết quả mong muốn. Nếu không, thay một vài tập Ai bởi tập con A(cid:48) i i| = p + 2k + 1 và áp dụng kết quả tới tập A(cid:48) i.

i| > 1 và

k (cid:80) i=0

thỏa mãn |A(cid:48) |A(cid:48)

Khi |Ai| = 1 với một vài tập Ai, ta cũng dễ dàng suy ra kết quả bằng cách áp dụng kết quả trước tới tập Aj có lực lượng hơn 1 với một vài giá trị thay đổi thích hợp của g.

Mệnh đề 2.2.2. Nếu p là số nguyên tố và A0, A1, . . . , Ak là các tập con khác rỗng của Zp với |Ai| (cid:62) k + 1 cho mọi i thì ta luôn có bất đẳng thức

k (cid:88)

|{a0 + · · · + ak|ai ∈ Ai, ai.aj (cid:54)= 1, 0 (cid:54) i < j (cid:54) k}|

i=0

(cid:62) min{p, |Ai| − (k + 1)2 + 1}.

k (cid:80) i=0

Chứng minh. Nếu |Ai| − (k + 1)2 < p thì qua việc áp dụng Định lý

k (cid:80) i=0

0≤i

1.1.5 với h = (cid:81) (xi.xj − 1) và m = |Ai| − (k + 1)2 ta có kết quả.

i thỏa mãn

k (cid:80) i=0

|A(cid:48) khác rỗng A(cid:48) Nếu không như trường hợp vừa xét ta thay một vài tập Ai bằng tập con i| = p + (k + 1)2 và áp dụng kết quả tới các

tập A(cid:48) i.

Chú ý. Đánh giá trong bổ đề trước là không rõ ràng. Thực tế, không

khó để chỉ ra rằng nếu lực lượng của Ai lớn hơn 2 + log2(k + 1) thì tập

(2.2.1) S = {a0 + · · · + ak : ai ∈ Ai, ai.aj (cid:54)= 1, ∀0 ≤ i < j ≤ k}

là khác rỗng. Thực tế, kết quả mạnh hơn sau đây là đúng.

25

Mệnh đề 2.2.3. Nếu p là một số nguyên tố và A0, A1, . . . , Ak là các tập con khác rỗng của Zp − {1, −1}, mỗi lực lượng s > log2(k + 1) thì tập

p − 3

2

S xác định trong (2.2.1) là khác rỗng. Điều này chặt với mọi s ≤ sao cho s có một bộ sưu tập của 2s các tập Ai ⊂ Zp − {1, −1} của mỗi lực lượng s sao cho tập S từ (2.2.1) là tập rỗng.

Chứng minh. Nếu s > log2(k + 1), cho H là một tập con ngẫu nhiên

p − 1 có phần tử của Zp − {1, −1} thu được bằng cách chọn, với mỗi 2

1

x

∈ Zp − {1, −1, 0} ngẫu nhiên, độc lập, chính xác một trong số cặp x, chúng là một phần tử của H. Ngoài ra thêm 0 vào H. Nếu Ai ∩ H (cid:54)= ∅ với mọi i, kết quả mong muốn sau bằng cách chọn ai ∈ Ai ∩ H và thấy rằng g.g(cid:48) (cid:54)= 1 với mọi g, g(cid:48) ∈ H. Tuy nhiên, với i cố định, nếu Ai chứa

1 0 hoặc chứa cả x và với một vài x ∈ Zp − {1, −1, 0} thì Ai ∩ H (cid:54)= ∅. x

1 chứng k + 1

Nếu không, xác suất rằng Ai ∩ H = ∅ chính xác là 2−s < tỏ rằng xác suất có thể Ai ∩ H (cid:54)= ∅ với mọi i, như yêu cầu.

1 , . . . , xδs

p − 3 Nếu s ≤ 2

, cho x1, . . . , xs là s phần tử của Zp − {1, −1, 0} sao cho tích của hai số bằng 1. Với mỗi 2s véctơ δ = (δ1, . . . , δs) ∈ {1, −1}s xác định một tập con Aδ = {xδ1 s } . Dễ thấy rằng mọi cách chọn một phần tử từ mỗi Aδ phải chứa một vài phần tử xi và nghịch đảo của nó. Điều này kết thúc chứng minh.

Mệnh đề 2.2.4. Nếu p là một số nguyên tố và A, B là hai tập con khác rỗng của Zp với |A| > |B| thì với e ∈ Zp bất kì

|{a + b : a ∈ A, b ∈ B, ab (cid:54)= e, a (cid:54)= b}| ≥ min{p, |A| + |B| − 4}. (2.2.2)

Chứng minh. Nếu |B| ≤ 2 và b(cid:48) ∈ B thì A chứa một tập con A(cid:48) của |A| − 2 phần tử mà không phải là b(cid:48) hoặc eb(cid:48)−1 và do đó trong trường

hợp này

26

|{a+b : a ∈ A, b ∈ B, ab (cid:54)= e, a (cid:54)= b}| ≥ |b(cid:48) +A(cid:48)| = |A|−2 ≥ |A|+|B|−4,

1

như yêu cầu. Do đó, ta giả sử rằng |A| > |B| ≥ 3. Nếu |A| + |B| − 5 < p,

áp dụng Định lý 1.1.6 với k = 1, h = (x0 −x1)(x0.x1 −e), A0 = A, A1 = B và m = |A| + |B| − 5. Do đó c0 = |A| − 1, c1 = |B| − 1 và hệ số của xc0 0 .xc1 trong h.(x0 + x1)m là (cid:33) (cid:32) (cid:32) (cid:33) m! m m − = (c0 − c1), (c0 − 1)!(c1 − 1)! c0 − 2 c0 − 1

là khác không mod p. Nếu |A| + |B| − 5 ≥ p thay B bởi một tập con B(cid:48) có p + 4 − |A| lực lượng và áp dụng kết quả tới A và B(cid:48) và kết luận trong trường hợp này |A + B| (cid:62) |A + B(cid:48)| = p.

Chú ý. Đánh giá sau là chặt với mọi lực lượng có thể của |A| > |B| > 1

như chứng tỏ bởi ví dụ sau.

A = {a, a + d, a + 2d, . . . , a + c0d}, B = {a, a + d, a + 2d, . . . , a + c1d}

trong đó a, d được chọn sao cho a(a + d) = (a + c0d)(a + c1d) = e. Nghiệm duy nhất của phương trình này trong trường hợp c1 = 1 ( nghĩa là |B| = 2), là e = 0 và d = −a cung cấp hai tập

A = {a, 0, . . . , −(c0 − 1)a}, B = {a, 0}.

Nếu c1 ≥ 2 nghiệm được cho bởi

(cid:118) (cid:117) (cid:117) (cid:116) a = , d = − . c0c1e (c0 − 1)(c1 − 1) (c0 + c1 − 1)a c0c1

Nghiệm như vậy tồn tại với mọi e sao cho (c0c1e)(c0 − 1)(c1 − 1) là một thặng dư bậc hai. Với |B| = 1 vế phải của (2.2.2) có thể hoàn thiện tới

|A| − 2 = |A| + |B| − 3 như giải thích trên và điều này là tầm thường.

Nếu |A| = |B| = s > 2 thì áp dụng mệnh đề 2.2.4 với A và một tập

con s − 1 lực lượng của B ta suy ra rằng trong trường hợp này, với mọi e ∈ Zp

27

|{a + b : a ∈ A, b ∈ B, ab (cid:54)= e, a (cid:54)= b}| ≥ min{p, |A| + |B| − 5}.

Không khó để kiểm tra rằng nếu s ≤ 2 thì tập trong vế trái của bất

đẳng thức sau có thể bằng rỗng. Với s ≥ 3 đánh giá trên là chặt, như

chứng tỏ bằng sự thay đổi dễ dàng của ví dụ được mô tả ở trên.

2.3 Điều kiện |A + B| = |A| + |B| − 1

Sử dụng phương pháp đa thức chúng ta đã đạt được kết quả sau đây:

|A + B| (cid:62) min{p, |A| + |B| − 1}

trong đó p là số nguyên tố và A, B là hai tập con thuộc trường Zp. Giả thiết A = {a1, a2, . . . , an} và B = {b1, b2, . . . , bm} là hai tập hữu hạn các số thực. Vấn đề đặt ra: Kết quả trên còn đúng khi A và B chỉ là tập hữu

hạn các số thực và khi nào dấu bằng xảy ra.

Định lý 2.3.1. Với hai tập hữu hạn các số thực A và B ta luôn có

|A + B| (cid:62) |A| + |B| − 1.

Chứng minh: Giả sử A = {a1, a2, . . . , an} và B = {b1, b2, . . . , bm} là hai tập hữu hạn các số thực. Sắp xếp a1 < a2 < · · · < an và b1 < b2 < · · · < bm. Khi đó

a1 + b1 < a1 + b2 < a1 + b3 < · · · < a1 + bm

< a2 + bm < a3 + bm < · · · < an + bm.

Từ đây ta nhận được bất đẳng thức |A+B| (cid:62) m+n−1 = |A|+|B|−1.

Tiếp theo, chúng ta quan tâm đến điều kiện bất đẳng thức trở thành

đẳng thức.

Ví dụ 2.3.2. Với tập A = {1, 2, 3, . . . , 10} và B = {1, 2, 3, . . . , 20} ta có

28

A+B = {2, 3, 4, . . . , 30}. Khi đó |A+B| = 29 = 10+20−1 = |A|+|B|−1.

Xét dãy a1 + b1 < a2 + b1 < a2 + b2 < · · · < a2 + bm < · · · < an + bm. Nếu |A + B| = m + n − 1 thì nhiều số hạng trong dãy trên phải xảy ra

dấu bằng, Như vậy, chúng ta phải có a1 +b2 = a2 +b1, và a1 +b3 = a2 +b2, .... Từ đó dẫn tới a2 − a1 = b2 − b1 = b3 − b2 = · · · . Từ đó dẫn đến A và B đều là những cấp số cộng với cùng công sai d > 0. Xét cấp số cộng A = {a + r.d|0 (cid:54) r (cid:54) n − 1} và B = {b + s.d|0 (cid:54) s (cid:54) m − 1}. Khi đó A + B = {a + b + j.d|0 (cid:54) j (cid:54) m + n − 2.}. Ta có |A + B| = m + n − 1 =

|A| + |B| − 1 và ta có

Định lý 2.3.3. Nếu A và B là hai tập hữu hạn chứa các phần tử lập

thành các cấp số cộng với cùng công sai thì

29

|A + B| = |A| + |B| − 1.

Chương 3

Vận dụng

3.1 Chứng minh Định lý Fermat, Định lý Wilson

Chúng ta sử dụng phương pháp đa thức để chứng minh một vài kết quả

trong Lý thuyết số.

Bổ đề 3.1.1. Với số nguyên dương n, đặt f (x) = (1+x)(2+x) . . . (n+x). Giả sử f (x) = b0 + b1x + b2x2 + · · · + bnxn. Khi đó ta có các hệ thức

n

k+2 bk+1.

n+1 + Cn−k

n−1

(n − k)bk = Cn+1−k bn−1 + Cn−1−k bn−2 + · · · + C2

Chứng minh: Từ (1 + x)(2 + x) . . . (n + x) = b0 + b1x + b2x2 + · · · + bnxn ta suy ra (2+x)(3+x) . . . (n+1+x) = b0 +b1(x+1)+· · ·+bn(x+1)n qua n(n + 1) 2!

30

việc thay x bởi x+1. Ta có ngay bn = 1, bn−1 = 1+2+· · ·+n = và hệ thức (1 + x)(2 + x) . . . (n + x)(n + 1 + x) = b0(x + 1) + b1(x + 1)2 + b2(x + 1)3 + · · · + bn(x + 1)n. Từ (n + 1 + x)f (x) = (x + 1)f (x + 1) suy ra (n + 1 + x)(b0 + b1x + · · · + bnxn) = b0(x + 1) + b1(x + 1)2 + b2(x +

1)3 + · · · + bn(x + 1)n+1. Như vậy 

bn = 1

(n + 1)bn−1 + bn−2 = C2

n+1 bn + C1 n+1 bn + C2

n bn−1 + C0 n bn−1 + C1

n−1 bn−2 n−1 bn−2 + C0

n−2 bn−3

(n + 1)bn−2 + bn−3 = C3

· · ·

n

2 b1

(n + 1)b2 + b1 = Cn−1 bn−1 + Cn−3

n+1 bn + Cn−2 n+1 bn + Cn−1

3 b2 + C0 2 b1 + C0

1 b0

(n + 1)b1 + b0 = Cn bn−1 + Cn−2

n−1 bn−2 + · · · + C1 n−1 bn−2 + · · · + C1 2 b1 + C1

1 b0 và có

n n bn−1 + Cn−1

n+1 bn + Cn

n−1 bn−2 + · · · + C2

(n + 1)b0 = Cn+1  

 bn = 1

bn−1 =

n bn−1

2bn−2 = C3 n(n + 1) 2! n+1 + C2

· · ·

n

4 b3

(n − 2)b2 = Cn−1 bn−1 + Cn−3

3 b2

n−1 bn−2 + · · · + C2 n−1 bn−2 + · · · + C1

(n − 1)b1 = Cn bn−1 + Cn−2

n+1 + Cn−2 n+1 + Cn−1 n n bn−1 + Cn−1

2 b1.

n+1 + Cn Do vậy (n−k)bk = Cn+1−k

n−1 bn−2 + · · · + C2 bn−1+Cn−1−k

  nb0 = Cn+1

n

k+2 bk+1.

n+1 + Cn−k

n−1

bn−2+· · ·+C2

Hệ quả 3.1.2. Đặt f (x) = (1 + x)(2 + x) . . . (p − 1 + x) với số nguyên tố lẻ p. Giả sử f (x) = b0 + b1x + b2x2 + · · · + bp−1xp−1. Khi đó ta có

(1) p | bk với k = 1, 2, . . . , p − 2 và p |(b0 + 1).

(2) Với mọi số nguyên n, p | (n + 1)(n + 2) . . . (n + p − 1) − np−1 + 1.

31

Từ đó suy ra p | (p − 1)! + 1 và p | np−1 − 1 khi (n, p) = 1.

Chứng minh: (1) Qua các công thức tính toán được ở trên ta có



bp−1 = 1

bp−2 =

p−1 bp−2

2bp−3 = C3 p(p − 1) 2! p + C2

· · ·

3 b2

p−1 bp−2 + Cp−3

p−2 bp−3 + · · · + C1

(p − 2)b1 = Cp−1

2 b1.

p + Cp−2 p + Cp−1

p−1 bp−2 + Cp−2

p−2 bp−3 + · · · + C2

(p − 1)b0 = Cp  

Sử dụng quy nạp theo k có p | bk với k = 1, 2, . . . , p − 2. Từ hệ thức cuối cùng suy ra hệ thức pb0 = (b0 + 1) + bp−2 + bp−3 + · · · + b1 và như vậy b0 + 1 chia hết cho p.

(2) Vì p | bk với k = 1, 2, . . . , p − 2 và b0 + 1 chia hết cho p nên p | (n + 1)(n + 2) . . . (n + p − 1) − np−1 + 1 với mọi số nguyên n. Từ đó suy ra p | (p − 1)! + 1 và p | np−1 − 1 khi (n, p) = 1.

Từ các kết quả trên ta suy ra bốn kết quả rất nổi tiếng dưới đây:

Định lý 3.1.3. Với số nguyên tố p và với mọi số tự nhiên n thỏa mãn

(n, p) = 1, ta luôn có:

(1) [Fermat] np−1 ≡ 1(modp).

(2) [Wilson] (p − 1)! + 1 ≡ 0(modp). (3) Nếu số nguyên tố p có dạng 4k + 1 thì (cid:2)(cid:0)p − 1 (cid:1)!(cid:3)2 + 1 ≡ 0(modp). 2

(4) Nếu số nguyên tố p có dạng 4k + 3 thì (cid:2)(cid:0)p − 1 (cid:1)!(cid:3)2 − 1 ≡ 0(modp). 2

với số nguyên n (cid:62) 2. Giả + · · · + + Tiếp theo, xét tổng Tn = 1 + 1 n 1 3

32

, trong r s 1 2 sử Tn được quy đồng và viết dưới dạng phân số tối giản Tn = đó r, s ∈ N và (r, s) = 1. Người ta đã chỉ ra r không chia hết cho s.

Ví dụ 3.1.4. Giả sử số nguyên tố p > 3 và hai số nguyên r, s thỏa mãn

1 = 1 + r s 1 22 + 1 32 + · · · + (p − 1)2 , (r, s) = 1.

= ((p − 1)!)2(cid:16) 1 + Khi đó số nguyên r chia hết cho số nguyên tố p. Chứng minh. Ta thấy ngay, số ((p − 1)!)2 r s 1 22 + (cid:17) 1 32 + là một số nguyên. Do {0, 1, 2, . . . , p − 1} là một hệ thặng · · · + 1 (p − 1)2

dư đầy đủ theo modulo p nên hệ {0, 1/1, 1/2, . . . , 1/p − 1} cũng là một

hệ thặng dư đầy đủ theo modulo p. Theo Định lý Wilson ta có ngay

(cid:17) ≡ ((p − 1)!)2(cid:16) 1 + ((p − 1)!)2 r s 1 22 + 1 32 + · · · + 1 (p − 1)2

≡ (−1)2[12 + 22 + 32 + · · · + (p − 1)2]

≡ ≡ 0(modp). (p − 1).p.(2p − 3) 6

. Vì ((p − 1)!, p) = 1

Do p (cid:62) 5 và (6, p) = 1 nên p chia hết số ((p − 1)!)2 r s nên r chia hết cho p.

Ví dụ 3.1.5. Tìm tất cả các số nguyên tố p, q và r thỏa mãn pq + qp = r.

Bài giải: Tối thiểu phải có một số nguyên tố chẵn. Số đó phải bằng 2.

Vì p, q là hai số nguyên tố nên r (cid:54)= 2. Không hạn chế có thể giả thiết q = 2. Vậy p2 + 2p = r. Vì r là số nguyên tố nên p phải là số lẻ. Nếu p (cid:54)= 3 thì p2 + 2p ≡ (±1)2 + (−1)p(mod3) ≡ 1 − 1(mod3). Vậy r chia hết cho 3, nhưng p2 + 2p = 3 chỉ thỏa mãn cho p = 1 : mâu thuẫn. Từ đây

suy ra p = 3, r = 17.

3.2 Vận dụng tổng tập hợp trong phương trình

nghiệm nguyên

33

Xét phương trình f (x, y, z) + g(x, y, z) = h(x, y, z) trên tập Z. Nếu phương trình có nghiệm trong Z thì nó cũng có nghiệm trong Zn. Bằng

cách xét tập A = {f (x, y, z)}, B = {g(x, y, z)}, C = {h(x, y, z)} và kiểm

tra A+B = C hay không để đưa ra kết luận phương trình vô nghiệm khi

(A + B) ∩ C = ∅ hoặc xét phương trình f (x, y, z) + g(x, y, z) = h(x, y, z) trên tập Z với điều kiện f (x, y, z) + g(x, y, z) ≡ h(x, y, z) mod n khi tập

(A + B) ∩ C chỉ gồm một vài phần tử.

3.2.1 Một vài phương trình vô nghiệm

Ví dụ 3.2.1. Xác định tất cả các số nguyên x, y, z thỏa mãn

x2 + 1 = 3y + 2016z4.

Bài giải: Nếu phương trình có nghiệm trong Z thì nó có nghiệm trong Z3. Khi đó A = {3y|y ∈ Z3} = {0}, B = {2016z4|z ∈ Z3} = {0} và A + B = {0}. Ta xác định C = {x2 + 1|x ∈ Z3} = {1, 2}. Từ C ∩ (A + B) = ∅ suy ra phương trình vô nghiệm.

Ví dụ 3.2.2. Xác định tất cả các số nguyên x, y, z thỏa mãn

x2 + 2015y3 + 2 = 5z10.

Bài giải: Nếu phương trình có nghiệm trong Z thì nó có nghiệm trong Z5. Khi đó A = {5z10|z ∈ Z5} = {0}, B = {2015y3|y ∈ Z5} = {0}. Ta xác định C = {x2 + 2|x ∈ Z5} = {1, 2, 3}. Từ A ∩ (B + C) = ∅ suy ra rằng, phương trình vô nghiệm.

Ví dụ 3.2.3. Xác định tất cả các số nguyên x, y, z thỏa mãn

x4 + 7y3 + 2 = 2016z5.

34

Bài giải: Nếu phương trình có nghiệm trong Z thì nó có nghiệm trong Z7. Khi đó A = {2016z5|z ∈ Z7} = {0}, B = {7y3|y ∈ Z7} = {0}. Ta xác định C = {x4 + 2|x ∈ Z7} = {2, 3, 4, 6}. Từ A ∩ (B + C) = ∅ suy ra rằng, phương trình vô nghiệm.

Ví dụ 3.2.4. Xác định tất cả các số nguyên dương x, y thỏa mãn

x2016 + 22016 + 3 = 2017y.

Bài giải: Nếu phương trình có nghiệm trong N thì nó có nghiệm trong Z2017. Ta có A = {x2016|x ∈ Z2017, x (cid:62) 0} = {0, 1}, B = {22016 + 3} = {4}. Ta xác định C = {2017y|y ∈ Z2017, y (cid:62) 0} = {0}. Từ C∩(A+B) = ∅ suy ra rằng, phương trình vô nghiệm.

Ví dụ 3.2.5. Chứng minh rằng, phương trình x2 = y3 + 7 không có

nghiệm nguyên.

Bài giải: Nếu phương trình có nghiệm trong Z thì nó có nghiệm trong Z4. Ta có A = {x2|x ∈ Z4} = {0, 1}, B = {y3 + 7} = {0, 2, 3}. Từ A ∩ B = {0} suy ra rằng, x = 2m, y = 2n + 1. Do x2 + 1 = y3 + 8 nên 4m2 + 1 = (2n + 3)(4n2 + 3). Từ đây suy ra 4m2 + 1 chia hết cho 4n2 + 3,

nhưng điều này là không thể. Do vậy, phương trình vô nghiệm.

Ví dụ 3.2.6. Chứng minh phương trình sau không có nghiệm nguyên

(x + 1)2 + (x + 2)2 + · · · + (x + 2019)2 = y2.

Bài giải: Đặt x = z − 1010. Phương trình đã cho trở thành

(z − 1009)2 + (z − 1008)2 + · · · + z2 + (z + 1)2 + · · · + (z + 1009)2 = y2.

Ta có 2019z2 + 2(12 + 22 + · · · + 10092) = y2 hay ta nhận được

2019z2 + 1009.1010.673 = y2.

Do vế trái A = {2019z2 + 1009.1010.673|z ∈ Z3} = {2} và vế phải B = {y2|y ∈ Z3} = {0, 1} với A ∩ B = ∅ nên phương trình đã cho vô nghiệm.

35

Ví dụ 3.2.7. [Balkan MO] Giải phương trình x5 − y2 = 4 trên Z.

Bài giải: Nếu phương trình đã cho có nghiệm trong Z thì nó cũng có nghiệm trong Z11. Vì (x5)2 = x10 ≡ 0, 1(mod 11) nên x5 ≡ −1, 0, 1(mod 11). Từ đó suy ra A = {x5 − 4|x ∈ Z11} = {6, 7, 8} và B = {y2|y ∈ Z11} = {0, 1, 3, 4, 5, 9}. Do A ∩ B = ∅ nên phương trình vô nghiệm.

3.2.2 Phương trình có nghiệm

Ví dụ 3.2.8. [Rusian MO 2013] Tìm tất cả các cặp số nguyên tố

(p, q) thỏa mãn điều kiện

p3 − q5 = (p + q)2.

Bài giải: Xét trường hợp cả hai số nguyên tố p, q đều khác 3. Khi đó

p ≡ 1, 2(mod 3) và q ≡ 1, 2(mod 3).

Khi p ≡ q(mod 3) thì A = {p3 − q5} = {0} và B = {(p + q)2} = {1}. Do

A ∩ B = ∅ nên không tồn tại p, q thỏa mãn những điều kiện vừa nêu ra.

Khi p (cid:54)≡ q(mod 3) thì A = {p3 − q5} = {1, 2} và B = {(p + q)2} = {0}.

Do A ∩ B = ∅ nên không tồn tại p, q thỏa mãn điều kiện vừa nêu ra.

Xét trường hợp p = 3. Khi đó q5 < 27, vô lý.

Xét trường hợp q = 3. Khi đó p3 − 243 = (p + 3). Giải ra p = 7. Tóm

lại, chỉ có duy nhất một cặp (7, 3) thỏa mãn phương trình đã cho.

3.2.3 Điều kiện tham số của phương trình

Định nghĩa 3.2.9. Ta gọi số nguyên b là nghịch đảo của số nguyên a

modulo m khi (a, m) = 1 nếu ab ≡ 1(mod m).

Định lý 3.2.10. Giả thiết hai số nguyên dương a, m thỏa mãn (a, m) =

36

1. Với tất cả các số nguyên dương nguyên tố với m và nhỏ hơn m xét A = {a1, a2, . . . , aϕ(m)|1 (cid:54) ai < m, (ai, m) = 1}. Khi đó ta cũng có A = {aa1, aa2, . . . , aaϕ(m)}.

Chứng minh: Vì (ai, m) = 1 và (a, m) = 1 nên (aai, m) = 1 với mỗi i = 1, 2, . . . , ϕ(m). Do vậy, mỗi phần tử thuộc tập B = {aa1, aa2, . . . , aaϕ(m)} đều nguyên tố với m. Mặt khác, do (a, m) = 1 nên từ aai ≡ aaj(mod m) ta suy ra ngay ai ≡ aj(mod m). Như vậy tập A và tập {aa1, aa2, . . . , aaϕ(m)} có cùng lực lượng. Qua đó ta nhận được A = {aa1, aa2, . . . , aaϕ(m)}.

Định lý 3.2.11. Nếu hai số nguyên dương a, m thỏa mãn (a, m) = 1 thì

a luôn có nghịch đảo theo modulo m.

Chứng minh: Xét C = {a1, . . . , aϕ(m)|1 (cid:54) ai < m, (ai, m) = 1}. Khi đó 1 thuộc tập C. Theo Định lý 3.2.10, hai tập sau bằng nhau

{a1, a2, . . . , aϕ(m)} = {aa1, aa2, . . . , aaϕ(m)}

nên có ai để aai ≡ 1(mod m). Vậy b = ai là nghịch đảo của a.

Hệ quả 3.2.12. Với hai số nguyên dương a, m thỏa mãn (a, m) = 1, phương trình ax ≡ b(mod m) luôn có nghiệm x ≡ a−1b(mod m).

Ví dụ 3.2.13. Giả sử hai số nguyên dương m, n có tính chất: (2017k −

1, m) = (2017k − 1, n) với mọi số nguyên dương k. Khi đó tồn tại số nguyên r để m = 2017rn.

Bài giải: Trước tiên ta chỉ ra rằng, với mọi số nguyên tố p (cid:54)= 2017 ta

luôn có vp(m) = vp(n). Thật vậy, giả sử rằng, vp(m) > vp(n). Ta biểu diễn m = pαb và n = pγc với α > γ và (b, p) = 1 = (c, p). Theo Định lý 3.2.11, tồn tại k để 2017k ≡ 1(mod pα). Như vậy pα|(2017k − 1, m) = (2017k−1, n), và suy ra pα|(2017k−1, n). Vậy pα|n, mâu thuẫn do α > γ. Từ đó suy ra sự tồn tại của số nguyên r để m = 2017rn.

Ví dụ 3.2.14. Giả sử n là một số nguyên dương. Ký hiệu d(n) là

số các ước dương của n và ϕ(n) là số các số nguyên dương thuộc tập

{1, 2, 3, . . . , n} nguyên tố với n. Xác định tất cả các số nguyên không âm

37

c để có số nguyên dương n thỏa mãn d(n) + ϕ(n) = n + c.

Bài giải: Ký hiệu A là tập tất cả các ước nguyên dương của n và B

là tập tất cả các số nguyên dương thuộc tập {1, 2, 3, . . . , n} nguyên tố

với n. Hiển nhiên A ∪ B ⊆ {1, 2, 3, . . . , n} và A ∩ B = {1}. Do vậy d(n) + ϕ(n) (cid:54) n + 1. Từ đó suy ra c = 0 hoặc c = 1.

Xét trường hợp c = 0 hay d(n) + ϕ(n) = n. Với n = 6 ta có A =

{1, 2, 3, 6}, B = {1, 5}. Khi đó d(6) + ϕ(6) = 6.

Xét trường hợp c = 1 hay d(n) + ϕ(n) = n + 1. Với n = 3 ta có

A = {1, 3}, B = {1, 2}. Khi đó d(3) + ϕ(3) = 3 + 1.

Ví dụ 3.2.15. [USAJMO 2013] Tồn tại hay không tồn tại hai số nguyên dương a, b để a5b + 3 và ab5 + 3 đều là lập phương của những số

tự nhiên?

Bài giải: Ký hiệu A = {x3|x ∈ Z9} = {0, 1, −1}. Giả sử đã xác định được hai số nguyên dương a, b để a5b + 3 và ab5 + 3 đều là lập phương 5 của những số tự nhiên. Khi đó ta phải có a5b + 3 và ab + 3 thuộc tập

5

{0, 1, −1}. Từ đây suy ra kết quả dưới đây:

a5b, ab ∈ {5, 6, 7}.

Xét trường hợp 3|a. Khi đó a5b ≡ 0(mod 9), vô lý. Do vậy (3, a) = 1. Tương tự (3, b) = 1. Theo Định lý Euler, ta có n6 ≡ 0, 1(mod 9). Vì ϕ(9) = 6 nên (a5b)(ab5) ≡ 0, 1(mod 9). Từ 5.5 ≡ 7(mod 9), 5.7 ≡

8(mod 9) và 7.7 ≡ 4(mod 9) suy ra rằng, không tồn tại hai số nguyên dương a, b để a5b + 3 và ab5 + 3 đều là lập phương của những số tự

nhiên.

Ví dụ 3.2.16. Xác định một cấp số cộng gồm nhiều vô hạn các số

nguyên dương khác nhau sao cho mỗi số hạng không thể biểu diễn thành

tổng hai số lập phương.

38

Bài giải: Giả sử cấp số cộng (an) với a0 = a và an+1 = an + d với mọi số nguyên n (cid:62) 0. Ta giới hạn xét số lớp thặng dư là những lập phương

theo modulo d. Trước tiên xét a3 ≡ 1(mod d) cho tất cả các số nguyên a. Với số nguyên tố p và (a, p) = 1 ta có ap−1 ≡ 1(mod p) theo Định lý nhỏ

của Fermat. Nếu p − 1 = 3 thì p = 4, mâu thuẫn. Nếu p − 1 = 6 = 3.2 thì p = 7. Dễ dàng kiểm tra A = {a3|a ∈ Z7} = {0, 1, −1}, trong đó −1 = 6. Từ đây suy ra A + A = {0, 1, −1, 2, −2}. Vậy, ta chọn a sao cho

a theo modulo 7 không thuộc A + A. Ta có thể chọn hai cấp số cộng (an) với số hạng đầu a0 = a = 3 hoặc a0 = a = 4, và công sai d = 7, thỏa mãn yêu cầu bài toán đặt ra.

Ví dụ 3.2.17. Giả sử a và b là hai số nguyên dương thỏa mãn (a, b) = 1.

Xét cấp số cộng (an) với a0 = a, an = a0 + nd với mọi số nguyên không âm n. Chứng minh rằng

(1) [Polya] Tồn tại nhiều vô hạn số hạng trong cấp số có ước nguyên

tố chung.

(2) Tồn tại nhiều vô hạn số hạng trong cấp số nguyên tố cùng nhau.

Bài giải: (1) Vì (a, b) = 1 nên a có nghịch đảo modulo b theo Hệ quả

3.2.12. Giả sử số nguyên m thỏa mãn am ≡ 1(mod b). Với mỗi số tự nhiên r ta xét sr = (a + b)(am)r Hiển nhiên sr ≡ a(mod b). Do vậy sr là một số hạng thuộc cấp số cộng (an). Các số hạng sr này có cùng ước nguyên tố, chẳng hạn ước nguyên tố của a, m, a + b.

(2) được chứng minh dễ dàng.

3.3 Phương pháp đa thức qua nghiệm

3.3.1 Chứng minh số vô tỷ

Theo kết quả sau đây, ta biết được rằng, một đa thức bậc n > 0 có

39

không quá n nghiệm phân biệt.

Định lý 3.3.1. [Bézout] Một đa thức bậc n > 0 có không nhiều hơn n

nghiệm phân biệt.

√ Ví dụ 3.3.2. Chứng minh rằng, số 3 là một số vô tỷ.

√ 3 là nghiệm của đa thức này nên Bài giải: Đa thức x2 − 3 là bất khả quy trong Z[x]. Vì đa thức x2 − 3 không có nghiệm hữu tỷ trong Q và √ 3 là một số vô tỷ.

Ví dụ 3.3.3. Chứng minh rằng, số α dưới đây là một số vô tỷ:

(cid:112) (cid:112) (cid:112) α = 10092 + 1 + 10102 + 1 + · · · + 20162 + 1.

Bài giải: Trước tiên ta chỉ ra số α không phải là một số nguyên. Thật √ n2 + 1 < n + vậy, từ việc đánh giá n < 1 n

với mọi i = 1, 2, . . . , 1008. ta có thể viết α = 1009 + t1 + 1 1008

√ Tiếp theo, bằng phương pháp quy nạp n ta chỉ ra αn = ai, trong đó 1010 + t2 + · · · + 2016 + t1008 với 0 < ti < Vì 0 < t1 + t2 + · · · + t1008 < 1 nên α không là số nguyên. n (cid:80) i=1

√

√ √

√ các ai đều là số nguyên dương, không là số chính phương, là đại số trên Q hay có một đa thức monic bậc dương thuộc vành Z[x] nhận αn làm a1 là nghiệm của đa thức monic x2−a1 ∈ Z[x], nghiệm. Với n = 1, α1 = kết luận đúng. Giả sử kết luận đúng cho n, có nghĩa: Có đa thức monic f (x) = xr + b1xr−1 + · · · + br−1x + br ∈ Z[x], r > 0, nhận αn làm nghiệm. an+1) = f (αn) = 0. Với n + 1, từ αn+1 = αn + Như vậy, đa thức f (x − an+1 ta suy ra f (αn+1 − an+1) nhận αn+1 làm nghiệm. Biểu diễn

√ √ √ f (x − an+1) = (x − an+1)r + b1(x − an+1)r−1 + · · ·

√

an+1) + br √ + br−1(x − = xr + g(x) + an+1h(x)

40

với đa thức g(x), h(x) ∈ Z[x] và deg g(x), deg h(x) (cid:54) r − 1. Xét đa thức φ(x) = (cid:0)xr + g(x)(cid:1)2 − an+1h(x)2 ∈ Z[x]. Đây là đa thức monic bậc 2r

n+1 + g(αn+1) +

với hệ số nguyên nhận αn+1 làm nghiệm, vì từ hệ thức αr √ √ an+1h(αn+1) = f (αn+1 −

(cid:0)αr an+1) = 0 suy ra n+1 + g(αn+1)(cid:1)2 − an+1h(αn+1)2 = 0

hay φ(αn+1) = 0.

Ví dụ 3.3.4. [Soviet MO 1991] Cho 2n số phân biệt a1, a2, . . . , an và b1, b2, . . . , bn đặt vào các ô của một lưới nguyên tạo bởi các đường x = 0, x = 1, . . . , x = n và y = 0, y = 1, . . . , y = n theo quy tắc sau: Ô

lưới nguyên ở cột thứ i và dòng thứ j thì ta viết số ai + bj. Chứng minh rằng, nếu tích các số thuộc mỗi cột là bằng nhau thì tích các số ở mỗi

dòng cũng bằng nhau.

n (cid:81) i=1

n (cid:81) j=1

Bài giải: Xét đa thức p(x) = (x + ai) − (x − bj). Hiển nhiên

deg p(x) < n. Theo giả thiết tất cả các số c = p(bj), j = 1, 2, . . . , n, đều bằng nhau. Như vậy, đa thức p(x) − c có bậc nhỏ hơn n, nhưng có

n (cid:81) j=1

n nghiệm phân biệt là b1, b2, . . . , bn. Đa thức này phải đồng nhất bằng 0 hay p(x) ≡ c với mọi giá trị của x. Ta nhận được c = p(−ai) = (−1)n+1 (ai + bj) với mọi i = 1, 2, . . . , n. Từ đó suy ra tích mỗi số ở

n (cid:81) j=1

mỗi dòng đều bằng nhau và (ai + bj) = (−1)n+1c.

Ví dụ 3.3.5. Cho 2n số chia thành hai nhóm phân biệt là a1, a2, . . . , an và b1, b2, . . . , bn thỏa mãn điều kiện: ai + aj = bi + bj với 1 (cid:54) i < j (cid:54) n. Chứng minh rằng, n là một lũy thừa của 2.

n (cid:80) i=1

n (cid:80) j=1

Bài giải: Xét đa thức f (x) = xai và g(x) = xbj. Khi đó f (x)2 =

1(cid:54)i

1(cid:54)i

n (cid:80) i=1

x2ai + 2 (cid:80) xai+aj = f (x2) + 2 (cid:80) xai+aj và g(x)2 = x2bi +

n (cid:80) i=1 2 (cid:80) 1(cid:54)i

1(cid:54)i

xbi+bj = g(x2) + 2 (cid:80) xbi+bj. Vì ai + aj = bi + bj với mọi

41

i, j = 1, 2, . . . , n, i < j, theo giả thiết, nên ta có ngay f (x)2 − f (x2) = g(x)2−g(x2) hay f (x)2−g(x)2 = f (x2)−g(x2). Do f (1)−g(1) = n−n = 0

nên f (x) − g(x) = (x − 1)kq(x) với k là số nguyên dương và đa thức q(x)

thỏa mãn q(1) (cid:54)= 0. Vậy

= . f (x) + g(x) = f (x2) − g(x2) f (x) − g(x) (x2 − 1)kq(x2) (x − 1)ka(x) = (x + 1)k q(x2) q(x)

Với x = 1 ta nhận được 2n = 2k hay n = 2k−1.

Với tập khác rỗng A ta định nghĩa A + A = {a + b|a, b ∈ A} và

A − A = {a − b|a, b ∈ A}.

Ví dụ 3.3.6. [RMC 2015] Giả sử A là một tập hữu hạn các số thực,

khác rỗng. Chứng minh rằng

card(A). card(A − A) (cid:54) card(A + A)2.

Bài giải: Đặt S = A + A và D = A − A. Xây dựng ánh xạ f : A × D →

S×S, (a, d) (cid:55)→ (a+xd, a+yd) với xd, yd ∈ A sao cho xd−yd = d và xd là lớn nhất. Hiển nhiên, khi biết d thì xd, yd được xác định duy nhất. Bây giờ ta

a + xd = a(cid:48) + xd(cid:48)   chỉ ra f là một đơn ánh. Nếu f (a, d) = f (a(cid:48), d(cid:48)) thì

 a + yd = a(cid:48) + yd(cid:48).

Từ hệ này suy ra d = xd − yd = xd(cid:48) − yd(cid:48) = d(cid:48). Từ đó suy ra a = a(cid:48) và xd = xd(cid:48). Như vậy, f được xác định hoàn toàn và là một đơn ánh. Do f là đơn ánh nên card(A). card(A − A) (cid:54) card(A + A)2.

Ví dụ 3.3.7. [RMC 2015] Giả sử n ∈ N, n (cid:62) 4. Xác định tập A = {a1, a2, . . . , an} ⊂ N sao cho A chứa 2015 và |ai − aj| là số nguyên tố cho tất cả các số phân biệt i, j ∈ {1, 2, . . . , n}.

Bài giải: Dễ dàng thấy ngay rằng A không thể chứa nhiều hơn hai số

cùng chẵn hoặc cùng lẻ vì điều kiện |ai − aj| phải là một số nguyên tố. Do n (cid:62) 4 nên n = 4 và A chứa hai số chẵn, hai số lẻ. Do 2015 ∈ A

nên hai số lẻ thuộc A hoặc là 2013, 2015 hoặc là 2015, 2017. Xét trường

42

hợp A chứa 2013, 2015. Hai số chẵn thuộc A là 2a, 2a + 2, trong đó a

là số nguyên dương. Do |2013 − 2a|, |2011 − 2a| và |2015 − 2a| là số

nguyên tố lẻ nên 2a không thể là 2010, 2012, 2014, 2016. Khi 2a < 2010

thì 2011−2a, 2013−2a, 2015−2a là ba số lẻ liên tiếp và đều là số nguyên

tố. Do vậy, một trong ba số đó phải bằng 3. Vậy 2a = 2008, a+2 = 2010.

Kiểm tra A = {2008, 2010, 2013, 2015} thỏa mãn. Khi 2a > 2016 thì

−2011+2a, −2013+2a, −2015+2a là ba số lẻ liên tiếp và đều là số nguyên

tố. Do vậy, một trong ba số đó phải bằng 3. Vậy 2a = 2018, a+2 = 2020.

Kiểm tra A = {2013, 2015, 2018, 2020} thỏa mãn. Tương tự ta cũng có

A = {2010, 2012, 2015, 2017} và A = {2015, 2017, 2020, 2022}.

3.3.2 Bài toán Waring về đa thức

Bài toán Waring đặt ra cho đa thức: Cho số nguyên dương n. Tìm số nguyên nhỏ nhất s = s(n) để mỗi đa thức g ∈ C[x] đều có thể biểu diễn

thành tổng dạng

1 + f n

2 + · · · + f n s ,

g = f n

trong đó các fi ∈ C[x]. Ta chỉ cần xét sự biểu diễn cho đa thức x, vì khi

x = f1(x)n + · · · + fs(x)n

thì với đa thức g(x) tùy ý có ngay

g(x) = f1(g(x))n + f2(g(x))n + · · · + fs(g(x))n.

Chính vì lý do đó mà ta chỉ cần quan tâm đến số s = s(n) nhỏ nhất để x = f1(x)n + · · · + fs(x)n. Số s nhỏ nhất là bao nhiêu và công thức xác định vẫn là bài toán chưa có lời giải. Người ta đã đưa ra các chặn cho

s(n) qua định lý sau đây.

Định lý 3.3.8. Ta luôn có các kết quả dưới đây:

(i) s(2) = 2.

43

(ii) Nếu n (cid:62) 3 thì 3 (cid:54) s(n) (cid:54) n.

(cid:1)2 + (cid:0)ix + (cid:1)2 = x ta có 1 4 i 4 Chứng minh: (i) Từ đồng nhất thức (cid:0)x + ngay s(2) = 2.

n (cid:89)

(ii) Chứng minh s(n) (cid:62) 3 khi n (cid:62) 3 : Giả sử s(n) < 3. Ta có biểu diễn

j=1

x = f1(x)n + f2(x)n = (f1 + αjf2),

ở đó α là căn nguyên thuỷ bậc n của đơn vị. Vì n (cid:62) 3 nên phải có ít

nhất hai nhân tử là hằng số. Vậy phải có j, k với j (cid:54)= k để



 f1 + αjf2 = a f1 + αkf2 = b  a, b ∈ C.

Giải hệ phương trình tuyến tính này ta được f1, f2 ∈ C. Do đó x = f1(x)n + f2(x)n là không đúng. Điều này chứng tỏ s(n) (cid:62) 3. Ta chỉ ra s(n) (cid:54) n khi n (cid:62) 3 : Với đa thức f (x) ta đặt sai phân

∆f (x) = f (x + 1) − f (x), ∆hf = ∆(∆h−1f ) khi h (cid:62) 2.

Dễ dàng kiểm tra deg(∆f ) = deg f − 1.Vậy deg(∆n−1(xn)) = 1. Điều này chứng tỏ ∆n−1(xn) = ax + b, a (cid:54)= 0. Vì

n−1 (cid:88)

j=0

(cid:19) ax + b = ∆n−1(xn) = (−1)n−1+j (x + j)n (cid:18)n − 1 j

và ta thay ax + b qua x1 ta có sự biểu diễn dạng x1 = f1(x1)n + · · · + fn(x1)n. Điều này chứng tỏ s(n) (cid:54) n.

Xét sự biểu diễn của đa thức thành tổng lũy thừa các đa thức tuyến

tính.

Định lý 3.3.9. Cho α1, . . . , αn+1 là những số khác nhau. Khi đó mỗi đa thức f (x) bậc n đều có thể biểu diễn một cách duy nhất thành dạng

44

f (x) = γ1(x + α1)n + · · · + γn+1(x + αn+1)n.

Chứng minh: Giả sử f (x) = a0xn+a1xn−1+· · ·+an. Ta coi γ1, . . . , γn+1 như các ẩn số. Từ đồng nhất thức

f (x) = γ1(x + α1)n + · · · + γn+1(x + αn+1)n

ta suy ra hệ n + 1 phương trình tuyến tính với n + 1 ẩn γi :



n+1) = a2

(cid:1)(γ1α1 + · · · + γn+1αn+1) = a1 (cid:1)(γ1α2 1 + · · · + γn+1α2 γ1 + γ2 + · · · + γn+1 = a0 (cid:0)n 1 (cid:0)n 2

1 + · · · + γn+1αn

n+1) = an.

  · · · = · · · (cid:1)(γ1αn (cid:0)n n

Vì các αi khác nhau nên định thức Vandermonde của hệ khác 0. Do đó hệ có một nghiệm duy nhất và ta có điều cần chứng minh.

Hệ quả 3.3.10. Cho α1, . . . , αn+1 là những số khác nhau. Giả sử t1, t2, . . . , tn là n nghiệm của đa thức f (x) bậc n. Khi đó có duy nhất một bộ γ1, . . . , γn+1 để γ1(ti +α1)n +· · ·+γn+1(ti +αn+1)n = 0 với i = 1, 2, . . . , n.

Chứng minh: Giả sử f (x) = a0xn + a1xn−1 + · · · + an. Ta có biểu diễn duy nhất γ1, . . . , γn+1 theo định lý trên. Khi đó γ1(ti + α1)n + · · · + γn+1(ti + αn+1)n = f (ti) = 0 với i = 1, 2, . . . , n.

Đa thức f (x) ∈ R[x] được gọi là đa thức dương trên R nếu f (x) > 0 với mọi x ∈ R. Đa thức f (x) ∈ R[x] được gọi là đa thức không âm trên R nếu f (x) (cid:62) 0 với mọi x ∈ R.

Ví dụ 3.3.11. Giả sử đa thức f (x) ∈ R[x] thỏa mãn f (x) (cid:62) 0 với mọi x ∈ R. Khi đó có thể biểu diễn f (x) = [g(x)]2 + [h(x)]2 với g(x), h(x) ∈ R[x].

45

Bài giải: Vì f (x) ∈ R[x] thỏa mãn f (x) (cid:62) 0 với mọi x ∈ R nên f (x) không thể có nghiệm thực với bội là số lẻ. Biểu diễn f (x) = [k(x)]2q(x)

với đa thức q(x) không có nghiệm thực. Theo kết quả đã biết, nếu q(x)

có nghiệm phức α thì nó phải có nghiệm phức liên hợp α. Do đó q(x) có biểu diễn q(x) = [h1(x) + ih2(x)][h1(x) − ih2(x)] với h1(x), h2(x) ∈ R[x]. Do đó f (x) = [k(x)]2([h1(x)]2 + [h2(x)]2) = [g(x)]2 + [h(x)]2.

Định lý 3.3.12. Mỗi đa thức f (x) (cid:62) 0 với mọi x (cid:62) 0 bậc 2n đều biểu diễn được thành dạng f (x) = [u(x)]2 + [v(x)]2 + x(cid:0)[r(x)]2 + [s(x)]2(cid:1), trong đó u(x), v(x), r(x), s(x) ∈ R[x].

n (cid:89)

Chứng minh: Với n = 0, kết luận là hiển nhiên. Xét n (cid:62) 1 : Phân tích

i=1

f (x) = (aix2 + bix + ci)

với ai > 0, aix2 + bix + ci (cid:62) 0 với mọi x (cid:62) 0. Vì ax2 + bx + c (cid:62) 0 khi x (cid:62) 0 ta suy ra ngay c (cid:62) 0. Khi đó

√ √ √ ax2 + bx + c = ( ax − c)2 + x(b + 2 ac).

Nếu b2 −4ac > 0 thì ax2 +bx+c = 0 có hai nghiệm phân biệt x1, x2, x1 < x2, cùng dấu. Khi b < 0 thì x1, x2 > 0 và ax2 + bx + c (cid:62) 0 không thỏa mãn cho mọi x (cid:62) 0. Vậy hoặc b2 − 4ac (cid:54) 0 hoặc b2 − 4ac (cid:62) 0, b (cid:62) 0. √ Điều này chứng tỏ b + 2 ac (cid:62) 0. Do đó ta có sự phân tích

ax2 + bx + c = (αx + β)2 + x(γ2 + δ2).

i )]. Dễ dàng kiểm tra

i + δ2

n (cid:81) i=1

Vậy ta có thể viết f (x) = [(αix + βi)2 + x(γ2

tích các đa thức dạng (a2 + b2) + x(c2 + d2) cũng là một đa thức cùng

dạng. Từ nhận xét này, sau một số bước thực hiện, ta có sự biểu diễn f (x) = [u(x)]2 + [v(x)]2 + x(cid:0)[r(x)]2 + [s(x)]2(cid:1).

3.4 Phương pháp đa thức trong bất đẳng thức

Sử dụng phương pháp đa thức vào việc chứng minh một số bất đẳng

46

thức dưới đây.

Mệnh đề 3.4.1. Giả sử dãy hữu hạn các số thực (ai), (bi), (ti) thỏa mãn 0 < a (cid:54) ai (cid:54) A, 0 < b (cid:54) bi (cid:54) B và ti (cid:62) 0 với mọi i = 1, . . . , n. Khi đó

n (cid:80) i=1

n (cid:80) i=1 (cid:16) n (cid:80) i=1

a2 i . (cid:17)2 (cid:62) (1) [Polya] + b2 i (cid:17)2 . (cid:16)(cid:114) ab AB 1 4 (cid:114)AB ab aibi

(cid:17)2 (cid:62) (2) [Cantorovic] (cid:17) . ti tiai (a + A)2 4aA ti ai (cid:16) n (cid:80) i=1 (cid:16) n (cid:80) i=1 (cid:17)(cid:16) n (cid:80) i=1

(cid:17) + x+ (cid:16) b A

. Từ ta suy ra bất đẳng thức , − + (cid:54) 0 + Chứng minh: (1) Tam thức f (x) = x2− (cid:54) B a B a b A (cid:16) b A Bb Aa B a Bb Aa có hai nghiệm (cid:17) bi ai B a b2 i a2 i

i −

hay b2 + (cid:54) 0 với i = 1, . . . , n. Cộng tất cả lại được: biai + a2 i b A (cid:16) b A (cid:54) bi ai (cid:17) B a Bb Aa

n (cid:88)

n (cid:88)

n (cid:88)

i=1

i=1

i=1

i=1

i=1

(cid:17) (cid:17) n (cid:88) (cid:16) n (cid:88) + (cid:62) 2 . biai (cid:62) (cid:118) (cid:117) (cid:117) (cid:116) b2 i + a2 i b2 i a2 i (cid:16) b A B a Bb Aa (cid:17)(cid:16) Bb Aa

n (cid:80) i=1

a2 i . (cid:17)2 (cid:62) Do đó + = + b2 i (cid:17)2 . (cid:16)(cid:114) ab AB 1 4 (cid:114)AB ab 1 4 (cid:16) b A B a (cid:17)2 Aa Bb aibi

(cid:54) (a + A)ti với

n (cid:80) i=1 (cid:16) n (cid:80) i=1 tiaA ai n (cid:80) i=1

i = 1, . . . , n, và ta có (cid:54) (a + A) tiai + ti. Theo Bất đẳng tiaA ai (2) Vì 0 < a (cid:54) ai (cid:54) A và ti (cid:62) 0 nên tiai + n (cid:80) i=1 (cid:115)

n (cid:80) i=1

thức Cauchy ta được (a + A)( aA( ) hay bất ti) (cid:62) 2 tiai)( ti ai

n (cid:80) i=1 (cid:17)

n (cid:80) i=1 n (cid:80) i=1 (cid:16) n (cid:80) i=1

3 > 0.

(cid:17)2 (cid:62) đẳng thức . tiai ti (a + A)2 4aA ti ai (cid:17)(cid:16) n (cid:80) i=1 (cid:16) n (cid:80) i=1

2 − a2 1 − a2 (cid:17)2 .

2 − a2 3

2 − b2 3

(cid:16) (cid:17)(cid:16) (cid:17) (cid:16) (cid:54) a1b1 − a2b2 − a3b3 a2 1 − a2 Ví dụ 3.4.2. Cho các số thực a1, a2, a3, b1, b2, b3 với a2 b2 1 − b2 Khi đó

2−a2 3

1−a2 a2

47

(cid:17) (cid:16) (cid:17) (cid:16) x2−2 x+ Bài giải: Xét tam thức f (x) = a1b1−a2b2−a3b3

1 − b2 b2

(cid:16) (cid:17) = (a1x − b1)2 − (a2x − b2)2 − (a3x − b3)2. Từ giả thiết suy ra

2 − b2 3 (cid:16) b1 a1

(cid:17) (cid:54) 0. Vậy f (x) = 0 có nghiệm và như thế ∆(cid:48) (cid:62) 0. a1 (cid:54)= 0 và f

Bổ đề 3.4.3. [Rolle] Nếu hàm y = g(x) xác định và liên tục trên đoạn [a; b], a < b, thỏa mãn g(a) = g(b) thì tồn tại x0 ∈ (a; b) để g(cid:48)(x0) = 0.

Xét đa thức bậc n (cid:62) 2 với n nghiệm sau đây:

f (x) = (x−a1)(x−a2) . . . (x−an) = xn−σ1xn−1+σ2xn−2−· · ·+(−1)nσn.

Mệnh đề 3.4.4. Nếu ai (cid:62) 0, i = 1, . . . , n, thì ta có các bất đẳng thức

(cid:62) (cid:62) n (cid:62) · · · (cid:62) k (cid:62) · · · (cid:62) n−1 σ1 (cid:1) (cid:0)n 1 (cid:114) σ2 (cid:1) (cid:0)n 2 (cid:114) σk (cid:1) (cid:0)n k (cid:115) σn−1 (cid:1) (cid:0) n n−1 (cid:114) σn (cid:1). (cid:0)n n

Chứng minh: Quy nạp theo n. Với n = 1 kết luận hiển nhiên đúng.

Giả sử kết luận đã đúng cho n − 1 số thực không âm. Với n, xét đa thức

f (x) = (x − a1)(x − a2) . . . (x − an)

có n nghiệm không âm a1, . . . , an với a1 < a2 < · · · < an. đa thức f (cid:48)(x) = 0 có n − 1 nghiệm không âm b1, . . . , bn−1 với ai < bi < ai+1 cho mọi i. Vậy đa thức

= xn−1 − σ1xn−2 + σ2xn−3 − · · · + σn−1 f (cid:48)(x) n n − 1 n

k

n−1

có đa thức đối xứng cơ bản σ1, σ2, σ3, . . . , σn−1 n − 1 n n − 3 n n − 2 n n − 2 n (−1)n−1 n (−1)n−1 n

(cid:62) của các bj. Theo giả thiết quy nạp có (cid:118) (cid:117) (cid:117) (cid:117) (cid:116) (cid:118) (cid:117) (cid:117) (cid:117) (cid:116) (cid:62) · · · (cid:62) (cid:62) · · · (cid:62) (cid:118) (cid:117) (cid:117) (cid:117) (cid:116)

n − 2 σ2 n (cid:1) (cid:0)n−1 2 n − 1 σ1 n (cid:1) (cid:0)n−1 1 n − k σk n (cid:1) (cid:0)n−1 k 1 σn−1 n (cid:1) (cid:0)n−1 n−1

(cid:62) (cid:62) · · · (cid:62) k (cid:62) · · · (cid:62) n−1 hay (cid:1). Bất đẳng thức σ1 (cid:1) (cid:0)n 1 (cid:114) σ2 (cid:1) (cid:0)n 2 (cid:114) σk (cid:1) (cid:0)n k

n−1

+ + · · · + (cid:118) (cid:117) (cid:117) (cid:116) a1a2 . . . an a1 a1a2 . . . an a2 (cid:114) σn−1 (cid:0) n n−1 a1a2 . . . an an √ (cid:62) n cuối là a1a2 . . . an. n

48

Bất đẳng thức này đúng theo Bất đẳng thức Cauchy.

Nhận xét 3.4.5. Kết quả trên vẫn đúng khi có một số ai bằng nhau.

Ví dụ 3.4.6. Với các số dương a, b, c, d, e ta có các bất đẳng thức sau:

(cid:62) 3 (1) . (cid:114)ab + ac + ad + bc + bd + cd 6 (cid:114)abc + abd + acd + bcd 4

3

(cid:62) (2) (cid:114)ab + ac + ad + ae + bc + bd + be + cd + ce + de 10

. (cid:114)abc + abd + abe + acd + ace + ade + bcd + bce + bde + cde 10

(cid:114) (cid:62) 3 (3) . a2 + b2 + c2 + d2 4 (cid:114)abc + abd + acd + bcd 4

Bài giải: (1),(2) được suy ra từ kết quả trên với n = 4, n = 5 và σ2, σ3, tương ứng.

(3) Vì 4(a2 + b2 + c2 + d2) (cid:62) (a + b + c + d)2 nên ta suy ra

4(a2 + b2 + c2 + d2) (cid:62) a2 + b2 + c2 + d2 + 2(ab + ac + ad + bc + bd + cd).

49

. Từ đây suy ra 3 Vậy a2 + b2 + c2 + d2 (cid:62) 2(ab + ac + ad + bc + bd + cd) (cid:114) (cid:62) 3 theo (1). a2 + b2 + c2 + d2 4 (cid:114)abc + abd + acd + bcd 4

Kết luận

Trong luận văn chúng tôi đã trình bày được các kết quả sau:

(1) Phát biểu và chứng minh Định lý không điểm của Hilbert và Định

lý không điểm tổ hợp.

(2) Trình bày những khái niệm cơ bản về lý thuyết đồ thị và ứng

dụng Định lý không điểm tổ hợp vào bài toán tô màu đồ thị.

(3) Trình bày một số kết quả cơ bản về phương pháp đa thức và tổng

thu hẹp các thặng dư.

(4) Trình bày một số kết quả đạt được qua việc vận dụng phương

50

pháp đa thức và tổng thu hẹp các thặng dư.

Tài liệu tham khảo

Tiếng Việt

[1] Lê Thị Thanh Nhàn (2015), Giáo trình Lý thuyết đa thức, NXB Đại

học Quốc gia Hà Nội.

Tiếng Anh

[2] Alon. N (1999), "Combinatorial Nullstellensatz", Combinatorics

Probability and Computing 8, No 1-2, pp. 7-29.

[3] Alon. N, Nathanson. B and Ruzsa. Z (1996), "The polynomial

method and restricted sums of congruence classes", Journal of Num-

51

ber Theory, Volume 56, Issue, February, pages 404-417.