Định lý thặng dư Trung Hoa và bài tập ứng dụng liên quan - Trần Minh Hiền

20. ĐỊNH LÝ THẶNG DƯ TRUNG HOA

20.1. GIỚI THIỆU

Chúng ta xét bài toán mở đầu sau. Giải hệ phương trình đồng dư







x≡3(mod 5) (1) x≡7(mod 8) (2) x≡5(mod 7) (3).

Giải. Từ đồng dư (1) ta có

x=5q₁+3. (4) Thay kết quả (4) trên vào đồng dư (2) ta được

5q₁+3≡7(mod 8)⇒5q₁≡4(mod 8).

Do5.5=25≡1(mod 8)và(5,8) =1nên

5.5q₁≡5.4(mod 8)⇒q₁ ≡4(mod 8)⇒q₁ =8q₂+4.

Từ đó (4) cho tax=5(8q2+4) +3=40q₂+23 (5). Thay (5) vào (3) ta được 40q₂+23≡5(mod 7)⇒40q₂≡ −18(mod 7)⇒5q₂≡3(mod 7).

Vì3.5=15≡1(mod 7)và(3,7) =1nên

3.5q₂≡3.3(mod 7)⇒15q₂≡9(mod 7)⇒q₂≡2(mod 7)⇒q₂=7q₃+2.

Lại thay kết quả trên vào (5) ta được

x=40(7q₃+2) +23=280q₃+103⇒x≡103(mod 280).

Để ý280=5×8×7. Tức hệ phương trình trên có nghiệm x≡103(mod 5×8×7).

20.2. ĐỊNH LÝ

Định lý 20.2.1. Cho ksố nguyên dương đôi một nguyên tố cùng nhaum₁,m₂, . . . ,m_k, và a₁,a₂, . . . ,a_k làksố nguyên tùy ý. Khi đó hệ đồng dư tuyến tính















x≡a₁(mod m₁) x≡a₂(mod m₂) . . . .

x≡a_k(mod m_k) có nghiệm duy nhất modm₁m₂. . .m_k.

Chứng minh. 1. Chứng minh sự duy nhất. Giả sử ta có hai nghiệm làx,y. Dẫn đến x≡y(≡a₁(mod m₁)), x≡y(≡a₂(mod m₂)), . . . ,x≡y(≡a_k(mod m_k)).

Vìm₁,m₂, . . . ,m_n nguyên tố cùng nhau đôi một nên

x≡y(mod m₁m₂. . .m_k).

Tứcyvàxcùng thuộc một lớp thặng dư theo modm₁m₂. . .m_k

2. Chứng minh sự tồn tại. Ta muốn viết các nghiệm như là một tổ hợp tuyến tính của cáca₁,a₂, . . . ,a_k x=A₁a₁+A₂a₂+···+A_ka_k.

Với cácA_i phải tìm thỏa mãn

A_j ≡0(mod m_i),∀j6=i và A_i≡1(mod m_i).

Đặt

N₁=m₂m₃. . .m_k N₂=m₁m₃. . .m_k . . . .

N_i=m₁m₂. . .m_i−1m_i+1. . .m_k.

Khi đó(Ni,m_i) =1vì(mi,m₁) = (mi,m₂) =. . .= (mi,m_i−1) = (mi,m_i+1) =. . .= (mi,m_k) =1 vàm_j|N_i,∀j6=i. Vì(N_i,m_i) =1nên tồn tạiN_i⁻¹, tức là

N_i.N_i⁻¹ ≡1(mod m_i).

Đến đây đặt

A_i=N_i.N_i⁻¹ thì

A_i≡1(mod m_i) và A_i≡0(mod m_j),∀j6=i(vìN_i≡0(mod m_j)⇒A_i≡0(mod m_j)).

Khi đó

x=A₁a₁+A₂a₂+···+A_ka_k =N₁.N₁⁻¹a₁+N₂N₂⁻¹a₂+···+N_kN_k⁻¹a_k sẽ thỏa mãn

x≡N_iN_i⁻¹a_i≡a_i(mod m_i) (vì tất cả các thừa số còn lại đều đồng dư 0 dom_i|N_j,∀j6=i).

20.3. ÁP DỤNG CƠ BẢN

Ví dụ 20.3.1. Giải hệ phương trình đồng dư







x≡2(mod 3) x≡3(mod 5) x≡5(mod 7).

Giải. Ta có

N₁ =5.7=35≡2(mod 3)⇒N₁⁻¹ =2, N₂ =3.7=21≡1(mod 5)⇒N₂⁻¹ =1, N₃ =3.5=15≡1(mod 7)⇒N₃⁻¹ =1.

Từ đó ta có

x=2.35.2+1.21.3+1.15.5=278≡68(mod 105) là nghiệm của hệ phương trình.

Ví dụ 20.3.2. Giải hệ phương trình















x≡6(mod 11) x≡13(mod 16) x≡9(mod 21) x≡19(mod 25).

Chứng minh. Ta có

N₁=16.21.25=8400≡7(mod 11)⇒N₁⁻¹=8, N₂=11.21.25=5775≡15(mod 16)⇒N₂⁻¹=15,

N₃=11.16.25=4400≡11(mod 21)⇒N₃⁻¹=2, N₄=11.16.21=3696≡21(mod 25)⇒N₄⁻¹=6.

Khi đó nghiệm của hệ phương trình là

x=6.8400.8+13.5775.15+9.4400.2+19.3696.6=2029869≡51669(mod 11.16.21.25=92400).

