Tóm tắt Luận văn Hệ phương trình Diophant tuyến tính và một số dạng toán liên quan

BỘ GIÁO DỤC VÀ ĐÀO TẠO

ĐẠI HỌC ĐÀ NẴNG

HUỲNH TẤN ANH TUẤN

HỆ PHƯƠNG TRÌNH

DIOPHANT TUYẾN TÍNH VÀ

MỘT SỐ DẠNG TOÁN LIÊN QUAN

Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP

Mã số: 60 46 01 13

TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC

Người hướng dẫn khoa học:

GS.TSKH. NGUYỄN VĂN MẬU

Đà Nẵng - Năm 2016

Công trình được hoàn thành tại

Đ Ạ I HỌC Đ À NẴNG

Người hướng dẫn khoa học: GS. TSKH. NGUYỄN VĂN MẬU

Phản biện 1: TS. Lê Văn Dũng

Phản biện 2: PGS.TS. Huỳnh Thế Phùng

Luận văn đã được bảo vệ trước Hội đồng chấm Luận văn tốt

nghiệp thạc sĩ Khoa học họp tại Đại học Đà Nẵng vào ngày 13

tháng 8 năm 2016

Có thể tìm hiểu luận văn tại:

- Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng

- Thư viện trường Đại học Sư phạm, Đại học Đà Nẵng

1

MỞ ĐẦU

1. Lí do chọn đề tài:

Chuyên đề phương trình Diophant đóng vai trò rất quan

trọng trong lý thuyết Số học. Đó là chuyên đề trọng tâm xuyên

suốt từ bậc tiểu học tới bậc trung học. Nó không chỉ là đối tượng

nghiên cứu trọng tâm của số học mà còn là công cụ đắc lực trong

nhiều lĩnh vực của phương trình và các ứng dụng khác.

Trong các kỳ thi học sinh giỏi toán quốc gia, Olympic Toán

khu vực và quốc tế thì các bài toán liên quan đến phương trình

Diophant cũng hay được đề cập và được xem như là những dạng

toán thuộc loại khó. Đặc biệt các bài toán về hệ phương trình

Diophant không nằm trong chương trình chính thức của số học ở

bậc trung học phổ thông.

Dưới sự định hướng và hướng dẫn của GS.TSKH Nguyễn

Văn Mậu tôi chọn đề tài “ Hệ phương trình Diophant tuyến tính

và một số dạng toán liên quan” làm đề tài nghiên cứu luận văn

của mình để có điều kiện tìm hiểu thêm về chuyên đề này.

2. Mục đích nghiên cứu:

Mục đích nghiên cứu của đề tài là hệ thống hóa chi tiết

các vấn đề lý thuyết về hệ phương trình Diophant tuyến tính và

hệ thống bài toán,bài tập liên quan để từ đó thấy được tầm quan

trọng và tính thiết thực của hệ phương trình Diophant tuyến tính.

3. Đối tượng và phạm vi nghiên cứu:

2

- Đối tượng nghiên cứu: Hệ phương trình Diophant, một số

dạng toán liên quan và bài tập đặc trưng.

- Phạm vi nghiên cứu: Các tài liệu tham khảo được GS.TSKH

Nguyễn Văn Mậu định hướng.

4. Phương pháp nghiên cứu:

- Tìm, đọc, phân tích một số tài liệu về hệ phương trình

Diophant và các tính chất, bài toán liên quan.

- Làm rõ các chứng minh trong tài liệu, hệ thống kiến thức

nghiên cứu.

5. Ý nghĩa khoa học và thực tiễn của đề tài:

- Hệ thống một cách khoa học những lý thuyết về hệ phương

trình Diophant và tính chất liên quan.

- Nêu và giải quyết các bài toán liên quan và ý nghĩa của

các bài toán liên quan trong dạy học, nghiên cứu toán học và thực

tiễn cuộc sống.

- Góp phần làm một tài liệu tham khảo cho việc dạy học và

bồi dưỡng học sinh giỏi số học ở phổ thông.

6. Cấu trúc của luận văn:

Luận văn gồm phần mở đầu, ba chương, phần kết luận và

danh mục tài liệu tham khảo.

