Tài liệu Luận văn về hàm tổng lcm

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC PHẠM VĂN DỰC VỀ HÀM TỔNG - LCM LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2016 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC PHẠM VĂN DỰC VỀ HÀM TỔNG - LCM LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60 46 01 13 NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. TS. Nông Quốc Chinh Thái Nguyên - 2016 i Mục lục Danh mục ký hiệu . . . . . . . . . . . . . . . . . . . . . . . . ii Lời mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 Một vài tính chất của bội chung nhỏ nhất 4 1.1 Khái niệm . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Các thuật toán tìm bội chung nhỏ nhất . . . . . . . . . . . 13 1.2.1 Rút gọn về tìm ước chung lớn nhất . . . . . . . . . . 13 1.2.2 Phương pháp dùng phân tích thừa số nguyên tố . . . 16 1.2.3 Phương pháp dùng bảng . . . . . . . . . . . . . . . 18 2 Hàm tổng bội chung nhỏ nhất 2.1 4 20 Một số kết quả thường dùng . . . . . . . . . . . . . . . . . 20 2.1.1 Tích chập Dirichlet . . . . . . . . . . . . . . . . . . 20 2.1.2 Hàm phi Euler . . . . . . . . . . . . . . . . . . . . . 21 2.1.3 Đa thức Bernoulli . . . . . . . . . . . . . . . . . . . 22 2.1.4 Công thức tổng Abel . . . . . . . . . . . . . . . . . 22 2.2 Hàm tổng của bội chung nhỏ nhất . . . . . . . . . . . . . . 23 2.3 Hàm tổng nghịch đảo của bội chung nhỏ nhất . . . . . . . . 29 3 Ứng dụng của lý thuyết về bội chung nhỏ nhất của các số nguyên dương trong Toán học phổ thông 36 3.1 Ứng dụng trong toán học phổ thông . . . . . . . . . . . . . 36 3.2 Một số bài toán Olympic về bội chung nhỏ nhất . . . . . . 39 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . 45 ii Danh mục ký hiệu N tập số tự nhiên Z tập số nguyên lcm(a, b) BCNN của hai số nguyên a và b gcd(a, b) ƯCLN của hai số nguyên a và b d|a d là ước của a f ∗g tích chập Dirichlet Bn (x) đa thức Bernoulli ϕ(n) hàm phi Euler µ(n) hàm Möbius ζ(s) hàm zeta Riemann 1 Lời mở đầu Trong số học, bội chung nhỏ nhất (least common multiple) của hai số nguyên a và b là số nguyên dương nhỏ nhất chia hết cho cả a và b. Ước chung lớn nhất của hai số nguyên a và b là số nguyên dương lớn nhất là ước của cả hai số nguyên a, b. Các kiến thức về bội chung nhỏ nhất và ước chung lớn nhất đã được giảng dạy từ đầu bậc học trung học. Trong khi ước chung lớn nhất của hai số nguyên được nhiều nhà Toán học nghiên cứu và tìm được nhiều ứng dụng trong các lĩnh vực toán học thì ngược lại, bội chung nhỏ nhất của hai số nguyên lại ít được nghiên cứu hơn rất nhiều. Ngoài các tính chất cổ điển, ứng dụng và thuật toán để tính bội chung nhỏ nhất của hai số nguyên đã biết thì các kiến thức mở rộng về nó còn hạn chế. Hàm tổng bội chung nhỏ nhất l(n) := n X lcm(j, n) j=1 được nghiên cứu bởi một số tác giả. Năm 1975, Alladi [1] nghiên cứu tổng n X (lcm(j, n))r (r ∈ R, r ≥ 1) j=1 và thu được n XX n≤x j=1 (lcm(j, n))r = ζ(r + 2) x2r+2 + O(x2r+1+ε ), 2 2(r + 1) ζ(2) Năm 2007, Bordellès [2] cải tiến sai số trong kết quả của Alladi trong trường hợp r = 1 và mở rộng cho trường hợp r = −1 bằng các kết quả 2 sau 1 l(n) = ((Id2 ·(ϕ + τ0 )) ∗ Id)(n), 2 n XX ζ(3) 4 lcm(j, n) = x + O(x3 (log x)2/3 (log log x)4/3 ) (x > e), 8ζ(2) n≤x j=1   12  n XX (log x)3 (log x)2 1 A = + γ + log + O(log x), lcm(j, n) 6ζ(2) 2ζ(2) 2π n≤x j=1 trong đó Ida = na (a ∈ Z),  1, τ0 (n) = 0, nếu n = 1; nếu ngược lại, F ∗ G là tích chập Dirichlet thông thường, và A là hằng số GlaisherKinkelin. Gần đây nhất, năm 2014, Ikeda và Matsuoka [3] định nghĩa hai hàm La (n) := n X (lcm(j, n))a j=1 Ta (x) := X La (n) n≤x với mọi a ∈ Z và x ≥ 1. Các tác giả nghiên cứu Ta (x) với a ≥ 2: X La (n) = n≤x ζ(a + 2) x2a+2 + O(x2a+1 (log x)2/3 (log log x)4/3 ) 2 2(a + 1) ζ(2) khi x → ∞, trong đó hằng số sinh ra chỉ phụ thuộc a, x ≥ 1 và k ∈ N với k ≥ 2. Với a ≤ −2, các tác giả thu được: với x ≥ 1 và k ∈ N với k ≥ 2, thì ∞ X   ζ(k) ζ(k)2 1+ L−k (n) = 2 ζ(2k) n=1 và   ζ(k) ζ(k)2 ζ(k)x−k+1 log x L−k (n) = 1+ − + O(x−k+1 ) 2 ζ(2k) (k − 1)ζ(k + 1) n≤x X 3 khi x → ∞, trong đó hằng số sinh ra chỉ phụ thuộc vào k. Mục tiêu của luận văn này là tổng hợp các tính chất của bội chung nhỏ nhất và trình bày kết quả về hàm tổng bội chung nhỏ nhất. Xuất phát từ những lí do đó nên tôi mạnh dạn chọn đề tài: “Về hàm tổng - Lcm” dưới sự hướng dẫn của PGS. TS. Nông Quốc Chinh. Ngoài phần mở đầu và tài liệu tham khảo, bố cục của luận văn gồm ba chương. Chương I trình bày những kiến thức chuẩn bị là cơ sở lý thuyết cho chương sau, bao gồm các khái niệm về bội chung nhỏ nhất, ước chung lớn nhất, mối liên hệ giữa bội chung nhỏ nhất và ước chung lớn nhất, các cách tính bội chung nhỏ nhất. Chương II trình bày các đánh giá về giá trị hàm tổng bội chung nhỏ nhất. Các kết quả này nằm trong hai bài báo của Bordellès trong [2] và của S. Ikeda và K. Matsuoka trong [3]. Chương III đưa ra ứng dụng lý thuyết về bội chung nhỏ nhất của các số nguyên dương trong Toán học phổ thông. Lời đầu tiên, tôi xin kính gửi lời cảm ơn sâu sắc và chân thành nhất tới PGS. TS. Nông Quốc Chinh - Trường Đại học Khoa học - Đại học Thái Nguyên vì sự tận tình giúp đỡ và chỉ bảo của thầy đối với tôi trong thời gian làm luận văn. Tôi cũng xin gửi lời cảm ơn đến Quý Thầy Cô Trường Đại học Khoa học - Đại học Thái Nguyên đã tận tình giảng dạy tôi trong suốt khóa học. Tôi xin cảm ơn Ban giám hiệu, Ban chủ nhiệm khoa Toán - Tin, Phòng Đào tạo - Trường Đại học Khoa học - Đại học Thái Nguyên đã giúp đỡ và tạo điều kiện cho tôi trong thời gian học tại trường. Xin gửi lời cảm ơn đến Quý Thầy, Cô trong Hội đồng chấm luận văn đã dành thời gian quý báu để đọc, chỉnh sửa, góp ý và phản biện cho tôi hoàn thành luận văn này một cách hoàn chỉnh nhất. Thái Nguyên, tháng 06 năm 2016 Học viên Phạm Văn Dực 4 Chương 1 Một vài tính chất của bội chung nhỏ nhất Chương này trình bày những kiến thức chuẩn bị là cơ sở lý thuyết cho chương sau, bao gồm các khái niệm về bội chung nhỏ nhất, ước chung lớn nhất, mối liên hệ giữa bội chung nhỏ nhất và ước chung lớn nhất, các cách tính bội chung nhỏ nhất. Nội dung của chương được tham khảo chủ yếu trong các tài liệu [4, 5, 6]. 1.1 Khái niệm Trong lý thuyết số, tập số tự nhiên là N = {1, 2, 3, 4, . . .}, và tập số nguyên là Z = {. . . , −3, −2, −1, 0, 1, 2, 3 . . .}. Định nghĩa 1.1.1. Số nguyên k được gọi là bội số của một số nguyên a khi và chỉ khi tồn tại một số nguyên b sao cho k = ab. Trong trường hợp này ta cũng nói k chia hết cho a. Định nghĩa 1.1.2. Một số nguyên dương k được gọi là bội chung của hai số nguyên a và b nếu k là bội số của a và k cũng là bội số của b. 5 Tương tự ta cũng có định nghĩa bội số chung của n số nguyên a1 , a2 , . . . , an . Định nghĩa 1.1.3. Số nguyên dương k được gọi là bội chung nhỏ nhất của hai số nguyên a và b nếu k là bội số chung của a và b và với mọi số nguyên dương k 0 là bội chung của a và b thì k ≤ k 0 . Ký hiệu lcm(a, b) = k. Ví dụ 1.1.4. Các bội của 4 là: 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, . . . và các bội của 6 là: 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, . . . Bội chung của 4 và 6 là các số cùng thuộc cả hai danh sách trên: 12, 24, 36, 48, 60, 72, . . . Do đó, từ danh sách một vài bội chung đầu tiên của 4 và 6 này, bội chung nhỏ nhất của 4 và 6 là lcm(4, 6) = 12. Khi cộng, trừ, hay so sánh các phân số tầm thường, một cách đơn giản là tìm bội số chung nhỏ nhất của các mẫu số, thường được gọi là mẫu số chung nhỏ nhất, bởi vì mỗi phân số có thể được biểu diễn thành một phân số với mẫu số này. Ví dụ, 2 1 4 7 11 + = + = 21 6 42 42 42 trong đó mẫu số 42 là bội chung nhỏ nhất của 21 và 6. Mệnh đề 1.1.5. Bội chung nhỏ nhất của hai số nguyên a và b là tồn tại và duy nhất. Chứng minh. Cho trước hai số nguyên a và b, khi đó |ab| là bội chung của a và b. Do đó luôn tồn tại bội chung của hai số. Suy ra tập tất cả các bội chung của a và b khác rỗng. Theo nguyên lý sắp thứ tự tốt (well-ordering principle), mọi tập số nguyên dương khác rỗng đều có phần tử nhỏ nhất. Do đó tồn tại lcm(a, b). 6 Để chứng minh tính duy nhất, gọi m = lcm(a, b), n = lcm(a, b). Khi đó ta có với mọi số nguyên dương c sao cho a | c và b | c thì m | c. Vậy ta có m | n và n | m. Suy ra m = ±n. Do m, n > 0, m = n.  Định nghĩa 1.1.6. Một số nguyên d được gọi là ước số của số nguyên a khi và chỉ khi tồn tại một số nguyên b sao cho a = bd. Ký hiệu d | a. Định nghĩa 1.1.7. Một số nguyên p được gọi là số nguyên tố nếu (i) p > 1, (ii) p không có ước số ngoại trừ 1 và p. Ví dụ, 37 là một số nguyên tố, 1 không phải là một số nguyên tố. Mọi số nguyên lớn hơn 1 không phải là số nguyên tố được gọi là hợp số. Định lý 1.1.8. Mọi số nguyên dương, ngoại trừ 1, đều là tích của các số nguyên tố. Chứng minh. Hoặc n là số nguyên tố thì n = 1 · n, hoặc n là hợp số có ước nằm giữa 1 và n. Nếu m là ước số nhỏ nhất của n, m là số nguyên tố. Thật vậy, vì nếu ngược lại, tồn tại l sao cho 1 < l < m và l | m kéo theo l | n, mẫu thuẫn với định nghĩa của m. Vậy m là số nguyên tố. Do đó n là số nguyên tố hoặc n chia hết cho một số nguyên tố nhỏ hơn n, đặt là p1 , trong trường hợp này n = p1 n1 , 1 < n1 < n. Ở đây, hoặc n1 là số nguyên tố, ta chứng minh xong, hoặc nó chia hết cho số nguyên tố p2 lớn hơn 1, trong trường hợp này n = p1 n1 = p1 p2 n2 , 1 < n2 < n1 < n. Lập luận tương tự, ta thu được một dãy số giảm n, n1 , . . . , nk−1 , . . . tất cả đều lớn hơn 1. Sớm hay muộn ta sẽ gặp nk−1 là một số nguyên tố, đặt là pk , và khi đó n = p1 p 2 · · · pk . (1.1) 7  Các số nguyên tố trong (1.1) không nhất thiết phân biệt, cũng không bắt buộc sắp xếp theo thứ tự đặc biệt. Nếu ta sắp xếp lại chúng theo thứ tự tăng dần, liên kết các số nguyên tố bằng nhau bằng các nhân tử đơn, và đổi ký hiệu một cách thích hợp, ta thu được n = pa11 pa22 · · · pakk (a1 > 0, a2 > 0, . . . , p1 < p2 < . . .). (1.2) Khi đó ta nói rằng n được biểu diễn dưới dạng cơ bản. Ví dụ, 666 = 2 · 3 · 3 · 37 = 2 · 32 · 37. Định lý 1.1.9. Dạng cơ bản của số nguyên n là duy nhất. Trước khi chứng minh định lý trên ta cần kết quả sau. Định lý 1.1.10. Nếu p là số nguyên tố, và p | ab, thì p | a hoặc p | b. Chứng minh. Giả sử p là số nguyên tố và p | ab. Nếu p | a ta chứng minh xong. Nếu p - a thì gcd(a, p) = 1 do p là số nguyên tố. Khi đó tồn tại hai số nguyên x và y sao cho xa + yp = 1 hay xab + ypb = b. Nhưng p | ab và p | pb, và do đó p | b.  Chứng minh của Định lý 1.1.9. Từ Định lý 1.1.10 suy ra p | abc · · · l ⇒ p | a hoặc p | b hoặc p | c . . . hoặc p | l, và nói riêng a, b, c, . . . , l là các số nguyên tố, nên p là một trong các số a, b, . . . , l. Bây giờ, giả sử rằng b n = pa11 · pa22 · · · pakk = q1b1 · q2b2 · · · qj j , b hai tích trên có dạng cơ bản. Khi đó pi | q1b1 · · · q2b2 · · · qj j với mọi i, nên mọi p đều là một số q , và tương tự mọi số q đều là một số p nào đó. Do 8 vậy k = j và vì cả hai tập được sắp xếp theo thứ tự tăng dần, pi = qi với mọi i. Nếu ai > bi và ta chia cho pbi i , ta thu được b b i−1 i+1 pa11 · · · pai i −bi · · · pakk = pb11 · · · pi−1 pi+1 · · · pbkk . Vế trái chia hết cho pi , trong khi vế phải không chia hết cho pi . Vậy mâu thuẫn. Tương tự bi > ai cũng suy ra mâu thuẫn. Suy ra ai = bi với mọi i. Định lý được chứng minh.  Bổ đề 1.1.11. Cho hai số nguyên a và b có phép phân tích nhân tử a = pk11 pk22 · · · pks s và b = pt11 pt22 · · · ptss . Khi đó a | b khi và chỉ khi ki ≤ ti với 1 ≤ i ≤ s. Chứng minh. Nếu p là số nguyên tố, m và n là các số nguyên sao cho α là bậc lũy thừa cao nhất của p để pα | m và β là bậc lũy thừa cao nhất của p để pβ | n thì tồn tại q, q 0 ∈ Z sao cho m = pα q , n = pβ q 0 . Do đó mn = pα+β q 00 , với q 00 ∈ Z. Cho nên, α + β là bậc lũy thừa cao nhất của p mà pα+β | mn. Nếu a | b thì b = au với u ∈ Z nào đó. Do đó, với mỗi i, 1 ≤ i ≤ s, bậc lũy thừa cao nhất của pi là ước của b bằng tổng bậc lũy thừa cao nhất của pi là ước của a và u. Do đó, ki ≤ ti với 1 ≤ i ≤ s. Ngược lại, giả sử ki ≤ ti với mọi 1 ≤ i ≤ s. Đặt ui = ti − ki với 1 ≤ i ≤ s. Đặt w = pu1 i pu2 2 · · · pus s . Thì b = aw. Nên a | b.  Ký hiệu min(x, y) và max(x, y) tương ứng là số nhỏ hơn và lớn hơn trong hai số x và y . Định lý 1.1.12. Nếu a = pk11 pk22 · · · pks s và b = pt11 pt22 · · · ptss , thì lcm(a, b) = pu1 1 pu2 2 · · · pus s trong đó ui = max(ki , ti ), 1 ≤ i ≤ s. Chứng minh. Đặt m = pu1 1 pu2 2 · · · pus s trong đó ui = max(ki , ti ), 1 ≤ i ≤ s. Vì ki ≤ ui và ti ≤ ui với mọi 1 ≤ i ≤ s nên theo Bổ đề 1.1.11, a | m, b | m. 9 ws 1 w2 Nếu c là một số nguyên sao cho a | c và b | c. Viết c = pw 1 p2 · · · ps . Khi đó theo Bổ đề 1.1.11, ki ≤ wi và ti ≤ wi với mọi 1 ≤ i ≤ s. Do đó, ui = max(ki , ti ) ≤ wi với mọi 1 ≤ i ≤ s. Theo Bổ đề 1.1.11, m | c. Suy ra m = lcm(a, b).  Định nghĩa 1.1.13. Một số nguyên dương d được gọi là ước chung của hai số nguyên a và b khi và chỉ khi d là ước số của a và d cũng là ước số của b. Định nghĩa 1.1.14. Ước chung lớn nhất của hai số nguyên a và b không đồng thời bằng 0, ký hiệu là gcd(a, b), là số nguyên dương lớn nhất d sao cho d | a và d | b. Ví dụ 1.1.15. gcd(1, 2) = 1, gcd(5, 10) = 5, gcd(6, 27) = 3, và với bất kỳ a, gcd(0, a) = gcd(a, 0) = a. Mệnh đề 1.1.16. Cho hai số nguyên không đồng thời bằng 0. Khi đó luôn tồn tại duy nhất một số tự nhiên thỏa mãn định nghĩa của ước chung lớn nhất. Chứng minh. Cho a, b ∈ Z không đồng thời bằng 0. Đặt S = {ma + nb : m, n ∈ Z và ma + nb > 0}. Rõ ràng S ⊂ Z, S 6= ∅ vì ta có thể chọn m, n = ±1 phụ thuộc vào dấu của a và b để ma + nb ∈ S . Khi đó theo nguyên lý sắp thứ tự tốt, S có phần tử nhỏ nhất, ký hiệu là g , g = m0 a + n0 b, m0 , n0 ∈ Z. Ta sẽ chứng minh g là ước chung lớn nhất của a và b. Đầu tiên, giả sử rằng g - a. Khi đó tồn tại duy nhất hai số q, r ∈ Z, với 0 ≤ r < g , sao cho a = qg + r. Theo giả sử, g - a, nên ta có 0 < r = a−qg = a−q(m0 a+n0 b) = a−qm0 a−qn0 b = (1−qm0 )a−qn0 b < g. Suy ra r là một phần tử của S mà nhỏ hơn g , mâu thuẫn với giả thiết. Do đó g | a. Tương tự, ta chứng minh được g | b. Giả sử h ∈ N là ước chung của a và b. Khi đó tồn tại k, l ∈ Z sao cho a = kh và b = lh, và ta có g = m0 a + n0 b = m0 kh + n0 lh = (m0 k + n0 l)h, 10 nên h | g . Do đó g là ước chung lớn nhất của a và b. Để chứng minh tính duy nhất, giả sử g 0 ∈ N cũng là ước chung lớn nhất của a và b. Khi đó ta có g 0 | g và g | g 0 , nên g = ±g , vì g, g 0 > 0, g = g 0 .  Định lý 1.1.17. Nếu a = pk11 pk22 · · · pks s và b = pt11 pt22 · · · ptss , thì gcd(a, b) = pv11 pv22 · · · pvss trong đó vi = min(ki , ti ) với mỗi 1 ≤ i ≤ s. Chứng minh. Đặt m = p1u1 pu2 2 · · · pus s trong đó ui = min(ki , ti ), 1 ≤ i ≤ s. Vì ui ≤ ki và ui ≤ ti với mọi 1 ≤ i ≤ s nên theo Bổ đề 1.1.11, m | a, m | b. ws 1 w2 Nếu c là một số nguyên sao cho c | a và c | b. Viết c = pw 1 p2 · · · ps . Khi đó theo Bổ đề 1.1.11, wi ≤ ki và wi ≤ ti ⇒ wi ≤ min(ki , ti ) = ui với mọi 1 ≤ i ≤ s. Theo Bổ đề 1.1.11, c | m. Suy ra m = gcd(a, b).  Từ Định lý 1.1.12 và Định lý 1.1.17 ta suy ra Định lý 1.1.18. Bội chung nhỏ nhất của hai số a và b liên hệ với ước chung lớn nhất của a và b theo công thức lcm(a, b) = |a · b| gcd(a, b) (1.3) Chứng minh. Giả sử a và b có phép phân tích nhân tử a = pk11 pk22 · · · pks s và b = pt11 pt22 · · · ptss . Do ki + ti = max(ki , ti ) + min(ki , ti ) với 1 ≤ i ≤ s. Vì vậy, ab = (pk11 pk22 · · · pks s ) · (pt11 pt22 · · · ptss ) = pk11 +t1 pk22 +t2 · · · pks s +ts = (pu1 1 pu2 2 · · · pus s ) · (pv11 pv22 · · · pvss ) = lcm(a, b) gcd(a, b).  Định lý 1.1.19. Cho a và b là các số nguyên dương, và đặt c = lcm(a, b). Gọi C là tập tất cả các bội chung của a và b. Tức là C = {z ∈ N : a | z và b | z}. Khi đó C = cN. 11 Chứng minh. Bởi vì c là bội chung của a và b, nên cả a và b đều là ước của c. Do vậy chúng cũng là ước của cn với bất kỳ n ∈ N. Nói cách khác, mọi cn là bội chung của a và b, nên cũng là một phần tử của C. Do đó, ta có cN ⊂ C. Để chứng minh chiều ngược lại, lấy d ∈ C, d là bội chung bất kỳ của a và b. Ta phải chỉ ra d ∈ cN. Để làm được điều này, ta áp dụng thuật toán chia, biểu diễn d = cq + r trong đó q và r là các số nguyên không âm, 0 ≤ r < c. Bây giờ cả d và c là bội của a, nên ta có thể viết c = as và d = at với s và t là các số nguyên dương. Thay vào đẳng thức trên dẫn tới at = asq + r. Chuyển vế và biến đổi ta được r = a(t − sq), chứng tỏ a là ước của r. Lập luận hoàn toàn tương tự cho b chứng tỏ b là ước của r. Do đó, r là bội chung của a và b. Bây giờ vì r < c, mà c là bội chung nhỏ nhất kéo theo r không thể là số dương. Vậy r = 0, và theo đẳng thức trên d = cq . Điều này chỉ ra d là một phần tử của cN. Vậy C ⊂ cN. Điều phải chứng minh.  Định lý trên chỉ ra bội chung nhỏ nhất của hai số nguyên là một ước của tất cả các bội chung khác của hai số đó. Định nghĩa 1.1.20. Hai số nguyên a và b được gọi là nguyên tố cùng nhau nếu gcd(a, b) = 1. Ví dụ, ta có 3 và 4 nguyên tố cùng nhau vì gcd(3, 4) = 1; 3 và 5 nguyên tố cùng nhau vì gcd(3, 5) = 1, 3 và 6 không nguyên tố cùng nhau do gcd(3, 6) = 3 6= 1. Định lý 1.1.21. Nếu r và s là hai số nguyên dương, và gcd(r, s) = 1 thì lcm(r, s) = rs. Chứng minh. Đặt c = lcm(r, s). Vì rs là bội chung của r và s, và c là bội chung nhỏ nhất, ta có c ≤ rs. Bây giờ ta có c là bội của r nên ta có thể viết c = rt với t là số nguyên dương. Bằng phép thế ta có c = rt ≤ rs nên t ≤ s. 12 Tiếp theo, sử dụng kết quả c cũng là bội của s, ta thu được s | c = rt, nên s | rt. Nhưng s và r nguyên tố cùng nhau. Do đó s | t. Vì t ≤ s, suy ra s = t. Cuối cùng, dùng hệ thức c = rt, ta thu được c = rs. Điều phải  chứng minh. Định lý 1.1.22. Nếu a, b và t là các số nguyên dương, thì lcm(at, bt) = t · lcm(a, b). Chứng minh. Đặt c = lcm(a, b) và d = lcm(at, bt). Khi đó a | c và b | c, nên at | ct và bt | ct. Điều này chỉ ra ct là bội chung của at và bt, nên ct ≥ d = lcm(at, bt). Mặt khác, ta có at | d và bt | d, nên ta có thể viết d = atx = bty với x và y là các số nguyên dương. Khi khi đó a | (d/t) và b | (d/t), nên d/t là bội chung của a và b. Điều này kéo theo d/t ≥ c, là bội chung nhỏ nhất. Nhân cả hai vế với t kéo theo d ≥ ct. Kết hợp với bất đẳng thức cd ≥ d, chứng tỏ d = ct. Tức là, ta có lcm(at, bt) = t · lcm(a, t).  Định lý 1.1.23. Cho các số nguyên a, b và c, ta có (i) lcm(a, b) = lcm(b, a), (ii) lcm(a, lcm(b, c)) = lcm(lcm(a, b), c) (iii) a = lcm(a, b) ⇔ b | a, (iv) lcm(a, gcd(a, b)) = a, Chứng minh. (i) Ta có lcm(a, b) = b·a a·b = = lcm(b, a). gcd(a, b) gcd(b, a) (ii) Nếu số nguyên tố p xuất hiện trong phân tích thừa số nguyên tố của a với số mũ a1 , trong phân tích của b với thừa số b1 và trong phân tích của c với thừa số c1 . Không mất tính tổng quát, giả sử a1 < b1 < c1 thì số mũ của p trong phân tích thừa số của lcm(b, c) là c1 , số mũ của p trong phân tích thừa số của lcm(a, lcm(b, c)) là c1 . Số mũ của p trong 13 phân tích thừa số của lcm(a, b) là b1 , số của p trong phân tích thừa số của lcm(a, lcm(b, c)) là c1 . Do đó lcm(a, lcm(b, c)) = lcm(lcm(a, b), c). (iii) Nếu b | a, thì tồn tại số nguyên c để bc = a hay a là bội của b. Hiển nhiên a cũng là bội của a. Vậy a là bội chung của a và b. Hơn nữa a là bội chung nhỏ nhất của a và b nên a lcm(a, b). Ngược lại, a = lcm(a, b) nên a là bội của b, kéo theo b | a. (iv) Đặt c = gcd(a, b), khi đó tồn tại số nguyên dương x sao cho cx = a. Vậy lcm(a, gcd(a, b)) = lcm(a, c) = lcm(cx, c) = cx = a. 1.2 1.2.1  Các thuật toán tìm bội chung nhỏ nhất Rút gọn về tìm ước chung lớn nhất Định lý 1.1.18 cho phép chúng ta rút gọn bài toán tìm bội chung nhỏ nhất thành bài toán tìm ước chung lớn nhất: lcm(a, b) = |a · b| . gcd(a, b) Ví dụ 1.2.1. Ta có lcm(21, 6) = lcm(48, 180) = 21 · 6 126 = = 42, gcd(21, 6) 3 48 · 180 8640 = = 720. gcd(48, 180) 12 Công thức trên cũng đúng khi một trong hai số a và b bằng 0, vì gcd(a, 0) = |a|. Chúng ta có sẵn các thuật toán nhanh để tìm ước chung lớn nhất mà không yêu phải phân tích nhân tử các số, ví dụ như thuật toán Euclid. Bởi vì gcd(a, b) là ước của cả a và b, để tính bội chung nhỏ nhất ta có thể thực hiện phép chia trước rồi mới thực hiện phép nhân. Tức là     |a| |b| |a · b| = · |b| = · |a|. (1.4) lcm(a, b) = gcd(a, b) gcd(a, b) gcd(a, b) 14 Ba cách viết trên cho ta kết quả giống nhau. Nhưng trong tính toán thực hành, hai cách viết sau giúp giảm kích thước tính toán cho cả phép chia và phép nhân, đồng thời giảm yêu cầu lượng bộ nhớ cần thiết để lưu trữ các giá trị trung gian (tránh được lỗi tràn bộ nhớ). Ví dụ 1.2.2. Xét lại Ví dụ 1.2.1, sử dụng (1.4) ta có thể đơn giản việc tính toán như sau 6 6 · 21 = · 21 = 42 gcd(21, 6) 3 48 48 lcm(48, 180) = · 180 = · 180 = 4 · 180 = 720. gcd(48, 180) 12 lcm(21, 6) = Ý tưởng của thuật toán Euclid dựa trên nguyên lý rằng ước chung lớn nhất của hai số không đổi nếu số lớn hơn được thay bằng hiệu của nó với số nhỏ hơn. Khi đó, từ đẳng thức gcd(a, b) = gcd(a − b, b) ta đã đưa về bài toán tìm ước số chung lớn nhất của hai số nhỏ hơn. Ví dụ gcd(252, 105) = gcd(252 − 105, 105) = gcd(147, 105) = gcd(147 − 105, 105) = gcd(42, 105) = gcd(42, 105−42) = gcd(42, 63) = gcd(42, 63− 42) = gcd(42, 21) = gcd(42 − 21, 21) = gcd(21, 21) = 21. Quá trình thực hiện phép trừ trên là một số hữu hạn bước do các số nguyên dương bị chặn dưới bởi 1. Tuy nhiên, thuật toán trên thực hiện rất nhiều phép trừ để tìm ước chung lớn nhất nếu như một trong hai số lớn hơn nhiều số còn lại. Một cách hiệu quả hơn là thay số lớn hơn bằng phần dư khi chia số lớn cho số nhỏ. Với cải tiến này, thuật toán sẽ không bao giờ yêu cầu số bước nhiều hơn 5 lần số kí tự của số nhỏ hơn. Điều này đã được chứng minh bởi Gabriel Lamé trong năm 1844. Từ đây ta có thuật toán Euclid để tìm ước chung lớn nhất của hai số nguyên a và b. 1. Cho a > b > 0. 2. Nếu a = bq thì gcd(a, b) = b. 3. Nếu a = bq + r (r 6= 0) thì gcd(a, b) = gcd(b, r). Phép chia Euclid trong trường hợp này được thực hiện như sau: a = bq + r1 ⇒ gcd(a, b) = gcd(b, r1 ) 15 b = r1 q1 + r2 ⇒ gcd(b, r1 ) = gcd(r1 , r2 ) r1 = r2 q2 + r3 ⇒ gcd(r1 , r2 ) = (r2 , r3 ) ......... rn−2 = rn−1 qn−1 + rn ⇒ gcd(rn−2 , rn−1 ) = gcd(rn−1 , rn ) rn−1 = rn qn ⇒ gcd(rn−1 , rn ) = rn . Từ đây suy ra gcd(a, b) = gcd(b, r1 ) = gcd(r1 , r2 ) = · · · = gcd(rn−2 , rn−1 ) = gcd(rn−1 , rn ) = rn . Nhận xét 1.2.3. Ước chung lớn nhất của hai số a và b là số dư cuối cùng khác không trong phép chia Euclid, tức là gcd(a, b) = rn . Ví dụ 1.2.4. Cho a = 1071 và b = 462. 1071 = 2 · 462 + 147 ⇒ gcd(1071, 462) = gcd(462, 147) 462 = 3 · 147 + 21 ⇒ gcd(462, 147) = gcd(147, 21) 147 = 7 · 21 + 0 ⇒ gcd(147, 21) = 21 Ta tìm được gcd(1071, 462) = 21. Lúc này ta có lcm(1071, 462) = 462 462 · 1071 = · 1071 = 22 · 1071 = 23562. gcd(1071, 462) 21 Bổ đề 1.2.5. Trong quá trình thực hiện các bước của thuật toán Euclid, tích của hai số hiện tại giảm xuống bằng một nhân tử ít nhất là 2 lần trong mỗi vòng lặp. Chứng minh. Xét vòng lặp mà cặp {a, b} (a > b) được thay bằng cặp {b, r} (nhắc lại rằng r là phần dư khi chia a cho b). Khi đó ta có r < b và 1 b + r ≤ a. Cho nên a ≥ b + r > 2r, và do đó br < ab.  2 Giả sử ta áp dụng thuật toán Euclid cho hai số a và b và ta thực hiện k bước. Từ Bổ đề 1.2.5 suy ra rằng sau k bước, tích của hai số hiện tại nhiều ab nhất là k . Vì đây là một số nguyên dương nên nó luôn lớn hơn hoặc bằng 2 1, ta có ab > 2k , 16 và do vậy k ≤ log2 (ab) = log2 a + log2 b. Do đó ta chứng minh được định lý sau. Định lý 1.2.6. Số bước của thuật toán Euclid tìm ước chung lớn nhất áp dụng cho hai số nguyên dương a và b không vượt quá log2 a + log2 b. Số bước của thuật toán tìm bội chung nhỏ nhất của hai số a và b không vượt quá log2 a + log2 b + 2. 1.2.2 Phương pháp dùng phân tích thừa số nguyên tố Định lý 1.1.8 và 1.1.9 nói rằng mọi số nguyên dương lớn hơn 1 đều có thể viết được duy nhất thành tích của các số nguyên tố. Các số nguyên tố có thể được coi như các phần tử nguyên tử mà khi kết hợp lại, tạo thành các hợp số. Ví dụ 90 = 22 · 32 · 51 = 2 · 3 · 3 · 5. Ở đây ta có hợp số 90 được tạo thành từ một nguyên tử là số nguyên tố 2, hai nguyên tử là số nguyên tố 3 và một nguyên tử là số nguyên tố 5. Kiến thức này có thể được dùng để tìm bội chung nhỏ nhất của hai số. 1. Tìm phân tích thừa số nguyên tố của cả hai số. 2. Viết số lần xuất hiện nhiều nhất của số nguyên tố xuất hiện trong phân tích của mỗi số. 3. Nhân các thừa số nguyên tố lại theo số lần xuất hiện. Ví dụ 1.2.7. Tính giá trị lcm(8, 9, 21). Giải. Đầu tiên, phân tích thừa số nguyên tố của các số và biểu diễn thành tích của các lũy thừa số nguyên tố. 8 = 23