Số nguyên tố
Trong toán học, với các số nguyên a và b, nếu a khác 0, chúng ta nói rằng a chia hết b (ký hiệu a|b) khi tồn tại một số nguyên c sao cho b = ac Ngược lại, b được coi là bội số của a, ký hiệu b a.
Cho hai số nguyên a và b không đồng thời bằng 0, ước chung lớn nhất (gcd) của a và b là số nguyên d dương thỏa mãn hai điều kiện: (1) d chia hết cho a và b; (2) nếu có số nguyên e chia hết cho a và b, thì e cũng chia hết cho d.
Hai số nguyên a và b được gọi là nguyên tố cùng nhau nếu ước số chung lớn nhất của chúng là 1 Số 1 chỉ có một ước dương duy nhất, trong khi mỗi số nguyên lớn hơn 1 có ít nhất hai ước dương, đó là 1 và chính nó Những số nguyên dương lớn hơn 1 chỉ có đúng hai ước dương được gọi là số nguyên tố, trong khi những số nguyên lớn hơn 1 không phải là số nguyên tố được gọi là hợp số.
Mệnh đề 1.1.3 nêu rõ rằng nếu a, b, c thuộc Z và a chia hết cho bc với điều kiện gcd(a, b) = 1, thì a cũng chia hết cho c Hơn nữa, nếu có hai dãy số nguyên a1, a2, , an và b1, b2, , bm thỏa mãn gcd(ai, bj) = 1 cho mọi i, j, thì gcd(a1a2 an, b1b2 bm) = 1 Đặc biệt, nếu gcd(p, q) = 1, thì gcd(p^n, q^m) = 1 với mọi m, n là các số nguyên dương Định lý 1.1.4, hay Định lý cơ bản về số nguyên tố, khẳng định rằng với một số nguyên n lớn hơn 1, n có thể được biểu diễn duy nhất dưới dạng n = p1^α1 * p2^α2 * * pk^αk, trong đó k > 0, αi là các số tự nhiên và pi là các số nguyên tố với p1 < p2 < < pk.
Đồng dư thức
Định nghĩa 1.2.1 (Đồng dư thức) (xem [1]) Cho m là số nguyên dương.
Số nguyên a được coi là đồng dư với số nguyên b theo mô-đun m nếu m chia hết cho hiệu a và b, ký hiệu là a ≡ b (mod m) Ngược lại, nếu không thỏa mãn điều kiện này, ta ký hiệu là a 6≡ b (mod m) Dưới đây là một số tính chất cơ bản của đồng dư thức.
Mệnh đề 1.2.2 (xem [1]) (i) a ≡ b (mod m) ⇔ tồn tại k ∈ Z để a b+km.
(ii) a ≡b (mod m) ⇔ a và b chia cho m có cùng một số dư.
(iv) Nếu a ≡b (mod m), thì b≡ a (mod m).
(v) Nếu a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m).
Mệnh đề 1.2.3 (xem [1]) Nếu a ≡ b (mod m) và c ≡ d (mod m) thì a+c ≡ b+d (mod m) và ac ≡bd (mod m).
Mệnh đề 1.2.4 (xem [1]) (i) Nếu ac ≡ bc (mod m), (c, m) = 1, thì a ≡ b (mod m).
Nếu \( ac \equiv bc \) (mod \( m \)) và \( (c, m) = d \), thì \( a \equiv b \) (mod \( md \)) Định lý Fermat nhỏ khẳng định rằng với \( p \) là số nguyên tố và \( a \) là số nguyên, ta có \( a^p \equiv a \) (mod \( p \)) Đặc biệt, nếu \( (a, p) = 1 \), thì \( a^{p-1} \equiv 1 \) (mod \( p \)) Định lý Euler chỉ ra rằng nếu \( m \) là số nguyên dương và \( \gcd(a, m) = 1 \), thì \( a^{\phi(m)} \equiv 1 \) (mod \( m \)), trong đó \( \phi(m) \) là hàm số Euler của \( m \).
Thặng dư bậc hai và ký hiệu Legendre
Số nguyên dương n được định nghĩa là một số nguyên a là thặng dư bậc hai theo mod n, hay còn gọi là số chính phương theo mod n, nếu tồn tại một số nguyên x sao cho x^2 ≡ a (mod n).
Ví dụ 1.3.2 1 2 ≡ 1 (mod 6), 3 2 ≡ 3 (mod 6), 4 2 ≡ 4 (mod 6) Suy ra các số 1,3,4 là các thặng dư bậc hai theo mod 6.
Số 2 là một thặng dư bậc hai theo mod 7, vì 3 2 ≡ 2 (mod 7) Trong khi đó
Trong lý thuyết số, 3 không được coi là thặng dư bậc hai theo modulo 7 Theo định nghĩa 1.3.3, nếu p là một số nguyên tố lẻ và a là một số nguyên tùy ý, thì ký hiệu Legendre a p được xác định để phân loại các số nguyên theo tính chất thặng dư bậc hai.
1 nếu gcd(a, p) = 1 và a là số chính phương mod p;
−1 nếu gcd(a, p) = 1 và a không là số chính phương mod p;
Tiếp theo ta nhắc lại một số tính chất của ký hiệu Legendre
Mệnh đề 1.3.4 (xem [2]) Cho p là số nguyên tố lẻ Khi đó
(7) Với mỗi số nguyên tố lẻ p bất kỳ,
(8) Với mỗi số nguyên tố lẻ p bất kỳ,
(9) Nếu p và q là các sốp nguyên tố lẻ thì q p p q
Sơ lược về đa thức bất khả quy
Đa thức bất khả quy là một khái niệm quan trọng trong đại số, được định nghĩa là một đa thức f(x) ∈ A[x] trong miền nguyên A, với điều kiện f(x) khác 0, không khả nghịch và không có ước thực sự Ngược lại, một đa thức khác 0, không khả nghịch mà không phải là bất khả quy được gọi là đa thức khả quy Vành Gauss, hay còn gọi là vành nhân tử hóa hoặc vành phân tích duy nhất (UFD), là một vành giao hoán D thỏa mãn các điều kiện của một miền nguyên.
(1) Mọi phần tử a khác không, khác đơn vị của D đều được phân tích được thành một tích của các phần tử bất khả quy của D.
Phân tích của một phần tử a theo điều kiện (1) là duy nhất, chỉ khác ở việc hoán vị các thừa số bất khả quy Theo Định lý 1.4.3, nếu D là một UFD thì D[x] cũng sẽ là một UFD.
Cách tiếp cận sơ cấp giải phương trình nghiệm nguyên
Nội dung của chương được tổng hợp từ các tài liệu [3], [4] và [5] Chủ yếu sử dụng tài liệu [4].
Cách tiếp cận sơ cấp giải phương trình nghiệm nguyên
Cách phân tích
Trong vành đa thức Z[x₁, x₂, , xₙ], mọi đa thức khác 0 và khác ±1 đều có thể phân tích thành tích của các đa thức bất khả quy Việc phân tích này là cơ sở quan trọng trong việc nghiên cứu tính chất của các đa thức trong toán học.
Z[x 1 , x 2 , , x n ] (vì nó là vành Gauss).
Ta có thể biểu diễn (2.1) dưới dạng tích của các hàm số f 1, f 2, , f k, với f 1, f 2, , f k thuộc Z[x 1, x 2, , x n] và a là một số nguyên trong Z Do a có thể phân tích thành các thừa số nguyên tố, nên a có thể được viết dưới dạng tích của k số nguyên a 1, a 2, , a k Nếu cần, có thể thêm các thừa số đơn vị hoặc nhóm các thừa số dư thừa lại với nhau Mỗi phân tích như vậy sẽ tương ứng với một hệ phương trình cụ thể.
Bằng việc giải tất cả các hệ phương trình như vậy sẽ cho ta tập tất cả các nghiệm của phương trình (2.1).
Ta sẽ minh họa phương pháp này bằng cách trình bày một vài ví dụ.
Ví dụ 2.1.1 (Titu Andreescu) Tìm tất cả các nghiệm nguyên của phương trình x 2 + 1 y 2 + 1 + 2(x−y)(1−xy) = 4(1 +xy).
Lời giải Viết phương trình dưới dạng x 2 y 2 −2xy + 1 +x 2 + y 2 −2xy+ 2(x−y)(1−xy) = 4, hoặc (xy−1) 2 + (x−y) 2 −2(x−y)(xy−1) = 4 Điều này tương đương với
Nếu (x+ 1)(y −1) = 2, ta có được các hệ phương trình x+ 1 = 2, y −1 = 1, x+ 1 = −2, y −1 = −1, x+ 1 = 1, y −1 = 2, x+ 1 = −1, y −1 = −2.
Giải các hệ ta được các nghiệm (1,2),(−3,0),(0,3),(−2,−1).
Nếu (x+ 1)(y −1) = −2, ta có được các hệ phương trình x+ 1 = 2, y −1 =−1, x+ 1 = −2, y −1 = 1, x+ 1 = 1, y −1 =−2, x+ 1 = −1, y −1 = 2.
Giải các hệ ta được các nghiệm (1,0),(−3,2),(0,−1),(−2,3) Tất cả tám cặp số đã tìm thấy đều thỏa mãn phương trình đã cho.
Ví dụ 2.1.2 Cho p và q là hai số nguyên tố Tìm nghiệm nguyên dương của phương trình
1 x + 1 y = 1 pq. Lời giải Phương trình đã cho tương đương với phương trình nghiệm nguyên
Với điều kiện x, y nguyên dương từ phương trình ban đầu, ta có x < 1 pq, dẫn đến x > pq Tiếp theo, chúng ta xem xét tất cả các ước số của tích p²q², từ đó thu được các hệ phương trình như sau: x - pq = 1 và y - pq = p²q²; x - pq = p và y - pq = pq²; x - pq = q và y - pq = p²q; cũng như x - pq = p² và y - pq = q²; và cuối cùng x - pq = pq và y - pq = pq.
(x−pq = pq 2 , y −pq = p, (x−pq = p 2 q, y−pq = q,
Giải các hệ trên ta được các nghiệm của phương trình ban đầu
(1 +pq, pq(1 +pq)), (p(1 +q), pq(1 +q)), (q(1 +p), pq(1 +p)),
Chú ý Khi xét phương trình 1 x + 1 y = 1 n (với n = p α 1 1 ã ã ãp α k k ), ta sẽ phải xột (2α 1 + 1)ã ã ã(2α k + 1) ước số nguyờn dương Thật vậy, phương trỡnh đó cho tương đương với
(x−n)(y −n) =n 2 và n 2 = p 2α 1 1 ã ã ãp 2α k k cú (2α 1 + 1)ã ã ã(2α k + 1) ước số.
Ví dụ 2.1.3 (Olympic Toán Ấn Độ) Xác định tất cả các cặp số nguyên không âm (x, y) thỏa mãn
Lời giải Phương trình đã cho tương đương với phương trình
Các hệ này tương đương với x+y = 7, xy = 12, x+y = 7, xy = 0.
Các nghiệm của phương trình là (3,4),(4,3),(0,7),(7,0).
Ví dụ 2.1.4 (Olympic Toán Ba Lan) Giải phương trình x 2 (y −1) +y 2 (x−1) = 1 với x, y là các số nguyên.
Lời giải Đặt x = u+ 1, y = v+ 1 Khi đó phương trình trở thành
Phương trình cuối cùng có thể được biểu diễn dưới dạng (u+v + 4)(uv + 1) = 5, từ đó cho thấy tổng u+v và tích uv phải thỏa mãn một trong bốn hệ phương trình sau: u+v = 1 và uv = 0, u+v = −9 và uv = −2, u+v = −3 và uv = 4, hoặc u+v = −5 và uv = −6.
Chỉ có hệ đầu tiên và cuối cùng trong số này có nghiệm thỏa mãn Ta có
(0,1),(1,0),(−6,1),(1,−6) Do đó, kết quả cuối cùng (x, y) = (u+ 1, v+ 1) phải là một trong các cặp (1,2),(−5,2),(2,1),(2,−5).
Ví dụ 2.1.5 (Titu Andreescu) Tìm tất cả các số nguyên n để phương trình x 3 +y 3 +z 3 −3xyz = n có nghiệm nguyên dương.
Lời giải Ta viết lại vế trái của phương trình x 3 +y 3 + z 3 −3xyz = (x+y +z) x 2 +y 2 +z 2 −xy −yz−zx hay x 3 +y 3 +z 3 −3xyz = (x+y +z)[(x−y) 2 + (y −z) 2 + (z −x) 2 ]
2 , (2.2) và ở một dạng khác ta cũng có x 3 +y 3 +z 3 −3xyz = (x+y +z) 3 −3(x+y +z)(xy +yz +zx) (2.3)
Phương trình ban đầu có nghiệm nguyên dương khi n = 3k + 1 hoặc n = 3k + 2 (với k ≥ 1) Khi đó, bộ ba (k + 1, k, k) và (k + 1, k + 1, k) trở thành các nghiệm của phương trình tương ứng với n = 3k + 1 và n = 3k + 2.
Xét trường hợp chia hết cho 3, từ (2.3) suy ra rằng (x+y+z)³ chia hết cho 3, do đó (x+y+z) cũng chia hết cho 3 Điều này dẫn đến n = (x+y+z)³ - 3(x+y+z)(xy + yz + zx) phải chia hết cho 9 Ngược lại, nếu n = 9k (với k ≥ 2), thì bộ ba (k -
1, k, k+ 1) thỏa mãn (x+y +z) [(x−y) 2 +(y−z) 2 2 +(z−x) 2 ] = 3k 6 2 = 9k = n Nếu n= 0 thì (a, a, a) (với a nguyên dương) là nghiệm của phương trình.
Kết luận: Điều kiện để phương trình có nghiệm nguyên dương đó là n 3k + 1 (với k ≥ 1), hoặc n = 3k + 2 (với k ≥ 1), hoặc n = 9k (với k = 0,2,3,4,5, )
Ví dụ 2.1.6 (Titu Andreescu, Dorin Andrica) Tìm tất cả các bộ ba số nguyên dương (x, y, z) thỏa mãn x 3 +y 3 +z 3 −3xyz = p với p là số nguyên tố lớn hơn 3.
Lời giải Phương trình đã cho tương đương với
Vì x, y, z nguyên dương nên x+ y + z > 1 Do đó từ phương trình trên ta phải có x+y +z = p và x 2 +y 2 +z 2 −xy−yz −zx = 1.
Phương trình cuối tương đương với phương trình
Không mất tính tổng quát, ta có thể giả sử rằng x ≥ y ≥ z Nếu x > y > z, thì ta có x− y ≥ 1, y −z ≥ 1 và x− z ≥ 2, điều này suy ra rằng (x−y) 2 + (y−z) 2 + (z −x) 2 ≥6 > 2.
Để giải bài toán, ta cần có x = y = z + 1 hoặc x - 1 = y = z Khi đó, số nguyên tố p = x + y + z sẽ thuộc một trong hai dạng 3k + 2 hoặc 3k + 1 Nếu p có dạng 3k + 2, các nghiệm của phương trình sẽ là (p + 1)/3, (p + 1)/3, (p - 2)/3 và các hoán vị tương ứng Ngược lại, nếu p có dạng 3k + 1, các nghiệm sẽ là (p + 2)/3, (p - 1)/3, (p - 1)/3 cùng các hoán vị tương ứng.
Ví dụ 2.1.7 Tìm tất cả bộ ba số nguyên (x, y, z) thỏa mãn x 3 +y 3 + z 3 = x+y +z = 3.
Lời giải Từ giả thiết và đồng nhất thức
Để giải bài toán, ta có công thức (x+y+z)³ = x³ + y³ + z³ + 3(x+y)(y+z)(z+x) Kết hợp với giả thiết x+y+z = 3, ta nhận được (3−x)(3−y)(3−z) = 8 Hơn nữa, do (3−x) + (3−y) + (3−z) = 9−(x+y+z) = 6, nên có hai trường hợp xảy ra: hoặc cả ba số 3−x, 3−y, 3−z đều là số chẵn, hoặc chỉ có một số là chẵn Trong trường hợp thứ hai, ít nhất một trong ba số |3−x|, |3−y|, |3−z| phải bằng một giá trị nhất định.
Trong bài toán này, ta có ba số x, y, z thỏa mãn điều kiện |3−x| = 8 và |3−y| = |3−z| = 1, dẫn đến x ∈ {−5, 11} và y, z ∈ {2, 4} Kết hợp với x + y + z = 3, ta suy ra chỉ có khả năng x = −5 và y = z = 4 Xét trường hợp khác khi ba số đều khác 0, với tính chất tích ba số bằng 8, ta có |3−x| = |3−y| = |3−z| = 2, từ đó suy ra x, y, z ∈ {1, 5} Với điều kiện x + y + z = 3, khả năng duy nhất là x = y = z = 1.
Tóm lại, các bộ số cần tìm là(1,1,1),(−5,4,4),(4,−5,4), và (4,4,−5).
Ví dụ 2.1.8 (Ion Cucurezeanu) Tìm tất cả các số nguyên tố p để phương trình x 4 + 4 = py 4 có nghiệm nguyên.
Phương trình vô nghiệm khi p = 2, bởi vì khi đó biểu thức bên trái x^4 + 4 trở thành số chẵn, dẫn đến x^4 cũng chẵn và x phải là số chẵn Do đó, x^4 + 4 ≡ 4 (mod 16), trong khi bên phải py^4 = 2y^4 không thỏa mãn điều kiện này.
2 (mod 16) khi y ≡1 (mod 2) ; như vậy vế trái và vế phải luôn khác nhau khi p= 2.
Xét p là số nguyên tố lẻ, từ đẳng thức x^4 + 4 = py^4, ta suy ra rằng x là số lẻ nếu và chỉ nếu y là số lẻ Biểu thức x^4 + 4 có thể viết lại dưới dạng (x^2 + 2)^2 - (2x)^2, do đó phương trình trở thành (x^2 + 2)^2 - (2x)^2 = py^4 Điều này dẫn đến phương trình tương đương (x^2 - 2x + 2)(x^2 + 2x + 2) = py^4.
Ta có gcd(x 2 −2x+ 2, x 2 + 2x+ 2) = 1 (thật vậy, ta thấy
Lấy \( d \) là ước chung lớn nhất của \( x^2 - 2x + 2 \) và \( x^2 + 2x + 2 \) với \( x \) lẻ, ta suy ra \( d = 1 \) Vì \( d \) là ước của 8, từ đó có \( x^2 - 2x + 2 = a^4 \) và \( x^2 + 2x + 2 = pb^4 \), trong đó \( a, b \) là các số nguyên thỏa mãn \( ab = y \) và \( (a, b) = 1 \) Từ đó suy ra \( (x - 1)^2 + 1 = a^4 \) và \( (x + 1)^2 + 1 = pb^4 \) Phương trình đầu tiên cho ta \( x = 1 \) và \( a^2 = 1 \); do đó, từ phương trình thứ hai ta có \( p = 5 \) và \( b^2 = 1 \) Kết luận, chỉ có số nguyên tố \( p = 5 \) thì phương trình có nghiệm, với các nghiệm \( (x, y) \) là \( (1, 1), (-1, 1), (1, -1), (1, 1) \).
Cách dùng bất đẳng thức
Quá trình này giúp hạn chế giá trị của các biến trong các khoảng nhất định, dẫn đến việc chỉ có một số lượng hữu hạn các đánh giá cho các biến thông qua các bất đẳng thức phù hợp Như vậy, chỉ có một số khả năng hữu hạn cho tất cả các biến hoặc cho một số biến cụ thể.
Ví dụ 2.1.9 Tìm các cặp số nguyên (x, y) thỏa mãn x 3 +y 3 = (x+y) 2
Tất cả các cặp số có dạng (k,−k) với k ∈ Z đều là nghiệm của phương trình Khi x + y ≠ 0, phương trình trở thành x² - xy + y² = x + y, tương đương với một phương trình khác.
Từ đó suy ra (x−1) 2 ≤ 1 và (y −1) 2 ≤ 1 (vì nếu chẳng hạn (x−1) 2 ≥ 2 thì (x−y) 2 = 0 = (y −1) 2 ; suy ra x = y = 1 mâu thuẫn với (x− 1) ≥ 2).
Từ đó ta hạn chế các biếnx, y vào trong đoạn [0,2] Do đó ta nhận được các nghiệm của phương trình là (0,1),(1,0),(1,2),(2,1),(2,2).
Ví dụ 2.1.10 (Olympic Rumani) Giải phương trình sau với các số x, y, z nguyên dương:
Lời giải Vì tính chất đối xứng của các biến, nên ta có thể giả sử 2 ≤ x ≤ y ≤z Từ đó ta có bất đẳng thức x 3 ≥ 3 5 , và do đó x ∈ {2,3,4,5}.
Nếu x = 2, thì 1 y + 1 z = 10 1 với y ∈ {11,12, ,20} (do y ≤ z) Do đó z = 10 + y−10 100 và (y−10)|100 Từ đó ta nhận được các nghiệm là (2,11,110),
Nếu x = 3, thì ta có 1 y + z 1 = 15 4 với y ∈ {3,4,5,6,7} (vì y ≤ z) Suy ra z = 4− 4y−15 y−60 và (4y−15)|(y−60) Ta có các nghiệm là (3,4,60), (3,5,15),
Nếux = 4, thì 1 y + z 1 = 20 7 vớiy ∈ {4,5}(vì y ≤ z) Ta có nghiệm là (4,4,10).Nếu x = 5, thì 1 y + 1 z = 2 5 và y = z = 5, ta thu được nghiệm là (5,5,5).
Ví dụ 2.1.11(Titu Andreescu) Tìm các bộ bốn số nguyên dương (x, y, z, w) thỏa mãn x 2 +y 2 +z 2 + 2xy + 2x(z−1) + 2y(z + 1) = w 2
Theo bất đẳng thức (x + y + z − 1)² < w² < (x + y + z + 1)², ta có thể kết luận rằng x² + y² + z² + 2xy + 2x(z−1) + 2y(z+1) chỉ có thể bằng (x + y + z)² Điều này dẫn đến phương trình x² + y² + z² + 2xy + 2x(z−1) + 2y(z+1) = x² + y² + z² + 2xy + 2xz + 2yz, từ đó suy ra 2x(z−1) + 2y(z+1) = 2xz + 2yz Cuối cùng, ta có −2x + 2y = 0, suy ra x = y Vì vậy, các nghiệm của phương trình là (m, m, n, 2m + n) với m, n ∈ Z+.
Ví dụ 2.1.12(Olympic Hungary) Tìm tất cả các nghiệm nguyên của phương trình x 3 + (x+ 1) 3 + (x+ 2) 3 +ã ã ã+ (x+ 7) 3 = y 3 Lời giải Đặt
< P(x) < 8x 3 + 120x 2 + 600x+ 1000 = (2x+ 10) 3 , vậy2x+ 7< y < 2x+ 10; vì thế y có thể là 2x+ 8hoặc 2x+ 9 Nhưng cả hai phương trìnhP(x)−(2x+8) 3 = −12x 2 +36x+272 = 0, vàP(x)−(2x+9) 3 −24x 2 −66x + 55 = 0 đều không có nghiệm nguyên, do vậy phương trình vô nghiệm khi x ≥ 0.
Chú ý rằng hàm số P(x) thỏa mãn điều kiện P(−x−7) = −P(x), dẫn đến (x, y) là nghiệm của phương trình khi và chỉ khi (−x − 7,−y) cũng là nghiệm Do đó, phương trình không có nghiệm với x ≤ −7, và nếu (x, y) là nghiệm, thì x phải nằm trong khoảng −6 ≤ x ≤ −1.
−3 ≤ x ≤ −1, ta có P(−1) = 440, không là lập phương của một số,
P(−2) = 216 = 6 3 , và P(−3) = 64 = 4 3 , vậy (−2,6) và (−3,4) là nghiệm của phương trình khi −3≤ x ≤ −1 Do đó (−4,−4) và (−5,−6) là nghiệm của phương trình khi −6≤ x ≤ −4 Vậy phương trình có nghiệm là (−2,6), (−3,4), (−4,−4), và (−5,−6).
Ví dụ 2.1.13 (Olympic Anh Quốc) Tìm tất cả các bộ ba số nguyên dương (x, y, z) thỏa mãn
Lời giải Không mất tính tổng quát, ta giả sử x ≥ y ≥ z Do đó ta thấy
Xét trường hợp nếu z = 1 thì 1 + x 1 1 + 1 y = 1, điều này không xảy ra.
Xét trường hợp z = 2 dẫn đến 1 + x 1
, suy ra y < 7 Mặt khác vì 1 + 1 x > 1, nên từ đẳng thức (*) ta suy ra y > 3 Thử các giá trị thích hợp của các biến ta thu được các nghiệm là
Xét trường hợp nếu z = 3thì 1 + x 1
= 3 2 Làm tương tự thì dẫn đến y < 5 và y ≥z = 3 Ta được các bộ số (8,3,3) và (5,4,3) là nghiệm. Tóm lại, các nghiệm của phương trình là (7,6,2), (9,5,2), (15,4,2),
(8,3,3) và (5,4,3) cùng với các hoán vị của nó.
Ví dụ 2.1.14 (Cuộc thi toán Putnam) Tìm tất cả các số nguyên dương n, k 1 , , k n thỏa món k 1 + ã ã ã+ k n = 5n−4 và k 1
1 +ã ã ã+ k 1 n = 1. Lời giải Theo bất đẳng thức Cauchy–Schwarz ta có
Theo bất đẳng thức 5n−4 ≥ n^2, ta có n ≤ 4 Giả sử k1 ≤ k2 ≤ ≤ kn Khi n = 1, k1 phải bằng 1 Tuy nhiên, với n > 1, ta không thể có k1 = 1.
Nếu n = 2, thì k1 + k2 = 6; suy ra (k1, k2) ∈ {(2,4),(3,3)} Kiểm tra thấy không cặp nào là nghiệm.
Nếu n= 3, thì k 1 +k 2 +k 3 = 11, nên3k 1 ≤ 11; suy ra 2 ≤k 1 ≤ 3 Vì thế (k 1 , k 2 , k 3 ) ∈ {(2,2,7),(2,3,6),(2,4,5),(3,3,5),(3,4,4)} Ta kiểm tra thấy chỉ có (2,3,6) thỏa mãn.
Nếu n = 4, thì dấu bằng của bất đẳng thức (AM–HM) xảy ra khi và chỉ khi k 1 = k 2 = k 3 = k 4 = 4.
Kết luận Nghiệm của phương trình là n = 1 và k 1 = 1; n = 3 và(k1, k2, k3) là một hoán vị của (2,3,6); n = 4 và (k1, k2, k3, k4) = (4,4,4,4).
Cách tham số hóa, số học mô-đun hóa
Trong nhiều trường hợp, các nghiệm nguyên của phương trình f(x₁, x₂,…, xₙ) = 0 có thể được biểu diễn dưới dạng tham số hóa Cụ thể, các nghiệm có thể được viết như sau: x₁ = g₁(k₁,…,kₗ), x₂ = g₂(k₁,…,kₗ), …, xₙ = gₙ(k₁,…,kₗ), trong đó g₁, g₂,…, gₙ là các hàm l-biến k₁,…,kₗ và nhận giá trị nguyên khi k₁,…,kₗ thuộc tập số nguyên Z.
Tập hợp nghiệm của các phương trình nghiệm nguyên thường có nhiều cách biểu diễn tham số hóa Đối với nhiều phương trình, việc tìm kiếm tất cả các nghiệm chính xác là không khả thi Tuy nhiên, phương pháp tham số hóa có thể chứng minh sự tồn tại của vô số nghiệm trong những trường hợp này.
Ví dụ 2.1.15 (Cuộc thi liên thành phố) Chứng minh rằng có vô số bộ ba (x, y, z) nguyên sao cho x 3 +y 3 + z 3 = x 2 +y 2 +z 2
Lời giải Đặt z = −y, phương trình trở thành x 3 = x 2 + 2y 2 Lấy y = mx với m ∈ Z, ta suy ra được x = 1 + 2m 2 Vậy ta có vô số nghiệm x = 2m 2 + 1, y = m(2m 2 + 1), z = −m(2m 2 + 1), m ∈ Z.
Ví dụ 2.1.16 (a) Cho m và n là các số nguyên dương phân biệt Chứng minh rằng tồn tại vô số bộ ba số nguyên dương (x, y, z) thỏa mãn x 2 +y 2 m 2 +n 2 z với z lẻ (hoặc z chẵn).
(b) Chứng minh rằng phương trình x 2 + y 2 = 13 z có vô số nghiệm nguyên dương x, y, z.
Lời giải (a) Xét đối với z lẻ Ta thấy họ các số xk = m m 2 + n 2 k , yk = n m 2 +n 2 k , zk = 2k+ 1, k ∈ Z + thỏa mãn phương trình.
Xét đối với z chẵn Ta thấy họ các số x k = |m 2 −n 2 |(m 2 +n 2 ) k−1 , y k = 2mn(m 2 +n 2 ) k−1 , z k = 2k, k ∈ Z +
(b) Vì 2 2 + 3 2 = 13, nên ta có thể chọn m = 2, n = 3 thay vào phương trình ở ý (a), và ta thu được kết quả là họ các nghiệm của phương trình x 2 +y 2 = 13 z là x 0 k = 2ã13 k , y k 0 = 3ã13 k , z k 0 = 2k+ 1, k ∈ Z + ; x 00 k = 5ã13 k−1 , y k 00 = 12ã13 k−1 , z k 00 = 2k, k ∈ Z +
Nhận xét Ta có thêm hai cách khác để chứng tỏ phương trình x 2 +y 2 (m 2 +n 2 ) z ở Ví dụ 2.1.16 có vô số nghiệm.
Theo đẳng thức Lagrange \( a^2 + b^2 c^2 + d^2 = (ac - bd)^2 + (ad + bc)^2 \), ta có thể tạo ra vô hạn các nghiệm bằng cách xây dựng đệ quy cho các dãy \( (x_k)_{k \geq 1} \) và \( (y_k)_{k \geq 1} \) với công thức: \( x_{k+1} = mx_k - ny_k \) và \( y_{k+1} = nx_k + my_k \), trong đó \( x_1 = m \) và \( y_1 = n \) Có thể kiểm tra rằng các giá trị \( (|x_k|, y_k, k) \) (với \( k \in \mathbb{Z}^+ \)) là các nghiệm của phương trình \( x^2 + y^2 = (m^2 + n^2) z \) đã cho.
Một phương pháp khác để tạo ra một họ nghiệm vô hạn là xem xét các số phức Gọi k là số nguyên dương, ta có A_k + iB_k = (m + in)^k với A_k, B_k ∈ Z Bằng cách lấy mô-đun của hai vế của các số phức, ta có thể tiếp tục phân tích.
A 2 k +B k 2 = m 2 + n 2 k , và như vậy (|A k |,|B k |, k) là một nghiệm của phương trình x 2 +y 2 = (m 2 + n 2 ) z đã cho.
Ví dụ 2.1.17 Tìm các bộ ba số nguyên duowng (x, y, z) thỏa mãn 1 x + y 1 = 1 z
Phương trình tương đương với z = x + y xy, với d = gcd(x, y) Khi đó, ta có x = dm và y = dn, trong đó gcd(m, n) = 1 Từ đó suy ra gcd(mn, m + n) = 1, vì nếu e = gcd(mn, m + n) thì e chia hết cho mn và m + n, dẫn đến e chia hết cho n² và m², từ đó suy ra e chia hết cho gcd(m², n²) Do gcd(m², n²) = 1, nên e = 1 Do đó, z = m + n dmn, kéo theo (m + n) | d, tức là d = k(m + n) với k ∈ Z⁺.
Do vậy, các nghiệm của phương trình được cho bởi công thức x = km(m+ n), y = kn(m+ n), z = kmn, với k, m, n∈ Z +
Từ lời giải của Ví dụ 2.1.17, ta có nhận xét sau đây.
Nếu a, b, c là các số nguyên dương và nguyên tố cùng nhau thỏa mãn điều kiện 1/a + 1/b = 1/c, thì tổng a + b sẽ là một số chính phương Cụ thể, với k = 1 từ chứng minh của Ví dụ 2.1.17, ta có a = m(m + n), b = n(m + n), c = mn, và do đó, a + b = (m + n)².
(2) Nếu a, b, c là các số nguyên dương thỏa mãn a 1 + 1 b = 1 c thì a 2 + b 2 + c 2 là số chính phương Thật vậy, theo cách đặt và kết quả trong chứng minh Ví dụ 2.1.17, ta có a 2 + b 2 + c 2 = k 2 m 2 (m +n) 2 + n 2 (m+n) 2 +m 2 n 2
Ví dụ 2.1.18 (Dorin Andrica) chứng minh rằng với các số nguyên dương a và b, phương trình x² - 2axy + a² - 4by² + 4by = z² có vô số nghiệm nguyên dương (xj, yj, zj) Các dãy số (xj), (yj), (zj) đều là các dãy số tăng.
Lời giải Ta sẽ sử dụng thêm kết quả phụ trợ sau đây.
Bổ đề 2.1.19 Nếu A, B là các số nguyên dương và nguyên tố cùng nhau, thì tồn tại các số nguyên dương u, v sao cho Au−Bv = 1.
Chứng minh rằng các số nguyên A, 2A, , (B-1)A đều khác nhau khi lấy mô-đun B Nếu k1A ≡ k2A (mod B) với k1 ≠ k2 trong tập {1, 2, , B-1}, thì ta có (k1 - k2)A ≡ 0 (mod B) Do gcd(A, B) = 1, suy ra k1 - k2 ≡ 0 (mod B) dẫn đến mâu thuẫn Hơn nữa, k.A ≢ 0 (mod B) với mọi k ∈ {1, 2, , B-1}.
Do đó có ít nhất một trong các số nguyên 1.A,2.A, ,(B −1).A sẽ có phần dư là1khi chia cho B Suy ra tồn tại u, v ∈ Z + sao cho u.A−1 = v.B,hay 1 = u.A−v.B.
Nghiệm nhỏ nhất (u₀, v₀) trong các nghiệm nguyên dương của phương trình Ax - By = 1 cho phép xác định tất cả các nghiệm nguyên dương khác thông qua công thức uₘ = u₀ + Bm và vₘ = v₀ + Am, với m thuộc tập hợp số nguyên dương Z⁺.
Quay trở lại vấn đề của ví dụ, ta hãy xem xét dãy số (y n ) n≥1 cho bởi công thức y n+1 = by n 2 + ay n + 1, y 1 ∈ Z + (*)
Rõ ràng là gcd(y n , y n+1 ) = 1 với mọi n ∈ Z + Do đó từ bổ đề nêu trên, ta suy ra tồn tại các dãy số nguyên dương (u n ) n≥1 ,(v n ) n≥1 sao cho y n+1 u n −y n v n = 1, n ∈ Z +
Do đó kết hợp với (∗) ta có buny 2 n + (aun −vn)yn+un −1 = 0, n∈ Z + (**)
Ta coi (∗∗) như một phương trình bậc hai với ẩn là y n và chỉ lấy y n ∈ Z + ; khi đó suy ra biệt thức của nó
∆ n = (au n −v n ) 2 −4bu n (u n −1) phải là một số chính phương Tức là, v 2 n −2au n v n + (a 2 −4b)u 2 n + 4bu n = z n 2 , n∈ Z +
Các dãy số (u n) n≥1 và (v n) n≥1 bao gồm các dãy con (u n j) j≥1 và (v n j) j≥1 tăng nghiêm ngặt Hơn nữa, tồn tại một họ vô hạn các nghiệm thỏa mãn điều kiện được xác định bởi (v n j, u n j, z n j) với j ≥1.
Vế trái của phương trình trong Ví dụ 2.1.18 có thể được viết lại dưới dạng (x− ay) 2 −4by(y − 1), biểu thị biệt thức của phương trình bậc hai byt 2 + (ay − x)t + y − 1 = 0 với ẩn mới là t Biệt thức này trở thành một số chính phương khi phương trình cuối có nghiệm nguyên Khi viết lại phương trình dưới dạng y bt 2 + at + 1 = 1 + xt, ta nhận thấy rằng t = 1 là một nghiệm nếu y(b + a + 1) = 1 + x, điều này thỏa mãn với vô hạn các cặp số nguyên (x, y) Qua tính toán, ta có z = by − y + 1, từ đó tìm ra một tập hợp vô hạn các nghiệm với x = (a+b+ 1)m − 1, y = m, z = (b−1)m + 1, với m ∈ Z +.
Trong bài viết này, chúng ta sẽ khám phá cách số học mô-đun hóa, một công cụ hữu ích trong việc chứng minh rằng một số phương trình nghiệm nguyên nhất định không có nghiệm, hoặc giúp thu hẹp phạm vi của các nghiệm có thể Việc áp dụng mô-đun hóa một cách hợp lý sẽ mang lại những kết quả rõ ràng và chính xác hơn trong việc phân tích các phương trình này.
Vớ dụ 2.1.20 Chứng minh rằng phương trỡnh (x+ 1) 2 + (x+ 2) 2 + ã ã ã+ (x+ 2001) 2 = y 2 vô nghiệm nguyên.
Lời giải Đặt x = z −1001 Phương trình trở thành
Vế trái đồng dư với2 (mod 3), vì vậy nó không thể là một chính phương.
Ví dụ 2.1.21 (Olimpic Toán Nga) Tìm tất cả các cặp số nguyên tố (p, q) thỏa mãn p 3 −q 5 = (p+ q) 2
Nghiệm duy nhất của phương trình là (7,3) Để chứng minh, giả sử p và q đều khác 3, khi đó p và q sẽ tương đương với 1 hoặc 2 (mod 3) Nếu p tương đương với q (mod 3), thì vế trái sẽ chia hết cho 3, trong khi vế phải không chia hết Ngược lại, nếu p không bằng q (mod 3), thì vế phải sẽ chia hết cho 3, còn vế trái thì không.
Nếu p = 3, thì 27−q 5 = (3 + q) 2 , suy ra q 5 = 27−(3 +q) 2 < 27 đó là điều không thể đối với bất kì số nguyên tố q nào.
Nếu q = 3, ta có p 3 − 243 = (p+ 3) 2 , có nghiệm nguyên duy nhất là p= 7.
Ví dụ 2.1.22 (Olympic Toán Balkan) Chứng minh rằng phương trình x 5 − y 2 = 4 vô nghiệm nguyên
Lời giải Ta xét phương trình mô-đun 11 Vì (x 5 ) 2 = x 10 = x ϕ(11) ≡ 1 (mod 11) (nếu (x,11) = 1), và ≡0 (nếu 11 | x), nên ta có x 5 ≡ −1, 0, hoặc
Phương trình x^5 - 4 đồng dư 6, 7 hoặc 8 mô-đun 11, nhưng các số chính phương mô-đun 11 chỉ có thể là 0, 1, 3, 4, 5 và 9 Do đó, phương trình này không có nghiệm nguyên.
Ví dụ 2.1.23 (Olimpic Toán Đức) Xác định tất cả các số nguyên tố p để hệ
(p+ 1 = 2x 2 p 2 + 1 = 2y 2 có một nghiệm nguyên duy nhất (x, y).
Lời giải Số nguyên tố duy nhất như vậy là p = 7 Thật vậy, không mất tính tổng quát, ta giả sử x, y ≥ 0 Chú ý p+ 1 = 2x 2 là số chẵn, vậy p6= 2.
Ta có phương trình 2x² ≡ 1 ≡ 2y² (mod p), từ đó suy ra x ≡ ±y (mod p) với p là số lẻ Vì x < y < p, ta có x + y = p, dẫn đến p² + 1 = 2(p−x)² = 2p² − 4px + p + 1 Kết quả là p² = 4px − p, từ đó suy ra p = 4x − 1, và 2x² = 4x Do đó, x có thể bằng 0 hoặc 2, tương ứng với p bằng −1 hoặc 7 Tuy nhiên, −1 không phải là số nguyên tố, do đó chỉ còn lại p = 7, là số nguyên tố, với nghiệm (x, y) = (2, 5) cho phương trình.
Cách quy nạp toán học và cách lùi vô hạn
Quy nạp toán học là một phương pháp chứng minh mạnh mẽ và hiệu quả, đặc biệt dùng để xác minh các mệnh đề liên quan đến số nguyên không âm.
Quy nạp toán học là một phương pháp mạnh mẽ để chứng minh rằng mệnh đề P(n) đúng với mọi n ≥ n0, trong đó n0 là một số nguyên không âm được xác định trước Dãy các mệnh đề P(n) với n ≥ 0 cho thấy sự liên kết và tính chính xác của quy trình này Dưới đây là một số dạng phổ biến của quy nạp toán học mà bạn có thể tham khảo.
Quy nạp toán học (dạng yếu): Giả sử rằng
• Với mọi k ≥n 0 , từ P(k) là đúng kéo theo P(k + 1) là đúng.
Khi đó P(n) đúng với mọi n ≥ n 0
Quy nạp toán học (với bước nhảy s): Cho s là một số nguyên dương cố định Giả sử rằng:
• Với mọi k ≥n 0 , từ P(k) đúng kéo theo P(k+ s) là đúng.
Khi đó P(n) đúng với mọi n ≥ n 0
Quy nạp toán học (dạng mạnh): Giả sử rằng
• Với mọi k ≥ n 0 , P(m) là đúng với mọi m mà n 0 ≤ m ≤ k kéo theo
Khi đó P(n) đúng với mọi n ≥ n0.
Phương pháp chứng minh quy nạp toán học được áp dụng rộng rãi trong nhiều lĩnh vực của toán học, đặc biệt là trong lý thuyết số Các ví dụ sau đây sẽ minh họa cách quy nạp toán học được sử dụng để nghiên cứu các phương trình nghiệm nguyên.
Ví dụ 2.1.25 (Olympic Toán Bungary) Chứng minh rằng với mọi số nguyên n≥ 3, tồn tại các số lẻ nguyên dương x, y, sao cho 7x 2 +y 2 = 2 n
Lời giải Ta sẽ chứng minh rằng tồn tại các số nguyên dương lẻ x n , y n sao cho 7x 2 n +y n 2 = 2 n với n ≥3.
Với n = 3, ta có x³ = y³ = 1 Giả sử với một số nguyên n ≥ 3, tồn tại các số nguyên lẻ xⁿ, yⁿ thỏa mãn 7x²ⁿ + yⁿ² = 2ⁿ Ta sẽ chứng minh rằng có một cặp (xⁿ⁺¹, yⁿ⁺¹) các số nguyên dương lẻ thỏa mãn 7x²ⁿ⁺¹ + y²ⁿ⁺¹ = 2ⁿ⁺¹.
Ta thấy có đúng một trong những số x n +y 2 n và |x n −y 2 n | là số lẻ (vì tổng của chúng là x n hoặc y n , đó là số lẻ) Nếu chẳng hạn x n +y 2 n là số lẻ, thì
2 cũng là số lẻ (vì tổng của số lẻ và số chẵn); do đó trong này trường hợp này ta có thể chọn x n+1 = x n +y n
2 cũng lẻ Do đó ta có thể chọn x n+1 = |x n −y n |
Ví dụ 2.1.26 (Dorin Andrica) Chứng minh rằng với mọi số nguyên dương n, phương trình x 2 +y 2 +z 2 = 59 n có nghiệm trên tập các số nguyên dương.
Chúng ta áp dụng quy nạp toán học với bước nhảy s = 2 và n 0 = 1 để giải bài toán Đối với các giá trị (x 1 , y 1 , z 1 ) = (1,3,7) và (14,39,42), ta có x 2 1 + y 1 2 + z 1 2 = 59 và x 2 2 + y 2 2 + z 2 2 = 59 2 Tiếp theo, chúng ta xác định (x n , y n , z n ) với n ≥ 3 theo công thức x n+2 = 59x n , y n+2 = 59y n , z n+2 = 59z n cho mọi n ≥ 1 Do đó, x 2 k+2 + y k+2 2 + z k+2 2 = 59 2 (x 2 k + y k 2 + z k 2), từ đó suy ra nếu x 2 k + y k 2 + z k 2 = 59 k thì x 2 k+2 + y k+2 2 + z k+2 2 = 59 k+2.
Chú ý rằng: Ta có thể viết cụ thể các nghiệm như sau
Ví dụ 2.1.27 Chứng minh rằng với mọi n ≥3 phương trình
1 x 1 + 1 x 2 +ã ã ã+ 1 x n = 1 (1) có nghiệm trên tập số nguyên dương phân biệt.
Lời giải Với trường hợp n= 3 ta có 1 2 + 1 3 + 1 6 = 1 Giả sử với k ≥ 3,
= 1, trong đó x 1 , x 2 , , x k là các số nguyên dương phân biệt, ta được
2x k = 1, trong đó 2,2x1,2x2, ,2xk phân biệt.
1, 3! 2 , , n−1 n! , n! là một nghiệm của phương trình (1), và tất cả các thành phần là phân biệt.
(ii) Một nghiệm khác của phương trình (1) có các thành phần là phân biệt, được đưa ra bởi
(iii) Một cách khác để xây dựng các nghiệm của phương trình (1) là xem xét dãy a 1 = 2, a m+1 = a 1 ã ã ãa m + 1, m ≥ 1.
Thật vậy, ta có a k+1 −1 = a k (a k −1), k ≥ 1, hoặc
1 −1 − a 1 n −1 = 1− a 1 n −1 Do đó mối quan hệ (2) được xác minh.
(iv) Nếu (s 1 , s 2 , , s n ) là nghiệm của phương trình
1 x 1 + 1 x 2 +ã ã ã+ 1 x n = 1 với s 1 < s 2 < ã ã ã < s n thỡ (s 1 , s 2 , , s n−1 , s n + 1, s n (s n + 1)) là nghiệm của phương trình
1 y 1 + 1 y 2 +ã ã ã+ 1 y n+1 = 1 và tất cả các thành phần đều phân biệt.
(v) Với a > 1, ta có đẳng thức 1 a−1 = 1 a + 1 a 2 +ã ã ã+ 1 a m + 1
(a−1)a m tạo ra nhiều họ khác nhau của các nghiệm Ví dụ: Từ
6 = 1 và a = 7, ta cú nghiệm 2,3,7,7 2 , ,7 n−3 ,6ã7 n−3 , n ≥ 4, trong khi từ
42 = 1 ta cú 2,3,7,43,43 2 , ,43 n−4 ,42ã43 n−4 , n ≥ 5 Từ việc xõy dựng ở trờn, ta suy ra rằng phương trình (1) có vô số nghiệm có các thành phần phân biệt.
(vi) Ta không biết liệu có hay không vô số nguyên dương n để phương trình
(1) nhận các nghiệm (x 1 , x 2 , , x n ), trong đó x 1 , x 2 , , x n đều là các số nguyên dương lẻ phân biệt.
Một số lập luận đơn giản cho thấy n phải là số lẻ trong trường hợp này Có nhiều ví dụ về các số nguyên n, chẳng hạn như khi n = 9.
Ví dụ 2.1.28 Chứng minh rằng phương trình
1 x 2 1 + 1 x 2 2 +ã ã ã+ 1 x 2 n = n+ 1 x 2 n+1 có nghiệm trên tập số nguyên dương khi và chỉ khi n ≥ 3.
Lời giải Với n= 1, phương trình trở thành
Xét tiếp với n = 2 Thì phương trình trở thành
Với 1 ≤ i ≤ 3, ta đặt x i = 3 n i y i , trong đó y i không chia hết cho 3 Không mất tính tổng quát ta giả sử rằng n1 ≥n2 Thì
3 2(n 2 +n 3 ) (y 2 y 3 ) 2 + 3 2(n 1 −n 2 ) (y 1 y 3 ) 2 = 3 2(n 1 +n 2 )+1 (y 1 y 2 ) 2 (3) Bởi vì y2, y3 không chia hết cho 3, nên
Do đó số mũ của 3 ở hai bên của (3) không thể bằng nhau.
Cuối cùng, xem xét n ≥3 Bắt đầu từ 5 2 = 4 2 + 3 2 , ta được
20 2 bằng cách chia cho 3 2 4 2 5 2 Nhân với 1
(x 1 , x 2 , x 3 , x 4 ) = 12ã15,15ã20,20 2 ,2ã12 2 là một nghiệm khin = 3 Theo quy nạp toán học, giả sử rằng (x 1 , , x n+1 ) là một nghiệm
1 x 2 1 +ã ã ã+ 1 x 2 n = n+ 1 x 2 n+1 với n≥ 3 và dẫn đến phương trình
Chú ý Với n= 1, ta có phương trình √
Phương trình 2x^1 = x^2 vô nghiệm Với n = 2, ta có x^2 + 2x^3 + x^1 = 3x^2, tương đương với a^2 + b^2 = 3c^2 Giả sử a, b, và c đều khác 0 và nguyên tố cùng nhau, tức là gcd(a, b, c) = 1 Bình phương của một số nguyên đồng dư với 0 hoặc 1 mô-đun 3, do đó a và b đều chia hết cho 3 Điều này dẫn đến c cũng chia hết cho 3, tạo ra mâu thuẫn với gcd(a, b, c) = 1.
Với n = 3, ta có ít nhất một nghiệm: (x 1 , x 2 , x 3 , x 4 ) = (3,3,6,4), tức là,
4 2 Với mỗi số nguyên n > 3, ta có thể sử dụng nghiệm với n= 3 và nhận được
Ví dụ 2.1.29 Chứng minh rằng với mọi n ≥ 412 đều có các số nguyên dương x 1 , , x n sao cho
Phương trình (1) có thể giải được trên tập số nguyên dương nếu phía bên phải của nó có tám số hạng Do đó, phương trình sau cũng sẽ có thể được giải.
Để chứng minh tính giải được của phương trình 1 x 3 1 + 1 x 3 2 + + 1 x 3 n + 7 = 1, ta thay phân số cuối bằng 8 phân số mới, dẫn đến việc phát sinh 7 phân số mới Sử dụng phương pháp quy nạp toán học với bước 7, ta chỉ cần xem xét các trường hợp n từ 412 đến 418 Ý tưởng chính là xây dựng cách giải cho mỗi trường hợp này dựa trên các trường hợp nhỏ hơn theo mô-đun 7.
Phần tiếp theo ở mục này ta xét cách lùi vô hạn Pierre de Fermat (1601
Pierre de Fermat, nổi tiếng với những đóng góp quan trọng cho toán học, mặc dù chỉ được xem là một nhà toán học nghiệp dư Ông nhận bằng luật dân sự tại Đại học Orleans trước năm 1631 và sau đó làm luật sư, cùng với vai trò là ủy viên hội đồng tại Toulouse.
Fermat đã ảnh hưởng sâu sắc đến toán học nhờ những khám phá và phương pháp độc đáo của ông Ông được coi là một trong những nhà toán học tiên phong trong việc áp dụng phương pháp chứng minh "lùi vô hạn" (infinite descent), mở ra nhiều hướng đi mới cho nghiên cứu toán học.
Cho P là một tính chất phụ thuộc vào các số nguyên không âm n và cho (P(n)) n≥1 là dãy các mệnh đề, trong đó
Phương pháp sau đây rất hữu ích trong việc chứng minh mệnh đề P(n) là sai với mọi số n đủ lớn.
Cho k là số nguyên không âm Giả sử rằng:
• Mỗi khi P(m) là đúng với một số nguyên dương m > k, thì phải có một số nguyên j nhỏ hơn, m > j ≥ k, làm P(j) là đúng.
Khi P(n) sai với mọi n ≥ k, điều này thể hiện một cách phát biểu tương phản của quy nạp toán học mạnh, áp dụng cho sự phủ định của mệnh đề P(n) Trong ngôn ngữ ẩn dụ, nếu bạn nhận thức rằng không thể đạt được bất kỳ nấc thang nào mà không cần đến một nấc thang thấp hơn, và đồng thời biết rằng không thể đạt được các bậc thang dưới cùng, thì bạn sẽ không thể đạt được bất kỳ nấc thang nào.
Phương pháp được mô tả ở trên thường được gọi là phương pháp lùi vô hạn Phương pháp lùi vô hạn (FMID) có thể được trình bày như sau:
Cho k là số nguyên không âm Giả sử rằng:
• Mỗi khi P(m) là đúng với một số nguyên m > k, thì phải có một số nguyên j nhỏ hơn, m > j > k, mà ở đó P(j) là đúng.
Khi đó P(n) là sai với mọi n > k.
Nếu có một số nguyên n mà P(n) đúng, thì có thể xây dựng một dãy số n > n1 > n2 > tất cả đều lớn hơn k Tuy nhiên, đối với các số nguyên không âm, không tồn tại dãy giảm dần vô hạn nào như vậy.
Hai trường hợp đặc biệt của FMID đặc biệt hữu ích trong nghiên cứu phương trình nghiệm nguyên, được trình bày sau đây:
Phương pháp lùi vô hạn 1 Không có dãy số nguyên không âm dạng n 1 > n 2 > ã ã ã.
(dạng tương đương: Nếu n0 là số nguyên dương nhỏ nhất n để cho P(n) là đúng, thì P(n) là sai với mọi n < n 0 ).
Phương pháp lùi vô hạn 2.Nếu dãy số nguyên không âm (ni) i≥1 thỏa mãn cỏc bất đẳng thức n 1 ≥ n 2 ≥ ã ã ã, thỡ tồn tại i 0 sao cho n i 0 = n i 0 +1 = ã ã ã.
Ví dụ 2.1.30 Giải phương trình sau trên tập số nguyên không âm x 3 + 2y 3 = 4z 3
Lời giải cho phương trình cho thấy nghiệm (0,0,0) là một nghiệm duy nhất Để chứng minh điều này, giả sử (x1, y1, z1) là một nghiệm không tầm thường của phương trình Qua phân tích, ta sẽ chỉ ra rằng không tồn tại nghiệm nào khác ngoài nghiệm đã nêu.
4 là vô tỉ, nên ta dễ suy ra được x 1 > 0, y 1 > 0, z 1 > 0.
Từ phương trình \( x^3 + 2y^3 = 4z^3 \), ta suy ra \( x_1 = 2x_2 \) với \( x_2 \in \mathbb{Z}^+ \) Tiếp theo, ta có \( 4x_2^3 + y_1^3 = 2z_1^3 \), dẫn đến \( y_1 = 2y_2 \) với \( y_2 \in \mathbb{Z}^+ \) Điều này cho phép ta rút ra \( 2x_2^3 + 4y_2^3 = z_1^3 \) và tương tự, \( z_1 = 2z_2 \) với \( z_2 \in \mathbb{Z}^+ \) Kết quả là \( x_2^3 + 2y_2^3 = 4z_2^2 \), từ đó tạo ra nghiệm mới \( (x_2, y_2, z_2) \) với điều kiện \( x_1 > x_2, y_1 > y_2, z_1 > z_2 \) Quá trình này tiếp tục cho phép xây dựng một dãy các nghiệm \( (x_n, y_n, z_n) \) với \( n \geq 1 \) sao cho \( x_1 > x_2 > x_3 > \ldots \), nhưng điều này mâu thuẫn với nguyên lý lùi vô hạn.
Ví dụ 2.1.31 Giải phương trình 2 x −1 = xy trên tập số nguyên không âm.
Một số cách giải khác
Nhiều phương trình nghiệm nguyên cơ bản không nằm trong các loại đã được mô tả trước đây Dưới đây, chúng ta sẽ khám phá một số ví dụ về những phương trình này.
Ví dụ 2.1.36 (Titu Andreescu) Giải hệ phương trình trên tập số nguyên dương
Các bất đẳng thức x² + 3y ≥ (x + 2)² và y² + 3x ≥ (y + 2)² không thể đồng thời đúng, vì nếu cả hai đều đúng, ta sẽ có mâu thuẫn 0 ≥ (x + y) + 8 Do đó, ít nhất một trong hai bất đẳng thức là sai Giả sử x² + 3y < (x + 2)², từ đó suy ra x² + 3y = (x + 1)² hay 3y = 2x + 1 Ta nhận được công thức x = 3k + 1, y = 2k + 1 với k nguyên không âm, và y² + 3x = 4k² + 13k + 4 Với k > 5, ta có (2k + 3)² < 4k² + 13k + 4 < (2k + 4)², cho thấy y² + 3x không thể là một số chính phương Chỉ có k = 0 làm cho y² + 3x trở thành một số chính phương, do đó nghiệm duy nhất của hệ là x = y = 1, u = v = 2.
Ví dụ 2.1.37 (Titu Andreescu) Giải phương trình
1 +x 1 + 2x 1 x 2 + 3x 1 x 2 x 3 +ã ã ã+ (n−1)x 1 x 2 ã ã ãx n−1 = x 1 x 2 ã ã ãx n trong đó x 1 , x 2 , , x n là các số nguyên dương phân biệt.
Lời giải Viết phương trình dưới dạng x 1 (x 2 ã ã ãx n −(n−1)x 2 ã ã ãx n−1 − ã ã ã −2x 2 −1) = 1 suy ra x 1 = 1 và x 2 (x 3 ã ã ãx n −(n−1)x 3 ã ã ãx n−1 − ã ã ã −3x 3 −2) = 2.
Bởi vì x 2 6= x 1 , suy ra x 2 = 2 và ta có x 3 (x 4 ã ã ãx n −(n−1)x 4 ã ã ãx n−1 − ã ã ã −4x 4 −3) = 3.
Ta có x 3 6= x 2 và x 3 6= x 1 , vì thế x 3 = 3 Tiếp tục quá trình này (tương đương với một quy nạp toán học hữu hạn), ta có được x1 = 1, x2 = 2, , x n−1 = n−1.
Cuối cùng, ta có (n−1) (x n −(n−1)) = n−1, vì thế x n = n.
Nhận xét Thay vào phương trình ta được đẳng thức
Giải phương trình 7x + x^4 + 47 = y^2 trên tập số nguyên dương, ta thấy nếu x là số lẻ thì 7x ≡ -1 (mod 4) và x^4 ≡ 1 (mod 4) Từ đó, ta có 7x + x^4 + 47 ≡ 3 (mod 4) Do vậy, không tồn tại số chính phương y^2 nào thỏa mãn phương trình trong trường hợp này.
Giả sử x chẵn x = 2t, với t là một số nguyên dương Với t ≥ 4, ta có
Bất đẳng thức (7t)² < 7²t + (2t)⁴ + 47 < (7t + 1)² cho thấy rằng bất đẳng thức bên trái là rõ ràng, trong khi bất đẳng thức bên phải tương đương với 8t⁴ + 23 < 7t Điều này có thể được kiểm chứng bằng phương pháp quy nạp toán học với t ≥ 4 Kết quả cho thấy không tồn tại số y² nào thỏa mãn phương trình này.
Vì thế ta chỉ còn phải xét t ∈ {1,2,3} Ta thấy chỉ có t = 2 thỏa mãn; khi đó x = 4, y = 52 là nghiệm duy nhất của phương trình.
Để chứng minh M > N, ta có thể viết lại hai phương trình ban đầu dưới dạng x^2 + t^3 = y^2 + z^3 và x^2 + t^3 = y^2 + z^3 + 1 Sau đó, ta kí hiệu n_k là số nghiệm nguyên của phương trình u^2 + v^3 = k với 0 ≤ u, v ≤ 10^6 Rõ ràng là n_k = 0 với mọi k lớn hơn l = 10^6^2 + 10^6^3, và ta có thể dựa vào nhận xét này để so sánh số nghiệm nguyên của hai phương trình ban đầu.
M = n 2 0 +n 2 1 +ã ã ã+n 2 l và N = n 0 n 1 +n 1 n 2 +ã ã ã+n l−1 n l (1) Để chứng minh, ví dụ, xét đẳng thức thứ hai, lưu ý rằng đối với bất kỳ nghiệm nguyên của x 2 +t 3 = y 2 + z 3 + 1 với 0 ≤ x, y, z, t ≤ 10 6 có một số k tương ứng (với 1≤ k ≤l) sao cho x 2 +t 3 = k, y 2 +z 3 = k−1 (2)
Với mỗi số k, các cặp (x, t) và (y, z) có thể được chọn độc lập theo n k và n k−1 Do đó, cho mỗi k từ 1 đến l, ta có nk−1nk nghiệm của phương trình x 2 + t 3 = y 2 + z 3 + 1 với k Từ đó, ta suy ra N = n 0 n 1 + n 1 n 2 + + n l−1 n l Việc chứng minh đẳng thức đầu tiên trong (1) tương tự như phương pháp đã thực hiện.
Dễ dàng để suy ra từ (1) rằng M > N Thật vậy, bằng biến đổi đại số ta thấy rằng
Ví dụ 2.1.40 (a) Chứng minh rằng tồn tại vô số bộ ba nguyên (x, y, z) thỏa mãn phương trình x 3 + 2y 3 + 4z 3 −6xyz = 1 (1)
(b) Xác định tất cả các nghiệm nguyên của (1).
Lời giải: Gọi s là căn bậc ba thực của 2 và ω = e^(2πi/3) Khi đó, phương trình (1) có thể được diễn đạt lại bằng cách phân tích vế bên trái thành x + ys + zs^2 + x + ysω + zs^2ω^2 + x + ysω^2 + zs^2ω = 1.
Bộ ba (x, y, z) = (1, 1, 1) là một nghiệm của phương trình (1) Do đó, bộ ba (x_n, y_n, z_n) được xác định bởi x_n + y_n s + z_n s^2 = x_1 + y_1 s + z_1 s^2 n cũng là một nghiệm của (1) cho mọi n ∈ Z, và tất cả các bộ ba số này đều phân biệt.
Chỉ có các nghiệm dưới dạng bộ ba (x_n, y_n, z_n) hoặc (-x_n, -y_n, -z_n) là hợp lệ Cụ thể, nếu (x, y, z) là một nghiệm của phương trình (1) với điều kiện x + ys + zs^2 > 0, thì nghiệm đó sẽ là (x_n, y_n, z_n), trong đó n là số nguyên duy nhất.
1 +s+ s 2 n ≤ x+ys+ zs 2 < 1 +s+s 2 n+1 Xây dựng nghiệm mới (u, v, w) bởi quan hệ u+vs+ ws 2 = x+ys+zs 2 1 +s+s 2 −n , do đó 1 ≤ u+ vs+ws 2 < 1 +s+s 2
= 1 2 h (u−vs) 2 + vs−ws 2 2 + ws 2 −u 2 i, và do đó |u−vs|, vs−ws 2 , ws 2 −u là các số nhỏ hơn hoặc bằng √
2 > 0, vì thế u+vs+ws 2 ≥ 1 +s+s 2 , có mâu thuẫn Tương tự, giả sử w ≤ −1, khi đó suy ra u+ vs+ws 2 ≤ − 1 +s+s 2 , có mâu thuẫn Vì thế w = 0, ta thu được các bất đẳng thức
2. Điều kiện thứ hai và thứ ba kéo theo −1 ≤ u, v ≤ 1, khi đó, ta chỉ thu được nghiệm là (u, v, w) = (1,0,0) hoặc (−1,1,0) Nghiệm thứ hai không thỏa mãn điều kiện thứ nhất, vì vậy(u, v, w) = (1,0,0)và (x, y, z) = (x n , y n , z n ),như điều ta muốn.
Một số dạng cổ điển của phương trình nghiệm nguyên
Dạng bậc nhất hai ẩn
Định lý 2.2.1 (xem [4]) Cho a, b, c ∈ Z sao cho ab 6= 0 Xét phương trình nghiệm nguyên bậc nhất ax+ by = c (2.4) với ẩn là x, y Khi đó ta có
(i) Phương trình (2.4) có nghiệm khi và chỉ khi d = gcd(a, b) là ước của c.
(ii) Nếu (x, y) = (x 0 , y 0 ) là một nghiệm riêng của (2.4), thì mọi nghiệm nguyên của (2.4) có dạng x = x 0 + b dt, y = y 0 − a dt với t ∈ Z (2.5)
Để chứng minh, nếu d - c, phương trình sẽ vô nghiệm Nếu d | c, ta chia cả hai vế của phương trình cho d, dẫn đến phương trình dạng adx + dby = dc với gcd(ad, bd) = 1 Do đó, chỉ cần xét phương trình nghiệm nguyên ax + by = c với gcd(a, b) = 1 Chúng ta cần tìm một biểu diễn của 1 dưới dạng tổ hợp tuyến tính của a và b, sử dụng thuật toán Euclide Giả sử a = bq + r với q, r ∈ Z và 0 ≤ r < |b|, ta có gcd(a, b) = gcd(b, r) Để hệ thống hóa, đặt a = r-1 và b = r0 (giả sử a ≥ b) và xét dãy các phép chia và dư liên tiếp.
Quá trình này sẽ kết thúc sau một số bước hữu hạn, bởi vì phần dư giảm dần theo thứ tự r −1 > r0 > r1 > r2 và không âm Điều này có nghĩa là tồn tại một số r n thỏa mãn điều kiện r n | r n−1 và r n+1 = 0.
Từ định nghĩa, ta có n = gcd(r n−1, r n) = gcd(r n−2, r n−1) = = gcd(r −1, r 0) gcd(a, b) Bằng cách tính toán lùi lại, r n có thể được biểu diễn dưới dạng tổ hợp hệ số nguyên của a và b, tức là rn = xna + ynb Do đó, một nghiệm riêng của phương trình (*) sẽ là (cx n, cy n).
(ii) Ta có ax+by = a x 0 + b dt
+b y 0 − a dt = ax 0 +by 0 = c Ngược lại nếu (x, y) là một nghiệm của phương trình thì ta có a(x−x 0 ) =−b(y−y 0 ).
Do đó a d (x−x0) =− b d (y −y0) với lưu ý gcd( a d , d b ) = 1 Suy ra tồn tại t ∈ Z để x−x 0 = d b t, thay vào ta được y −y 0 = − a d t.
Bộ ba Pitago
Một trong những phương trình nghiệm nguyên đáng nhớ nhất là phương trình Pitago. x 2 + y 2 = z 2 (2.6)
Phương trình được nghiên cứu kĩ bởi Pitago liên quan đến các tam giác vuông có độ dài các cạnh bên là các số nguyên.
Nếu bộ ba số nguyên (x₀, y₀, z₀) thỏa mãn phương trình 2.6, thì tất cả các bộ ba có dạng (kx₀, ky₀, kz₀) với k ∈ Z cũng sẽ thỏa mãn phương trình này Do đó, chúng ta chỉ cần tìm các nghiệm (x, y, z) của phương trình 2.6 với điều kiện gcd(x, y, z) = 1, tương đương với việc x, y, z là các số nguyên tố cùng nhau.
Một nghiệm nguyên thủy (x₀, y₀, z₀) của phương trình 2.6, với điều kiện x₀, y₀, z₀ là các số nguyên tố cùng nhau, chỉ có một trong x₀ và y₀ là số chẵn Theo định lý 2.2.2, bất kỳ nghiệm nguyên thủy (x, y, z) nào trên tập các số nguyên dương của phương trình 2.6 với y chẵn đều có dạng x = m² - n², y = 2mn, z = m² + n², trong đó m và n là các số nguyên dương nguyên tố cùng nhau, với điều kiện m > n và m + n là số lẻ.
Chứng minh rằng hai số nguyên x và y không thể cùng là số lẻ, vì nếu vậy thì z^2 = x^2 + y^2 ≡ 2 (mod 4), điều này mâu thuẫn với quy tắc rằng z^2 chỉ có thể là 0 hoặc 1 theo mô-đun 4 Do đó, chỉ có một trong hai số x hoặc y là lẻ Đồng nhất thức m^2 - n^2 + (2mn)^2 = m^2 + n^2 cho thấy bộ ba được đưa ra là nghiệm cho phương trình, trong đó y là số chẵn Vì x phải là số lẻ, ta có thể giả sử mà không mất tính tổng quát rằng m là số lẻ và n là số chẵn.
Hơn nữa, nếu gcd m 2 −n 2 ,2mn, m 2 +n 2 = d ≥ 2, thì d là ước của
Vì (m, n) = 1, suy ra d = 2, dẫn đến m² + n² là chẵn, mâu thuẫn với m lẻ và n chẵn Do đó, d = 1, chứng tỏ nghiệm (2.7) là nguyên thủy Ngược lại, giả sử (x, y, z) là một nghiệm nguyên thủy của (2.6) với y = 2a Khi đó, x và z là số lẻ, dẫn đến z + x và z - x là số chẵn Đặt z + x = 2b và z - x = 2c, giả sử b và c nguyên tố cùng nhau Từ đó, 4a² = y² = z² - x² = (z + x)(z - x) = 4bc, suy ra a² = bc Vì (b, c) = 1, nên b = m² và c = n² với m và n là số nguyên dương Điều này cũng cho thấy m + n là số lẻ, từ đó x = b - c = m² - n², y = 2mn, z = b + c = m² + n².
Một bộ ba (x, y, z) có dạng (2.7) được gọi là nguyên thủy Để tìm tất cả các nghiệm nguyên thủy cho phương trình (2.6), ta gán các giá trị 2, 3, 4, cho m Đối với mỗi giá trị của m, ta chọn các số nguyên n sao cho gcd(m, n) = 1 và n < m.
Ước số của một vài số có dạng đặc biệt
Ước số của a 2 + b 2
Định lý 2.3.1 (xem [4]) Mỗi ước số nguyên tố lẻ của a 2 + 1 có dạng 4k+ 1.
Để chứng minh, xét p là số nguyên tố có dạng 4m + 1 hoặc 4m + 3 Giả sử p chia hết cho (a² + 1) với p = 4m + 3, ta có a² ≡ -1 (mod p) Điều này dẫn đến a^(p-1) = a^(4m+3) = a^(4m+2) ≡ -1 (mod p), mâu thuẫn với định lý Theo Định lý 2.3.2, nếu a và b là hai số nguyên tố cùng nhau và p là số nguyên tố lẻ chia hết cho a² + b², thì p phải có dạng p ≡ 1 (mod 4) Ngược lại, nếu p ≡ 3 (mod 4) là ước số nguyên tố của a² + b², thì p sẽ chia hết cho cả a và b.
Giả sử p = 4m + 3 là một số nguyên tố, với a^2 + b^2 ≡ 0 (mod p) Từ đó, ta có a^(p−1) ≡ −b^(p−1) do gcd(a, b) = 1 Khi áp dụng Định lý 2.3.1, ta nhận được a^(p−1) + b^(p−1) ≡ (1 + 1) (mod p), dẫn đến 1 + 1 ≡ 0 (mod p), điều này mâu thuẫn với tính chất của p là số lẻ.
Nếu gcd(a, p) = 1, thì cũng có gcd(b, p) = 1 do a² + b² chia hết cho p và gcd(p, x) = 1 với mọi x ∈ Z Theo Định lý 2.3.1, ta có a^(p−1) ≡ 1 (mod p) và b^(p−1) ≡ 1 (mod p) Hơn nữa, nếu p = 4m + 3, từ việc p | (a² + b²), ta suy ra a² ≡ −b² (mod p), dẫn đến a²^(p−1).
(mod p), tức là, a p−1 ≡ −b p−1 (mod p) Điều này kết hợp với thực tế (*), ta suy ra được 1≡ −1 (mod p), đây là điều mâu thuẫn Vậyp|a vàp|b.
Nhận xét Rõ ràng là phát biểu (ii) của Định lý 2.3.2 suy ra Định lý 2.3.1 và phát biểu (i) của Định lý 2.3.1.
Giả sử có (ii), chọn b = 1, ta thấy nếu p ≡ 3 (mod 4) và p | (a² + 1), thì từ (ii) suy ra p | a và p | 1, điều này mâu thuẫn Do đó, ước nguyên tố lẻ của a² + 1 phải có dạng p ≡ 1 (mod 4) Hơn nữa, nếu gcd(a, b) = 1 và p là ước nguyên tố lẻ của a² + b², thì không xảy ra trường hợp “p - a và p - b”; từ đó suy ra p không thể ≡ 3 (mod 4), tức là p ≡ 1 (mod 4) Định lý 2.3.3 (Bổ đề Thue) khẳng định rằng với n là số nguyên dương và a ∈ Z sao cho gcd(a, n) = 1, tồn tại các số x, y ∈ Z thỏa mãn điều kiện nhất định.
0< |x|,|y| ≤√ n và thỏa mãn ax ≡y (mod n).
Chứng minh Kết quả của định lý là đúng khi n = 1 (vì lúc đó lấy 0 < x = y = 1 ≤√
Để chứng minh, chúng ta bắt đầu với điều kiện 1 ≡ 0 (mod 1) ≡ a (mod 1) cho mọi a ∈ Z Giả sử n > 1, ta có √ n < n Xét trường hợp n không phải là số chính phương, ta có b√ nc < √ n < b√ nc + 1 ≤ n.
Vì n < (b√ nc+ 1) 2 nên áp dụng nguyên lý chuồng chim bồ câu ta suy ra tồn tại hai cặp (x 1 , y 1 ) 6= (x 2 , y 2 ) với 1≤ x 1 , x 2 , y 1 , y 2 ≤ b√ nc+ 1 sao cho ax 1 −y 1 ≡ ax 2 −y 2 (mod n) hay a(x 1 −x 2 ) ≡ y 1 −y 2 (mod n).
Giả sử x₁ ≠ x₂, ta có y₁ ≠ y₂ vì nếu y₁ = y₂ thì a(x₁ − x₂) ≡ 0 (mod n) Kết hợp với giả thiết (a, n) = 1, suy ra x₁ − x₂ chia hết cho n, điều này mâu thuẫn với 1 ≤ x₁, x₂ ≤ b√n + 1 ≤ n Đặt x = x₁ − x₂ và y = y₁ − y₂, ta có 0 < |x|, |y| ≤ b√n < √n và thỏa mãn ax ≡ y (mod n) Nếu x₁ = x₂, thì 0 ≡ y₁ − y₂ (mod n), dẫn đến y₁ = y₂, tạo ra mâu thuẫn Do đó, khi n > 1 không phải là số chính phương, tồn tại x, y thỏa mãn điều kiện trên.
0< |x|,|y| < √ n và ax ≡ y (mod n). Còn lại ta xét trường hợp n là số chính phương, chẳng hạn n = d 2 với d > 1 (vì n >1) Khi đó b√ nc= d = √ n < b√ nc+ 1 = d+ 1 Đặt
Theo định lý, ta có (d+1)² = d² + 2d + 1 > d² = n, từ đó suy ra tồn tại hai cặp (x₁, y₁) khác (x₂, y₂) với 1 ≤ x₁, x₂, y₁, y₂ ≤ d + 1 sao cho ax₁ - y₁ ≡ ax₂ - y₂ (mod n), hay a(x₁ - x₂) ≡ y₁ - y₂ (mod n) Đặt x = x₁ - x₂ và y = y₁ - y₂ Nếu x = 0, tức là x₁ = x₂, thì y₁ - y₂ chia hết cho n, nhưng với 1 ≤ y₁, y₂ ≤ d + 1, ta có 0 ≤ |y₁ - y₂| ≤ d < d² = n, dẫn đến y₁ = y₂ và (x₁, y₁) = (x₂, y₂), điều này tạo ra mâu thuẫn Do đó, x ≠ 0 và y ≠ 0 Nếu y = 0, thì ax ≡ 0 (mod n) và x chia hết cho n, nhưng với 0 ≤ |x| ≤ d < d² = n, ta lại suy ra x = 0, tạo ra mâu thuẫn một lần nữa.
Trong trường hợpn = d 2 > 1, ta thấy tồn tại x, y thỏa mãn 0< |x|,|y| ≤
Hệ quả 2.3.4 Cho n là một số nguyên dương, và cho a ∈ Z sao cho gcd(a, n) = 1 Khi đó
(i) Nếu n không là số chính phương thì tồn tại các số x, y ∈ Z sao cho
0< |x|,|y| < √ n và thỏa mãn ax ≡y (mod n).
(ii) Nếu n là số chính phương n = d 2 (vớid ∈ Z + ) thì tồn tại các số x, y ∈ Z sao cho 0< |x|,|y| ≤ √ n= d và thỏa mãn ax ≡y (mod n).
Trong nghiên cứu về một số phương trình nghiệm nguyên, nếu một vế của phương trình có dạng x² + a² với gcd(x, a) = 1, và vế còn lại có một ước số dạng 4k + 3, thì phương trình này sẽ không có nghiệm trong tập số nguyên.
Để chứng minh rằng phương trình \(x^n + 2^{n-1} = y^2\) không có nghiệm trên tập số nguyên dương lẻ với \(n\) là số nguyên lẻ, ta có thể viết lại phương trình dưới dạng \(x^n + 2^n = y^2 + 2^{n-2} \cdot 2^{n-1}\) Điều này dẫn đến biểu thức \(x^n + 2^2 = y^2 + 2^{n-1}\).
Vế trái của phương trình chứa một ước số nguyên tố có dạng 4k + 3 Nếu x thuộc dạng này, thì ít nhất một ước số nguyên tố x^n + 2^n cũng sẽ có dạng 4k + 3, vì n lẻ lớn hơn 1 dẫn đến 2^n ≡ 0 (mod 4) và (4k + 3)^n ≡ 3 (mod 4) Do đó, vế trái sẽ có dạng 4k + 3 Ngược lại, nếu x có dạng 4k + 1, thì x + 2 là ước số của x^n + 2^n, và x + 2 sẽ có dạng 4k + 3.
Trong mỗi trường hợp, với y lẻ và n lẻ lớn hơn 3, ta có gcd(y, 2n−1^2) = 1, và y^2 + 2n−1^2 có một ước số nguyên tố dạng 4k + 3 Đồng thời, vì gcd(y, 2n−1^2) = 1, theo Định lý 2.3.2 (i), ước nguyên tố lẻ của y^2 + (2n−1^2)^2 phải có dạng p = 4k + 1, dẫn đến một mâu thuẫn.
Ví dụ 2.3.6 (Ion Cucurezeanu) Chứng minh rằng phương trình x 3 −x 2 + 8 = y 2 vô nghiệm trên tập số nguyên.
Lời giải Với x lẻ, ta viết phương trình dưới dạng
Rõ ràng, nếu x là số lẻ và gcd(x, y) = 1, thì trường hợp x = 4k + 1 dẫn đến x + 2 = 4k + 3, tạo ra một ước nguyên tố dạng 4k + 3 Điều này mâu thuẫn với Định lý 2.3.2 (i) về số x² + y² Tương tự, nếu x = 4k + 3, thì x² - 2x + 4 có dạng 4m + 3, từ đó suy ra x² + y² cũng có ước nguyên tố dạng 4m + 3, lại một lần nữa vi phạm Định lý 2.3.2 (i).
Với x = 2u, phương trình trở thành 4(2u 3 −u 2 + 2) = y 2 Suy ra y chẵn, giả sử y = 2t Thay vào ta được phương trình 2u 3 −u 2 + 2 = t 2
Nếu u là số lẻ, vế trái sẽ đồng dư với 3 (mod 4), do đó không thể là số chính phương Ngược lại, nếu u là số chẵn, vế trái đồng dư với 2 (mod 4) và cũng không thể là số chính phương.
Vậy trong mọi trường hợp phương trình đều vô nghiệm.
Ví dụ 2.3.7 Giải phương trình nghiệm nguyên x 5 −4 = y 2
Nếu x là số chẵn, thì y cũng chẵn; giả sử y = 2n, ta có phương trình 2^5t^5 - 4 = 4n^2, dẫn đến 8t^5 - 1 = n^2 Lấy mô-đun 8 hai vế, ta suy ra n^2 ≡ 7 (mod 8), điều này không thể xảy ra Do đó, x phải là số lẻ và y cũng lẻ Ta viết lại phương trình là x^5 = y^2 + 2^2 Vì x là ước của y^2 + 2^2, nên x không thể có dạng 4k + 3 (theo Định lý 2.3.2(i)) Do đó, x phải có dạng 4k + 1 và phương trình có thể được viết lại là x^5 + 2^5 = y^2 + 6^2.
Nếu 3 - y chúng ta lại đạt được một mâu thuẫn (vì x+ 2 = 4k + 3 là một ước của y 2 + 6 2 và gcd(y,6) = 1)).
Nếu y = 3y 1 (rõ ràng là y 1 lẻ), thì x 5 + 2 5 = 3 2 y 1 2 + 4 Ta thấy nếu d= gcd x+ 2, x x+2 5 +2 5 , thì d|5 Thật vậy, từ đẳng thức a 5 +b 5 = (a+b) 5 −
Đối với biểu thức 5ab(a+b)(a+b)² - ab, ta suy ra a⁵ + b⁵ = (a+b)⁴ - 5ab(a+b)² + 5a²b² Với a = x = 4k + 1 lẻ và b = 2, ta có d|x + 2 = 4k + 3 và d|x⁵ + 2⁵ Do đó, d là số lẻ và d|5a²b² = 5(2x)² Tuy nhiên, gcd(x + 2, 2x) = 1, vì nếu t|x + 2 và t|2x thì t|4, nhưng x + 2 lẻ nên t cũng lẻ, suy ra t = 1 Do đó, gcd(d, (2x)²) = 1 Kết hợp với d|5(2x)², ta suy ra d|5.
Ước số của a 2 + 2b 2
Định lý 2.3.9 (xem [4]) Một số nguyên tốplẻ có thể được viết làp = a 2 +2b 2 vớiavàb là hai số nguyên khi và chỉ khip ≡1 (mod 8)hoặcp ≡ 3 (mod 8).
Chứng minh Nếu p = a 2 + 2b 2 thì a 2 ≡ −2b 2 (mod p) Do 0 < |b| < p nên (p, b) = 1, suy ra tồn tại số nguyên b 0 sao cho bb 0 ≡ 1 (mod p) Do đó (ab 0 ) 2 ≡ −2 (mod p) Tức là kí hiệu Legendre
= 1 Từ đó suy ra rằng
− 2 p = 1 khi và chỉ khi p−1 2 + p 2 8 −1 = 2k, với số nguyênk nào đó Điều này tương đương với (p−1)(p+5) 8 = 2k Dẫn đến p ≡ 1 (mod 8) hoặc p ≡ 3 (mod 8).
Ngược lại, giả sử p ≡ 1 (mod 8)hoặc p ≡ 3 (mod 8) Thì
Có tồn tại số nguyên a sao cho a² ≡ -2 (mod p) và gcd(a, p) = 1 Theo hệ quả của Bổ đề Thue, tồn tại các số nguyên x, y với 0 < x, y < √p sao cho p | ax - y Do đó, ta có p(a²x² - y²) = (ax - y)(ax + y), từ đó suy ra p | (a² + 2)x² - (2x² + y²) Vì p | a² + 2, nên tồn tại số nguyên k sao cho 2x² + y² = pk, với 0 < 2x² + y² < 3p, dẫn đến k thuộc {1, 2}.
Với k = 1, ta có p = 2x 2 + y 2 điều phải chứng minh Với k = 2, ta có 2p = 2x 2 +y 2 ; vì thế 2|y Khi đó ta có thể viết y = 2y, vậy nênp = x 2 + 2z 2 , đó là điều phải chứng minh.
Chú ý 2.3.10 (i) Kết quả trong định lý trên cho thấy rằng mỗi số nguyên tố p đồng dư với 1 hoặc 3 mô-đun 8 là không bất khả quy trong vành
−2 | a, b ∈ Z} Tức là p = a 2 + 2b 2 có thể viết được thành tích của hai phần tử u = a+ b√
−2 trong đó u, v khác 0, và u, v không khả nghịch trong Z[√
Nếu p là số nguyên tố có dạng 8k−1 hoặc 8k−3 và p chia hết cho a² + 2b², thì p cũng chia hết cho a và b Cụ thể, nếu p chia hết cho a, thì p cũng chia hết cho b Chúng ta cần tìm một số nguyên b₀ sao cho bb₀ ≡ 1 (mod p) Từ a² ≡ −2b² (mod p), ta suy ra (ab₀)² ≡ −2 (mod p) Vì gcd(ab₀, p) = 1, điều này cho thấy mối quan hệ giữa a, b và p.
= 1, từ đó ta được p ≡ 1 (mod 8) hoặc p ≡ 3 (mod 8), đó là mâu thuẫn.
Ta có thể sử dụng các kết quả trên trong nghiên cứu một vài phương trình nghiệm nguyên như sau:
Nếu một vế của một phương trình có thể được viết là x 2 + 2y 2 với gcd(x, y) = 1, trong khi vế còn lại có một ước số nguyên tố đồng dư với
−1 hoặc −3 mô-đun 8, thì phương trình không có nghiệm nguyên.
Ví dụ 2.3.11 (Ion Cucurezeanu) Chứng minh rằng x 3 −3 = 2y 2 không có nghiệm nguyên.
Lời giải Viết phương trình ở dạng tương đương
Cần lưu ý rằng phần bên phải của cả hai phương trình không chia hết cho 8 Điều này có thể được kiểm tra trực tiếp bằng cách thay y = 2t và y = 2t + 1 vào y^2 + 1 và y^2 + 2; kết quả cho thấy y^2 + 1 và y^2 + 2 đều không chia hết cho 4.
Bây giờ ta kiểm tra vế trái Bởi vì x là số lẻ, nên ta chỉ cần kiểm tra các trường hợp x = 8k ±1 và x = 8k ±3.
Nếu x = 8k + 1, phía bên trái của (i) chia hết cho 8, mâu thuẫn Điều tương tự cũng đúng với (ii) khi x = 8k−1.
Nếu x = 8k ± 3, thì x² − x + 1 có dạng 8m − 1 hoặc 8m − 3, dẫn đến việc x² − x + 1 phải có một ước số nguyên tố p ở dạng 8k − 1 hoặc 8k − 3 Theo Chú ý 2.3.10(ii), vì p là ước của y² + 2 = y² + 2.1, nên ta có p|y và p|1, điều này là không thể xảy ra.
Ước số của a 2 − 2b 2
Định lý 2.3.12 (xem [4]) Một số nguyên tố plẻ có thể được viết làp = a 2 −2b 2 đối với một số số nguyênavàbkhi và chỉ khip≡ 1 (mod 8) hoặc p ≡ −1(mod 8).
Chứng minh Thật vậy, nếu p = a 2 − 2b 2 , thì a 2 ≡ 2b 2 (mod p) Đặt b 0 là số nguyên sao cho bb 0 ≡ 1 (mod 8), vậy (ab 0 ) 2 ≡ 2 (mod p), ta được 2 p
= 1 khi và chỉ khi p≡ 1 (mod 8), hoặc p≡ −1 (mod 8).
Nếu p ≡ 1 (mod 8) hoặc p ≡ −1 (mod 8), theo Bổ đề Thue, có thể tìm hai số nguyên dương x và y với 0 < x, y < √ p sao cho p chia hết cho a²x² − y², với a là số nguyên thỏa mãn a² ≡ 2 (mod p) Do đó, p cũng chia hết cho (a² − 2)x² + 2x² − y², dẫn đến p chia hết cho 2x² − y² Từ đó, ta có 0 < 2x² − y² < 2p, suy ra p = 2x² − y².
Chú ý (i) Nếu p là số nguyên tố có dạng 8k −3 hoặc 8k+ 3 và p|a 2 −2b 2 thì p|a và p|b.
Thật vậy, nếu p - a, thì p - b và ta cần tìm số nguyên b 0 sao cho bb 0 ≡
1 (mod p) Từ a 2 ≡ 2b 2 (mod p), ta suy ra (ab 0 ) 2 ≡ 2 (mod p) Bởi vì gcd(ab 0 , p) = 1, ta có
= 1, từ đó ta được p ≡ ±1 (mod 8), đó là mâu thuẫn.
(ii) Từ Định lý 2.3.12, ta thấy rõ ràng là nếu p là số nguyên tố có dạng p≡ ±1 (mod 8), thì phương trình Pell x 2 −2y 2 = p là có nghiệm.
Theo Định lý 2.3.12, nếu một vế của phương trình được biểu diễn dưới dạng x² - 2y² với gcd(x, y) = 1, và vế còn lại có một ước số nguyên tố đồng dư với ±3 (mod 8), thì phương trình này sẽ không có nghiệm nguyên.
Ví dụ 2.3.13 Xét phương trình 8xy−(x+y) = z 2 Chứng minh rằng (i) Phương trình không có nghiệm nguyên dương.
(ii) Phương trình có vô số nghiệm trong tập số nguyên âm.
Lời giải (i) Viết phương trình dưới dạng
Phương trình (8x−1)(8y−1) = 8z^2 + 1 có nghiệm nguyên dương, với điều kiện 8x − 1 ≥ 7 Do đó, 8x − 1 có thể có một ước số nguyên tố dạng 8m−1 hoặc 8m−3 Tuy nhiên, theo Định lý 2.3.9, 8x−1 không thể là ước của 2(2z)^2 + 1, dẫn đến mâu thuẫn trong giả định ban đầu.
(ii) Các bộ ba số (x, y, z) trong đó x = −1, y = −9n 2 −2n, z = −9n−1,với n là số nguyên dương tùy ý, thỏa mãn là các nghiệm nguyên âm của phương trình.
Luận văn trình bày cách giải phương trình nghiệm nguyên và nghiên cứu một vài dạng ước số đặc biệt Cụ thể:
2) Cách dùng bất đẳng thức.
5) Cách quy nạp toán học.
8) Ước của cách dạng đặc biệt a 2 +b 2 , a 2 + 2b 2 , a 2 −2b 2
Đề tài luận văn này được thực hiện nhằm thỏa mãn nhu cầu của người học trong việc mở rộng và nâng cao kiến thức, đồng thời bổ sung những thông tin bổ ích ngoài sách giáo khoa.
Dựa trên các tài liệu tham khảo, bài viết này trình bày một số phương pháp giải phương trình có nghiệm nguyên Tác giả hy vọng trong tương lai sẽ có cơ hội nghiên cứu sâu hơn về chủ đề này.