Chương 1. Phương trình Diophant tuyến tính.

Chương 2. Hệ phương trình Diophant tuyến tính.

Chương 3. Một số dạng toán liên quan.

3

CHƯƠNG 1

PHƯƠNG TRÌNH DIOPHANT

TUYẾN TÍNH

Chương này trình bày về thuật toán Euclid tìm ước chung

lớn nhất của các số nguyên dương và đề cập tới phương trình

Diophant tuyến tính hai hay nhiều biến. Nêu điều kiện (cần và

đủ) tồn tại nghiệm nguyên và thuật toán tìm nghiệm nguyên của

phương trình. Một số bài toán tìm nghiệm nguyên dương của

phương trình Diophant tuyến tính. Nội dung của chương được

tham khảo chủ yếu từ các tài liệu [1], [4], và [6].

1.1. PHƯƠNG TRÌNH DIOPHANT TUYẾN TÍNH

TRÊN TẬP SỐ NGUYÊN

1.1.1. Ước chung lớn nhất

Ta nhắc lại khái niệm ước chung lớn nhất của hai số nguyên

dương và một số tính chất cơ bản .

Định nghĩa 1.1 ([1]). Cho hai số nguyên a, b > 0. Ta định

nghĩa ước chung lớn nhất (greatest common divisor) của a và b là

số nguyên dương lớn nhất c mà cả a và b đều chia hết cho c . Ước

chung lớn nhất được kí hiệu là (a, b) = c hoặc gcd(a, b) = c. Ta sẽ

sử dụng (a, b) để chỉ ước chung lớn nhất của a và b. Ta cũng dùng

kí hiệu a|b để chỉ a là ước số của b hay b chia hết cho a .

Định nghĩa 1.2. Nếu ước chung lớn nhất (a, b) = 1 thì ta

nói hai số nguyên dương a và b là nguyên tố cùng nhau.

4

Định lý 1.1. Nếu a, b nguyên dương và (a, b) = d thì

ꢀ

ꢁ

a

d

b

d

,

= 1.

Định lý 1.2. Cho a, b, c là các số nguyên dương.

Khi đó (a + cb, b) = (a, b).

Định nghĩa 1.3. Cho a và b hai số nguyên dương. Tổ hợp

tuyến tính của a và b có dạng ax + by, trong đó x, y là số nguyên.

Định lý 1.3. Cho a và b là hai số nguyên dương, c là ước

số chung của a và b thì c cũng là ước số của ma + nb với m, n là

các số nguyên, nghĩa là

(c|a; c|b) ⇒ c|(ma + nb).

Định lý 1.4. Cho hai số nguyên a, b > 0. Khi đó d = (a, b)

là số nguyên dương nhỏ nhất biểu diễn được dưới dạng ax + by

với x, y nguyên.

Định lý 1.5. Nếu a, b là các số nguyên dương thì tập hợp

các tổ hợp tuyến tính của a và b trùng với tập các bội nguyên của

(a, b).

Định nghĩa 1.4. Ta mở rộng định nghĩa ước chung lớn nhất

cho n số nguyên dương với n ≥ 2. Xét n số nguyên dương. Ta định

nghĩa ước chung lớn nhất của chúng là số lớn nhất trong các ước

chung của n số đó và kí hiệu là (a₁, a₂, ..., a_n).

Định lý 1.6. Nếu a₁, a₂, ..., a_nlà các số nguyên dương thì

5

(a₁, a₂, ..., a_n−1, a_n) =(a₁, a₂, ..., (a_n−1, a_n))

Bổ đề 1.1. Nếu c và d hai số nguyên dương và c = dq + r,

với q và r nguyên dương thì (c, d) = (r, d).

1.1.2. Thuật toán Euclid mở rộng

Mục này đề cập tới thuật toán Euclid quen thuộc để tìm

ước chung lớn nhất của hai số nguyên dương. Đó là thuật toán

cực kì nhanh để tìm ước chung lớn nhất.

Định lý 1.7 (Thuật toán Euclid ). Để tìm ước chung lớn

nhất của hai số nguyên dương a và b ta đặt r₋₁= a, r₀= b, rồi

tính liên tiếp thương q_i+1và số dư r_i+1theo r_i−1= r_iq_i+1+ r_i+1

