Link tải luận văn miễn phí cho ae Kết nối

1 Kiến thức chuẩn bị
1.1 Dạng chuẩn Hecmit . . . . . . . . . . . . . . . . . . . . .
1.2 Ma trận đơn môđula . . . . . . . . . . . . . . . . . . . .
2 Phương trình Đi-ô-phăng tuyến tính
2.1 Ước chung lớn nhất . . . . . . . . . . . . . . . . . . . . .
2.2 Thuật toán Ơ-clít mở rộng . . . . . . . . . . . . . . . . .
2.3 Phương trình Đi-ô-phăng tuyến tính . . . . . . . . . . . .
2.4 Một số ứng dụng của phương trình Đi-ô-phăng . . . . . .
3 Hệ phương trình Đi-ô-phăng tuyến tính
3.1 Hệ phương trình Đi-ô-phăng tuyến tính . . . . . . . . . .
3.2 Điều kiện tồn tại nghiệm nguyên . . . . . . . . . . . . . .
3.3 Thuật toán Hecmit . . . . . . . . . . . . . . . . . . . . .
3.4 Nghiệm nguyên dương của hệ phương trình Đi-ô-phăng . .
3.5 Quy hoạch tuyến tính Đi-ô-phăng . . . . . . . . . . . . .
Kết luận
Tài liệu tham khảo Phương trình Đi-ô-phăng tuyến tính (Linear Diophantine Equations)
mang tên nhà toán học cổ Hy Lạp Đi-ô-phăng ở xứ Alexandria vào khoảng
Thế kỷ thứ 3 sau Công nguyên. Đi-ô-phăng đã viết một chuyên luận có
tên “Arithmetica”, đó là cuốn sách sớm nhất được biết về lý thuyết số và
đại số.
Phương trình Đi-ô-phăng là phương trình đại số đòi hỏi tìm nghiệm
hữu tỉ hay nguyên. Phương trình đại số là phương trình chỉ bao gồm các
biểu thức đa thức của một hay nhiều biến. Tính “Đi-ô-phăng” của phương
trình là ở chỗ các hệ số của đa thức phải là các số hữu tỉ (hay số nguyên)
và nghiệm cũng chỉ có thể là số hữu tỉ (hay số nguyên).
Hai phương trình quen biết từ lý thuyết số sơ khai, có từ trước thời
Đi-ô-phăng là những ví dụ về phương trình Đi-ô-phăng. Cả hai loại phương
trình này đều đã được người Babylon biết đến. Đó là
1. Phương trình bậc nhất (tuyến tính), hai biến
ax + by = c.
2. Phương trình bậc hai (phi tuyến), ba biến
x2 + y2 = z2.
Luận văn này có mục đích tìm hiểu và trình bày thuật toán Ơ-clít tìm
các nghiệm nguyên của phương trình Đi-ô-phăng tuyến tính n biến có dạng
a1x1 + a2x2 + ... + anxn = b, Ta thấy các ước của 8 là ±1, ±2, ±4, ±8 và các ước của 20 là ±1, ±2,
±4, ±5, ±10. Từ đó, ước chung của 8 và 20 là ±1, ±2, ±4. Vì thế, ước
chung lớn nhất của 8 và 20 là 4. Ta viết (8, 20) = 4.
Định nghĩa 2.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 (relatively prime).
Định lý 2.1. Nếu a, b nguyên dương và (a, b) = d thì (a
d,
b d
) = 1.
Ví dụ sau minh họa cho định lý trên.
Ví dụ 2.2. Xét hai số 20 và 45.
Bằng cách phân tích ra thừa số ta có 20 = 22×5 và 45 = 32×5. Từ đó,
ta tìm được ước chung lớn nhất của 20 và 45 bằng 5, tức là (20, 45) = 5.
Ta thấy
(20
5
,
45
5
) = (4, 9) = 1.
Định lý 2.2. Cho a, b, c là các số nguyên dương. Khi đó (a+cb, b) = (a, b).
Ví dụ 2.3. Xét ba số: a = 110, b = 44, c = 22.
Theo Định lý 2.2, ta sẽ có
(110 + 22 × 44, 44) = (110, 44) hay (1078, 44) = (110, 44).
Để kiểm tra đẳng thức này, ta cần tính (1078, 44) và (110, 44). Ta thấy
44 = 22 × 11, 110 = 2 × 5 × 11 và 1078 = 2 × 72 × 11.
Từ đó suy ra (1078, 44) = (110, 44) = 22. Kết quả kiểm tra đúng.
Định nghĩa 2.3. Cho a và b là hai số nguyên dương. Tổ hợp tuyến tính
(linear combination) của a và b là tổng có dạng ax + by, trong đó x, y là
số nguyên.
Định lý 2.3. Nếu a, b là các số nguyên dương và 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 và c|b) ⇒ c|(ma + nb).

dk3Q2XbjtOG5vlx

---