Ví dụ 20.3.3. Tìm tất cả các nghiệm của phương trìnhx²≡1(mod 144).

Chứng minh. Vì 144=16.9, và (16,9) =1. Do đó theo định lý thặng dư Trung Hoa thì nghiệm của bài toán chính là nghiệm của hệ phương trình

(x≡1(mod 16) x≡1(mod 9).

Vìx² ≡1(mod 16)có 4 nghiệmx≡ ±1,±7(mod 16)vàx² ≡1(mod 9)có hai nghiệm x≡ ±1(mod 9). Do đó ta có tất cả 8 trường hợp xảy ra

x≡1(mod 16) và x≡1(mod 9) (1), x≡1(mod 16) và x≡ −1(mod 9) (2), x≡ −1(mod 16) và x≡1(mod 9) (3), x≡ −1(mod 16) và x≡ −1(mod 9) (4),

x≡7(mod 16) và x≡1(mod 9) (5), x≡7(mod 16) và x≡ −1(mod 9) (6), x≡ −7(mod 16) và x≡1(mod 9) (7), x≡ −7(mod 16) và x≡ −1(mod 9) (8).

Cả tám hệ phương trình trên đều ứng vớik=2và

N₁ =9≡9(mod 16)⇒N₁⁻¹=9⇒N₁.N₁⁻¹ =81, N₂ =16≡7(mod 9)⇒N₂⁻¹=4⇒N₂.N₂⁻¹ =64.

Do đó phương trình ban đầu có tất cả 8 nghiệm sau

(1): x≡1.81+1.64=145 ≡1(mod 144), (2): x≡1.81+ (−1).64=17 ≡17(mod 144), (3): x≡(−1).81+1.64=−17 ≡ −17(mod 144), (4): x≡(−1).81+ (−1).64=−145 ≡ −1(mod 144), (5): x≡7.81+1.64=631 ≡55(mod 144), (6): x≡7.81+ (−1).64=503 ≡71(mod 144), (7): x≡(−7).81+1.64=−503 ≡ −71(mod 144), (8): x≡(−7).81+ (−1).64=−603 ≡ −55(mod 144).

20.4. CHỨNG MINH SỰ TỒN TẠI MỘT MỆNH ĐỀ TOÁN HỌC

Bài 20.4.1. Choa,blà hai số nguyên dương lớn hơn 1,(a,b) =1. Chứng minh rằng tồn tạik∈Zsao cho

A= (ab−1)ⁿ.k+1 là hợp số với mọinnguyên dương.

Phân tích và giải. 1. Để chứng minhAlà hợp số, thì cần chứng minhAchia hết cho một số nào đó.

Tự nhiên nhất trong bài này là chứng minh luônA chia hết choahoặc chia hết chob.Xét theo

modathì (

A≡k+1(mod a) vớinchẵn A≡ −k+1(mod a) vớinlẻ.

2. Khi đó cầnA.

..athì cần điều kiện gì củak?ĐểA. ..athì

(k≡ −1(mod a) vớinchẵn k≡1(mod a) vớinlẻ.

3. Hoàn toàn tương tự cho điều kiện củakđể muốnA.

..b??Tương tự đểA. ..bthì (k≡ −1(mod b) vớinchẵn

k≡1(mod b) vớinlẻ. .

4. Từ đây, để đảm bảo Aluôn chia hết cho cả ahoặcb ứng vớin chẵn hoặcn lẻ, thì phải chọnk như thế nào?Theo định lý thặng dự Trung hoa thì hệ

(k≡1(mod a) k≡ −1(mod b) có nghiệm.

5. Kiểm tra lại thông tin củaAứng vớikchọn là nghiệm của hệ trên?Khi đó





 A.

..a vớinlẻ

A.

..b vớinchẵn

Ta có điều phải chứng minh.

Bài 20.4.2. Chứng minh rằng với mọi số nguyên dương ntùy ý, luôn tồn tại nsố nguyên dương liên tiếp gồm toàn hợp số.

Phân tích và giải. 1. Để chứng minh n số nguyên dương liên tiếp gồm toàn hợp số, thì ta phải chứng minh mỗi số trong nsố này phải có một ước nguyên tố. Từ đó cần phải bắt đầu từ đâu?

Gọi p₁ < p₂ < . . . < p_n lànsố nguyên tố tùy ý.

2. Ta muốnnsố dạng:m+1,m+2, . . . ,m+n, mỗi số chia hết cho một thừa số nguyên tố trên? Hãy triển khai chi tiết này?Ta chỉ ra tồn tại sốmmà















m+1≡0(mod p₁) m+2≡0(mod p₂) . . . .

m+n≡0(mod p_n)

⇔















m≡ −1(mod p₁) m≡ −2(mod p₂) . . . .

m≡ −n(mod p_n).

Theo định lý thặng dư Trung Hòa thì hệ trên có nghiệmmlớn tùy ý. Từ đó với mọii=1,2, . . . ,n thì

p_i|m+i.

(tuy nhiên vìp_i|m+inên có thểm+i= p_i, lúc đó thìm+ilại là số nguyên tố. Để đảm bảom+i là hợp số thì ta chọn msao cho m> p_nlà được). Ta chọnm> p_n thìnsố

m+1,m+2, . . . ,m+n đều là hợp số (mỗi sốm+ichia hết cho một ước nguyên tố p_i).

Bài 20.4.3(IMO 1989). Chứng minh rằng với mọi số nguyên dươngntùy ý, luôn tồn tạinsố nguyên dương liên tiếp mà mỗi số không là lũy thừa của một số nguyên dương nào khác.

Phân tích và giải. 1. Nhìn bài toán này, ta nghĩ ngay đến một sự tương tự với bài 20.2. Tuy nhiên đối với bài 20.2 chứng minh mỗi số đó là hợp số. Còn trong bài toán này chứng minh mỗi số không là lũy thừa của một số nguyên dương. Mượn ý tưởng của bài trên, từ hợp số đến không là lũy thừa, ta lưu ý điều gì? Một số nguyên achia hết cho số nguyên tố p, nhưng không chia hết cho p² thìakhông là lũy thừa của một số nguyên.

2. Gọi p₁< p₂< . . . <p_n lànsố nguyên tố tùy ý.Ta muốnnsố dạng:m+1,m+2, . . . ,m+n, mỗi số m+i chia hết cho một thừa số nguyên tố p_i, nhưng không được chia hết cho p²_i. Từ đó xây dựng đồng dư như thế nào?Ta chỉ ra tồn tại số mmà















m+1≡ p₁(mod p²₁) m+2≡ p₂(mod p²₂) . . . .

m+n≡ p_n(mod p²_n)

⇔















m≡ p₁−1(mod p²₁) m≡ p₂−2(mod p²₂) . . . .

m≡ p_n−n(mod p²_n).

Theo định lý thặng dư Trung Hòa thì hệ trên có nghiệmmlớn tùy ý, chọnm>p_n. Từ đó với mọi i=1,2, . . . ,nthì

p_i|m+i nhưng p²_i ∤m+i.

Chứng tỏnsố liên tiếpm+1,m+2, . . . ,m+nđều không là lũy thừa của một số nguyên nào đó.

Cách 2. Với mỗim∈Z⁺, xét2nsố nguyên tố phân biệt p₁,p₂, . . . ,p_n,q₁,q₂, . . . ,q_nvà hệ phương trình đồng dư















x≡ −1(mod p₁q₁) x≡ −2(mod p₂q₂) . . . .

x≡ −n(mod p_nq_n).

Theo định lý thặng dư Trung Hoa thì hệ trên có nghiệm. Tức là tồn tạim∈Zsao cho m≡ −i(mod p_iq_i),∀i=1,2, . . . ,n.

Từ đó suy ra các sốm+1,m+2, . . . ,m+nlànsố nguyên liên tiếp và không có số nào là lũy thừa của một số nguyên nào cả (vì trong phân tích của mỗi số đó có ít nhất hai thừa số nguyên tố).

Bài 20.4.4. Chứng minh rằng với mỗi số tự nhiên n, tồn tại một cấp số cộng gồm nsố hạng sao cho mọi số hạng của nó đều là lũy thừa của một số tự nhiên với số mũ lớn hơn 1.

Phân tích và giải. 1. Việc chỉ ra một cấp số cộng nào là khó. Do đó việc đầu tiên là nghĩ đến chọn cấp số cộng nào cho dễ kiểm tra. Cấp số cộng đơn giản nhất là 1,2, . . . ,n. Tuy nhiên dãy này không thỏa. Do đó ta nghĩ đến chọn cấp số cộng "tương tự như trên" là a,2a,3a, . . . ,na.

2. Vì mong muốna,2a, . . . ,nalà lũy thừa của một số tự nhiên. Do đó sốacần sự xuất hiện của các hạng tử 2,3, . . . ,ntrong biểu diễn, tức cần có dạng

a=2^k23^k34^k4. . .n^kn. (ở đây đánh chỉ số củaktheo số hạng trong cơ số)

3. Đểalà lũy thừa của một số nguyên tố, thì các lũy thừak₂,k₃, . . . ,k_nphải có nhân tử chung, nhân tử chung này tự nhiên nhất là nhân tử nguyên tố chung p₂, tức là cần

















 k₂..

.p₂ k₃.

..p₂ . . . . k_n.

..p₂.

4. Khi đó 2a=2^k2+13^k34^k4. . .n^kn, để 2a là lũy thừa của một số nguyên tố, thì các lũy thừak₂+

1,k₂, . . . ,k_nphải có nhân tử nguyên tố chung p₃, tức là cần



















k₂+1. ..p₃ k₃.

..p₃ . . . . k_n..

.p₃.

5. Cứ tiếp tục tìm điều kiện cho các số 2a,3a, . . . ,na là lũy thừa của một số nguyên, thì điều kiện cho các lũy thừa k₂,k₃, . . . ,k_nlà gì?Như phân tích ở trên thì cần có

k₂.

..p₂, k₃.

..p₂, k₄.

..p₂, k₅.

..p₂, . . . , k_n.

..p₂, k₂+1..

.p₃, k₃..

.p₃, k₄..

.p₃, k₅..

.p₃, . . . , k_n..

.p₃, k₂.

..p₄, k₃+1.

..p₄, k₄.

..p₄, k₅.

..p₄, . . . , k_n.

..p₄,

. . . , . . . , . . . , . . . , . . . , . . .

6. Từ đó các sốk₂,k₃, . . . ,k_n tồn tại theo định lý thặng dư Trung Hoa. Với mọii=3, . . . ,ntồn tại số nguyên dươngk_i thỏa mãn

(k_i−1≡ −1(mod p_i)

k_i≡0(mod p_j),j6=i,j ∈ {3, . . . ,n}.

và

k_i..

.p₂,∀i=2,3, . . . ,n.

Khi đó thì

a=2^k23^k3. . .n^pn=

2^k2p2.2^k3p2. . .n^knp2 p₂

2a=2^k2+13^k3. . .n^pn =

2^k2

+1

p3 .2^k3p3. . .n^knp3 p₃

. . . .

na=2^k23^k3. . .n^pn+1 =

2^k2pn.2^k3pn . . .n^kn+1pn pn

.

Ta có điều phải chứng minh.

Bài 20.4.5(Bankal 2000). ChoAlà một tập con khác rỗng củaZ⁺. Chứng minh rằng tồn tại số nguyên dươngnsao cho tập hợp

nA={nx|x∈A} chứa toàn lũy thừa của một số tự nhiên với số mũ lớn hơn 1.

Giải. Bài toán này tương tự như bài 20.4. Do đó lời giải tương tự. Đặt A={a₁,a₂, . . . ,a_k}

và

p₁,p₂, . . . ,p_k

làksố nguyên tố phân biệt. Theo định lý thặng dư Trung Hoa, với mọii=1,2, . . . ,k, tồn tại số nguyên dươngm_ithỏa mãn

(m_i≡ −1(mod p_i)

m_i≡0(mod p_j)(j6=i,j ∈ {1,2, . . . ,k}).

Khi đó

m₁+1..

.p₁, m₂..

.p₁, . . . , m_k..

.p₁, m₁.

..p₂, m₂+1.

..p₂, . . . , m_k.

..p₂,

. . . , . . . , . . . , m_k.

..p₁, m₁.

..p_k, m₂.

..p_k, . . . , m_k+1.

..p_k. Đến đây đặt

n=a^m₁¹a^m₂². . .a^m_k^k

ta có

na₁ =a^m₁¹⁺¹a^m₂². . .a^m_k^k = a

m1+1 p1

1 a

m2 p1

2 . . .a

mkp1

k

!p1

na₂ =a^m₁¹a^m₂²⁺¹. . .a^m_k^k = a

m1p2

1 a

m2+1 p2

2 . . .a

mkp2

k

!p2

. . . .

na_k =a^m₁¹a^m₂². . .a^m_k^k+1= a

m1 pk

1 a

m2 pk

2 . . .a

mk+1 pk

k

!p_k

Bài 20.4.6. Chứng minh rằng với mọi số nguyên n, tồn tại một tập số nguyên n phần tử để tổng các phần tử của các tập con không rỗng của nó là 1 lũy thừa.

Giải. Ta sét tập số nguyênS={x₁,x₂, . . . ,x_n}, tậpScó2ⁿ−1tập con không rỗng củaS. Đặt S₁,S₂, . . . ,S₂ⁿ₋₁

là tổng các phần tử của các tập này. Áp dụng bài 20.5, tồn tại số nguyênbthỏa mãn {bS₁,bS₂, . . . ,bS₂ⁿ₋₁}

bao gồm toàn các lũy thừa. Từ đó ta chọn tập

F={bx₁,bx₂, . . . ,bx_n} thì tậpF thỏa mãn điều kiện bài toán.

Bài 20.4.7. Chứng minh rằng với mọi số tự nhiênn, luôn tồn tạinsố tự nhiên liên tiếp sao cho bất kỳ số nào cũng có ước dạng2^k−1,k∈N.

Phân tích giải. 1. Gọinsố nguyên liên tiếp làx+1,x+2, . . . ,x+n. Yêu cầu bài toán giúp ta nghĩ đến hệ thặng dư















x≡ −1(mod p₁) x≡ −2(mod p₂) . . . .

x≡ −n(mod p_n) Từ đây dẫn đến việc chọn p₁,p₂, . . . ,p_n.

2. Nếu p_i là các số nguyên tố thì rất khó kiểm soát điều kiện2^k−1, nên ta chọn luôn p_i là các số Mersen p_i=2^ki−1(p_ikhông cần nguyên tố).

3. Để đảm bảo(p_i,p_j) =1dẫn đến việc chọnk_i,k_j.

4. Mặt khác

2^ki−1,2^kj−1

=1⇔(ki,k_j) =1 (thật vậy, nếu gọiqlà ước nguyên tố chung của 2^ki−1,2^kj−1thì

(2^ki ≡1(mod q)

2^kj ≡1(mod q) ⇒2^(ki,kj)≡1(mod q)⇒q=1⇔(k_i,k_j) =1.

)

5. Từ các nhận xét trên, ta dễ dàng chọn đượck₁,k₂, . . . ,k_nthỏa(ki,k_j) =1,∀i,j=1,2, . . . ,n(i6= j) (có thể chọn luônk_i là số nguyên tố thứi).

Bài 20.4.8. Cho nlà số nguyên dương lẻ và n>3. Gọik,t là các số nguyên dương nhỏ nhất sao cho kn+1vàtnđều là số chính phương. Chứng minh rằng điều kiện cần và đủ đểnlà số nguyên tố là

min{k,t}> n 4. 1. Điều kiện cần: Giả sửnnguyên tố. Khi đó

n|tnvàtn chính phương nênn²|tn⇒n|t. Từ đó

t ≥n> n 4.

Hơn nữa đặta²=kn+1thìa² ≡1(mod n). Kết hợpnnguyên tố nêna≡ ±1(mod n). Nhưng vì a>1nêna≥n−1(vìn−1là số nhỏ nhất đồng−1modulo n). Dẫn đến

kn+1≥(n−1)² ⇒k≥n−2⇒k> n

4 vìn>3nênn−2> n 3. 2. Điều kiện đủ

• nchỉ có một ước nguyên tố duy nhất, đặtn=p^α, với p≥3do nlẻ. Nếuα chẵn, ta lấy t =1< n

4 thì

tn= p^α

là số chính phương, mâu thuẫn với giả thiết. Nếuα lẻ,α ≥3, ta lấy t = p< p^α

4 = n 4 thì

tn= p^α+1,α+1chẵn nêntnlà số chính phương vớit < n

4, mâu thuẫn. Vậyα =1haynlà số nguyên tố.

• Nếuncó ít nhất hai ước nguyên tố phân biệt. Khi đó ta có thểndưới dạngn= p^α.m, trong đó plà một số nguyên tố lẻ, m là số nguyên dương lẻ,(m,p) =1. Theo định lý thặng dư Trung Hoa, tồn tại số nguyênssao cho

(s≡1(mod p^α) s≡ −1(mod m).

Từ đón|s²−1. Hơn nữa ta có thể chọnssao cho

|s| ≤ n 2.

Vìs6≡1(mod m)nêns6=1vàs6≡ −1(mod p^α)nêns6=−1. Dẫn đếns²6=1. Từ đây lấy k= s²−1

n

thìklà số nguyên dương, hơn nữakn+1=s²là số chính phương và

k= s²−1 n < s²

n ≤

n² 4

n = n 4 mâu thuẫn với điều kiện

min{k,t}> n 4. Vậy trường hợp này không thể xảy ra.

Từ đó nphải là số nguyên tố.

20.5. ĐỊNH LÝ THẶNG DƯ TRUNG HOA VÀ SỐ FERMAT

Bài 20.5.1. Chứng minh rằng tồn tại số nguyênksao cho2ⁿ.k+1là hợp số với mọi số nguyên dương n.

Phân tích giải. 1. Xétnviết dưới dạngn=2^m.l,l là số tự nhiên lẻ. Khi đó 2ⁿk+1=2^2m.lk+1≡ −k+1(mod 2^2m+1).

Do đó ta sẽ tìmkđể

−k+1≡0(mod 2^2m+1).

2. Trước hết ta cóF₀,F₁,F₂,F₃,F₄là các số nguyên tố vàF₅=641×6700417và(F_i,F_j) =1,∀i6= j.

Đặt p=641,q=6700417.

3. Theo định lý thặng dư Trung Hoa, tồn tại số nguyên dương kthỏa mãn



























k≡1(mod F₀) k≡1(mod F₁) k≡1(mod F₂) k≡1(mod F₃) k≡1(mod F₄) k≡1(mod p) k≡ −1(mod q).

4. Nếum<5thì

2ⁿ=2^2ml ≡ −1(mod F_m)⇒2ⁿk≡ −1(mod F_m)⇒2ⁿk+1.. .F_m. 5. Nếum=5thì

2ⁿ =2^2nl≡ −1(mod F₅)⇒2ⁿk≡ −1(mod p)⇒2ⁿk+1. ..p.

6. Nếum>5thì

2ⁿ=2^2ml = 2²⁵

2^m−5l

≡1(mod F₅)⇒2ⁿk≡ −1(mod q)⇒2ⁿk+1. ..q.

Bài 20.5.2. Cho trước các số nguyên dươngn,s. Chứng minh rằng tồn tại nsố nguyên dương liên tiếp mà mỗi số đều có ước là lũy thừa bậcscủa một số nguyên dương lớn hơn 1.

Phân tích giải. 1. Xét dãy số FermatF_n=2²ⁿ+1(n=1,2, . . .). Liên quan đến số này có tính chất đáng lưu ý là

(F_n,F_m) =1,∀n6=m.

2. Áp dụng định lý thặng dư Trung Hoa cho n số nguyên tố cùng nhau F₁^s,F₂^s, . . . ,F_n^s và n số r_i=−i(i=1,2, . . . ,n)thì tồn tại số nguyênx₀ sao cho

x₀+i. ..F_i^s.

Vậy dãy {x₀+1,x₀+2, . . . ,x₀+n}gồmnsố nguyên dương liên tiếp, số hạng thứichia hết cho F_i^s.

Bài 20.5.3(IMO Shortlist 1998). Xác định tất cả số nguyên dươngnsao cho vớinnày tồn tạim∈Z để

2ⁿ−1|m²+9.

Phân tích giải. 1. Viếtndưới dạngn=2^s.t(s,t ∈N),t là số lẻ.

2. Nếut ≥3thì2^t−1|2ⁿ−1nên2^t−1|m²+9. Ta có

2^t−1≡ −1(mod 4).

Tức là số2^t−1có dạng4k+3, do đó nó có ước nguyên tốpmà p≡ −1(mod 4). Dĩ nhiên p6=3 vì

3∤2^t−1,∀t lẻ.

Từ đó suy ra

p|m²+9⇒m²≡ −9(mod p).

Chứng tỏ−9là thặng dư bậc hai theo modulo p, tuy nhiên 1=

−9 p

= −1

p

· 9

p

= (−1)^p−21 3

p 2

= (−1)^p−21 nên p−1

2 phải là số chẵn, tức là p≡1(mod 4), vô lý.

3. Từ đây suy rat =1hayn=2^s. Ta chứng minh đây là tất cả các số cần tìm bằng cách chỉ ra sốm để2ⁿ−1|m²+9. Ta có

2ⁿ−1=2^2s−1= (2−1)(2+1)(2²+1)

2²²+1

···

2^2s−1+1

. Từ đó để

2ⁿ−1|m²+9⇒2^2k+1|m²+9,∀k=0,1, . . . ,s−1.

Mặt khác các số Fermat có tính chất

2^2m+1,2²ⁿ+1

=1,∀m6=n.

Theo định lý thặng dư Trung Hoa thì tồn tại nghiệmx₀thỏa mãn hệ đồng dư



















x≡2(mod 2²+1) x≡2²(mod 2³+1) x≡2³(mod 2⁴+1) . . . .

x≡2^2s−2(mod 2^2s−1+1).

Từ đó suy ra

x²₀+1≡0(mod 2^2t+1+1),∀t =0,1,2, . . . ,s−2.

Từ đây suy ra

2ⁿ−1|9(x²₀+1) =m²+9 vớim=3x₀, đây chính là giá trịmcần tìm.

Bài 20.5.4(HÀN QUỐC 1999). Tìm tất cả các số tự nhiênnthỏa mãn2ⁿ−1chia hết cho 3 và tồn tại số nguyênmđể

2ⁿ−1

3 |4m²+1.

Phân tích giải. 1. Nếun≡1(mod 2)thìn=2k+1(k∈N), khi đó

2ⁿ =2^2k+1=2.4^k ≡2(mod 3)⇒2ⁿ−1≡1(mod 3) không thỏa mãn2ⁿ−1.

..3.

2. Nếun≡0(mod 2), đặtn=2^k.u(ulà số tự nhiên lẻ). Nếuu≥3thì 2^u−1|2ⁿ−1vì2ⁿ−1=2^2k.u−1= (2^u)^2k−1.

Do đó

2^u−1|4m²+1.

Mặt khác, vìu≥3nên

2^u−1≡ −1(mod 4).

Khi đó tồn tại pnguyên tố, p≡ −1(mod 4), là ước của2^u−1. Khi đó p|4m²+1.

Sử dụng tính chất "Nếu plà số nguyên tố dạng4k+3vàa²+b²..

.pthì cảavàbđều chia hết cho p". Áp dụng vào đẳng thức trên thì

2m.

..pvà1. ..p,

vô lý. Do đó u=1, tứcncó dạng n=2^k . Ta chứng minh đây là tất cả các số cần tìm.

3. Khin=2^k thì

2ⁿ−1

3 = 2^2k−1

3 =F₁.F₂. . . . .F_k−1

vớiF_i là số Fermat thứi : F_i=2²ⁱ+1. Theo định lý thặng dư Trung Hoa thì hệ























x≡2(mod 2²+1) x≡2²(mod 2³+1) x≡2³(mod 2⁴+1) . . . .

x≡2^2k−2(mod 2^2k−1+1).

x≡0(mod 2).

có nghiệm, gọi nghiệm đó là x₀ thìx₀ chẵn, đặtx₀=2mthì 4m²+1=x²₀+1.

..2ⁿ−1.

20.6. ỨNG DỤNG TRONG CÁC BÀI TOÁN SỐ TỔ HỢP

Bài 20.6.1(ĐÀI LOAN TST 2002). Trong lưới điểm nguyên của mặt phẳng tọa độOxy, một điểmA với tọa độ(x₀,y₀)∈Z² được gọi là nhìn thấy được từOnếu đoạn thẳngOAkhông chứa điểm nguyên nào khác ngoàiOvàA. Chứng minh rằng với mọi nnguyên dương lớn tùy ý, tồn tại hình vuôngn×n có các đỉnh có tọa độ nguyên, hơn nữa tất cả các điểm nguyên nằm bên trong và trên biên của hình vuông đều không nhìn thấy được từO.

Phân tích giải. 1. Trước tiên ta phải tìm điều kiện cần và đủ để A(x_A,y_A)nhìn thấy được từO?Dễ thấy điều kiện cần và đủ để A(x_A,y_A)nhìn thấy được từ Olà(x_A,y_A) =1.

(a) Thật vậy, nếuAnhìn thấy được, giả sử(xA,y_A) =d>1. Khi đóx_A=dx₁,y_A=dy₁(x1,y₁) = 1. Từ đây suy ra

x_A x₁ = y_A

y₁ =d.

Chứng tỏ ba điểmO,A(x_A,y_A)vàM(x₁,y₁)thẳng hàng, điểmM(x₁,y₁)nguyên. Dẫn đếnA không nhìn thấy được, vô lý. Vậy(x_A,y_A) =1.

(b) Ngược lại, nếu A(xA,y_A)có (xA,y_A) =1 thì Anhìn thấy được từ O. Giả sử A không nhìn thấy được, tức tồn tại điểm nguyênM(x₁,y₁)trên đoạnOA. Vì ba điểmO,M,Athẳng hàng

nên x_A

x₁ = y_A

y₁ ⇒x_A.y₁=y_A.x₁. Vì(x_A,y_A) =1nênx_A.

..x₁. Đặtx_A=dx₁thay vào thì dy₁=y_A⇒y_A.

..d.

Chứng tỏ(x_A,y_A).

..dnên(x_A,y_A)>1, vô lý. Do đóAnhìn thấy được từ O.

2. Để giải quyết bài toán, ta xây dựng một hình vuôngn×nvớinnguyên dương tùy ý sao cho mọi điểm nguyên(x,y)nằm trong hoặc trên biên hình vuông đều không thể nhìn thấy được từO. Tức là phải xây dựng một dãy tọa độ (x_i,y_j)>1. Từ đây nghĩ đến sử dụng các thừa số nguyên tố, một mặt đồng dư theo dòng, một mặt đồng dư theo cột trong ma trận là sẽ thỏa mãn. Thật vậy chọn p_{i j} là các số nguyên tố đôi một khác nhau (0≤i, j≤n)(gồm(n+1)² số nguyên tố). Sắp xếp các số nguyên tố này theo ma trận

M=









p_n0 p_n1 p_n2 ··· p_nn

··· ··· ··· ··· ···

p₂₀ p₂₁ p₂₂ ··· p_2n p₁₀ p₁₁ p₁₂ ··· p_1n p₀₀ p₀₁ p₂₂ ··· p_0n









Khi đó xét hệ phương trình đồng dư theo tích các số trên dòng



















x≡0(mod p₀₀.p₀₁.p₀₂. . .p_0n) x+1≡0(mod p₁₀.p₁₁.p₁₂. . .p_1n) x+2≡0(mod p₂₀.p₂₁.p₂₂. . .p_2n) . . . .

x+n≡0(mod p_n0.p_n1.p_n2. . .p_nn) và hệ phương trình đồng dư theo tích các số trên cột



















y≡0(mod p₀₀.p₁₀.p₂₀. . .p_n0) y+1≡0(mod p₀₁.p₁₁.p₂₁. . .p_n1) y+2≡0(mod p₀₂.p₁₂.p₂₂. . .p_n2) . . . .

y+n≡0(mod p_0n.p_1n.p_2n. . .p_nn) .

Theo định lý thặng dư Trung Hoa thì hai hệ trên có nghiệm, gọix₀,y₀ là nghiệm tương ứng của hai hệ trên, ta thấy

(x₀+i,y₀+j).

..p_{i j}⇒(x₀+i,y₀+j)>1,∀0≤i,j≤n.

Điều đó chứng tỏ mọi điểm nằm trong hoặc trên biên hình vuôngn×nxác định bởi điểm phía dưới bên trái là (x₀,y₀), điểm cao nhất bên phải là(x₀+n,y₀+n)đều không thể nhìn thấy được từ điểmO.

Bài toán này mặc dù xuất hiện khá lâu, nhưng tôi không để ý đến, và chỉ thực sự quan tâm và thấy được cái hay của nó khi học cùng em Lê Quang Bình trong đợt tập huấn thi TST 2013 với giáo sư Hà Huy Khoái, khi đó giả thiết phát biểu rất hay bởi ngôn ngữ đời thường là con cáo và ông thợ săn.

Bài 20.6.2 (BULGARIA 2003). Ta gọi một tập hợp các số nguyên dươngC là tốt nếu với mọi số nguyên dươngkthì tồn tạia,bkhác nhau trongCsao cho(a+k,b+k)>1. Giả sử ta có một tậpCtốt mà tổng các phần tử trong đó bằng 2003. Chứng minh rằng ta có thể loại đi một phần tửctrongCsao cho tập còn lại vẫn là tập tốt.

20.7. ỨNG DỤNG TRONG ĐA THỨC

Bài 20.7.1. Cho tập S={p₁,p₂, . . . ,p_k} gồm k số nguyên tố phân biệt và P(x) là đa thức với hệ số nguyên sao cho với mọi số nguyên dươngn, đều tồn tại p_i trongS sao cho p_i|P(n). Chứng minh rằng tồn tại p_i0 trongSsao cho

p_i0|P(n),∀n∈Z⁺. Chứng minh. Giả sử không tồn tại một phần tử p_inào trongSđể

p_i|P(n),∀n∈Z⁺.

Nghĩa là với mỗi p_i∈S(i=1,2, . . . ,k), đều tồn tạia_i∈Z⁺ sao cho p_i∤P(a_i).

Theo định lý thặng dư Trung Hoa thì tồn tại số nguyên dươngx₀ sao cho















x₀ ≡a₁(mod p₁) x₀ ≡a₂(mod p₂) . . . .

x₀ ≡a_k(mod p_k).

VìP(x) là đa thức hệ số nguyên nên sử dụng tính chất "nếuu≡v(mod m)thìP(u)≡P(v)(mod m)"

ta được















P(x₀)≡P(a₁)(mod p₁) P(x₀)≡P(a₂)(mod p₂) . . . .

P(x₀)≡P(a_k)(mod p_k).

VìP(a_i)6.

..p_i,∀i=1,2, . . . ,knên từ hệ trên suy ra P(x₀)6..

.p_i,∀i=1,2, . . . ,k

trái với giả thiết bài toán. Vậy giả thiết phản chứng là sai, ta có điều phải chứng minh.

Không khó để nhận ra, tập số trong bài 20.9 có thể thay bằng {p^α₁¹,p^α₂², . . . ,p^α_k^k}mà không ảnh hưởng gì. Thậm chí có thể thay bằng tập{a₁,a₂, . . . ,a_k} với các sốa_i nguyên tố cùng nhau từng cặp một. Tuy nhiên kết quả của bài toán này còn có thể mở rộng hơn nữa, tức tậpScó thể thay bằng tập số nguyên bởi ví dụ dưới đây.

Bài 20.7.2. Cho S={a₁,a₂, . . . ,a_n} ⊂Z⁺ và P(x)∈Z[x]. Biết rằng với mọi số nguyên dươngk, đều tồn tại chỉ sối∈ {1,2, . . . ,n}sao cho

a_i|P(k).

Chứng minh rằng tồn tại một chỉ sối₀ nào đó sao cho a_i0|P(k),∀k∈Z⁺.

Phân tích giải. 1. Tương tự như bài toán trên, ý tưởng ban đầu là phản chứng. Viết rõ ý phản chứng này?Giả sử kết luận bài toán là sai. Tức là với mỗii∈ {1,2, . . . ,n}, tồn tại số nguyênx_iđể

a_i∤P(xi).

2. Chuyển điều kiệna_i∤P(x_i)về số nguyên tố. Điều kiện đểP(x_i)không chia hết choa_i xét về mặt số nguyên tố như thế nào?Khi đó tồn tại số p^k_iⁱ, với p_inguyên tố thỏa mãn

p^k_iⁱ|a_i nhưng p^k_iⁱ ∤P(x_i).

Choi chạy từ 1 đếnnta được tập hợp các số sau{p^k₁¹,p^k₂², . . . ,p^k_nⁿ}.

3. Tương tự như bài toán trên, đã chỉ ra mâu thuẫn khi áp dụng định lý thặng dư Trung Hoa được chưa? Rõ ràng chưa thể áp dụng được, vì các số p_ichưa phân biệt, tức trong chúng có một số số trùng nhau? Giả sử p₁,p₂ trùng nhau, p^k₁¹|a₁,p^k₂²|a₂, khi đó ta chọn lũy thừak₁,k₂ như thế nào để hai tính chất đó đều thỏa mãn? Rõ ràng phải chọn số nhỏ nhất trong hai sốk₁,k₂. Từ đó định hướng cho những số nguyên tố trùng nhau. Nếu trong tập {p^k₁¹,p^k₂², . . . ,p^k_nⁿ} có những số có cơ số trùng nhau, với những cơ số đó, ta giữ lại cơ số có số mũ nhỏ nhất, và loại khỏi tập những lũy thừa còn lại. Khi đó ta được tập

{p^q₁¹,p^q₂², . . . ,p^q_m^m},(m≤nvà p₁,p₂, . . . ,p_m là những số nguyên tố phân biệt).

Chú ý rằnga_i(i=1,2, . . . ,n)sẽ chia hết cho một số số hạng trong tập này, chứ không nhất thiết chỉ chia hết cho 1 số.

4. Đến đây hoàn thành nốt phần còn lại bằng cách áp dụng định lý thặng dư Trung Hoa? Từ p^q₁¹,p^q₂², . . . ,p^q_m^m là những số đôi một nguyên tố cùng nhau, ta xét hệ đồng dư sau















x≡x₁(mod p^q₁¹) x≡x₂(mod p^q₂²) . . . .

x≡x_m(mod p^q_m^m).

Theo định lý thặng dư Trung Hoa thì hệ trên có nghiệmx₀. VìP(x)là đa thức hệ số nguyên nên















P(x₀)≡P(x₁)(mod p^q₁¹) P(x₀)≡P(x₂)(mod p^q₂²) . . . .

P(x₀)≡P(x_m)(mod p^q_m^m).

VìP(x_i)6≡0(mod p^q_iⁱ),i=1,2, . . . ,mnên

P(x₀)6≡0(mod p^q_iⁱ),i=1,2, . . . ,m chứng tỏ

P(x0)6≡0(mod a_i),i=1,2, . . . ,n mâu thuẫn với giả thiết của bài toán. Ta có điều phải chứng minh.

Bài toán trên là điển hình cho cách sử dụng định lý Trung Hoa.

Bài 20.7.3. Chứng minh rằng tồn tại một đa thức P(x)∈Z[x], không có nghiệm nguyên sao cho với mọi số nguyên dươngn, tồn tại số nguyênxsao cho

P(x).. .n.

Chứng minh. Phân tích giải

1. Xét đa thức P(x) = (3x+1)(2x+1). Với mỗi số nguyên dương n, ta biểu diễn n dưới dạng n=2^k(2m+1).

2. Vì(2^k,3) =1nên tồn tạiasao cho

3a≡1(mod 2^k).

Từ đó ta muốn có

3x≡ −1(mod 2^k) thì chỉ cần chọnxsao cho

x≡ −a(mod 2^k).

3. Vì(2,2m+1) =1nên tồn tại số nguyênbsao cho

2b≡1(mod 2m+1).

Do đó ta muốn có

2x≡ −1(mod 2m+1) thì cần chọn xsao cho

x≡ −b(mod 2m+1).

4. Nhưng do(2^k,2m+1) =1nên theo định lý thặng dư Trung Hoa, tồn tại số nguyênxlà nghiệm của hệ

(x≡ −a(mod 2^k) x≡ −b(mod 2m+1).

Từ đó theo lý luận trên, với mọi số nguyên dươngnđều tồn tạixđểP(x)..

.n. Rõ ràngP(x)không có nghiệm nguyên.

Một câu hỏi thú vị không quá tầm thường. Đa thứcP(x) = (3x+1)(2x+1)có phải là đa thức duy nhất thỏa mãn điều kiện bài toán trên hay không? Hãy xây dựng đa thức trong trường hợp tổng quát xem sao??

Để hiểu hơn nội dung định lý dưới đây, ta xét ví dụ

Ví dụ 20.7.1. Chon=12=2².3và đa thứcP(x) =x²+5x. Khi đó phương trình P(x)≡0(mod 3)

có hai nghiệm làx≡0,1(mod 3)và phương trình

P(x)≡0(mod 4) có hai nghiệmx≡0,4(mod 4). Từ đó phương trình

P(x)≡0(mod 12) có bốn nghiệm là

x≡0,3,4,7(mod 12).