với i = 0,1,2,... cho tới khi gặp số dư r_n+1= 0. Khi đó, số dư khác

không cuối cùng r_nsẽ là ước chung lớn nhất của a và b.

Định lý 1.8. Cho a, b là hai số nguyên dương. Khi đó

(a, b) = k_n.a + m_n.b,

với k_nvà m_nlà số hạng thứ n của dãy số được xác định theo đệ

quy bởi

k₋₁= 1, m₋₁= 0, k₀, m₀= 1 và

k_i= k_i−2− k_i−1.q_i, m_i= m_i−2− m_i−1.q_ivới i = 1, 2, ..., n

trong đó q_ilà thương số của phép chia trong thuật toán Euclid,

khi thuật toán được dùng để tìm ước chung lớn nhất của a và b.

1.1.3. Phương trình Diophant tuyến tính trên tập số

nguyên

6

Định nghĩa 1.5. Phương trình Diophant là phương trình

đa thức với các hệ số nguyên và nghiệm của phương trình cũng là

số nguyên hoặc số tự nhiên. Phương trình Diophant cơ bản nhất

là phương trình Diophant tuyến tính.

Ví dụ phương trình ax+by = c với a, b, c ∈ Z (Z là tập hợp

các số nguyên).

Định lý 1.9. Cho a, b và c là các số nguyên với a và b không

cùng bằng 0, Phương trình Diophant tuyến tính ax + by = c có

nghiệm khi và chỉ khi d = (a, b) là ước của c.

Định lý 1.10. Cho a và b là hai số nguyên không cùng

bằng 0 với d = (a, b). Phương trình ax + by = c không có nghiệm

nguyên khi c không chia hết cho d. Nếu d|c thì phương trình có

vô số nghiệm nguyên. Hơn nữa, nếu x = x₀, y = y₀là một nghiệm

riêng của phương trình thì mọi nghiệm của phương trình có dạng

b

d

a

d

x = x₀+ .n, y = y₀− .n

trong đó n là số nguyên. Biểu thức trên gọi là nghiệm tổng quát

của phương trình.

Định lý 1.11. Nếu a₁, a₂, ..., a_nlà các số nguyên dương thì

phương trình a₁x₁+ a₂x₂+ · · · + a_nx_n= c có nghiệm nguyên khi

và chỉ khi c chia hết cho d = (a₁, a₂, ..., a_n). Thêm vào đó, nếu

phương trình có nghiệm thì phương trình sẽ có vô số nghiệm.

1.2. PHƯƠNG TRÌNH DIOPHANT TUYẾN TÍNH

TRÊN TẬP SỐ NGUYÊN DƯƠNG

7

Trong nhiều bài toán thực tế người ta cần tìm nghiệm nguyên

dương của phương trình Diophant tuyến tính. Trong những bài

toán đó, cũng có thể dùng thuật toán Euclid và thuật toán Euclid

mở rộng để tìm nghiệm nguyên dương của phương trình cần giải .

8

CHƯƠNG 2

HỆ PHƯƠNG TRÌNH DIOPHANT

TUYẾN TÍNH

Chương này nhắc lại khái niệm về dạng chuẩn Hecmit ,ma trận

đơn Modula có liên quan tới việc giải hệ phương trình Diophant

tuyến tính, các điều kiện cần và đủ để hệ có nghiệm nguyên, thuật

toán tìm nghiệm riêng và nghiệm tổng quát của hệ. Một số bài

toán tìm nghiệm nguyên dương của hệ phương trình Diophant

tuyến tính.Nội dung chương được tham khảo chủ yếu từ các tài

liệu [1]-[6]

2.1. HỆ PHƯƠNG TRÌNH DIOPHANT TUYẾN

TÍNH TRÊN TẬP SỐ NGUYÊN

2.1.1. Dạng chuẩn Hecmit

Định nghĩa 2.1. Một ma trận cấp m × n có hạng bằng số

hàng của ma trận được gọi là ở dạng chuẩn Hecmit nếu:

- Ma trận có dạng [BO] , trong đó B là ma trận cấp m × m

có nghịch đảo;

- B có dạng tam giác dưới;

