Tài liệu MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN CHIA HẾT

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ———————o0o——————– TRẦN THỊ THẢO MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN CHIA HẾT 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. TS Đặng Huy Ruận HÀ NỘI - 2014 Mục lục Mở đầu 3 1 Một số khái niệm và kiến thức 1.1 Phép chia hết . . . . . . . . . 1.2 Phép chia có dư . . . . . . . . 1.3 Số nguyên tố . . . . . . . . . 1.4 Các số nguyên tố cùng nhau 1.5 Ước số chung lớn nhất . . . . 1.6 Bội số chung nhỏ nhất . . . . 1.7 Định nghĩa đồ thị . . . . . . . 1.8 Đồ thị gán nhãn . . . . . . . . 1.9 Nguồn . . . . . . . . . . . . . cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Một số phương pháp giải bài toán chia hết 2.1 Phương pháp chia có dư . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Phương pháp chia có dư . . . . . . . . . . . . . . . . . 2.1.2 Các ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.3 Các bài toán tương tự . . . . . . . . . . . . . . . . . . . 2.2 Phương pháp đồng dư . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Phép đồng dư . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Vận dụng phương pháp đồng dư để giải toán . . . . . . 2.2.3 Các bài toán tương tự . . . . . . . . . . . . . . . . . . . 2.3 Phương pháp quy nạp . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Nguyên lý quy nạp . . . . . . . . . . . . . . . . . . . . . 2.3.2 Phương pháp chứng minh bằng quy nạp . . . . . . . . 2.3.3 Vận dụng phương pháp quy nạp để giải các bài toán chia hết . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.4 Các bài toán tương tự . . . . . . . . . . . . . . . . . . . 2.4 Phương pháp tiêu chuẩn chia hết . . . . . . . . . . . . . . . . . 2.4.1 Phương pháp đồng dư với 1 . . . . . . . . . . . . . . . 2.4.2 Phương pháp dãy số dư . . . . . . . . . . . . . . . . . . 2.4.3 Phương pháp nhóm chữ số . . . . . . . . . . . . . . . . . 2.4.4 Các bài toán tương tự . . . . . . . . . . . . . . . . . . . 1 4 4 5 5 6 7 8 9 10 11 13 13 13 14 16 16 16 17 21 22 22 22 23 26 27 28 30 32 35 Luận văn thạc sỹ 2.5 . . . . . . . . 35 36 36 40 41 41 42 46 Lời giải - Đáp số Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 58 59 2.6 3 Học viên: Trần Thị Thảo Phương pháp vận dụng định lý . . . . . . 2.5.1 Một số định lý chia hết . . . . . . 2.5.2 Các ví dụ . . . . . . . . . . . . . . 2.5.3 Các bài toán tương tự . . . . . . . Phương pháp nguồn đồng dư . . . . . . . 2.6.1 Nguồn đồng dư . . . . . . . . . . . 2.6.2 Xây dựng một số nguồn đồng dư. 2.6.3 Ứng dụng của nguồn đồng dư. . . 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mở đầu Bài toán chia hết là một trong những bài toán khó của Số học. Phương pháp giải bài toán chia hết rất đa dạng, đòi hỏi người làm phải biết vận dụng các phương pháp một cách thích hợp. Chính vì thế, với mong muốn đưa ra một tài liệu tương đối đầy đủ về bài toán chia hết, em đã viết luận văn “ Một số phương pháp giải bài toán chia hết”. Trong khuôn khổ của luận văn này, em xin phép được trình bày một vài phương pháp cơ bản để giải bài toán chia hết. Các phương pháp đó là: Phương pháp chia có dư, phương pháp đồng dư, phương pháp quy nạp, phương pháp tiêu chuẩn chia hết, phương pháp vận dụng định lý và phương pháp nguồn đồng dư; trong đó phương pháp nguồn đồng dư có thể nói là một phương pháp mới để xác định tính chia hết của các số. Ngoài mục lục, lời nói đầu, kết luận, tài liệu tham khảo thì luận văn được chia làm ba chương: Chương 1: Một số khái niệm và kiến thức cơ bản. Chương 1 trình bày một số khái niệm và các kiến thức cơ bản của tính chia hết nhằm phục vụ cho nội dung của chương 2. Chương 2: Một số phương pháp giải bài toán chia hết. Chương 2 trình bày sáu phương pháp giải bài toán chia hết. Mỗi một phương pháp đều kèm theo ví dụ minh họa và bài tập đề nghị. Chương 3: Lời giải - đáp số. Chương 3 đưa ra lời giải hoặc đáp số cho các bài tập sau mỗi phương pháp ở chương 2. Mặc dù đã có nhiều cố gắng, song do thời gian và trình độ còn hạn chế nên luận văn “ Một số phương pháp giải bài toán chia hết” không tránh khỏi những thiếu sót. Em rất mong nhận được những ý kiến chỉ bảo của quý thầy cô và bạn đọc để bản luận văn được hoàn thiện hơn. Hà Nội, tháng 6 năm 2014 3 Chương 1 Một số khái niệm và kiến thức cơ bản 1.1 Phép chia hết 1. Định nghĩa 1.1 Cho a, b là hai số nguyên và b khác 0. Ta nói a chia hết . cho b và kí hiệu là a .. b, nếu tồn tại số nguyên k sao cho a = b.k. Khi a chia hết cho b, thì ta nói b là ước của a và kí hiệu b \ a. Ngoài ra ta còn nói a là bội của b. Khi a chia hết cho b, thì a cũng chia hết cho −b , nên ta chỉ cần xét các ước nguyên dương của a. Chẳng hạn: Số 12 có các ước là ±1, ±2, ±3, ±4, ±6, ±12, nhưng ta chỉ cần xét các ước dương của 12 là 1, 2, 3, 4, 6, 12. 2. Một số định lý về chia hết. Định lý 1.1 Nếu các số a1 , a2 , . . . , an chia hết cho m thì tổng a1 + a2 + · · · + an chia hết cho m. Thật vậy, vì ai , (1 ≤ i ≤ n) chia hết cho m nên tồn tại số nguyên ki để ai = ki .m. Do đó: ! n n n X X X a1 + a2 + · · · + an = ai = i=1 ki .m = i=1 P ki .m i=1 Vì tổng các số nguyên là số nguyên, tức ki là số nguyên, nên tổng a1 +· · ·+an chia hết cho m . Định lý 1.2 Nếu a và b chia hết cho m, thì hiệu a − b và b − a cũng chia hết cho m . Thật vậy, vì a và b đều chia hết cho m nên tồn tại các số nguyên t, s để a = t.m và b = s.m. Do đó: 4 Luận văn thạc sỹ Học viên: Trần Thị Thảo a − b = t.m − s.m = (t − s) .m b − a = s.m − t.m = (s − t) .m . . Vì hiệu hai số nguyên là số nguyên nên (a − b) ..m và (b − a) ..m. Hệ quả 1.1 Nếu tổng một số số hạng chia hết cho m và trừ một số hạng, còn tất cả các số hạng khác đều chia hết cho m, thì số hạng này cũng chia hết cho m. Định lý 1.3 Nếu mỗi số ai , (1 ≤ i ≤ n) chia hết cho mi , thì tích a1 a2 . . . an chia hết cho tích m1 m2 . . . mn . Thật vậy, vì ai , (1 ≤ i ≤ n) chia hết cho mi nên tồn tại số nguyên ki , để ai = ki .mi . Khi đó: a1 a2 . . . an = k1 m1 .k2 m2 . . . kn mn = (k1 k2 . . . kn ) (m1 m2 . . . mn ) Vì tích các số nguyên là số nguyên nên tích a1 a2 . . . an chia hết cho tích m1 m2 . . . mn . Hệ quả 1.2 Nếu a chia hết cho m, thì với số tự nhiên n tùy ý, an chia hết cho mn . Hệ quả 1.3 Nếu chỉ một thừa số chia hết cho m, thì tích của số đó với các số khác cũng chia hết cho m. 1.2 Phép chia có dư Định nghĩa 1.2 Giả sử a, b là hai số nguyên và b 6= 0. Ta nói rằng số a chia cho số b có thương là q và số dư là r, nếu a có thể biểu diễn bằng đẳng thức a = bq + r , trong đó 0 ≤ r ≤ |b| − 1. Định lý 1.4 Cho a, b là hai số nguyên và b 6= 0. Khi đó tồn tại duy nhất cặp số (q, r), sao cho a = bq + r với 0 ≤ r ≤ |b| − 1. Nhận xét: Cho b > 0 và a tùy ý. Khi đó nếu chia a cho b thì số dư chỉ có thể là 0, 1, 2, . . . , b − 1. 1.3 Số nguyên tố 1. Định nghĩa 1.3 Số tự nhiên p > 1 được gọi là số nguyên tố, nếu ngoài 1 và p, nó không còn một ước tự nhiên nào khác. Số tự nhiên lớn hơn 1 có nhiều hơn hai ước tự nhiên được gọi là hợp số. 5 Luận văn thạc sỹ Học viên: Trần Thị Thảo Số 1 chỉ có đúng một ước số tự nhiên. Số 1 không phải là số nguyên tố cũng không phải là hợp số. 2. Các tính chất i) Mọi số tự nhiên lớn hơn 1 đều có ít nhất một ước là số nguyên tố (ước nguyên tố). ii) Nếu số tự nhiên a lớn hơn 1 và không chia hết cho các số nguyên tố bé hơn, thì a là số nguyên tố. Nhận xét: Từ tính chất ii, cho ta thuật toán xác định tính nguyên tố: Giả sử a là số tự nhiên lớn hơn 1, để xác định a là số nguyên tố hay √ không, ta chỉ cần xét các số nguyên tố nhỏ hơn a. Nếu a không chia hết cho bất kỳ số nào trong các số này thì a là số nguyên tố. Ngược lại, nếu a chia hết cho ít nhất một trong các số này thì a là hợp số. iii) Tập hợp các số nguyên tố là vô hạn. iv) Mọi số tự nhiên lớn hơn 1 đều có thể phân tích một cách duy nhất thành tích các thừa số nguyên tố. Tức với số tự nhiên n > 1 bất kỳ ta luôn biểu diễn được duy nhất dưới dạng n = pk11 pk22 . . . pkmm (∗) trong đó pi (1 ≤ i ≤ m) là các số nguyên tố, ki (1 ≤ i ≤ m) là các số nguyên dương. Dạng biểu diễn (∗) ở trên được gọi là dạng chính tắc của số n . v) Nếu p là số nguyên tố, thì với mọi số tự nhiên a đều có ap − a chia hết cho p . 1.4 Các số nguyên tố cùng nhau 1. Định nghĩa 1.4 Hai số a, b được gọi là hai số nguyên tố cùng nhau và kí hiệu là (a, b) = 1, nếu chúng chỉ có một ước chung duy nhất đó là số 1. 2. Các tính chất 6 Luận văn thạc sỹ Học viên: Trần Thị Thảo Định lý 1.5 Nếu a và b nguyên tố cùng nhau, thì tồn tại các số nguyên x0 và y0 để ax0 + by0 = 1. Định lý 1.6 Nếu các số a, b nguyên tố cùng nhau và n chia hết cho cả a và b, thì n chia hết cho tích ab. Định lý 1.7 Nếu tích ac chia hết cho b và a, b nguyên tố cùng nhau, thì c chia hết cho b. 1.5 Ước số chung lớn nhất 1. Định nghĩa 1.5 Ước số lớn nhất của hai số nguyên a và b được gọi là ước số chung lớn nhất của a và b, ký hiệu là (a, b) và viết thu gọn là ƯSCLN. 2. Một số tính chất của ước số chung lớn nhất Định lý 1.8 Giả sử a, b là hai số nguyên và một trong hai số này khác không, d = (a, b) là ƯSCLN của a và b. Khi đó tồn tại các số nguyên x0 , y0 để ax0 + by0 = d. Định lý 1.9 Giả sử a, b là hai số nguyên, trong đó có ít nhất một số khác không và d = (a, b) là ƯSCLN của chúng. Số c là ước chung của a và b khi và chỉ khi c là ước của d. Định lý 1.10 Giả sử a, b là các số nguyên và r là số dư của phép chia a cho b. Khi đó (a, b) = (b, r) 3. Thuật toán Euclid ( thuật toán tìm ước chung lớn nhất) Để tìm ước chung lớn nhất của hai số tự nhiên a, b (a > b) ta thực hiện các bước sau: -B1: Chia a cho b được số dư r1 . -B2: Chia b cho r1 được số dư r2 . -B3: Chia r1 cho r2 được số dư r3 . . . . Giả sử sau i bước ta có được các số dư r1 , r2 , . . . , ri−1 , ri . Sang bước thứ i + 1, ta chia số dư ri−1 cho ri được số dư ri+1 . Cứ tiếp tục quá trình trên cho tới bước k nào đó, mà ta nhận được số dư rk là ước của số dư rk−1 thì dừng lại. Và số dư rk chính là ước chung lớn nhất của a và b . 7 Luận văn thạc sỹ 1.6 Học viên: Trần Thị Thảo Bội số chung nhỏ nhất Trong mục này ta chỉ hạn chế xét các số tự nhiên. Định nghĩa 1.6 Số tự nhiên bé nhất đồng thời là bội của cả số a và số b được gọi là bội số chung nhỏ nhất của a và b, ký hiệu là [a, b] và viết thu gọn là BSCNN. 2. Một số tính chất của bội số chung nhỏ nhất Định lý 1.11 Với hai số tự nhiên a, b bất kỳ, ta luôn có (a, b) . [a, b] = ab. Hệ quả 1.4 Giả sử a và b là hai số tự nhiên và n0 = [a, b] là BSCNN của a và b. Số tự nhiên n là bội của a và b khi và chỉ khi nó là bội số của n0 . 3. Thuật toán tìm bội số chung nhỏ nhất Để tìm bội số chung nhỏ nhất của hai số tự nhiên a và b ta thực hiện hai bước sau: Bước 1: Tìm ƯSCLN của a và b bằng thuật toán Euclid. a.b , đó chính là BSCNN của a và b. (a, b) Ví dụ 1.1 Tìm bội số chung nhỏ nhất của 2004 và 720. Bước 2: Tìm thương Lời giải Trước hết ta tìm ước số chung lớn nhất của 2004 và 720 bằng thuật toán Euclid. 2004 = 720.2 + 564; 720 = 564.1 + 156; 564 = 156.3 + 96; 156 = 96.1 + 60; 96 = 60.1 + 36; 60 = 36.1 + 24; 36 = 24.1 + 12; 24 = 12.2. Suy ra (2004, 720) = 12. Vậy bội số chung nhỏ nhất của 2004 và 720 là 8 2004.720 = 120240. 12 Luận văn thạc sỹ 1.7 Học viên: Trần Thị Thảo Định nghĩa đồ thị Định nghĩa 1.7 • Tập hợp X 6= ∅ các đối tượng và bộ E các cặp sắp thứ tự và không sắp thứ tự các phần tử của X được gọi là một đồ thị, đồng thời được ký hiệu bằng G (X, E) ( hoặc G = (X, E) hoặc G (X) ). • Các phần tử của X được gọi là đỉnh. Cặp đỉnh không sắp thứ tự được gọi là cạnh, cặp đỉnh sắp thứ tự được gọi là cạnh có hướng hay cung. • Đồ thị chỉ chứa các cạnh được gọi là đồ thị vô hướng, còn đồ thị chỉ chứa các cung được gọi là đồ thị có hướng. • Nếu đồ thị chứa cả cạnh lẫn cung thì nó được gọi là đồ thị hỗn hợp hay đồ thị hỗn tạp. • Một cung ( hay một cạnh) có thể bắt đầu hoặc kết thúc tại cùng một đỉnh. Cung hay cạnh loại này được gọi là khuyên hay nút. • Cặp đỉnh x, y được nối với nhau bằng cạnh (cung) a thì x, y được gọi là các đỉnh hay hai đầu của cạnh (cung) a và a được gọi là cạnh (cung) thuộc đỉnh x, đỉnh y • Nếu cung b xuất phát từ đỉnh u và đi vào đỉnh v, thì u được gọi là đỉnh đầu, còn v được gọi là đỉnh cuối của cung b . • Trong trường hợp không cần phân biệt giữa cạnh và cung ta quy ước dùng cạnh thay cho cả cung. • Đồ thị G (X, E) không có khuyên và mỗi cặp đỉnh được nối với nhau bằng không quá một cạnh, được gọi là đồ thị đơn hay đơn đồ thị và thông thường được gọi là đồ thị. • Đồ thị G (X, E) không có khuyên và có ít nhất một cặp đỉnh được nối với nhau bằng từ hai cạnh trở lên được gọi là đa đồ thị. Ví dụ 1.2 Cho đồ thị hỗn hợp có khuyên G (X, E) với tập đỉnh X = {x1 , x2 , x3 , x4 , x5 , x6 , x7 } Tập cạnh và cung: 9 Luận văn thạc sỹ Học viên: Trần Thị Thảo E = {x1 , x2 ; x2 , x3 ; x4 , x6 ; x5 , x6 ; x3 , x3 ; x1 , x6 ; x5 , x5 } = {a1 , a2 , a3 , a4 , a5 , b1 , b2 } trong đó a1 , a2 , a3 , a4 , a5 - các cạnh; b1 , b2 - các cung; cung b1 có x1 là đỉnh đầu, x6 là đỉnh cuối. Dạng biểu diễn hình học của đồ thị G (X, E) trên như sau: Hình 1.1 1.8 Đồ thị gán nhãn P Kí hiệu = {t1 , t2 , . . . , tn } Đồ thị G mà trên mỗi cạnh c của nó được đặt tương ứng với kí hiệu ti ∈ P (1 ≤ i ≤ n) (trên cạnh c ghi kí hiệu ti ) được gọi là đồ thị được gán nhãn. Kí hiệu ti được gọi là nhãn của cạnh c . Đồ thị với nhãn của tất cả các cạnh đều là số, được gọi là đồ thị có trọng số. P Ví dụ 1.3 Cho đồ thị G có dạng sau, với = {t1 , t2 , t3 } Hình 1.2 10 Luận văn thạc sỹ 1.9 Học viên: Trần Thị Thảo Nguồn 1.Định nghĩa 1.8 Nguồn là một đa đồ thị có hướng và có thể có khuyên được gán nhãn mà trên đó tách ra một đỉnh được gọi là đỉnh vào (đỉnh vào được đặt trong một ô tròn có mũi tên đi vào), một tập con các đỉnh được gọi là các đỉnh ra (mỗi đỉnh ra được đặt trong một ô chữ nhật). Nguồn thường được kí hiệu là I Ví dụ 1.4 Cho nguồn I có dạng sau: Hình 1.3 2. Nhãn của nguồn Giả sử nguồn I có đỉnh vào V , tập đỉnh kết là F . * Nhãn của đường: Giả sử ∀a, b ∈ T và T là một đường nào đó đi từ đỉnh a đến đỉnh b T = (a)ci1 ci2 . . . cis . . . cin (b) trong đó cis có nhãn là tis (1 ≤ s ≤ n). Khi đó dãy kí hiệu ti1 , ti2 , . . . , tis , . . . , tin được gọi là nhãn của đường T , và được kí hiệu là T . Như vậy T = ti1 ti2 . . . tis . . . tin Tập gồm nhãn của tất cả các đường đi từ đỉnh a đến đỉnh b trong nguồn I được kí hiệu là NI (a, b). Ví dụ 1.5 Nguồn I trong hình vẽ 3 Xét đường đi từ đỉnh x2 đến đỉnh x5 , khi đó ta có: T = (x2 )(x2 , x4 )(x4 , x3 )(x3 , x5 )(x5 ) ⇒ T = t7 t2 t3 T1 = (x2 )(x2 , x4 )(x4 , x5 )(x5 ) ⇒ T1 = t7 t4 11 Luận văn thạc sỹ Học viên: Trần Thị Thảo NI (x2 , x5 ) = {T , T1 } = {t7 t2 t3 , t7 t4 } * Nhãn của nguồn: Tập gồm nhãn của tất cả các đường xuất phát từ đỉnh vào và đi tới các đỉnh S NI (V, a) , được gọi là nhãn của nguồn I , đồng thời kí kết F , tức là tập a∈F S NI (V, a). hiệu là N (I). Như vậy N (I) = a∈F 12 Chương 2 Một số phương pháp giải bài toán chia hết Bài toán chia hết là một trong những bài toán khó của số học. Có rất nhiều phương pháp để giải quyết bài toán chia hết. Song trong phạm vi hạn hẹp của luận văn, tác giả chỉ xin trình bày các phương pháp cơ bản sau: * Phương pháp đồng dư. * Phương pháp quy nạp. * Phương pháp tiêu chuẩn chia hết. * Phương pháp vận dụng định lý. * Phương pháp nguồn đồng dư. Đối với mỗi phương pháp ngoài phần trình bày nội dung phương pháp, tác giả đều đưa ra một hệ thống ví dụ để vận dụng và các bài tập kèm theo hướng dẫn hoặc đáp số. 2.1 2.1.1 Phương pháp chia có dư Phương pháp chia có dư Giả sử chia số a cho số b được thương là q và dư r, ta viết a = bq + r (r = 1, 2, . . . , q − 1). Khi đó ta xét từng trường hợp của a ứng với (r = 1, 2, . . . , q − 1) để giải quyết bài toán. 13 Luận văn thạc sỹ 2.1.2 Học viên: Trần Thị Thảo Các ví dụ Ví dụ 2.1 Chứng minh với mọi số nguyên a, số a3 − a chia hết cho 6 ( Phương pháp giải bài toán chia hết, Đặng Huy Ruận ) Lời giải Ta có: a3 − a = a (a − 1) (a + 1) Xét các trường hợp của a khi chia a cho 6: • Nếu a = 6q thì a3 − a = 6q (6q − 1) (6q + 1) chia hết cho 6. • Nếu a = 6q + 1 thì a3 − a = (6q + 1)6q(6q + 2) chia hết cho 6. • Nếu a = 6q + 2 thì a3 − a = (6q + 2)(6q + 1)(6q + 3) = 6(3q + 1)(6q + 1)(2q + 1) chia hết cho 6. • Nếu a = 6q +3 thì a3 −a = (6q +3)(6q +2)(6q +4) = 12(2q +1)(3q +1)(3q +2) chia hết cho 6. • Nếu a = 6q + 4 thì a3 − a = (6q + 4)(6q + 3)(6q + 5) = 6(3q + 2)(2q + 1)(6q + 5) chia hết cho 6. • Nếu a = 6q + 5 thì a3 − a = (6q + 5)(6q + 4)(6q + 6) = 12(6q + 5)(3q + 2)(q + 1) chia hết cho 6. Vậy với mọi số nguyên a thì số a3 − a chia hết cho 6. Nhận xét: Ngoài cách giải trên ta còn có thể giải quyết bài toán nhờ tính chất: Tích hai số nguyên liên tiếp luôn chia hết cho 2, tích ba số nguyên liên tiếp luôn chia hết cho 3 mà (2, 3) = 1 do đó a3 − a = a(a − 1)(a + 1) chia hết cho 6. Như vậy tích ba số nguyên liên tiếp luôn chia hết cho 6. Ví dụ 2.2 Cho số nguyên a không chia hết cho 2 và 3. Chứng minh rằng A = 4a2 + 3a + 5 chia hết cho 6. Lời giải Vì a không chia hết cho 2 và 3 nên a có dạng a = 6q + 1 hoặc a = 6q + 5. • Nếu a = 6q + 1 thì A = 4 (6q + 1)2 + 3(6q + 1) + 5 = 6(24q 2 + 11q + 2) chia hết cho 6. • Nếu a = 6q + 5 thì A = 4(6q + 5)2 + 3(6q + 5) + 5 = 6(24q 2 + 43q + 20) chia hết cho 6. 14 Luận văn thạc sỹ Học viên: Trần Thị Thảo Vậy A = 4a2 + 3a + 5 chia hết cho 6 với mọi a không chia hết cho 2 và 3. Ví dụ 2.3 Chứng minh rằng A(n) = n4 + 6n3 + 11n2 + 6n chia hết cho 24. (Thi học sinh giỏi Toán toàn quốc lớp 9 năm 1975) Lời giải Ta có: A(n) = n4 + 6n3 + 11n2 + 6n = n(n + 1)(n + 2)(n + 3) Vì tích của ba số nguyên liên tiếp chia hết cho 3 nên A(n) chia hết cho 3. Vì trong bốn số nguyên liên tiếp luôn có hai số chẵn liên tiếp, một trong hai số chẵn đó chia hết cho 4, số còn lại chia hết cho 2 nên A(n) chia hết cho 8, mà (3, 8) = 1 nên A(n) chia hết cho 24. Ví dụ 2.4 Chứng minh rằng nếu a2 + b2 chia hết cho 3 với mọi a, b nguyên, thì a và b chia hết cho 3. ( Phương pháp giải bài toán chia hết, Đặng Huy Ruận) Lời giải Ta có: a = 3q + r, b = 3p + s trong đó r, s ∈ {−1, 0, 1}. Khi đó: a2 + b2 = (3q + r)2 + (3p + s)2 = 9(q 2 + p2 ) + 6(qr + ps) + r2 + s2 . . . Vì (a2 + b2 ) .. 3 nên (r2 + s2 ) .. 3 Mặt khác r, s ∈ {−1, 0, 1} suy ra r2 + s2 ∈ [0, 2]. Do đó . (r2 + s2 ) .. 3 ⇔ r2 + s2 = 0 ⇔ r = s = 0 Suy ra a = 3q, b = 3p hay a và b chia hết cho 3.. Vậy nếu a2 + b2 chia hết cho 3 với mọi a, b nguyên, thì a và b chia hết cho 3. Ví dụ 2.5 Chứng minh rằng với mọi số nguyên không âm n, hiệu A(n) = n5 −n chia hết cho 5. Lời giải Ta có: A(n) = n(n − 1)(n + 1)(n2 + 1) 15 Luận văn thạc sỹ Học viên: Trần Thị Thảo Số n có thể biểu diễn bằng một trong các dạng sau: n = 5q; n = 5q + 1; n = 5q + 2; n = 5q + 3; n = 5q + 4 Xét các trường hợp của n và làm tương tự như trong ví dụ 2.1 . ta có A(n) = (n5 − n) .. 5 Nhận xét: Ngoài cách giải trên ta cũng có thể làm cách khác như sau: • Nếu n tận cùng bằng một trong các chữ số 0, 1, 4, 5, 6, 9 thì một trong ba . thừa số đầu tiên của A(n) chia hết cho 5 do đó A(n) .. 5 • Nếu n tận cùng bằng một trong các chữ số 2, 3, 7, 8 thì n2 sẽ tận cùng . bằng chữ số 4 hoặc 9 nên n2 +1 sẽ tận cùng bằng 5 hoặc 0 suy ra (n2 +1) .. 5 . do đó A(n) .. 5 . Vậy A(n) = (n5 − n) .. 5 2.1.3 Các bài toán tương tự Bài 2.1 Chứng minh rằng với mọi số nguyên a , số a(a6 − 1) chia hết cho 7. Bài 2.2 Chứng minh rằng số A = n5 − n3 + 4n chia hết cho 120. Bài 2.3 Chứng minh rằng với mọi số nguyên không âm n , số n2 + n + 1 không chia hết cho 2005. Bài 2.4 Chứng minh: Nếu với các số nguyên a, b mà a2 + b2 chia hết cho 7 thì a và b chia hết cho 7. Bài 2.5 Chứng minh n2 + n + 2 không chia hết cho 15, với mọi n nguyên. Bài 2.6 Chứng minh rằng m3 + 3m2 − m − 3 chia hết cho 48, với mọi m lẻ. Bài 2.7 Chứng minh rằng n4 − 4n3 − 4n2 + 16n chia hết cho 384, với mọi số tự nhiên n chẵn. (Thi học sinh giỏi toàn quốc lớp 9 năm 1970) 2.2 2.2.1 Phương pháp đồng dư Phép đồng dư 1. Định nghĩa 2.1 Cho a, b là các số nguyên và m là số nguyên dương. Ta nói a đồng dư với b theo môđun m và kí hiệu a ≡ b (mod m) nếu a và b có cùng số dư khi chia cho m. . Như vậy a ≡ b (mod m) ⇔ (a − b).. m 16 Luận văn thạc sỹ Học viên: Trần Thị Thảo 2. Tính chất (a) a ≡ a (mod m). (b) a ≡ b (mod m) ⇒ b ≡ a (mod m). (c) a ≡ b (mod m), b ≡ c (mod m) ⇒ a ≡ c (mod m). (d) a ≡ b (mod m) ⇒ a + c ≡ b + c (mod m), ∀c ∈ Z. (e) a ≡ b (mod m) ⇒ ac ≡ bc (mod m). (f) ac ≡ bc (mod m) và (c, m) = 1 ⇒ a ≡ b (mod m). (g) a ≡ b (mod m) ⇒ ak ≡ bk (mod m), k ≥ 1 (h) (a + b)m ≡ bm (mod m), (a > 0) 2.2.2 Vận dụng phương pháp đồng dư để giải toán Sau đây là một số ví dụ sử dụng các tính chất của đồng dư để giải quyết các bài toán chia hết. Ví dụ 2.6 Chứng minh rằng A = 51.43n + 10.3n chia hết cho 61. Lời giải Ta có: A = 51.43n + 10.3n = 51.64n + 10.3n . Vì 64 ≡ 3 (mod 61) nên 64n ≡ 3n (mod 61). Do đó: A ≡ 51.3n + 10.3n ≡ 61.3n ≡ 0 (mod 61). Vậy A = 51.43n + 10.3n chia hết cho 61. Ví dụ 2.7 Tìm số dư của số A = 20142014 + 20152015 + 20162016 khi chia cho 3. Lời giải Tìm số dư của số A = 20142014 + 20152015 + 20162016 khi chia cho 3. Ta có: 2015 ≡ 2 (mod 3) ⇒ 20152015 ≡ 22015 (mod 3). Mà: 22 ≡ 1 (mod 3); 2015 = 2.1007 + 1, 17 Luận văn thạc sỹ Học viên: Trần Thị Thảo nên: 20152015 ≡ 2 (mod 3) Ta có: 2016 ≡ 0 (mod 3) ⇒ 20162016 ≡ 0 (mod 3); 2014 ≡ 1 (mod 3) ⇒ 20142014 ≡ 1 (mod 3). Do đó: A ≡ 0 + 1 + 2 ≡ 0 (mod 3) hay A chia hết cho 3 . 2004n + 1920 chia hết cho 124, ∀n ∈ N∗ . Ví dụ 2.8 Chứng minh 19242003 Lời giải Đặt: 2004n A = 19242003 + 1920. Ta có: 124 = 4.31. Dễ thấy A chia hết cho 4 (vì 1924 và 1920 chia hết cho 4), do đó ta chỉ cần chứng minh A chia hết cho 31. Vì: 1924 ≡ 2 (mod 31); 1920 ≡ −2 (mod 31) Nên: 2004n A ≡ 22003 −2 (mod 31) n Ta có 25 = 32 ≡ 1 (mod 5) nên ta cần tìm số dư của 20032004 khi chia cho 5. Ta có: 2003 ≡ 3 n n (mod 5) ⇒ 20032004 ≡ 32004 (mod 5). Ta có 34 ≡ 1 (mod 5) nên ta cần tìm số dư của 2004n khi chia cho 4. Ta có: 2004 ≡ 0 (mod 4) ⇒ 2004n ≡ 0 (mod 4) ⇒ 2004n = 4k, (k ∈ N∗ ). Suy ra: n n k 20032004 ≡ 32004 = 34k = 34 ≡ 1 n (mod 5) ⇒ 20032004 = 1 + 5m, (m ∈ N∗ ) Từ đó ta có: 2004n 22003 m = 21+5m = 2.25 ≡ 2.1 ≡ 2 18 (mod 31) Luận văn thạc sỹ Học viên: Trần Thị Thảo Vậy: 2004n A ≡ 22003 −2≡2−2≡0 (mod 31) hay A chia hết cho 31. Ví dụ 2.9 Một số tự nhiên khi chia cho 4 dư 3, chia cho 17 dư 9, chia cho 19 dư 13. Hỏi số đó chia cho 1292 dư bao nhiêu? (Các chuyên đề số học bồi dưỡng học sinh giỏi trung học cơ sở, Phạm Minh Phương và nhóm giáo viên chuyên toán đại học sư phạm Hà Nội 2005) Lời giải Gọi A là số tự nhiên cần tìm. Theo bài ra ta có:  A ≡ 3 (mod 4) A ≡ 9 (mod 17) A ≡ 13 (mod 19)  Từ A ≡ 13 (mod 19) ⇒ A = 19k + 13. Mà A ≡ 9 (mod 17), nên 19k + 13 ≡ 9 (mod 17) ⇔ 2k + 4 ≡ 0 (mod 17) ⇔k+2≡0 (mod 17) ⇔ k ≡ −2 (mod 17) Hay k = 17m − 2. Suy ra: A = 19(17m − 2) + 13 = 323m − 25. Vì A ≡ 3 (mod 3) nên: 323m − 25 ≡ 3 (mod 4) ⇔ 3m ≡ 0 (mod 4) ⇔ m ≡ 0 (mod 4) ⇔ m = 4t Do đó: A = 323.4t − 25 = 1292t − 25 ⇒ A ≡ −25 ≡ 1267 (mod 1292). Vậy A chia cho 1292 dư 1267. 99 Ví dụ 2.10 Tìm hai chữ số tận cùng của số A = 79 . (Các chuyên đề số học bồi dưỡng học sinh giỏi trung học cơ sở, Phạm Minh Phương và nhóm giáo viên chuyên toán đại học sư phạm Hà Nội 2005) 19