Sử dụng tính nguyên tố để giải bài toán cực trị trên tập đối số nguyên

Bài viết để cập đến một số bài toán cực trị (Tìm giá trị lớn nhất hay giá trị nhỏ nhất của hàm số trên tập hợp các đối số nguyên). Các bài toán minh họa mang màu sắc số học bởi nó xuất phát từ các vấn đề của số học như tính chia hết, tính chẵn lẻ, tính nguyên tố,…
Nội dung trích xuất từ tài liệu:
Sử dụng tính nguyên tố để giải bài toán cực trị trên tập đối số nguyênTẠP CHÍ KHOA HỌC − SỐ 14/2017 153 SỬ DỤNG TÍNH NGUYÊN TỐ ĐỂ GIẢI BI TOÁN CỰC TRỊ TRÊN TẬP ĐỐI SỐ NGUYÊN Hoàng Ngọc Tuyến1 Trường Đại học Thủ đô Hà Nội Tóm tắt tắt: ắt Bài viết để cập đến một số bài toán cực trị (Tìm giá trị lớn nhất hay giá trị nhỏ nhất của hàm số trên tập hợp các đối số nguyên). Các bài toán minh họa mang màu sắc số học bởi nó xuất phát từ các vấn đề của số học như tính chia hết, tính chẵn lẻ, tính nguyên tố,… Lớp bài toán cực trị này, vì lý do trên nó mang những nét đặc thù riêng với cách giải bằng cách vận dụng các kiến thức số học, trên cơ sở tuân thủ những nguyên lý cơ bản của Lý thuyết cực trị. Từ khóa: khóa Nguyên lý phân rã,, Giá trị lớn nhất, Giá trị nhỏ nhất.1. MỞ ĐẦU Thông thường, để giải bài toán cực trị ta thường sử dụng công cụ của giải tích Toánhọc như đạo hàm, tích phân. Tuy nhiên các đối tượng đề cập nhận các giá trị rời rạc, dovậy nói chung các phương pháp giải truyền thống không áp dụng được. Vì lẽ đó, đứng về góc độ của bài toán cực trị dĩ nhiên trong khi giải ngoài việc tuân thủcác nguyên lý cơ bản của Lý thuyết cực trị, ta sử dụng công cụ chính là phương pháp đặctrưng của số học như: lý thuyết đồng dư, tính nguyên tố,… cũng như áp dụng các định lýquan trọng của Lý tuyết số như: định lý Euler, định lý Fecma,…2. MỘT SỐ KIẾN THỨC CHUẨN BỊ2.1. Tính chia hết trong tập hợp số nguyên2.1.1. Định nghĩa Với hai số nguyên a và b, ta nói a chia hết cho b (hay a là bội của b, hay b là ướccủa a), nếu tồn tại số nguyên c sao cho a = b.c1 Nhận bài ngày 10.3.2017; chỉnh sửa, gửi phản biện và duyệt đăng ngày 20.3.2017 Liên hệ tác giả: Hoàng Ngọc Tuyến; Email: hntuyen@daihocthudo.edu.vn154 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI Khi đó, ta ký hiệu là a b Ngược lại, ta nói a không chia hết cho b2.1.2. Một số tính chất cơ bản của tính chia hết (i) Nếu a,b nguyên dương mà a b thì a ≥ b (ii) Nếu a i b, ∀i = 1, n thì (a1 + a 2 + ... + a n ) b (iii) Với hai số nguyên không âm bất kỳ a và b, trong đó b ≠ 0 , luôn tồn tại cặp sốnguyên duy nhất q và r sao cho: a = bq + r. Trong đó 0 ≤ r < b (Hay r nhận một trong cácgiá trị 0; 1; 2;…; b-1)2.2. Số nguyên tố2.2.1. Định lý cơ bản về số nguyên tố Định lý: Cho n là số nguyên dương lớn hơn 1. Khi đó n luôn biểu diễn một cách duynhất (hiểu theo nghĩa không tính đến việc sắp xếp các nhân tử): α α αk n = p1 1 p 2 2 ...p k Trong đó αi (i = 1, k) là các số tự nhiên và pi là các số nguyên tố thỏa mãn: 1< p1 < ... < pk (Dạng khai triển chính tắc của số nguyên dương n)2.2.2. Định lý nhỏ Fecma Định lý: Nếu p nguyên tố và a là số nguyên tùy ý, thì (a p - a) p Nói riêng: khi (a, p) = 1 thì (a p-1 - 1) p2.2.3. Định lý (Mối liên hệ giữa tính chia hết và số nguyên tố) Định lý: Giả sử a và b là số nguyên dương, p là số nguyên tố. Nếu ab p thì hoặc a p hoặc b p2.3. Đồng dư2.3.1. Một số tính chất cơ bản của đồng dư (i) Nếu a ≡ b(mod n) và c ≡ d(mod n) thì a + c ≡ b + d(mod n) và ac ≡ bd(mod n) (ii) Nếu p nguyên tố và ab ≡ 0(mod p) thì a ≡ 0(mod p) hay b ≡ 0(mod p)TẠP CHÍ KHOA HỌC − SỐ 14/2017 1552.3.2. Định lý Euler Định lý: Nếu m là số nguyên dương và (a, m) = 1 thì a φ (m) ≡ 1(mod m) Trong đó φ (m) là số các số nguyên dương nhỏ hơn m nguyên tố cùng nhau với m. ( φ (m) được gọi là Phi-hàm ơ-le)2.4. Hàm phần nguyên2.4.1. Định nghĩa Với số thực x, ta gọi phần nguyên của x, ký hiệu [ x ] là số nguyên lớn nhất khôngvượt quá x.2.4.2. Các tính chất quan trọng (i) [ x ] = a ⇔ x = a + d trong đó a nguyên và 0 ≤ d < 1 (ii) [ x + y ] = x thì x nguyên và 0 ≤ y < 1 (iii) ∀n ∈ ⇒ [ n + x ] = n + [ x ] (iv) [ x + y ] ≥ [ x ] + [ y ] (v) ∀n ∈ ⇒ n [ x ] ≤ [ nx ] * n  (vi) ∀n, q ∈ N, q ≠ 0 ⇒ q   ≤ n q   1 (vii)  x +  = [ 2x ] - [ x ]  22.5. Giá trị lớn nhất và nhỏ nhất của hàm số2.5.1. Định nghĩa Cho hàm số f(x) xác định trên miền D (x ∈ D) Ta nói M là giá trị lớn nhất của hàm số f(x) trên miền D, và ký hiệu:  f(x) ≤ M; ∀x ∈ D M = max f(x) nếu  x∈D ∃x 0 ∈ D;f(x 0 ) = M Ta cũng nói m là giá trị ...