- Các phần tử đường chéo của B dương;

- Mọi phần tử khác của B không âm;

- Phần tử lớn nhất ở mỗi hàng của B là duy nhất và nằm trên

đường chéo chính của B, còn O là ma trận không cấp m×(n − m).

9

Định nghĩa 2.2. Các phép toán sau về ma trận được gọi là

phép toán cột sơ cấp:

a) Đổi chỗ hai cột;

b) Nhân một cột với -1 (tức đổi dấu một cột);

c) Thêm một bội nguyên của một cột vào một cột khác.

Định lý 2.1 ([1]). Mọi ma trận với hệ số hữu tỉ có hạng

bằng hàng của ma trận có thể đưa về dạng chuẩn Hecmit bằng

cách thực hiện các phép toán cột sơ cấp.

Định nghĩa 2.3. Tập hợp G ⊂ Rⁿgọi là một nhóm (cộng

tính) nếu có

(i) θ ∈ G (nhóm chứa phần tử không)

(ii) Nếu x, y ∈ G thì x + y ∈ G và −x ∈ G (tổng các phần

tử thuộc nhóm và phần tử đối của một phần tử thuộc nhóm phải

là một phần tử thuộc nhóm).

Ta nói nhóm sinh bởi các véctơ a¹, a², ..., a^m∈ Rⁿnếu

ꢂ

G = λ₁a¹+ · · · + λ_ma^m|λ₁, ....., λ_m∈Z

Định nghĩa 2.4. Nhóm G được gọi là một dàn nếu G sinh

bởi các véctơ độc lập tuyến tính. Khi đó, tập hợp các véctơ này

được gọi là một cơ sở của dàn.

Hệ quả 2.1. Nếu a¹, a², ..., a^mlà các véctơ hữu tỉ thì nhóm

sinh bởi a¹, a², ..., a^mlà một dàn, nghĩa là nhóm đó sinh bởi các

véctơ độc lập tuyến tính.

10

Định lý 2.2 ([1]). Giả sử A và A⁰là hai ma trận hữu tỉ với

hạng bằng số hàng có dạng chuẩn Hecmit tương ứng là [BO] và

[B⁰O]. Khi đó, các cột của A và các cột của A⁰sinh ra cùng một

dàn như nhau khi và chỉ khi B = B⁰.

Hệ quả 2.2. Mọi ma trận hữu tỉ với hạng bằng số hàng có

duy nhất một dạng chuẩn Hecmit.

Nhận xét: Nếu b₁₁, ..., b_mmlà các phần tử đường chéo của

dạng chuẩn Hecmit [BO] của A thì với mọi j = 1, ..., m tích số

b₁₁× · · · × b_ijbằng ước chung lớn nhất của các định thức con cấp

j của j hàng đầu của A (do ước này bất biến đối với các phép

toán cột sơ cấp). Điều này cho một cách khác để thấy rằng đường

chéo chính trong dạng chuẩn Hecmit là duy nhất.

2.1.2. Ma trận đơn modula

Các phép toán cột sơ cấp của ma trận còn có thể được mô

tả bởi cái được gọi là các ma trận đơn modula. Trước hết, ta chú

ý là mỗi phép toán cột sơ cấp trên ma trận A cấp m × n đều có

thể thực hiện bằng cách nhân bên phải A với một ma trận sơ cấp

tương ứng E cấp n × n, cụ thể E là ma trận thu được bằng cách

áp dụng cùng phép toán đó trên ma trận đơn vị cấp n × n.

Cho A là ma trận m hàng, n cột (m ≤ n) và I_nlà ma trận

đơn vị cấp n × n. Khi đó:

a) Phép đổi chỗ hai cột i và j của A tương đương với phép

nhân A với ma trận nhận được từ I_nbằng cách đổi chỗ hai cột i

và j.

11

b) Phép nhân cột j của A với −1 tương đương với phép

nhân A với ma trận nhận được từ I_nbằng cách đổi dấu cột j.

c) Thêm bội nguyên k của cột i vào cột j của A tương

đương với nhân A với ma trận nhận được từ I_nbằng cách thêm

bội nguyên k của cột i vào cột j.

Định nghĩa 2.5. Cho U là một ma trận vuông không suy

