Ước nguyên tố của một lớp các dãy số nguyên

Chia sẻ: AtaruMoroboshi _AtaruMoroboshi | Ngày: | Loại File: PDF | Số trang:15

Thêm vào BST

Báo xấu

40
lượt xem 3
download

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

Rất nhiều vấn đề trong Số Học liên quan đến sự tồn tại vô hạn các số nguyên tố trong một dãy nguyên. Ví dụ như định lý Dirichlet, các số nguyên tố Fermat hay các số nguyên tố Mersene. Một vấn đề đơn giản hơn, đó là nói đến các ước nguyên tố của phần tử trong dãy. Bài viết này bàn về khái niệm ước nguyên tố của một dãy số nguyên, và tập các ước nguyên tố đó. Phạm vi bài viết là ở mức độ sơ cấp, mặc dù vấn đề nói đến trong bài vẫn được nghiên cứu ở lý thuyết Số cao cấp. Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Ước nguyên tố của một lớp các dãy số nguyên

Hội thảo khoa học, Ninh Bình 15-16/09/2018 ƯỚC NGUYÊN TỐ CỦA MỘT LỚP CÁC DÃY SỐ NGUYÊN Nguyễn Song Minh Hội toán học Hà Nội Tóm tắt nội dung Rất nhiều vấn đề trong Số Học liên quan đến sự tồn tại vô hạn các số nguyên tố trong một dãy nguyên. Ví dụ như định lý Dirichlet, các số nguyên tố Fermat hay các số nguyên tố Mersene. Một vấn đề đơn giản hơn, đó là nói đến các ước nguyên tố của phần tử trong dãy. Bài viết này bàn về khái niệm ước nguyên tố của một dãy số nguyên, và tập các ước nguyên tố đó. Phạm vi bài viết là ở mức độ sơ cấp, mặc dù vấn đề nói đến trong bài vẫn được nghiên cứu ở lý thuyết Số cao cấp. 1 Các quy ước và ký hiệu Suốt bài viết này, tôi sử dụng các ký hiệu với ý nghĩa được quy ước thống nhất như sau: • gcd( a, b): Ước số chung lớn nhất của a; b ∈ Z. • m - a: Số nguyên a không chia hết cho số nguyên m (với m 6= 0). • b x c: Số nguyên lớn nhất không vượt quá số thực x (phần nguyên của x). • ϕ(m): Phi hàm Euler. • v p (m): Hàm định giá p-adic. • P: Tập hợp chứa tất cả các số nguyên tố. 2 Các kiến thức cơ sở Dãy số nguyên về bản chất, là hàm số với tập nguồn là Z+ và tập đích là Z. Do giá trị của các phần tử trong dãy là các số nguyên, vì thế chúng ta có được các tính chất 235
Hội thảo khoa học, Ninh Bình 15-16/09/2018 Số Học của chúng. Một vấn đề rất tự nhiên được đặt ra, đó là tìm hiểu các số nguyên tố là ước của ít nhất một trong những phần tử trong dãy. Bởi vậy, chúng ta quan tâm đến khái niệm sau. Định nghĩa 1. Cho dãy số nguyên { an }n∈Z+ , số nguyên tố p được gọi là ước nguyên tố của dãy khi và chỉ khi tồn tại chỉ số m sao cho p | am . Trong suốt bài viết này, với { an }n∈Z+ là một dãy số nguyên thì tập hợp các ước nguyên tố của dãy { an }n∈Z+ được ký hiệu là P( an ). Còn với một tập con S của Z thì P(S) được hiểu là tập các số nguyên tố là ước của một phần tử nào đó trong S. Để minh họa cho định nghĩa nêu trên, ta xét một số ví dụ sau. Ví dụ 1. Với dãy các luỹ thừa của 2 là an = 2n−1 , khi đó chỉ có 2 là ước nguyên tố của dãy. Nói khác đi P 2n−1 = {2}. Ví dụ 2. Với dãy các luỹ thừa của 2 là an = 2n − 1. Khi đó mọi ước nguyên tố của dãy là các số nguyên tố lẻ, nói khác đi P (2n − 1) = P \ {2}. Lý do là bởi vì 2 - (2n − 1) ∀ n ∈ Z+ và nếu p là số nguyên tố lẻ thì theo định lý Fermat bé ta có p −1 p| 2 −1 . Ví dụ 3. Xét dãy số nguyên sau đây an = 2n + 3n + 6n − 1. Dễ kiểm tra rằng 6 | a2 , do vậy 2, 3 đều là các phần tử của P ( an ), thêm nữa với p ∈ P \ {2, 3} thì theo định lý Fermat bé ta có 6a p−2 = 3.2 p−1 + 2.3 p−1 + 6 p−1 − 6 ≡ 3 + 2 + 1 − 6 ≡ 0 (mod p). Điều đó cho thấy rằng P ( an ) = P. Bạn đọc hẳn nhận ra vấn đề với dãy số ở ví dụ này, chính là bài toán IMO 2005. Ngoài khái niệm về ước nguyên tố của dãy nguyên và tập ước nguyên tố, để thuận tiện cho việc theo dõi bài viết. Tôi nhắc lại một vài định lý và bổ đề Số Học hay sử dụng ở đây. 236
Hội thảo khoa học, Ninh Bình 15-16/09/2018 Định lý 1 (Euler). Với ϕ(m) là số các số nguyên dương không vượt quá m và nguyên tố cùng nhau với m, khi đó a ϕm ≡ 1 (mod m). Từ định lý Euler, ta có một hệ quả đáng chú ý sau đây. Hệ quả 1. Cho k số nguyên khác 0 là a1 , a2 , . . . , ak và một số nguyên dương m > 1, khi đó tồn tại N đủ lớn để N +nϕ(m) ai ≡ aiN (mod m) ∀ i = 1, k, n ∈ Z+ . Chứng minh. Giả sử ta có phân tích ra thừa số nguyên tố của m là t kj m= ∏ pj , p j ∈ P, p1 < p2 < . . . < pt , k j ∈ Z+ . j =1 Giả sử N = max k j : j = 1, t , khi đó. kj kj 1. Nếu p j - ai thì từ | m, vì phi hàm Euler có tính chất nhân tính nên ϕ pj pj | ϕ(m) sử dụng định lý Euler ta có ϕ(m) k ai ≡ 1 (mod p j j ). Từ đó mà có được N +nϕ(m) k ai ≡ aiN (mod p j j ). 2. Nếu p j | ai thì do N ≥ k j nên N +nϕ(m) k ai ≡ aiN ≡ 0 (mod p j j ). kj N +nϕ(m) N +nϕ(m) Từ p j | ai − aiN ∀ j = 1, t để có m | ai − aiN ∀ i = 1, k. Với số nguyên tố p bất kỳ, ta có ϕ( p) = p − 1. Vì vậy, trong trường hợp m = p thì định lý Euler trở thành định lý sau đây. Định lý 2 (Fermat bé). Với p là số nguyên tố và p - a, khi đó a p −1 ≡ 1 (mod p) 237
Hội thảo khoa học, Ninh Bình 15-16/09/2018 Định lý 3 (Định lý Trung Hoa về số dư). Với m1 , m2 , . . . , mn là các số nguyên dương đôi một nguyên tố cùng nhau còn r1 , r2 , . . . , rn là các số nguyên bất kỳ, khi đó tồn tại duy nhất r ∈ {0, 1, . . . , m1 m2 . . . mk − 1} thỏa mãn hệ đồng dư sau r ≡ rk mod mk ∀ k = 1, n. Những kiến thức cơ bản nêu trên là cần thiết để theo dõi các vấn đề ở mục tiếp theo, ngoài ra bạn đọc cần có những trang bị về định giá p-adic, bổ đề nâng bậc hay những kiến thức về cấp, căn theo modulo và thặng dư bậc hai để xử lý các bài tập đề nghị. 3 Một số vấn đề cơ bản Bài toán 1 (Định lý Schur). Cho đa thức hệ số nguyên f ( x ) có bậc dương, khi đó tập các ước nguyên tố của dãy an = f (n) là vô hạn. Lời giải. Giả sử ngược lại là tập tất cả các ước nguyên tố của dãy an = f (n) chỉ là tập hữu hạn sau đây P ( f n ) = { p1 , p2 , . . . , p t } . Do f ∈ Z[ x ] nên f ( x ) = a0 + a1 x + . . . + an x n , với ai ∈ Z ∀ i = 1, n, ta xét hai trường hợp sau. 1. Nếu a0 = 0, khi đó p | f ( p) ∀ p ∈ P cho nên dãy an nhận mọi số nguyên tố làm ước nguyên tố. Điều này, mâu thuẫn với giả sử ở trên. 2. Nếu a0 6= 0 với mỗi số nguyên dương k đặt kp1 p2 . . . pt = mk , ta có f ( a0 mk ) = a0 + a1 a0 mk + . . . + an a0n mnk 2 n −1 n = a0 . 1 + a1 m k + a2 a0 m k + . . . + a n a0 m k . Đặt g( x ) = 1 + a0 a1 x + . . . + a0n−1 an x n vì deg( g) = deg( f ) = n ∈ Z+ cho nên phương trình | g( x )| = 1 chỉ có hữu hạn nghiệm, tức là tồn tại k ∈ Z+ sao cho | g (mk )| > 1. Để ý rằng g( x ) ∈ Z[ x ] nên giá trị g (mk ) là một số nguyên và vì thế nó có ước nguyên tố p nào đó. Rõ ràng g (mk ) ≡ 1 (mod mk ), cho nên gcd ( g (mk ) , mk ) = 1. Điều này cũng dẫn đến gcd (mk , p) = 1 cho nên p ∈ / P ( f n ), dẫn đến điều mâu thuẫn. 238
Hội thảo khoa học, Ninh Bình 15-16/09/2018 Dựa vào định lý Schur, chúng ta có thể giải quyết bài toán sau. Bài toán 2. Cho các số nguyên dương a, b với a > b, tìm tất cả các đa thức hệ số nguyên P( x ) thỏa mãn P ( n ) | ( a n − b n ) ∀ n ∈ Z+ . Lời giải. Ta xét hai trường hợp. 1. Nếu deg( P) > 0, khi đó theo định lý Schur sẽ tồn tại vô số ước nguyên tố p của dãy P(n). Giả sử p là một ước nguyên tố bất kỳ như thế (với p > a) và p | P(m) với m ∈ Z+ , ta có p | ( am − bm ) . Mặt khác do P( x ) ∈ Z[ x ] nên P(m + p) ≡ P(m) ≡ 0 (mod p). Từ đây ta lại có p | am+ p − bm+ p . Vì p - a, p - b và am ≡ bm (mod p) nên kết hợp định lý Fermat bé ta có am+ p − bm+ p ≡ am ( a p − b p ) ≡ am ( a − b ) (mod p). Điều này kéo theo p | ( a − b), nhưng do a − b là một số nguyên dương cố định cho nên nó không thể có vô số ước nguyên tố. Vậy nên trường hợp này không thể xảy ra. 2. Nếu deg( P) ≤ 0, tức P( x ) là đa thức hằng thế thì P( x ) = d với d = P(1) và là ước của a − b. Lúc đó do ( a − b) luôn là ước của an − bn với mọi số nguyên dương n do đó trường hợp này thỏa. Vậy, kết quả của bài toán là P( x ) = d ∀ x ∈ R với d là một ước số bất kỳ của a − b. Kết quả của Schur ứng với lớp dãy số đặc biệt, đó là các dãy sinh ra từ các đa thức hệ số nguyên. Ở bài toán tiếp theo, chúng ta sẽ xử lý một bài toán về mục đích thì tương tự nhưng dãy số được cho phức tạp hơn chút xíu. 239
Hội thảo khoa học, Ninh Bình 15-16/09/2018 Bài toán 3. Chứng minh rằng P ( an ) là vô hạn, với an = blog (2017n + 1)c ∀ n ∈ Z+ . Lời giải. Giả sử P ( an ) chỉ là hữu hạn. Ta lấy ra 5 số nguyên tố pi ∈ / P ( an ), theo CRT sẽ tồn tại 5 số nguyên dương liên tiếp N + 1, N + 2, . . . , N + 5 sao cho pk | ( N + k ) ∀ k = 1, 5. Giờ gọi m là chỉ số lớn nhất sao cho am ≤ N + 1, khi đó am+1 > N + 1 và vì j k m +1 1 < am+1 − am = log 2017 + 1 − blog (2017m + 1)c < 5. Cho nên ta có được { am ; am+1 } ∩ { N + 1, N + 2, . . . , N + 5} 6= ∅. / P ( an ) thoả p | am am+1 , và điều đó mâu thuẫn Từ đây thấy sẽ tồn tại số nguyên tố p ∈ với giả sử ban đầu của chúng ta. Nhận xét 1. Bài toán trên, chỉ là hệ quả của bài toán sau đây (ứng với d = 5). Và lời giải là hoàn toàn tương tự. Bài toán 4. Cho d là một số nguyên dương lớn hơn 1, dãy số nguyên { an }n∈Z+ tăng ngặt và thỏa mãn a n +1 − a n < d ∀ n ∈ Z+ . Chứng minh rằng tập các ước nguyên tố của dãy là vô hạn. Bài toán vừa nêu này tôi không đưa ra lời giải chi tiết, vì nó còn một phiên bản nâng cấp mạnh hơn nhiều. Ở bài toán tiếp theo, thì cách xử lý như hai bài trước tỏ ra thiếu hiệu lực. Bài toán 5. Cho dãy số nguyên { an }n∈Z+ tăng ngặt và giả sử tồn tại một đa thức hệ số thực P( x ) thỏa mãn a n +1 − a n < P ( n ) ∀ n ∈ Z+ . Chứng minh rằng tập các ước nguyên tố của dãy { an }n∈Z+ là vô hạn. 240
Hội thảo khoa học, Ninh Bình 15-16/09/2018 Lời giải. Đặt 1 + deg( P) = k, khi đó tồn tại N0 đủ lớn sao cho a n +1 < a n + P ( n ) < a n + n k ∀ n ∈ Z+ , n > N0 . Giả sử P ( an ) là tập hữu hạn, cụ thể P ( a n ) = { p1 , p2 , . . . , p t } . Với mỗi số nguyên dương n thỏa n > M = max N0 , a N0 , ta xét hai tập hợp sau n o k k Pn = p11 p2k2 . . . pkt t : k i ∈ N, p11 p2k2 . . . pkt t < n , An = { ai : ai < n} . k Lấy e ∈ Pn , thế thì e = p11 p2k2 . . . pkt t với k 2ki ≤ pi i ≤ e < n. Như vậy 0 ≤ k i < log2 n, nên theo quy tắc nhân ta có đánh giá sau |Pn | < (1 + log2 n)t ∀ n > M. Mặt khác ta lại có n > M thì n > N0 nên với am = max An ta có a N0 ≤ am < am−1 + mk < . . . < a N0 + ∑ jk < a N0 + mk+1 . N0 < j k +1 n − a N0 − 1 ∀ n > M. Với giả thiết phản chứng ở trên thì An ⊂ Pn ∀ n > M, tức là có √ k +1 n − a N0 − 1 |An | < < 1 ∀ n > M. (1 + log2 n) t |Pn | Lấy giới hạn ở vô cùng, cho ta điều vô lý. Vậy, P ( an ) phải là tập vô hạn. Bây giờ là một bài toán xét kỹ thì cùng bản chất, mặc dù đọc qua yêu cầu thì cảm thấy khác biệt với các bài toán trên. Bài toán 6 (China TST, 2006). Cho các số nguyên dương m và n, chứng minh rằng luôn tồn tại số nguyên dương k sao cho 2k − m có ít nhất n ước nguyên tố phân biệt. 241
Hội thảo khoa học, Ninh Bình 15-16/09/2018 Lời giải. Giả sử với mọi số nguyên dương k số ước nguyên tố của 2k − m đều nhỏ hơn n, ta giả sử K là số thỏa 2K − m có nhiều ước nguyên tố nhất. Và phân tích ra thừa số nguyên tố của 2K − m là k 2K − m = p11 p2k2 . . . pkt t . 1+ k 1 1+ k 2 Đặt M = p1 p2 . . . p1t +kt , thế thì với k đủ lớn ta có được 2K +kϕ( M) − m ≡ 2K − m (mod M). Tức là 2K +kϕ( M) − m chia hết cho 2K − m, nên 2K +kϕ( M) − m nhận mọi ước nguyên tố của 2K − m làm ước nguyên tố. Nhưng do vai trò của K nên 2K +kϕ( M) − m cũng chỉ được phép có đúng bấy nhiêu ước nguyên tố, đồng thời do v pi ( M ) = v pi 2K − m + 1 ∀ i = 1, t nên K +kϕ( M) K v pi 2 − m = v pi 2 − m ∀ i = 1, t. Từ đó dẫn đến điều vô lý là 2K +kϕ( M) − m = 2K − m ∀ k ∈ Z+ . Bằng kỹ thuật tương tự, ta dễ dàng có được lời giải cho bài toán sau. Bài toán 7. Cho a, b, c là các số nguyên thỏa ac 6= 0 và b > 1. Xét dãy số f n = abn + c ∀ n ∈ Z+ . Chứng minh rằng P ( f n ) là tập vô hạn. Tôi không trình bày lời giải chi tiết cho bài toán này, thay cho việc đó tôi nêu ra và xử lý kết quả khá mạnh sau của Polya. Bài toán 8 (Polya). Giả sử a1 , a2 , . . . , am là các số nguyên dương phân biệt, 0 < a1 < a2 < . . . < am và P1 ( x ), P2 ( x ), . . . , Pm ( x ) là các đa thức hệ số nguyên khác đa thức 0. Khi đó dãy số nguyên cho bởi công thức dưới đây, sẽ có vô hạn ước nguyên tố f n = a1n P1 (n) + a2n P2 (n) + . . . + anm Pm (n) ∀ n ∈ Z+ . Lời giải. Không mất tính tổng quát, ta giả sử hệ số bậc cao nhất của Pm ( x ) là dương. Giả sử rằng P ( f n ) là tập hữu hạn, cụ thể P ( f n ) = { p1 , p2 , . . . , p t } . 242
Hội thảo khoa học, Ninh Bình 15-16/09/2018 Rõ ràng là lim f n = +∞, cho nên tồn tại N0 đủ lớn sao cho f N0 > 1 và đồng thời với số nguyên dương m cho trước ta sẽ có N0 +nϕ(m) ai ≡ aiN0 (mod m). Giả sử ta có phân tích ra thừa số nguyên tố của f N0 là k f N0 = p11 p2k2 . . . pkt t ; k i ∈ N. 1+ k 1 1+ k 2 2+ k Đặt M = p1 p2 . . . p1t +kt và M0 = p1 1 p22+k2 . . . p2t +kt , thế thì ϕ M 0 = M ∏ ( p i − 1) = p1 p2 . . . p t ϕ ( M ). 1≤ i ≤ t Điều đó kết hợp với Pi ( x ) ∈ Z[ x ] để thấy với mọi số nguyên dương n ta có N +nϕ( M0 ) f N0 +nϕ( M0 ) = ∑ a j 0 Pj N0 + nϕ M0 ≡ ∑ a j 0 Pj ( N0 ) ≡ f N0 N (mod M). 1≤ j ≤ m 1≤ j ≤ m Do v pi ( M ) = 1 + v pi f N0 ∀ i = 1, t, nên từ đó có được ∀ i = 1, t, ∀ n ∈ Z+ . v pi f N0 +nϕ( M0 ) = v pi f N0 Điều đó cho thấy rằng lim f N0 +nϕ( M0 ) = f N0 . Kết quả vừa rút ra, trái với nhận xét từ ban đầu của chúng ta là lim f n = +∞. Vậy, P ( f n ) phải là tập vô hạn. Ta quan tâm đến một vấn đề khác liên quan đến kết quả của Polya nêu trên, đó là với dãy f n xác định như thế thì liệu số ước nguyên tố của một phần tử của dãy có bị giới hạn hay không? Cụ thể là nếu ta cố định một số nguyên dương k, thì có tồn tại hay không một chỉ số m để f m có ít nhất k ước nguyên tố phân biệt. Bài toán 9. Giả sử a1 , a2 , . . . , am là các sô nguyên dương phân biệt, và P1 ( x ), P2 ( x ), . . . , Pm ( x ) là các đa thức hệ số nguyên khác đa thức 0. Xét dãy số nguyên cho bởi công thức f n = a1n P1 (n) + a2n P2 (n) + . . . + anm Pm (n) ∀ n ∈ Z+ . Chứng minh rằng, với k là số nguyên dương cho trước, luôn tồn tại m ∈ Z+ sao cho f m có ít nhất k ước nguyên tố phân biệt. 243
Hội thảo khoa học, Ninh Bình 15-16/09/2018 Lời giải. Nếu không tồn tại m ∈ Z+ sao cho f m có ít nhất k ước nguyên tố phân biệt, thì mọi phần tử của dãy f n đều có hữu hạn ước nguyên tố. Ta giả sử K là số thỏa f K có nhiều ước nguyên tố nhất. Và phân tích ra thừa số nguyên tố của f K là k f K = p11 p2k2 . . . pkt t . 1+ k 1 1+ k 2 2+ k 1 2+ k 2 Lại đặt M = p1 p2 . . . p1t +kt và M0 = p1 p2 . . . p2t +kt , để với n đủ lớn ta có f K +nϕ( M0 ) ≡ f K (mod M). Từ đây có f K | f K +nϕ( M0 ) và bởi vậy f K +nϕ( M0 ) cũng có t ước nguyên tố là các ước nguyên tố của f K . Nhưng do vai trò của K nên f K +nϕ( M0 ) cũng chỉ có bấy nhiêu ước nguyên tố. Đồng thời do v pi ( M ) = 1 + v pi ( f K ) và f K +nϕ( M0 ) ≡ f K (mod M ) nên với mọi n đủ lớn ta sẽ có v pi f K +nϕ( M0 ) = v pi ( f K ) ∀ i = 1, t. n o Điều này kéo theo dãy con f K +nϕ( M0 ) là dãy dừng, mâu thuẫn với việc + n ∈Z lim f n = +∞. Bây giờ, ta xét đến một bài toán olympic ứng dụng trực tiếp kết quả của Polya ở trên. Bài toán 10 (China MO, 2011). Cho m, n là các số nguyên dương. Chứng minh rằng tồn tại vô hạn các cặp số nguyên dương ( a; b) sao cho ( a + b) | am a + bnb và gcd( a, b) = 1. Lời giải. Nếu m = n = 1 thì bài toán cực kỳ là tầm thường, bởi vì nếu điều đó xảy ra ta có thể chọn b = 1 còn a tùy ý. Vì thế, ta có thể giả sử n > 1 và xét dãy số xác định như sau ak = (mn)k − n ∀ k ∈ Z+ . Theo bài toán trên thì P ( ak ) là tập vô hạn, như vậy ta có thể lấy ra vô số các số nguyên tố p từ P ( ak ) thỏa mãn p > m + n đồng thời khi đó tồn tại k p sao cho p | ak p , tức là (mn)k p ≡ n (mod p). Bởi vì 0 < n − 1 < p nên từ định lý Fermat bé ( p − 1) - k p , ta chọn a là số dư của k p khi chia p − 1 còn b = p − a, để có a, b ∈ Z+ và gcd( a, b) = gcd( a, a + b) = gcd( a, p) = 1. 244
Hội thảo khoa học, Ninh Bình 15-16/09/2018 Lại có p - mn nên theo định lý Fermat bé, ta có n ≡ (mn)k p ≡ (mn) a (mod p). Thêm một lần nữa sử dụng định lý Fermat bé, để có n am + bn = a(mn) a + ( p − a) n p ≡ an + ( p − a) n ≡ 0 a a b (mod p). Bây giờ để ý rằng p = a + b và p - nb , ta có điều cần chứng minh. Nhận xét 2. Nếu bỏ đi yêu cầu gcd( a, b) = 1 thì bài toán sẽ trở nên tầm thường, bởi vì khi đó với số nguyên tố p bất kỳ ta chỉ cần chọn 2 ( a, b) = p − 1, ( p − 1) . Từ bài toán của Polya nêu trên, ta thấy rằng với cặp số nguyên dương phân biệt a, b bất kỳ thì dãy số f n = an + bn sẽ có vô hạn ước nguyên tố. Có một vấn đề đặt ra ở đây là nếu ta lấy ra một dãy con nào đó của f n , thì dãy con đó còn có vô hạn ước nguyên tố hay không? Ta có bài toán sau đây. Bài toán 11. Cho a và b là các số nguyên dương nguyên tố cùng nhau, với a + b > 3. Khi đó, nếu p là một số nguyên tố lẻ thì tồn tại ước nguyên tố lẻ khác p của a p + b p , và đồng thời ước nguyên tố đó không là ước của a + b. ap + bp Lời giải. Ta có Φ p = là một số nguyên dương lớn hơn 1, bởi vậy Φ p luôn có a+b ước nguyên tố q nào đó. Mặt khác do p lẻ, nên ta có v2 ( a p + b p ) = v2 ( a + b ). Từ đó sẽ có Φ p là số lẻ, kéo theo q lẻ. 1. Nếu Φ p chỉ có ước nguyên tố là p, thế thì từ ( a + b) | ( a p + b p ) và ( a p + b p ) ≡ ( a + b) (mod p), ta có a + b cũng có và chỉ có ước nguyên tố lẻ là p, đồng thời v p ( a p + b p ) = v p ( a + b) + 1. 245
Hội thảo khoa học, Ninh Bình 15-16/09/2018 Tức là ta có biểu diễn sau a p + b p = 2k p l +1 = p ( a + b ). Tuy nhiên, ta lại có đánh giá sau p p 3 3 a + b ≥ a + b = ( a + b) a − ab + b 2 2 > ( a + b )2 . Nhưng p | ( a + b) do đó từ a + b ≥ p mà có điều mâu thuẫn là a p + b p > p ( a + b ). 2. Nếu Φ p có ước nguyên tố q 6= p, thế thì hễ q | ( a + b) ta có điều vô lý là vq Φ p = vq ( a p + b p ) − vq ( a + b) = 0. Như vậy, Φ p luôn phải có một ước nguyên tố q lẻ và q 6= p, để ý rằng Φ p | ( a p + b p ) mà ta có điều cần chứng minh. Từ lời giải bài toán trên, ta thấy từ dãy f n = an + bn có thể trích ra một dãy con f pn có vô hạn ước nguyên tố. Cũng cần nói thêm rằng, bài toán trên là một phiên bản của định lý Zsigmondy nổi tiếng. Nhưng chuyện đó bàn sau, giờ ta đến với một bài toán khác như sau. Bài toán 12 (Romania TST, 2014). Cho m và k là các số nguyên dương cho trước với m lẻ, chứng minh rằng luôn tồn tại n sao cho mn + nm có ít nhất k ước nguyên tố phân biệt. k Lời giải. Lấy ra một số nguyên tố p lớn hơn m + 2 bất kỳ và xét n = mp2.3 , ta có  !  k p2.3 −1 k k m .3 m p2.3 −1 k 3k k nm + mn = mm m + p3 .2m = mm m + p3 .2m  .   Giờ để ý rằng do p > 3 nên 3 | p2 − 1 và vì thế k v3 p2.3 − 1 = v3 ( p2 − 1) + k > k. ! k p2.3 −1 p 2.3k −1 m 3k Tức là ∈ Z+ , nên nếu đặt m = a, p2m = b thì a, b ∈ Z+ thỏa 3k gcd( a, b) = 1 tất nhiên a + b > 3, đồng thời k k n m + m n = m m a3 + b3 . 246
Hội thảo khoa học, Ninh Bình 15-16/09/2018 Theo bài toán phía trên thì tồn tại k số nguyên tố phân biệt p1 , p2 , . . . , pk sao cho j i 3 3j 3 3i pj | a + b , pj - a + b ∀ j = 1, k, ∀ i = 0, j − 1. Rõ ràng nm + mn có k ước nguyên tố phân biệt là p1 , p2 , . . . , pk . Nhận xét 3. Bài toán này hoàn toàn có thể xử lý như ở các bài China TST 2006 (bài toán 6) và kết quả của Polya (bài toán 8). Tôi xử lý bằng cách trên, để muốn nhấn mạnh ý nghĩa của bài toán 10, đó là một kết quả khá hay và nó có vai trò trong nhiều bài toán khó. Để kết thúc phần này, tôi xin đưa ra kết quả cực mạnh sau của Hiroshi Kobayashi. Một kết quả, mà theo tôi biết là chưa có chứng minh sơ cấp. Định lý 4. Cho S là một tập vô hạn các số nguyên dương thỏa mãn P(S) là hữu hạn, khi đó với mọi hằng số nguyên c khác 0 ta có P(S + c) là tập vô hạn, với S + c = { s + c : s ∈ S }. Ở phần tiếp sau đây, là các bài toán luyện tập. 4 Bài tập Bài 1. Tìm tất cả các đa thức hệ số nguyên P( x ) sao cho gcd ( P (n) , P (2017n )) = 1 ∀ n ∈ Z+ . Bài 2. Cho các số nguyên dương k, m và đa thức hệ số nguyên P( x ) có bậc dương, chứng minh rằng tồn tại n ∈ Z+ sao cho mỗi giá trị P(n), P(n + 1), . . . , P(n + m) đều có ít nhất k ước số nguyên tố phân biệt. Bài 3. Cho P( x ) là đa thức hệ số nguyên bất khả quy trên Q[ x ] có bậc dương, chứng minh rằng tồn tại vô số số nguyên tố p sao cho với mỗi p như thế sẽ tồn tại n ∈ Z+ thỏa mãn v p ( P(n)) = 1. 247
Hội thảo khoa học, Ninh Bình 15-16/09/2018 Bài 4. Cho f ( x ) là một đa thức hệ số thực và số nguyên dương k, biết rằng với số nguyên dương n bất kỳ đều tồn tại m ∈ N sao cho f (n) = mk . Chứng minh rằng tồn tại đa thức hệ số hữu tỷ P( x ) sao cho f ( x ) = P k ( x ). Bài 5. Cho trước số nguyên dương k và đa thức hệ số nguyên P( x ) có bậc dương, chứng minh rằng tồn tại vô số số nguyên tố p sao cho phương trình đồng dư P( x ) ≡ 0 (mod pk ) có nghiệm. Bài 6. Cho trước số nguyên dương a không là số chính phương, chứng minh rằng tồn tại vô số số nguyên tố p lẻ thỏa mãn p −1 a 2 ≡ −1 (mod p). Bài 7. Cho các số nguyên dương a và b với a > 1, xét dãy số f n = a ϕ(n) + b. 1. Chứng minh rằng P ( f n ) là tập vô hạn. 2. Chứng minh rằng P \ P ( f n ) cũng là tập vô hạn. Bài 8. Chứng minh rằng P ( f n ) là tập vô hạn, với j log n k f n = 32 ∀ n ∈ Z+ . n Bài 9 (Iran TST, 2009). Cho trước số nguyên dương a, xét dãy f n = 22 + a. Chứng minh rằng P ( f n ) là tập vô hạn. Bài 10. Với mỗi số nguyên dương m, ký hiệu p(m) là ước nguyên tố lớn nhất của √ 3 m2 + 2018. Chứng minh rằng tồn tại vô số số nguyên dương n sao cho p(n) < 2 n2 . Bài 11. Cho số nguyên dương a (với a > 2), xét dãy số f n = an+1 + 1. Chứng minh rằng với mỗi số nguyên dương m, tồn tại số nguyên tố p là ước của f m và p > 2m. Bài 12. Chứng minh rằng, tồn tại vô số số nguyên dương n sao cho n2 + 1 không có ước chính phương lớn hơn 1. Bài 13. Tìm tất cả các đa thức hệ số nguyên P( x ) và hằng số k sao cho với mọi số nguyên dương n thì 2n P(n) + k luôn là số chính phương. 248
Hội thảo khoa học, Ninh Bình 15-16/09/2018 Bài 14. Cho m là một số nguyên dương, chứng minh rằng tồn tại vô số số nguyên dương n sao cho 7m | (3n + 5n + 6n ) . Bài 15 (IMO SL, 2014). Cho số nguyên dương c, xét dãy an được xác định bởi công thức truy hồi như sau a1 = c và an+1 = a3n − 4ca2n + 5c2 an + c ∀ n ∈ Z+ . Chứng minh rằng với mọi n > 1 sẽ tồn tại số nguyên tố p sao cho p | an và p - ai ∀ i < n. Bài 16. Tìm các số nguyên dương a và b, sao cho tồn tại vô số số nguyên dương n thỏa mãn n2 | ( a n + b n ) . Bài 17. Cho P( x, y) là một đa thức hai biến số có các hệ số là các số nguyên, dãy số nguyên { an }n∈Z+ thỏa mãn a n +3 = a n + P ( a n +1 , a n +2 ) ∀ n ∈ Z+ . Chứng minh rằng P ( an ) là tập vô hạn. 5 Nguồn tham khảo [1] G. Pólya, Gabor Szego: ¨ "Problems and Theorems in Analysis" [2] P. Morton: "Musings on the Prime Divisors of Arithmetic Sequences." [3] H. Kobayshi: "On Existence of Infinitely Many Prime Divisors in a Given Set." [4] Diễn đàn Mathscope [5] Diễn đàn Mathlinks [6] Diễn đàn Mathoverflow 249