Đề tài đã hệ thống lại lý thuyết về thặng dư, thặng dư bình phương; hoàn thiện về phương trình thặng dư và cách giải; tập trung trình bày một vài ứng dụng của thặng dư và thặng dư bình phương; tổng hợp một số bài toán thặng dư, thặng dư bình phương trong các kì thi Olympic Toán các nước.
AMBIENT/
Chủ đề:
Nội dung Text: Tóm tắt luận văn Thạc sĩ Khoa học: Thặng dư và thặng dư bình phương
- ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
------------
MAI THỊ NGỌC
THẶNG DƯ VÀ THẶNG DƯ
BÌNH PHƯƠNG
LUẬN VĂN THẠC SĨ TOÁN HỌC
Hà Nội – 2016
- ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
------------
MAI THỊ NGỌC
THẶNG DƯ VÀ THẶNG DƯ
BÌNH PHƯƠ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
Người hướng dẫn khoa học : GS.TSKH. Nguyễn Văn Mậu
Hà Nội - Năm 2016
- i
Mục lục
MỞ ĐẦU 3
1 Một số kiến thức cơ bản 5
1.1 Thặng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Thặng dư . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.2 Lớp thặng dư . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Hệ thặng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1 Hệ thặng dư đầy đủ . . . . . . . . . . . . . . . . . . . 9
1.2.2 Hệ thặng dư thư gọn . . . . . . . . . . . . . . . . . . 11
1.3 Các định lý cơ bản về thặng dư . . . . . . . . . . . . . . . . . 14
1.3.1 Định lý Euler và định lý Fermat . . . . . . . . . . . . 15
1.3.2 Định lý thặng dư Trung Hoa . . . . . . . . . . . . . . 17
1.4 Thặng dư bình phương . . . . . . . . . . . . . . . . . . . . . 18
1.4.1 Tiêu chuẩn thặng dư bình phương . . . . . . . . . . . 18
1.4.2 Kí hiệu Legendre . . . . . . . . . . . . . . . . . . . . 20
1.4.3 Luật tương hỗ bậc hai . . . . . . . . . . . . . . . . . . 26
1.4.4 Thặng dư bình phương với modulo hợp số . . . . . . . 30
1.4.5 Nhận xét về thặng dư bậc cao . . . . . . . . . . . . . 33
2 Phương trình thặng dư 34
2.1 Phương trình thặng dư một ẩn . . . . . . . . . . . . . . . . . 34
2.1.1 Phương trình thặng dư một ẩn . . . . . . . . . . . . . 34
2.1.2 Phương trình thặng dư tuyến tính . . . . . . . . . . . 35
2.1.3 Phương trình thặng dư modulo nguyên tố . . . . . . . 38
2.1.4 Hệ phương trình thặng dư bậc nhất một ẩn . . . . . . 40
2.2 Phương trình bậc nhất nhiều ẩn . . . . . . . . . . . . . . . . 46
2.2.1 Phương trình bậc nhất hai ẩn . . . . . . . . . . . . . . 46
2.2.2 Phương trình Diophant bậc nhất tổng quát . . . . . . 48
- ii
2.3 Phương trình Diophant phi tuyến . . . . . . . . . . . . . . . 51
2.3.1 Phương trình Pythagore . . . . . . . . . . . . . . . . . 51
2.3.2 Biểu diễn một số dưới dạng tổng hai bình phương . . . 54
3 Một số dạng toán liên quan đến thặng dư và thặng dư bình
phương 58
3.1 Một số dạng toán liên quan đến thặng dư . . . . . . . . . . . 58
3.2 Một số dạng toán của thặng dư bình phương . . . . . . . . . 62
3.2.1 Ứng dụng trong bài toán chứng minh chia hết . . . . . 62
3.2.2 Ứng dụng trong tập hợp các số nguyên tố . . . . . . . 65
3.2.3 Ứng dụng trong các bài toán dãy số nguyên và đa thức 68
3.2.4 Phương trình nghiệm nguyên . . . . . . . . . . . . . . 72
4 Một số dạng toán về thặng dư từ các đề thi Olympic 77
4.1 Sử dụng hệ thặng dư đầy đủ trong bài toán đếm . . . . . . . 77
4.2 Bài toán tính tổng và chứng minh đẳng thức số . . . . . . . . 81
4.3 Một số bài toán liên quan số học . . . . . . . . . . . . . . . . 83
4.3.1 Quan hệ thặng dư . . . . . . . . . . . . . . . . . . . . 83
4.3.2 Định lý Fermat nhỏ và định lý Euler . . . . . . . . . . 85
4.3.3 Một số bài toán số Fermat . . . . . . . . . . . . . . . 90
Kết luận 94
Tài liệu tham khảo 95
- 3
Mở đầu
1. Lý do chọn đề tài
Lý thuyết thặng dư - lý thuyết đặc biệt quan trọng trong số học và đã
được nhiều nhà Toán học nghiên cứu, vận dụng trong việc giải nhiều bài toán
hay, khó và có ứng dụng thực tế.
Trong các kì thi Olympic Toán học ở Việt Nam và các nước trên thế giới
thì lý thuyết thặng dư là phần được quan tâm đáng kể, vì thế việc có những
hiểu biết ban đầu về thặng dư sẽ giúp ta giải nhiều bài toán khó trong số
học một cách nhẹ nhàng, ngắn gọn và đẹp.
Tuy nhiên, trong nhà trường phổ thông thì thời lượng giảng dạy cho
phần lý thuyết thặng dư chưa nhiều nên học sinh thường thấy phần kiến
thức này rất khó, vượt ra hiểu biết của các em. Vì vậy để giúp bản thân có
những hiểu biết sâu sắc hơn về lý thuyết thặng dư, phục vụ tốt hơn cho công
tác bồi dưỡng học sinh giỏi, tôi chọn đề tài "Thặng dư và thặng dư bình
phương" để nghiên cứu.
2. Mục tiêu nghiên cứu
Hệ thống lý thuyết, tổng hợp một số dạng toán quan trọng về thặng dư
và thặng dư bình phương.
3. Nhiệm vụ nghiên cứu
Chương 1 hệ thống lại lý thuyết về thặng dư, thặng dư bình phương.
Ở chương 2 hoàn thiện về phương trình thặng dư và cách giải, còn chương
3 tập trung trình bày một vài ứng dụng của thặng dư và thặng dư bình
phương. Cuối cùng, chương 4 tổng hợp một số bài toán thặng dư, thặng dư
bình phương trong các kì thi Olympic Toán các nước.
4. Khách thể và đối tượng nghiên cứu
Đối tượng nhiên cứu là lý thuyết thặng dư, thặng dư bình phương và
ứng dụng của chúng.
5. Phạm vi nghiên cứu
Nghiên cứu lý thuyết và ứng dụng của thặng dư, thặng dư bình phương.
- 4
6. Phương pháp nghiên cứu
Để thực hiện luận văn tác giả chủ yếu thu thập và nghiên cứu các tài
liệu từ nhiều nguồn khác nhau, rồi phân tích lý thuyết về thặng dư, thặng
dư bình phương, từ đó xây dựng một số ứng dụng của nó và biên tập theo
hệ thống từ cách hiểu của bản thân.
7. Giả thuyết khoa học
Nếu luận văn được thực hiện thành công, nó sẽ là một tài liệu tham
khảo bổ ích cho giáo viên và học sinh muốn tìm hiểu về thặng dư, thặng dư
bình phương. Trong đó phần lý thuyết được chứng minh chặt chẽ, các bài
toán ứng dụng được hệ thống theo dạng và tương đối đầy đủ và cập nhật
theo mức độ từ dễ đến khó.
8. Đóng góp mới của đề tài
Luận văn đã chỉ ra được một số dạng toán ứng dụng lý thuyết thặng
dư, thặng dư bình phương, từ đó đề xuất được một số bài tập mang tính cập
nhật.
9. Cấu trúc của luận văn
Cấu trúc của luận văn gồm ba phần: phần mở đầu, phần nội dung và
phần kết luận.
Nội dung luận văn gồm bốn chương:
- Chương 1. Một số kiến thức cơ bản
- Chương 2. Phương trình thặng dư
- Chương 3. Một số dạng toán liên quan đến thặng dư và thặng dư bình
phương
- Chương 4. Một số dạng toán về thặng dư từ các đề thi Olympic
Để hoàn thành luận văn, em đã nhận được sự giúp đỡ của thầy cô, bạn
bè, đặc biệt là sự chỉ bảo hướng dẫn tận tình của GS.TSKH Nguyễn Văn
Mậu, cùng các thầy cô trong Seminar bộ môn Toán của trường Đại học Khoa
học Tự nhiên - Đại học Quốc gia Hà Nội. Em xin bày tỏ lòng biết ơn chân
thành tới GS.TSKH Nguyễn Văn Mậu và các thầy cô giáo trong khoa Toán
- Cơ - Tin học, trường Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà
Nội đã hướng dẫn em hoàn thành khóa học Cao học 2014-2016.
Do thời gian thực hiện luận văn không nhiều, kiến thức còn hạn chế nên
khi làm luận văn không tránh khỏi những hạn chế và sai sót. Em mong nhận
được sự góp ý và những ý kiến phản biện của quý thầy cô và bạn đọc.
Em xin chân thành cảm ơn!
- 5
Chương 1
Một số kiến thức cơ bản
Thặng dư là một khái niệm cơ bản và quan trọng của lý thuyết số. Khái
niệm thặng dư do Kaclơ Friđơrich Gauss (1777-1855) trình bày trong tác phẩm
"Disquistiones Arthmeticcae" năm 1801. Trong chương này trình bày lại một số
kiến thức quan trọng về thặng dư và thặng dư bình phương.
1.1 Thặng dư
1.1.1 Thặng dư
.
Định nghĩa 1.1. Cho m là số nguyên dương, a, b là các số nguyên sao cho (a−b).. m,
ta nói a và b đồng dư hay thặng dư modulo m, và viết
a = b (mod m)
Ví dụ 1.1. Dễ thấy −12 = 43 (mod 5) và −12 = 43 (mod 11), nhưng −12 không
cùng thặng dư với 43 (mod 7); Mỗi số nguyên chẵn thặng dư với 0 modulo 2, và
mỗi số nguyên lẻ thặng dư với 1 modulo 2; Nếu x không chia hết cho 3, thì x2 = 1
(mod 3).
Định lý 1.1. Phép thặng dư a = b (mod m) có nghĩa khi và chỉ khi hiệu a − b chia
hết cho m. Nói cách khác, các số a và b có cùng số dư khi chia cho m, nếu và chỉ
nếu hiệu a − b chia hết cho m.
Chứng minh. Giả sử a = b (mod m). Khi đó các số a và b có cùng số dư r khi
chia cho m.
Bởi vậy a = mq + r, b = mq0 + r, trong đó q, q0 là các số nguyên nào đó.
Trừ vế với vế hai đẳng thức trên ta được a − b = mq − mq0 = m(q − q0 ).
Do đó hiệu a − b chia hết cho m.
- 6
Ngược lại, giả sử hiệu a − b chia hết cho m.
Khi đó tồn tại số nguyên k , để a − b = k.m.
Chia (có dư) số b cho m ta được b = q.m + r, trong đó 0 ≤ r < m.
Cộng vế với vế các đẳng thức trên, ta được a = k.m + q.m + r = (k + q).m + r
đồng thời r vẫn thoả mãn bất đẳng thức kép 0 ≤ r < m, nghĩa là a có cùng số dư
với b khi chia cho m, tức a = b (mod m).
Từ định lý 1.1 ta rút ra được một số nhận xét sau:
Nhận xét 1.1. Các phép thặng dư có thể cộng vế với vế, nghĩa là, nếu ai = bi
(mod m), thì
a1 + a2 + · · · + an = b1 + b2 + · · · + bn (mod m).
Nói cách khác, nếu ai và bi có cùng số dư khi chia cho m, thì các tổng a1 +a2 +· · ·+an
và b1 + b2 + · · · + bn cũng có cùng số dư khi chia cho m.
Chứng minh. Vì ai = bi (mod m) (0 ≤ i ≤ n), nên theo định lý 1.1, các số
ai − bi (0 ≤ i ≤ n) chia hết cho m.
Bởi vậy tồn tại các số nguyên ki để ai − bi = ki .m. Khi đó
(a1 + a2 + · · · + an ) − (b1 + b2 + · · · + bn )
= (a1 − b1 ) + (a2 − b2 ) + · · · + (am − bm )
= k1 m + k2 m + · · · + kn m = (k1 + k2 + · · · + kn )m
Vậy (a1 + a2 + · · · + an ) − (b1 + b2 + · · · + bn ) chia hết cho m, nên, theo định lý 1.1,
a1 + a2 + · · · + ai + · · · + an = b 1 + b 2 + · · · + b i + · · · + b n (mod m).
Nhận xét 1.2. Các phép thặng dư có thể trừ vế với vế, nghĩa là từ a = b (mod m)
và c = d (mod m) suy ra a − c = b − d (mod m).
Chứng minh. Vì a = b (mod m) và c = d (mod m), nên theo định lý 1.1, các số
a − b, c − d chia hết cho m.
Do đó tồn tại các số nguyên k, l, để a − b = k.m, c − d = l.m.
Trừ vế với vế hai đẳng thức trên ta được
(a − c) − (b − d) = (a − b) − (c − d) = km − lm = (k − l)m.
Bởi vậy (a − c) − (b − d) chia hết cho m. Do đó, theo định lý 1.1,
(a − c) = (b − d) (mod m).
- 7
Nhận xét 1.3. Các phép thặng dư có thể nhân vế với vế, nghĩa là, nếu a1 = b1
(mod m), a2 = b2 (mod m), . . . , ai = bi (mod m), . . . , an = bn (mod m), thì
a1 a2 . . . ai . . . an = b1 b2 . . . bi . . . bn (mod m)
Chứng minh. Định lý được chứng minh bằng quy nạp theo n.
Cơ sở quy nạp: Với n = 2 ta có a1 = b1 (mod m), a2 = b2 (mod m) nên theo
định lý 1.1, các hiệu a1 − b1 , a2 − b2 chia hết cho m.
Khi đó tồn tại các số nguyên k1 , k2 để a1 − b1 = k1 m, a2 − b2 = k2 m.
Do đó
a1 a2 − b 1 b 2 = a1 a2 − a1 b 2 + a1 b 2 − b 1 b 2
= (a1 a2 − a1 b2 ) + (a1 b2 − b1 b2 )
= a1 (a2 − b2 ) + b2 (a1 − b1 )
= a1 k2 m + b2 k1 m
= (a1 k2 + b2 k1 )m.
Bởi vậy a1 a2 − b1 b2 chia hết cho m nên, theo định lý 1.1, a1 a2 = b1 b2 (mod m).
Quy nạp, giả sử khẳng định đã đúng với n = t, t > 2, nghĩa là từ t phép đồng
dư tùy ý
a1 = b 1 (mod m), a2 = b2 (mod m), . . . , ai = bi (mod m), . . . , at = bt (mod m)
đã suy ra được a1 a2 . . . ai . . . at = b1 b2 bi bt (mod m).
Xét t + 1 phép đồng dư bất kỳ, a1 = b1 (mod m), a2 = b2 (mod m), . . . , at = bt
(mod m), at+1 = bt+1 (mod m). Khi đó, theo giả thiết quy nạp từ t phép đồng dư
đầu đã có a1 a2 . . . at = b1 b2 . . . bt (mod m).
Ký hiệu, At = a1 a2 . . . at , Bt = b1 b2 . . . bt . Khi đó, theo định lý 1.1, hiệu At − Bt
chia hết cho m, nên tồn tại số nguyên l, để At − Bt = l.m.
Do at+1 = bt+1 (mod m) nên theo định lý 1.1 at+1 − bt+1 chia hết cho m. Bởi
vậy tồn tại số nguyên k để at+1 − bt+1 = k.m. Xét hiệu
At at+1 − Bt .bt+1 = At at+1 − At bt+1 + At bt+1 − Bt bt+1
= At (at+1 − bt+1 ) + bt+1 (At − Bt )
= At .k.m + bt+1 .l.m
= (At .k + bt+1 .l)m.
- 8
nên a1 a2 . . . at at+1 − b1 b2 . . . bt bt+1 = At at+1 − Bt bt+1 chia hết cho m. Do đó, theo định
lý 1.1 thì a1 a2 . . . an = b1 b2 . . . bn (mod m).
Hệ quả 1.1. Các phép thặng dư có thể nâng lên lũy thừa, nghĩa là, nếu a = b
(mod m) thì với mọi số nguyên không âm n đều có an = bn (mod m).
Hệ quả 1.2. Giả sử P (x) là đa thức tùy ý với hệ số nguyên
P (x) = t0 + t1 x + t2 x2 + · · · + tn xn .
Khi đó nếu a = b (mod m), thì
P (a) = t0 + t1 a + t2 a2 + · · · + tn an = t0 + t1 b + t2 b2 + · · · + tn bn = P (b) (mod m).
1.1.2 Lớp thặng dư
Ta đã biết với mỗi số nguyên a đều tồn tại q, r sao cho a = mq+r với 0 ≤ r < m,
khi đó r và a có mối liên quan như thế nào theo modulo m? Liệu rằng có thể thay
thế a bởi r hoặc ngược lại trong quá trình giải quyết vấn đề. Từ đó ta cần tìm hiểu
mối tương quan giữa a và r.
Định lý 1.2. Quan hệ thặng dư modulo m là một quan hệ tương đương, nghĩa là
với mọi số nguyên a, b, c ta có
(i)Tính phản xạ: a = a (mod m),
(ii)Tính đối xứng: Nếu a = b (mod m) thì b = a (mod m),
(iii)Tính bắc cầu: Nếu a = b (mod m) và b = c (mod m) thì a = c (mod m).
Chứng minh. (i) Vì 0 = a − a luôn chia hết cho m nên a = a (mod m).
(ii) Từ a = b (mod m) ta được m|(a − b) suy ra m|(b − a) hay b = a (mod m).
(iii) Ta thấy nếu a = b (mod m) và b = c (mod m) thì tồn tại số nguyên x và
y sao cho a − b = mx; b − c = my .
Do đó
a − c = (a − b) + (b − c) = mx + my = m(x + y),
Vậy a = c (mod m).
Mỗi lớp tương đương của số a trên quan hệ tương đương được gọi là một lớp
thặng dư modulo m, được viết a + mZ, gồm tất cả các số nguyên có cùng thặng
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