biến. Khi đó, U được gọi là ma trận đơn modula nếu U nguyên

và có định thức bằng ±1. Cũng có thể mở rộng khái niệm đơn

modula cho cả các ma trận suy biến. Các ma trận đơn modula

đã được các nhà toán học Smith, Frobenius, Veblen và Franklin

nghiên cứu.

Sau đây là một số tính chất đáng chú ý của ma trận đơn

modula.

Định lý 2.3 ([1]). Các điều sau tương đương đối với mọi

ma trận hữu tỉ không suy biến U cấp n × n:

(i) U là đơn modula;

(ii) U⁻¹là đơn modula;

(iii) Dàn sinh bởi các cột của U là Zⁿ(không gian véctơ

nguyên n chiều);

(iv) Ma trận đơn vị là dạng chuẩn Hecmit của U;

(v) U nhận được từ ma trận đơn vị bằng các phép toán

cột sơ cấp.

Hệ quả 2.3. Cho A và A⁰là hai ma trận không suy biến

(cùng cấp).

12

Khi đó, các điều sau tương đương:

(i) Các cột của A và các cột của A⁰sinh ra cùng một dàn;

(ii) A⁰nhận được từ A bằng các phép toán cột sơ cấp;

(iii) A⁰= AU với ma trận đơn modula U nào đó (tức

⁻¹A⁰đơn modula).

A

2.1.3. Hệ phương trình Diophant tuyến tính trên tập

số nguyên

Cho ma trận A cấp m × n (tức ma trận với mọi phần tử

hữu tỉ) và véctơ hữu tỉ b với m thành phần, hãy tìm véctơ nguyên

x sao cho

Ax = b

(2.1)

Ta có thể viết lại hệ này ở dạng chi tiết như sau: Tìm

x₁, x₂, ..., x_nnguyên thỏa mãn



a₁₁x₁+ a₁₂x₂+ ..... + a_1nx_n= b₁





a₂₁x₁+ a₂₂x₂+ ..... + a_2nx_n= b₂

..................................................

a_m1x₁+ a_m2x₂+ ..... + a_mnx_n= b_m





trong đó a₁₁, a₁₂, ..., a_mnvà b₁, b₁, ..., b_mlà các số hữu tỉ (1 ≤ m ≤ n).

2.1.4. Điều kiện tồn tại nghiệm nguyên

Sau đây là một điều kiện cần và đủ để hệ phương trình

Diophant tuyến tính Ax = b có nghiệm nguyên.

Định lý 2.4 ([1]). Giả sử A là một ma trận hữu tỉ có hạng

bằng số hàng của A và b là véctơ cột hữu tỉ. Khi đó, hệ Ax = b có

nghiệm nguyên x khi và chỉ khi yb là số nguyên đối với mọi véctơ

hàng hữu tỉ y mà yA là véctơ nguyên.

13

Cho A là một ma trận hữu tỉ. Kí hiệu L là dàn sinh bởi các

véctơ cột của A . Định lí 2.4 cho một điều kiện cần và đủ để véctơ

hữu tỉ b ∈ L. Cụ thể là từ chứng minh Định lí 2.4 cho thấy rằng

nếu A có hạng bằng số hàng của nó và nếu dạng chuẩn Hecmit

của A là [BO] ( B có dạng tam giác dưới) thì b ∈ L khi và chỉ khi

B

⁻¹b là véctơ nguyên. Một điều kiện cần và đủ khác như sau:

Định lý 2.5 ([1]). Cho A là một ma trận nguyên cấp m×n

và rank(A) = m. Khi đó, ba điều sau tương đương:

(i) Các định thức con cấp m của A có ước chung lớn nhất

bằng 1 ;

(ii) Hệ Ax = b có nghiệm nguyên x đối với mọi véctơ

nguyên ;

(iii) Với mọi véctơ y , nếu y^TA là véctơ nguyên thì y

nguyên.

Từ Định lí 2.1 có thể dễ dàng suy ra rằng đối với bất kỳ hệ

hữu tỉ Ax = b có ít nhất một nghiệm nguyên sẽ tồn tại các véctơ

nguyên x¹, ..., x^tsao cho

