zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Tài Liệu Phổ Thông

» Trung học phổ thông

Một số phương pháp giải toán số học sơ cấp - Hà Duy Hưng

Chia sẻ: Nguyễn Công Liêu | Ngày: | Loại File: PDF | Số trang:14

Báo xấu

259
lượt xem 32
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu "Một số phương pháp giải toán số học sơ cấp" cung cấp cho các bạn một số khái niệm cơ bản trong lý thuyết số sơ cấp như số mũ, một khái niệm quan trọng trong việc hình thành các số p−adic, cấp của một số định lý Lagrange và ứng dụng trong các bài toán chia hết, hệ thặng dư, nghịch đảo của một số,.... Mời các bạn cùng tham khảo nội dung tài liệu để có thêm tài liệu phục vụ nhu cầu học tạp và nghiên cứu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Một số phương pháp giải toán số học sơ cấp - Hà Duy Hưng

www.MATHVN.com 1 Một số phương pháp giải toán số học sơ cấp Hà Duy Hưng Tóm tắt. Lý thuyết số có mối liên hệ gần gũi với nhiều lĩnh vực toán học khác nhau như đại số, giải tích, hình học, thậm chí cả tô pô (Ví dụ một chứng minh rất hay của Paul Erdos về sự vô hạn của tập các số nguyên tố dựa trên tôpô). Chính vì vậy các chứng minh số học thường được dựa trên nhiều ý tưởng và nhiều phương pháp khác nhau. Bài viết này đề cập đến một số khái niệm cơ bản trong lý thuyết số sơ cấp như số mũ- một khái niệm quan trọng trong việc hình thành các số p−adic, cấp của một số - định lý Lagrange và ứng dụng trong các bài toán chia hết, hệ thặng dư, nghịch đảo của một số, ... và các ứng dụng thú vị trong giải toán số học, đặc biệt trong các bài toán trong lý thuyết chia hết và đồng dư. Bài viết này dựa trên các bài giảng tôi hay sử dụng trong giảng dạy ở các buổi chuyên đề và tập huấn đội tuyển Olympic Toán học các cấp. Một vài lời khuyên khi giải các bài toán SỐ HỌC sơ cấp: 1. Đừng để hình thức đánh lừa !!! 2. Ý tưởng của các chứng minh thường hay nằm ở trong chính các chứng minh của các kết quả cơ bản. 3. Rất thường xuyên dựa vào những sự kiện đơn giản nào đấy và là phân môn có tính giải trí trí tuệ cao ==> Tập trung làm hoặc biết nhiều bài toán khó, định lý mạnh không hẳn đã tốt!!! 4. Đôi khi đòi hỏi sự tưởng tượng, những tính toán bằng tay với những phép tính rất lớn!!! Ví dụ: (a) 210 ≡ 107 (mod 2003) - VMO 2004, (b) 14 ≡ 452 (mod 2011) - VMO 2011, (c) (2n + 1)3 + 53 + 13 = (2n − 1)3 + (n + 4)3 + (4 − n)3 - Vietnam TST 2005, (d) 1729 = 12 + 123 = 93 + 103 - Câu chuyện giữa Hardy và Ramanujan. Ta xét bài toán cụ thể sau đây Bài tập 0.1. (Romania TST 2011) Chứng minh rằng tồn tại vô số số nguyên dương n sao cho n2 + 1 có hai ước dương có hiệu đúng bằng n. Bài toán nhìn qua có vẻ không đơn giản, lý do biểu thức n2 + 1 có vẻ không hề đơn giản như hình thức của nó. Ví dụ bài toán xét xem liệu có vô hạn ước nguyên tố có dạng n2 + 1 hay không đến nay vẫn là một OPEN PROBLEM!. Tuy nhiên, thực tế thì bài toán này chỉ cần sử dụng hiểu biết về một dãy quen thuộc đó là . . . Xem tiếp ở trang sau . . . www.MATHVN.com
www.MATHVN.com 2 dãy Fibonacci, với F 0 = 0, F1 = 1, và Fn+2 = Fn+1 + Fn . Theo đẳng thức Cessani 2 n 2 thì Fn+1 − Fn+2 Fn = (−1) . Do đó F2k + 1 = F2k+1 F2k−1 . Thành thử ta có thể lấy n = F2k . Kết luận: Nên học một cách hệ thống theo một giáo trình nào đó. Ví dụ về vài quyển sách số học thích hợp với các học sinh và thầy cô dạy chuyên Toán: 1. Số học của GS. Hà Huy Khoái. 2. Elementary Theory of Numbers of Waclaw Sierpinski 3. Number Theory of A. Baker 4. Problems in Number theory bản thảo không xuất bản của Hojoo Lee (v. 2007). 5. . . . www.MATHVN.com
1 LÝ THUYẾT CHIA HẾT VÀ ĐỒNG DƯ www.MATHVN.com 3 1 Lý thuyết chia hết và đồng dư 1.1 Tổng quan Vấn đề lý thuyết: 1. Ước chung lớn nhất - Bội chung bé nhất. Định lý Berzout. 2. Số nguyên tố, hợp số - Hai định lý cơ bản liên quan đến số nguyên tố: Fermat (tổng quát: Euler) - Wilson. 3. Định lý phần (thặng) dư Trung Hoa. Các công cụ, phương pháp giải toán trong phần này rất nhiều 1. Cấp của một số và ứng dụng 2. Nghịch đảo của một số 3. Hai định lý bốn số của Euler. 4. Công thức Legendre - Polignac, Số mũ. 5. Ứng dụng của các định lý cổ điển: Định lý Trung Hoa về sự tồn tại, Định lý Fermat bé- Định lý Euler, Định lý Wilson. Bên cạnh đó một số các định lý cổ điễn quan trọng: như định lý Fermat về phân loại số nguyên tố 4k ± 1. 6. Hệ thặng dư đầy đủ, thu gọn. 7. Ba nguyên lý cơ bản: Nguyên lý sắp thứ tự tốt, Nguyên lý Dirichlet, Nguyên lý quy nạp. Đây là ba nguyên lý thường xuyên gắn bó với lý thuyết số và cũng là những nguyên lý cơ bản nhất. 1.2 Cụ thể 1.2.1 Ước chung lớn nhất- Định lý Berzout Định nghĩa 1. Cho n > 1 số nguyên không đồng thời bằng không và n số nguyên a1 , . . . , an không đồng thời bằng không. Số nguyên d lớn nhất có tính chất d | ai với mọi i = 1, n được gọi là ước chung lớn nhất của n số a1 , . . . , an . Ta kí hiệu gcd(a1 , . . . , an ). Định lý 1. (Berzout) Tồn tại các số nguyên không x1 , . . . , xn sao cho n X gcd(x1 , . . . , xn ) = x i ai i=1 n P Đặc biệt ta suy ra một số nguyên N biểu diễn được ở dạng xi ai khi và chỉ khi gcd(a1 , . . . , an ) | N . i=1 Một hệ quả nữa là UCLN chia hết cho mọi ước chung. Liên quan đến kết quả trên là bài toán đổi tiền rất nổi tiếng của Frobenius như sau: Ta có n đồng xu với các mệnh giá a1 , . . . , an là các số nguyên dương và nguyên tố cùng nhau. Ta cần xác định số tiền lớn nhất không thể đổi được thành các đồng xu trên. Bài toán tương đương với việc tìm số N www.MATHVN.com
1 LÝ THUYẾT CHIA HẾT VÀ ĐỒNG DƯ www.MATHVN.com 4 n P lớn nhất để phương trình xi ai = N vô nghiệm nguyên không âm. Việc xác định giá trị lớn nhất i=1 đến nay vẫn là một bài toán mở. Tuy nhiên ta có một số kết quả khá đơn giản sau: Định lý 2. 1. Trường hợp n = 2 được giải bởi Sylvester năm 1880: số N lớn nhất là N = a1 a2 − a1 − a2 . 2. Bài toán có nghĩa khi n > 2: chẳng hạn N ≤ (n − 1)a1 · · · an . Sau đây là một số kết quả đơn giản rất đáng lưu ý. Định lý 3. 1. Nếu (a, b) = 1 thì (am + bn , as bt ) = 1 với s, t nguyên không âm, m, n nguyên dương. ab 2. BCN N (a, b) = (a, b) (a, b) · (a, c) 3. a ≥ . (a, b, c) p ( a + bp 1 nếu p - a + b 4. gcd ,a + b = ở đây p là số nguyên tố lẻ, (a, b) = 1. a+b p nếu p | a + b. n a −1 5. gcd , a − 1 = gcd (n, a − 1) với mọi a > 1 và n nguyên dương. a−1 6. Tính chất của dãy Mersen: gcd(am − 1, an − 1) = a(m,n) − 1 với a > 1 và các số nguyên dương m, n. Định lý 4. (Bốn số) Nếu a, b, c, d là các số nguyên khác không thỏa mãn ab = cd. Khi đó tồn tại x, y, z, t nguyên sao cho    a = xy  b = tz   c = xz (nếu a, b, c, d dương thì x, y, z, t cũng có thể lấy là dương)      d = ty  (y, z) = 1. Sau đây là một số bài toán liên quan: Bài tập 1.1. (Germany 2008) Cho a, b, c là các số nguyên dương thỏa mãn a + b | ab và a + c | ac. Chứng minh rằng gcd(a, b, c) > 1. Hướng dẫn giải sẽ có ở trang tiếp theo ... www.MATHVN.com
1 LÝ THUYẾT CHIA HẾT VÀ ĐỒNG DƯ www.MATHVN.com 5 Gợi ý giải bài số 1. Ta cần phân tích xem với hai số x, y nguyên dương mà x + y | xy có tính chất gì đặc biệt. Đặt u = (x, y), ta viết x = ux1 , y = uy1 . Khi đó x1 +y1 | u(x1 y1 ). Vì gcd(x1 +y1 , x1 y1 ) = 1 nên x1 + y1 | u. Từ đây suy ra u > x1 , y1 . Do đó ta tìm được dạng tổng quát của các cặp số nguyên dương (x, y) như thế đó là x = x1 (x1 + y1 )t, y = y1 (x1 + y1 )t, trong đó t, x1 , y1 nguyên dương và (x1 , y1 ) = 1. Ta nên phát biểu rõ ràng lại những gì vừa làm được. Bổ đề 1. 1. Điều kiện cần và đủ để hai số x, y nguyên dương thỏa mãn x + y | xy là x = x1 (x1 + y1 )t, y = y1 (x1 + y1 )t, trong đó t, x1 , y1 nguyên dương và (x1 , y1 ) = 1. √ √ 2. Nếu x, y nguyên dương và x + y | xy thì gcd(x, y) > x, y. (a, b) · (a, c) a Quay lại bài toán, theo giả thiết (a, b) · (a, c) > a. Mặt khác a ≥ > (như trên (a, b, c) (a, b, c) đã chỉ ra), suy ra (a, b, c) > 1. 2 Sau đây là một bài toán hay Bài tập 1.2. (Russia MO 1997) Tìm tất cả các bộ ba (a, b, c) nguyên dương thỏa mãn  2 a + b = (a, b)  b + c = (b, c)2 c + a = (c, a)2 .  Hướng dẫn giải sẽ có ở trang tiếp theo ... www.MATHVN.com
1 LÝ THUYẾT CHIA HẾT VÀ ĐỒNG DƯ www.MATHVN.com 6 Bài giải. Đặt d = (a, b, c) và ta viết a = dx, b = dy, c = dz. Lưu ý rằng x, y, z là các số nguyên dương và (x, y, z) = 1. Các biểu thức của bài toán gợi ý chúng ta nhớ lại ước lượng trong phần 3 của định lý 3. Ta có (a, b) · (a, c)  a ≥   d (a, c) + (b, c) ⇒ (a, b)2 = a + b ≥ (a, b) · .  (a, b) · (b, c) d b ≥  d Suy ra (a, b) · d ≥ (a, c) + (b, c). (1) Tương tự, ta có thể thiết lập được 2 bất đẳng thức nữa. Cộng chúng lại ta được d ≥ 2 . Ta thay thế a = dx, b = dy, c = dz vào hệ điều kiện và cộng lại sẽ nhận được X d d d 2(x + y + z) = d (x, y)2 ⇒ |x+y+z ⇒ | x, y, z ⇒ = 1. (d, 2) (d, 2) (d, 2) Vậy d | 2. Do đó d = 2. Thay vào () cộng lại ta được (x, y) = (y, z) = (z, x). Từ (x, y, z) = 1 suy ra (x, y) = (y, z) = (z, x) = 1. Vì vậy x + y = y + z = z + x = 2 ⇒ x = y = z = 1. Từ đó ta được a = b = c = 2 . 2 √ √ √ Bài tập 1.3. Cho a, b, c, d√là các số nguyên dương thỏa mãn ad = bc và a < b 3 < c 2 < d 6. Chứng minh rằng a ≥ 1 + 6d2 + 1. (Chọn đội tuyển Toán Chuyên SPHN 2006) Hướng dẫn giải có ở trang tiếp theo . . . www.MATHVN.com
1 LÝ THUYẾT CHIA HẾT VÀ ĐỒNG DƯ www.MATHVN.com 7 Bài √ giải. 2 Chỉ cần biến √ yêu cầu của bài toán ta sẽ thấy cần xét biểu thức a2 + 6d2 − đổi ngược lại √ 2 ad = a + 6d2 − 2 6bc. Tuy nhiên bc không phải biểu thức nguyên, do đó ta làm trội nó lên bởi 3b2 + 2c2 . Do đó ta đi xét hiệu S := a2 + 6d2 − 3b2 − 2c2 Theo định lý bốn số, tồn tại x, y, z, t thỏa mãn a = xy, b = xz, d = tz, c = ty. Ta có S = (xy)2 + 6(tz)2 − 3(xz)2 − 2(ty)2 = (3z 2 − y 2 )(2t2 − x2 ). Để ý rằng 3z 2 > y 2 , 2t2 > x2 . Thành thử S là số nguyên dương. Vậy S ≥ 1. Từ đó suy ra √ √ √ a2 + 6d2 ≥ 1 + 3b2 + 2c2 > 1 + 2 6bc = 1 + 2 6ad ⇒ (a − 6d)2 > 1 √ √ ⇒ a − 1 > d 6 ⇒ (a − 1)2 > 6d2 ⇒ a ≥ 1 + 6d2 + 1. www.MATHVN.com
1 LÝ THUYẾT CHIA HẾT VÀ ĐỒNG DƯ www.MATHVN.com 8 1.2.2 Cấp của một số và cấu trúc ước của một vài biểu thức số học đặc biệt Cho m > 1, a là các số nguyên thỏa mãn (a, m) = 1. Xét dãy a0 , a1 , . . . , am gồm m + 1 số nguyên tố cùng nhau với m. Do đó tồn tại hai số i < j mà ai ≡ aj (mod m). Do đó aj−i ≡ 1 (mod m). Tóm tại, tồn tại số nguyên dương x sao cho ax ≡ 1 (mod m) . Định nghĩa 2. Cho m > 1 là một số nguyên. Với mỗi số nguyên a mà (a, m) = 1 ta kí hiệu h là số nguyên dương bé nhất x thỏa mãn tính chất: ah ≡ 1 (mod m). Kí hiệu ordm (a) := h. Câu hỏi. Cho trước một số nguyên dương a và một modulo m > 1. Câu hỏi đặt ra là liệu có tồn tại a nguyên để h là cấp của a theo modulo m? Bài tập 1.4. Cho n là số nguyên dương. Hãy xác định cấp của 1. 3 theo modulo 2n . 2. 2 theo modulo 3n . Bài giải. 1. Kí hiệu h = ord2n (3). Ta hãy bắt đầu bằng việc tính toán trực tiếp: Với n = 1 thì h = 1: Vì 31 ≡ 1 (mod 2) Với n = 2 thì h = 2: Vì 31 6≡ 1 (mod 4), nhưng 32 ≡ 1 (mod 4). Với n = 3 thì h = 2: Vì 31 6≡ 1 (mod 8), nhưng 32 ≡ 1 (mod 8). Với n = 4 thì h = 4: Vì 3i 6≡ 1 (mod 16) với i = 1, 2, 3, nhưng 34 ≡ 1 (mod 16). Với n = 5 thì h = 8: Vì 3i 6≡ 1 (mod 32) với i = 1, 2, . . . , 7, nhưng 38 ≡ 1 (mod 32). Dự đoán: với n ≥ 3 thì ord2n (3) = 2n−2 . Chú ý rằng a2 + 1 là số chẵn không chia hết cho 4 với mọi số lẻ a. Với mọi số nguyên x > 2 ta có 0 1 x−3 . 1+2+1| + ·{z· · + 1} 32x−2 2 2 − 1 = (3 − 1) 3 + 1 3 + 1 · · · 3 2 . +1 .2 có x − 3 số 1 = 2x . | {z } | {z } | {z } .. 1 | {z } .2 . .. 22 . .. 21 . .. 21 n−3 Đặc biệt 2n | 32 − 1. . Ta còn phải chứng minh 2n−2 là số nguyên dương bé nhất có tính chất 3h − 1.. 2n . Ta viết h = 2a · b, với b là số lẻ. Chú ý rằng với b lẻ thì 3b ≡ 3 (mod 8), ta có h b b 20 b 21 b 2a−3 3 −1= 3 −1 3 + 1 (3 ) + 1 · · · (3 ) +1 . | {z } | {z }| {z } | {z } .. 1 . . . .2 .. 22 .. 21 .. 21 www.MATHVN.com
1 LÝ THUYẾT CHIA HẾT VÀ ĐỒNG DƯ www.MATHVN.com 9 Vậy 2a+1 - 3h − 1. Do đó 2n−2 ≤ 2a hay a ≥ n − 2. Do đó h ≥ 2n−2 . Kết luận: ord2n (3) = 2n−2 với mọi n ≥ 3. 2. Đáp số : ord3n (2) = 2 · 3n−1 . 2 Một trường hợp đặc biệt: Một số g nguyên được gọi là căn nguyên thủy (CNT) của m nếu như cấp của nó theo modulo m bằng φ(m). Dĩ nhiên không phải số nào cũng có căn nguyên thủy, tất cả những số m có căn nguyên thủy là 2, 4, pk , 2pk trong đó p là số nguyên tố lẻ. Định lý 5. Cho m > 1, a là các số nguyên nguyên tố cùng nhau. Nếu h = ordm (a) và x là số nguyên không âm thỏa mãn tính chất ax ≡ 1 (mod m) thì h | x. Tổng quát: ax ≡ ay (mod m) khi và chỉ khi h | x − y. Hệ quả 1. Nếu p là số nguyên tố, p - a, và h = ordp (a) thì h | p − 1. Đây là hệ quả trực tiếp của định lý Fermat bé và định lý 5 nói trên: ap−1 ≡ 1 (mod p) với mọi p nguyên tố và p - a. n Hệ quả 2. Nếu p là một số nguyên tố lẻ và p | a2 + 1, với n là số nguyên dương, thì p ≡ 1 (mod 2n+1 ). n+1 Chứng minh. Gọi h = ordp (a) thì h | p − 1. Mặt khác, p | a2 − 1 nên h | 2n+1 . Vậy h = 2m . Nếu 2 n n m ≤ n, thì h | 2n , do đó ah − 1 | a2 − 1, suy ra p | a2 ± 1, mâu thuẫn. n Nhận xét. Từ hệ quả ta suy ra mọi ước lẻ d của a2 + 1 đều có dạng 2n+1 k + 1, với k là số nguyên. n n Nhận xét. Trường hợp a = 2, thì 22 + 1 là số Fermat thứ n, kí hiệu Fn = 22 + 1. Ta có tính chất mạnh hơn: Nếu p | Fn , với n > 1 thì p ≡ 1 (mod 2n+2 ). (Đây là một định lý mang tên nhà Toán học Pháp tên đầy đủ là Francois Édouard Anatole Lucas). Gợi ý chứng minh nhận xét: Sử dụng một kết quả về thặng dư bình phương: nếu p ≡ 1 (mod 8) là số nguyên tố, thì tồn tại x nguyên để x2 ≡ 2 (mod p). Từ p | Fn suy ra p ≡ 1 (mod 2n+1 ), do đó n+1 n p ≡ 1 (mod 8). Vậy tồn tại x để x2 ≡ 2 (mod 8). Lũy thừa 2n cả hai vế ta được x2 ≡ 22 ≡ −1 n+1 (mod ). Do đó p | x2 + 1. Áp dụng kết quả của hệ quả 2 một lần nữa, ta được p ≡ 1 (mod 2n+2 ). 2 Nhận xét. Hai số Fermat khác nhau luôn nguyên tố cùng nhau, do đó tập các ước nguyên tố của chúng khác nhau. aq − 1 Hệ quả 3. Giả sử rằng a là số nguyên > 1, các số p, q nguyên thỏa mãn p | . Khi đó p = q a−1 nếu a ≡ 1 (mod p) hoặc p ≡ 1 (mod q) nếu ngược lại. www.MATHVN.com
1 LÝ THUYẾT CHIA HẾT VÀ ĐỒNG DƯ www.MATHVN.com 10 Một trong những biểu thức đặc biệt có cấu trúc ước khá đặc biệt là các biểu thức có dạng a2 + nb2 , trong đó n là số nguyên dương. Ở đây ta quan tâm đến trường hợp n = 1. Ta có kết quả sau Định lý 6. (a) Nếu p là một ước nguyên tố dạng 4k + 3 của a2 + b2 , với a, b nguyên, thì p | a, b. (b) (Định lý Fermat) Nếu p là số nguyên tố dạng 4k + 1, thì p = c2 + d2 , trong đó c, d nguyên dương nào đấy. (c) (Định lý Fermat-Euler) Mọi ước nguyên tố p của biểu thức a2 + b2 thì hoặc là bằng 2, hoặc có dạng 4k + 1, hoặc có dạng 4k + 3 cộng thêm số mũ của p trong a2 + b2 là số chẵn. p−1 Gợi ý chứng minh: (a) Chuyển về dạng đồng dư a2 ≡ −b2 (mod p). Do vậy ap−1 ≡ (−1) 2 bp−1 p−1 (mod p). Giả sử p - a, khi đó p - b. Theo định lý Fermat bé thì 1 ≡ (−1) 2 (mod p), mâu thuẫn. (b) Đầu tiên ta cần bổ đề sau p−1 2 Bổ đề 2. Nếu p ≡ 1 (mod 4) là một số nguyên tố thì ! ≡ −1 (mod p). 2 Chứng minh. Theo định lý Wilson, nếu p là một số nguyên tố thì (p − 1)! ≡ −1 (mod p). Chú ý rằng p − k ≡ (−1) · k (mod p), nên 2 p−1 p−1 p−1 p − 1 (p − 1)! ≡ 1 · 2 · · · · p− · · · (p − 1) ≡ (−1) 2 ! (mod p), 2 2 2 p−1 do 2 là số nguyên chẵn nên ta có kết quả. √ Đặt K =[ p], thì p < (K + 1)2 . Do p ≡ 1 (mod 4) nên tồn tại x mà x2 ≡ −1 (mod 4) (ví dụ lấy x = p−12 !) Xét tập hợp S = {u + xv : 0 ≤ u, v ≤ K}. Ta có |S| = (K + 1)2 > p nên theo nguyên lý Dirichlet sẽ có hai phần tử trùng nhau modulo p. Do đó có ui , vi để u1 + xv1 ≡ u2 + xv2 (mod p) ⇒ (u1 − u2 )2 ≡ x2 (v1 − v2 )2 ≡ −(v1 − v2 )2 (mod p). Đặt c = |u1 − u2 | và d = |v1 − v2 | ta được ngay p = c2 + d2 . Ví dụ bằng số: 5 = 22 + 12 , 2017 là số nguyên tố dạng 4k + 1 và ta có 2017 = 92 + 442 . (c) coi như bài tập về nhà!!!. 2 Bài tập 1.5. Cho n > 1, a là các số nguyên dương mà n | an + 1. Chứng minh rằng gcd(a + 1, n) > 1. Hướng dẫn giải có ở trang sau . . . www.MATHVN.com
1 LÝ THUYẾT CHIA HẾT VÀ ĐỒNG DƯ www.MATHVN.com 11 Bài giải. Vì n > 1 nên n luôn có ít nhất một ước nguyên tố, ta chọn p là ước nguyên tố bé nhất. Khi đó gcd(p, n − 1) = 1. Gọi h = ordp (a). Ta có p | an + 1 | a2n − 1 nên h | 2n. Lại có h | p − 1 nên h | (2n, p − 1) = (2, p − 1) = 1, 2. Nếu h = 1 thì p | a − 1, do đó an + 1 ≡ 2 (mod p). Suy ra p = 2. Nhưng khi đó a là số lẻ nên gcd(a + 1, n) là số chẵn. Nếu h = 2 thì p lẻ và từ p | a2 − 1 suy ra p | a + 1. Khi đó p | gcd(a + 1, n). 2 Nhận xét. Nếu p là số nguyên tố và n > 1 thỏa mãn n | (p − 1)n + 1 thì p | n. ( n | 2m−1 + 1 Bài tập 1.6. Tìm tất cả các cặp số nguyên dương (m, n) thỏa mãn m | 2n−1 + 1. Hướng dẫn giải có ở trang sau . . . www.MATHVN.com
1 LÝ THUYẾT CHIA HẾT VÀ ĐỒNG DƯ www.MATHVN.com 12 Nếu m = 1 thì n = 1, 2 và ngược lại. Giả sử m, n > 1. Lấy một ước nguyên tố p bất kì của n suy ra p | 2m−1 + 1. Nếu chuyển về dạng p | 22(m−1) − 1 sẽ không được gì sáng sủa. Bài này đòi hỏi khéo léo hơn. Ta viết m − 1 = 2a · x, n − 1 = 2b · y, trong đó a, b, x, y nguyên dương và xy lẻ. Ta có p | 2m−1 + 1 = a (2x )2 + 1. Điều này gợi ý cho ta kết quả sau n Bổ đề 3. Nếu p | a2 + 1, với p là số nguyên tố lẻ, thì p ≡ 1 (mod 2n+1 ). Áp dụng bổ đề ta được ngay p ≡ 1 (mod 2)a+1 . Như vậy, mọi ước của n đều có dạng 2a+1 k + 1. Do tích của các số có dạng 2a+1 k + 1 cũng có dạng 2a+1 k + 1 nên n ≡ 1 (mod 2a+1 ). Suy ra b ≥ a + 1. Đổi vai trò, suy ra a ≥ b + 1, mâu thuẫn. 1.3 Phương trình đồng dư bậc nhất và ứng dụng Ta xét phương trình ax ≡ b (mod m) (2) với a, b, m là các số nguyên, trong đó m > 1. Định lý 7. Phương trình (2) có nghiệm khi và chỉ khi gcd(a, m) | b. Chứng minh. Nếu gcd(a, m) | b thì b = t · gcd(a, m). Theo định lý Berzout, tồn tại các số nguyên u, v để gcd(a, m) = ua + vm. Suy ra b = (tu)a + (tv)m. Hay a(tu) ≡ b (mod m). Ngược lại, nếu tồn . tại x để ax ≡ b (mod m) thì ax = b + my. Suy ra b = ax − my .. gcd(a, m). Một trong những trường hợp đặc biệt hay sử dụng đó là khi b = 1. Khi đó mỗi nghiệm nguyên x của (2) ta sẽ gọi là một nghịch đảo của a theo modulo m. Chú ý rằng hai nghịch đảo của cùng a theo modulo m thì đều đồng dư với nhau modulo m (tính duy nhất nghiệm modulo m). Ta dùng kí hiệu chung a−1 (hoặc a0 hay a). Nhận xét. Nghịch đảo của a theo modulo m là khái niệm tương tự với khái niệm số nghịch đảo của một số. Định lý 8. Nếu x chạy qua một hệ thặng dư thu gọn modulo m, thì x−1 cũng chạy qua một hệ thặng dư thu gọn modulo m. Khái niệm nghịch đảo cho phép có thể làm việc với các phân số theo modulo nguyên tố p tùy ý. Ta lưu ý đến các tính chất sau đây b Nhận xét. Nếu a, b là các số nguyên, (a, m) = 1 và a | b thì ≡ b · a−1 (mod m) . a Một số kết quả ở trên có thể dễ dàng mở rộng nhờ khái niệm nghịch đảo. www.MATHVN.com
1 LÝ THUYẾT CHIA HẾT VÀ ĐỒNG DƯ www.MATHVN.com 13 Bài tập 1.7. Nếu (a, b) = 1 là hai số nguyên dương không đồng thời bằng 1 và p nguyên tố lẻ thỏa n n mãn p | a2 + b2 . Khi đó p ≡ 1 (mod 2n+1 ). Chứng minh. Ta có p - b. Gọi b0 thỏa mãn bb0 ≡ 1 (mod p), ta có n n n 2n 0 ≡ b02 a2 + b2 ≡ (ab0 ) + 1 (mod p). n Do đó p | (ab0 )2 + 1. Áp dụng kết quả đã biết suy ra ngay p ≡ 1 (mod 2n+1 ). www.MATHVN.com
1 LÝ THUYẾT CHIA HẾT VÀ ĐỒNG DƯ www.MATHVN.com 14 1.4 Bài tập hỗn hợp Bài tập 1.8. Cho n là một số nguyên dương, chứng minh rằng mọi ước nguyên tố của số A = (n + 1)2005 − n2005 có dạng 10k + 1 hoặc 802k + 1. Bài tập 1.9. Cho hai số nguyên dương a, b thỏa mãn (a) a2 + ab + b2 | a3 + b3 (b) a − b là một số nguyên tố. Chứng minh rằng a3 − b3 = n4 với n nguyên nào đó. Bài tập 1.10. Chứng minh rằng với mỗi số nguyên dương lẻ n, thì mọi ước nguyên dương của số 72n + 5 · 7n + 1 đều có dạng 4k + 1. m n+1 Bài tập 1.11. Chứng minh rằng không có số nguyên dương m, n nào mà + = 4. n m Bài tập 1.12. Tìm tất cả các cặp số nguyên không âm (x, y) thỏa mãn 33x + 31 = 2y . x2011 − 1 Bài tập 1.13. Chứng minh rằng phương trình = y 7 − 1 không có nghiệm nguyên. x−1 (a + 1)n − an Bài tập 1.14. Tìm (a, n) nguyên dương sao cho là một số nguyên. n Bài tập 1.15. Tìm tất cả các cặp số nguyên dương (n, p) trong đó p là số nguyên thỏa mãn n ≤ 2p và np−1 | (p − 1)n + 1. Bài tập 1.16. Tìm x, y, z nguyên dương thỏa mãn 4 - z − 1 và x2 = y z − 3. Bài tập 1.17. Chứng minh rằng tồn tại vô số cặp (p, q) nguyên tố phân biệt thỏa mãn p | 2q−1 − 1 và q | 2p−1 − 1. Bài tập 1.18. Chứng minh rằng không tồn tại x, y các số nguyên dương để x2011 − y 2011 | y 20 . Bài tập 1.19. Cho m, n là các số nguyên dương thỏa mãn m2 + mn + n2 | mn(m + n) và m > n. Chứng minh rằng (m − n)3 ≥ 3mn. Bài tập 1.20. Tìm n nguyên dương để 1. 3n | n3 + 1. 2. n2 | 2n + 1. Bài tập 1.21. (Wolstenholme) Co p ≥ 5 là số nguyên tố. Ta viết 1 1 1 a + + ··· + = , 1 2 p−1 b với a, b là số nguyên và (a, b) = 1 thì p2 | a. Bài tập 1.22. Cho hai số nguyên dương a > b > 1 trong đó b là một số lẻ và n là một số nguyên dương. Chứng minh rằng nếu bn | an − 1, thì 3n ab > . n Biên soạn: Hà Duy Hưng www.MATHVN.com

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.