ꢂ

{x |Ax = b, x ∈} = x⁰+ λ₁x¹+ · · · + λ_tx^t|λ₁, ...., λ_t∈

trong đó x¹, ..., x^tđộc lập tuyến tính và t = (số cột của A )

−rank(A) . Sự tồn tại của một hệ nghiệm cơ bản như thế đã

được Smith phát biểu năm 1861.

2.1.5. Thuật toán Hecmit

Mục này trình bày thuật toán Hecmit tìm dạng tổng quát

14

cho các nghiệm nguyên của hệ phương trình Diophant tuyến tính

Ax = b, trong đó A là ma trận nguyên cấp m × n, rank(A) = m

và b là véctơ nguyên gồm m thành phần.

Như đã biết (Hệ quả 2.4) với A, b như trên, tồn tại ma trận

đơn modula U sao cho H = AU là dạng chuẩn Hecmit của A, tức

H = [BO] với B cấp m × m không âm, có dạng tam giác dưới,

không suy biến và mỗi hàng của B có duy nhất một phần tử lớn

nhất, nằm trên đường chéo chính của B.

Theo định nghĩa của ma trận modula, U có nghịch đảo U⁻¹

. Do đó hệ Ax = b có thể viết lại ở dạng tương đương AUU⁻¹x = b

. Đặt H = AU , y = U⁻¹x ∈ R hay x = Uy, ta thấy hệ Ax = b

trở thành hệ phương trình tuyến tính với ma trận hệ số có dạng

tam giác Hy = b và x = Uy. Từ đó nếu véctơ y nguyên thì nghiệm

x = Uy cũng nguyên.

Do là ma trận đơn modula ( tức nguyên và detU = ±1 )

nên theo Định lí 2.3, U⁻¹cũng nguyên và detU = ±1 . Vì thế,

mối quan hệ y = U⁻¹x và x = Uy giữa hai véctơ nguyên x và y

là quan hệ hai chiều. Giải hệ tam giác

Hy = b

(2.2)

ta nhận được nghiệm y_i= y_i⁰, i = 1, ..., m. Nếu y_i⁰nguyên, ta nhận

được một nghiệm nguyên của hệ (2.1) ban đầu. Nếu trái lại ( tồn

tại i với y_i⁰không nguyên ) thì hệ (2.1) không có nghiệm nguyên.

Như vậy, sự tồn tại nghiệm nguyên của hệ (2.1) quy về sự tồn tại

nghiệm nguyên của hệ (2.2). Kí hiệu U = (u_kj)_n×nvà chú ý rằng

15

x = Uy ta nhận được dạng tổng quát cho các nghiệm nguyên của

hệ (2.1) ( phụ thuộc n − m tham số nguyên y_i):

m

n

X

x_k=

u_kjy_j⁰+

u_kjy_j, k = 1, 2, ....., n

(2.3)

j=0

j=m+1

trong đó y_j(m + 1 ≤ j ≤ n) là các tham số nguyên tùy ý (giá trị

các biến tự do) hay ở dạng véctơ x = Uy

với y = (y₁⁰, ......, y_m⁰, y_m+1, ......, y_n)^T, y_j∈ Z, j = m + 1, ...., n

Thuật toán Hecmit (tóm tắt) giải hệ Ax = b, gồm các bước

sau:

- Biến đổi A về dạng chuẩn Hecmit H = [BO] .

- Tìm ma trận đơn modula U sao cho H = AU .

- Giải phương trình Hy = b tìm nghiệm nguyên y⁰

=

ꢀ

ꢁ

y₁⁰, ....., y_m⁰

- Tìm nghiệm tổng quát của Ax = b theo công thức (2.3)

2.2. HỆ PHƯƠNG TRÌNH DIOPHANT TUYẾN

TÍNH TRÊN TẬP SỐ NGUYÊN DƯƠNG

Trong nhiều bài toán thực tế người ta cần tìm nghiệm nguyên

dương ( chứ không đơn thuần nghiệm nguyên ) của hệ phương

trình Diophant tuyến tính.

Mục này sẽ trình bày về hệ hai phương trình ba ẩn với

nghiệm nguyên dương giải bằng phương pháp “ chìa khóa”

Bài toán tổng quát : Tìm nghiệm nguyên dương của hệ

phương trình

ꢃ

a₁x + b₁y + c₁z = s₁

(1)

a₂x + b₂y + c₂z = s₂

16

Phương pháp:

Ta gọi “chìa khóa” của hệ (1) là bộ số (x₀, y₀, z₀) thỏa mãn:

x₀, y₀, z₀∈ Z và

ꢃ

a₁x₀+ b₁y₀+ c₁z₀= 0

a₂x₀+ b₂y₀+ c₂z₀= 0

Nếu (x₁, y₁, z₁) là một nghiệm của hệ (1) thì với

x₂= x₁+ mx₀; y₂= y₁+ my₀; z₂= z₁+ mz₀

ta cũng có

a₁x₂+ b₁y₂+ c₁z₂= s₁; a₂x₂+ b₂y₂+ c₂z₂= s₂

tức là (x₂, y₂, z₂) cũng là một nghiệm của hệ (1). Nếu các nghiệm

này nguyên dương thì ta có nghiệm nguyên dương. Ta chú ý rằng

trong hệ (1) nếu x xác định thì y và z cũng xác định. Vì vậy khi ta

cho x chạy qua tất cả các giá trị nguyên dương có thể có của nó,

ta sẽ tìm được các giá trị tương ứng của y và z. Trong các trường

hợp này, có bao nhiêu trường hợp các giá trị tương ứng của y và

z đều nguyên dương thì hệ có bấy nhiêu nghiệm nguyên dương.

Ngoài ra ta còn áp dụng thuật toán Hecmit để tìm nghiệm

nguyên dương của hệ phương trình Diophant tuyến tính Ax =

b,trong đó A ∈ R^m×nlà ma trận nguyên và rank (A) = m, b ∈ R^m

là véctơ nguyên.

17

CHƯƠNG 3

MỘT SỐ DẠNG TOÁN LIÊN QUAN

Chương này đề cập tới một số dạng toán liên quan đến hệ

phương trình Diophant tuyến tính : Phân thức chính quy và bài

toán quy hoạch tuyến tính nguyên. Nội dung của chương được

tham khảo chủ yếu từ các tài liệu [3],[7]

3.1. PHÂN THỨC CHÍNH QUY

3.1.1. Định nghĩa và các tính chất

Mục này trình bày một số định nghĩa và các tính chất về

phân thức chính quy.

Định lý 3.1 ([3]). (Bất đẳng thức AM − GM suy rộng). Giả

sử cho trước hai dãy số dương x₁, x₂, · · · , x_n; p₁, p₂, · · · , p_n.Khi

đó

ꢄ

ꢅ

p₁+p₂+···+p_n

x₁p₁+ x₂p₂+ · · · + x_np_n

p₁+ p₂+ · · · + p_n

x^p₁¹.x^p₂².....x^p_nⁿ

≤

Dấu đẳng thức xảy ra khi và chỉ khi x₁= x₂= · · · = x_n

Định nghĩa 3.1. Hàm số f(x) xác định trên R⁺được gọi là

hàm phân thức chính quy nếu

n

X

a_kx^α

k

f (x) =

k=1

18

trong đó

n

X

a_k≥ 0, k = 1, 2, ...., n;

a_kα_k= 0

k=1

Từ định nghĩa trên ta có các tính chất sau.

Tính chất 3.1. Nếu f(x) là hàm phân thức chính quy thì

f(x) > 0 ứng với mọi x > 0

Tính chất 3.2. Nếu f(x) và g(x) là các hàm phân thức chính

quy thì với mọi cặp số dương α, β, hàm số

h (x) := αf (x) + βg (x)

cũng là hàm phân thức chính quy.

Tính chất 3.3. Nếu f(x) và g(x) là các hàm phân thức chính

quy thì hàm số

h (x) := f (g (x))

cũng là hàm phân thức chính quy.

Tính chất 3.4. Nếu f(x) là hàm phân thức chính quy thì

hàm số

h (x) := [f (x)]^m, m ∈ N^∗

cũng là hàm phân thức chính quy.

Tương tự ta định nghĩa hàm phân thức chính quy nhiều biến

sau.