Luận văn Một số tính chất số học của hệ số nhị thức

1p+ · · ·+msps, n= n0+n1p+ · · ·+nsps với 0≤ mi,ni ≤ p−1, khi đó( n m ) ≡ s ∏ i=0 ( ni mi ) (mod p) 7Ta sẽ chứng minh định lý này. Trước tiên ta có định nghĩa sau. Định nghĩa 1.2.2. Cho đa thức f (X) = a0+ a1X + · · ·+ anXn ∈ Z[X ]. Ta viết f (X) ≡ 0(mod p) nếu ai ≡ 0(mod p) với mọi i = 1, . . . ,n. Với hai đa thức f (X) và g(X) trong Z[X ], ta viết f (X) ≡ g(X)(mod p) nếu f (X)− g(X)≡ 0(mod p). Bổ đề 1.2.3. Với i≥ 0, ta có (1+X)pi ≡ 1+X pi(mod p). Chứng minh. Ta chứng minh bằng quy nạp theo i. Với i= 0 thì khẳng định là hiển nhiên. Giả sử khẳng định đã đúng với i≥ 0. Ta có (1+X)p i+1 ≡ ( 1+X p i )p (mod p) ≡ 1+ p−1 ∑ k=1 ( p k ) X p ik+X p i+1 (mod p) ≡ 1+X pi+1(mod p), vì ta có p | (pk) với mọi k = 1, . . . , p−1. Chứng minh Định lý Lucas. Ta có n ∑ m=0 ( n m ) Xm = (1+X)n = s ∏ i=0 ( (1+X)p i )ni ≡ s ∏ i=0 (1+X p i )ni = s ∏ i=0 ( ni ∑ mi=0 ( ni mi ) Xmip i ) (mod p) = s ∏ i=0 ( p−1 ∑ mi=0 ( ni mi ) Xmip i ) = n ∑ m=0 ( s ∏ i=0 ( ni mi )) Xm (mod p) Đồng nhất hệ số ở hai vế ta được (n m )≡∏si=0 (nimi) (mod p). Ví dụ 1.2.4. Với n= 57,m= 32, p= 5, ta có n= 57= 2125, m= 32= 1125. Dễ thấy (57 32 ) = 9929472283517787 ≡ 2 (mod5), còn (21)(11)(22) = 2 ≡ 2 (mod5), do đó (57 32 )≡ (21)(11)(22) (mod5). 8Định lý Lucas có thể phát biểu tương đương lại dưới dạng: Với số nguyên tố p và các số nguyên dương n,m,r,s thỏa mãn 0≤ r,s≤ p−1, ta có( np+ r mp+ s ) ≡ ( n m )( r s ) (mod p) Kết quả này ngay lập tức cho ta (np mp )≡ (nm) (mod p). Dễ dàng thấy rằng nếu n= n0+n1p+ · · ·+nsps thì với mỗi k = 1,s, ta có ( n pk ) ≡ b n pk c ≡ nk (mod p). Trong trường hợp đặc biệt với k = 1 ta có (n p )≡ bn p c (mod p). 1.2.1 Hệ quả Dưới đây là một số hệ quả của Định lý Lucas. Hệ quả 1.2.5. Cho p là một số nguyên tố và m,n,k là ba số nguyên dương thỏa mãn m≤ n. Khi đó( npk mpk ) ≡ ( n m ) (mod p). Chứng minh. Ta đã biết (np mp )≡ (nm) (mod p). Giả sử (npk mpk ) ≡ (nm) (mod p) đúng với k nguyên dương nào đó. Ta sẽ chứng minh ( npk+1 mpk+1 ) ≡ ( n m ) (mod p). Thật vậy, theo Định lý Lucas ta có( npk+1 mpk+1 ) ≡ ( npk mpk ) (mod p). Kết hợp với giả thiết quy nạp, ta có điều phải chứng minh. 9Một số bài tập ứng dụng Bài tập 1. Chứng minh (1000 500 ) không chia hết cho 7. Chứng minh. Thật vậy, ở đây n= 1000, k= 500 và r= n−k= 500, và viết trong cơ số 7, ta có 500= 3+1 ·7+3 ·72+1 ·73 = 13137. Khi cộng m = 13137 và r = 13137 trong cơ số 7 thì không có nhớ. Do đó theo Định lý Kummer, lũy thừa cao nhất của 7 mà chia hết (1000 500 ) là 70 = 1. Tức là (1000 500 ) không chia hết cho 7. Bài tập 2. Tìm chữ số tận cùng của (99 19 ) . Chứng minh. Ta sẽ đi tìm số dư của của (99 19 ) cho 2 và 5. Viết trong cơ số 2, ta có n = 99 = 26+ 25+ 2+ 1 = 11000112 và k = 19 = 24+ 2+ 1 = 00100112. Theo Định lý Lucas( 99 19 ) ≡ ( 1 0 )( 1 0 )( 0 1 )( 0 0 )( 0 0 )( 1 1 )( 1 1 ) ≡ 0(mod2). Viết trong cơ số 5, ta có n= 3 ·52+4 ·5+4= 3445 và k= 19= 3 ·5+4= 0345. Theo Định lý Lucas( 99 19 ) ≡ ( 3 0 )( 4 3 )( 4 4 ) = 4(mod5). Do đó (99 19 )≡ 4(mod10) và chữ số tận cùng của (9919) là 4. Bài tập 3. Cho p là một số nguyên tố, n là một số tự nhiên. Lấy modulo p các hàng của tam giác Pascal ta thu được một tam giác gọi là tam giác p-Pascal. Chứng minh rằng số các phần tử khác không trong hàng thứ n của một tam giác p-Pascal bằng∏(ni+1) trong đó ni là chữ số thứ i trong biểu diễn theo cơ số p của n. 10 Chứng minh. Các phần tử ở hàng thứ n của tam giác p-Pascal khác không tương ứng với các số 0≤ k ≤ n mà p - (nk). Theo Định lý Kummer, p - (n k ) khi và chỉ khi phép trừ n cho k theo cơ số p không có phép nhớ nào. Do đó ki ≤ ni với mọi i, ở đây ki là chữ số thứ i trong biểu diễn theo cơ số p của k. Do vậy ta có ni+1 cách chọn cho ki, từ 0 đến ni. Như vậy dễ dàng thấy rằng số các phần tử khác không trong hàng thứ n của một p tam giác Pascal bằng ∏(ni+1). Bài tập 4. Cho 0< k< n+1. Chứng minh rằng nếu p - (n k ) và p - n+1, thì p - (n+1 k ) . Chứng minh. Giả sử n = n0+ n1p+ · · · và k = k0+ k1p+ · · · là các biểu diễn theo cơ số p của n và k tương ứng. Vì p - n+1 nên 0≤ n0 ≤ p−2. Vì p - (n k ) nên theo Định lý Kummer, không có nhớ khi cộng k và n−k theo cơ số p, hay ki ≤ ni với mọi i. Tương tự ta cũng có bất đẳng thức này với cặp k và n+1 vì n+1 cũng có biểu diễn theo cơ số p giống n ngoại trừ chữ số hàng đơn vị hơn 1 đơn vị. Do đó, p - (n+1 k ) . Bài tập 5. Chứng minh rằng với mọi số tự nhiên n, thì Cn = 1n+1 (2n n ) là cũng số tự nhiên. (SốCn này được gọi là số Catalan thứ n.) Chứng minh. Để chứng minh Cn là số tự nhiên, ta sẽ chỉ ra rằng với mọi ước nguyên tố p của n+1, ta có vp(n+1)≤ vp( ( 2n n ) ). Gọi l = vp(n+1). Khi đó trong cơ số p, n+1 có biểu diễn là n+1= as · · ·a1a00 · · ·0( với l số 0 tận cùng và a0 6= 0). Do vậy n có biểu diễn trong cơ số p là n= as · · ·a1(a0−1)(p−1) · · ·(p−1)( với l số (p−1) tận cùng). 11 Do đó phép cộng n+n trong cơ số p cần ít nhất l phép nhớ, do vậy vp( ( 2n n ) )≥ l = vp(n+1). Bài tập 6. ĐặtCk = 1 k+1 (2k k ) . Chứng minh rằng ∑nk=1Ck ≡ 1 (mod3) khi và chỉ khi n+1 có chứa ít nhất một chữ số 2 khi được biểu diễn theo cơ số 3. Chứng minh. Chú ý rằng( 2n+2 n+1 ) −4 ( 2n n ) = 2 2n+1 n+1 ( 2n n ) −4 ( 2n n ) =−2Cn. Do đóCn ≡ (2n+2 n+1 )− (2nn ) (mod3). Bởi vậy n ∑ k=1 Ck ≡ (( 2n+2 n+1 ) − ( 2n n )) + (( 2n n ) − ( 2n−2 n−1 )) + · · · = ( 2n+2 n+1 ) +1 (mod3). Do đó, theo Định lý Kummer, khi cộng n+1 với chính nó trong cơ sở 3, ta phải có ít nhất 1 số nhớ, và điều này xảy ra khi và chỉ khi n+1 có chứa ít nhất 1 chữ số 2 khi biểu diễn theo cơ số 3. Bài tập 7. [2010 Vietnam Team Selection Test/6] Gọi Sn là tổng bình phương của các hệ số của đa thức (1+x)n. Chứng minh rằng S2n+1 không chia hết cho 3. Giải. Ta có (1+ x)n = n ∑ k=0 (n k ) xn. Do vậy Sn = n ∑ k=0 ( n k )2 = ( 2n n ) . Do vậy chúng ta phải chứng minh rằng (4n 2n ) + 1 không chia hết cho 3. Ta viết 4n và 2n theo cơ số 3: 4n = idid−1 · · · i03 và 2n = jd jd−1 · · · j03. Theo 12 Định lý Lucas, ta có( 4n 2n ) = ( i0 j0 )( i1 j1 ) · · · ( id jd ) (mod 3). Nếu với k nào đó mà ik < jk thì vế trái của đẳng thức đồng dư trên sẽ chia hết cho 3 và do vậy (4n 2n ) +1 chia cho 3 dư 1, và ta có điều phải chứng minh. Bây giờ ta sẽ giả sử ik ≥ jk∀k. Khi đó biểu diễn theo cơ số 3 của 2n= 4n−2n chính là 2n= 4n−2n= (id− jd)(id−1− id−1) · · ·(i0− j0). So sánh 2 biểu diễn theo cơ số 3 của 2n, ta suy ra ik− jk = jk, với mọi k. Từ đó suy ra cặp (ik, jk) hoặc bằng (0,0) hoặc bằng (2,1). Gọi S là tập các chỉ số k ∈ {1, . . . ,d} mà (ik, jk) = (2,1). Khi đó vì 2n= d ∑ k=0 (ik− jk)3k = ∑ k∈S 3k là một số chẵn, nên số phần tử s của tập S là chẵn. Do vậy( 4n 2n ) ≡ ( 0 0 )k−s(2 1 )s = 2s ≡ 1 (mod 3). Suy ra (4n 2n ) +1 chia cho 3 dư 2. Như vậy ta đã chỉ ra rằng (4n 2n ) +1 chia cho 3 luôn dư 1 hoặc 2. Đây là điều phải chứng minh. Bài tập 8. Cho p là một số nguyên tố, k,n là các số nguyên dương. Chứng minh rằng (pn−1 k ) ≡ (−1)σp(k) (mod p) với σp(k) là tổng các chữ số của k khi biểu diễn theo cơ số p. Chứng minh. Vì p−1≡−1 (mod p) nên ta có (p−1k )≡ (−1)k (mod p). Dễ thấy rằng các chữ số của pn−1 khi biểu diễn theo cơ số p đều bằng p−1. Do đó, lại theo Định lý Lucas, ta có( pn−1 k ) ≡∏ ( p−1 ki ) (mod p). 13 trong đó ki là chữ số thứ i trong biểu diễn của k theo cơ số p. Áp dụng nhận xét ở trên ta có ∏ (p−1 ki ) ≡ ∏(−1)ki = (−1)∑ki. Vì vậy(pn−1 k )≡ (−1)σp(k) (mod p). Bài tập 9. Cho p,q là hai số nguyên tố phân biệt. Chứng minh rằng(2pq−1 pq−1 )≡ 1 (mod pq) khi và chỉ khi (2p−1p−1 )≡ 1 (mod q) và (2q−1q−1 )≡ 1 (mod p). Chứng minh. Ta thấy 2pq−1= (2q−1)p+ p−1 do đó chữ số cuối cùng trong biểu diễn theo cơ số p của 2pq− 1 là p− 1. Tương tự như vậy, chữ số cuối cùng trong biểu diễn theo cơ số p của pq−1 cũng là p−1. Do đó, theo Định lý Lucas,( 2pq−1 pq−1 ) ≡ ( 2q−1 q−1 )( p−1 p−1 ) ≡ ( 2q−1 q−1 ) (mod p). Tương tự ta có( 2pq−1 pq−1 ) ≡ ( 2p−1 p−1 )( q−1 q−1 ) ≡ ( 2p−1 p−1 ) (modq). Ta có (2pq−1 pq−1 ) ≡ 1 (mod pq) khi và chỉ khi (2pq−1pq−1 ) ≡ 1 (mod p) và(2pq−1 pq−1 )≡ 1 (mod q), điều này lại tương đương với (2q−1q−1 )≡ 1 (mod p) và(2p−1 p−1 )≡ 1 (mod q), theo hai đẳng thức dồng dư ở trên. Bài tập 10. Cho p là số nguyên tố và n,m là hai số tự nhiên tùy ý. Chứng minh rằng p2 | ( pnpm)− (nm). Chứng minh. Trước tiên, chú ý rằng (X + 1)pn = (X + 1)p(n−1)(X + 1)p. Đồng nhất hệ số của X pmở hai vế đẳng thức trên, ta được( pn pm ) = ( p(n−1) pm )( p 0 ) + ( p(n−1) pm−1 )( p 1 ) + · · ·+ ( p(n−1) pm− p+1 )( p p−1 ) + ( p(n−1) pm− p )( p p ) . Theo Định lý Lucas, mỗi hệ số nhị thức đều chia hết cho p. Vì thế tất cả các số hạng trong tổng trên đều chia hết cho p2, trừ số hạng đầu tiên và 14 cuối cùng. Do đó( pn pm ) ≡ ( p(n−1) pm ) + ( p(n−1) p(m−1) ) (mod p2). Lùi vô hạn, ta có( p(n−1) pm ) + ( p(n−1) p(m−1) ) ≡ ( n−1 m ) + ( n−1 m−1 ) ≡ ( n m ) (mod p2). Chứng minh hoàn tất. 15 Chương 2 Hệ số nhị thức modulo lũy thừa nguyên tố Trong chương này chúng tôi trình bày một mở rộng của Định lý Wilson, mở rộng của Định lý Lucas và một kết quả của Granwille về đồng dư modulo lũy thừa nguyên tố của hệ số nhị thức. 2.1 Mở rộng của định lý Wilson Ký hiệu (n!)p cho tích tất cả các số nguyên dương không vượt quá n và không chia hết cho p. Định lý Wilson phát biểu rằng với mọi số nguyên tố p, (p−1)!≡−1 (mod p) hay (p!)p ≡−1 (mod p). Trong phần này ta sẽ chứng minh một số mở rộng của Định lý Wilson. Định lý 2.1.1. Cho p là một số nguyên tố, n là một số nguyên dương bất kỳ, n= n0+n1p+ · · ·+nsps. Khi đó (−1) b n p c (n!)p ≡ n0! (mod p). Chứng minh. Ta thấy (n!)p = b npc−1 ∏ k=0 (kp+1)(kp+2) · · ·(kp+ p−1)×( bn p cp+1 )( bn p cp+2 ) · · · ( bn p cp+n0 ) . 16 Dễ thấy rằng (kp+1)(kp+2)...(kp+ p−1)≡ (p−1)! (mod p), còn ( bn p cp+1 )( bn p cp+2 ) ... ( bn p cp+n0 ) ≡ n0! (mod p). Từ nhận xét này kết hợp với Định lý Wilson, ta có (−1) b n p c (n!)p ≡ n0! (mod p) Định lý 2.1.2. Cho p là số nguyên tố, và n là số tự nhiên. Ta viết n = n0+n1p+ · · ·+nsps trong cơ số p. Khi đó, ta có n! pvp(n!) = (−1)vp(n!)n0!n1! · · ·ns!(mod p). Chứng minh. Ta có n!= (n!)p · p[n/p] · ([n/p])!. Do vậy, ta có 1 p[n/p] n!= (n!)p[n/p]!. Do đó theo Định lý 2.1.1, ta có 1 p[n/p] n!≡ (−1)[n/p]n0!([n/p])!(mod p). (Chú ý rằng n0 chính là số dư của n cho p, tức là chữ số hàng đơn vị của n khi viết theo cơ số p.) Thay n bởi [n/p] trong công thức trên, ta suy ra 1 p[n/p 2] [n/p]!≡ (−1)[n/p2]n1!([n/p2]!)(mod p). (Chú ý rằng n1 chính là số dư của n cho p2, cũng là chữ số hàng đơn vị của [n/p] khi viết theo cơ số p.) Cứ tiếp tục quá trình như vậy, ta suy ra với mọi 17 i≥ 0 ta có 1 p[n/p i+1] [n/pi]!≡ (−1)[n/pi+1]ni!([n/pi+1]!)(mod p). Kết hợp các đẳng thức này, ta suy ra 1 p∑i≥1[n/pi] n!≡ (−1)∑i≥1[n/pi]n0!n1! · · ·ns!(mod p). Theo Bổ đề 1.1.2, ta có vp(n!) = ∑i≥1[n/pi]. Do đó, n! pvp(n!) ≡ (−1)vp(n!)n0!n1! · · ·ns!(mod p). Định lý 2.1.3. Cho p là một số nguyên tố, pq là một lũy thừa bất kỳ của nó. Khi đó (pq!)p ≡ δ (mod pq) trong đó δ = 1, nếu p= 2,q≥ 3.−1, trong những trường hợp còn lại. Chứng minh. Dễ thấy rằng chúng ta có thể chia tích (pq!)p thành hai nhóm, gồm tích các m mà m 6≡ m−1 (mod pq) và một nhóm là tích các m mà m≡ m−1 (mod pq). Từ đây ta được (pq!)p đồng dư với tích các m≤ pq mà m2≡ 1 (mod pq). Ta có m2−1= (m−1)(m+1) (mod pq). Do đó pq|(m−1)(m+1). Vì gcd(m−1,m+1) = 1 hoặc 2 nên ta có hai trường hợp như sau. 1. Nếu gcd(m− 1,m+ 1) = 1 thì hoặc pq|m− 1 hoặc pq|m+ 1 do đó m≡±1 (mod pq). Vì thế m= 1 hoặc pq−1. 2. Nếu gcd(m− 1,m+ 1) = 2 thì m− 1 = 2z,m+ 1 = 2t, với z, t ∈ N, gcd(z, t) = 1. • Nếu p 6= 2 thì pq|(m−1)(m+1) = 4zt nên pq|zt với gcd(z, t) = 1. Suy ra pq hoặc chia hết z hoặc chia hết t hay pq hoặc chia hết m− 1 hoặc chia hết m+ 1 nên tựu lại ta quay lại trường hợp thứ nhất trên. 18 • Nếu p= 2 thì 2q|4zt. Nếu q< 3 thì bằng vài tính toán đơn giản ta thấy m = 1 hoặc pq− 1. Nếu q ≥ 3 hoặc 2q−2|z hoặc 2q−2|t. Do đó hoặc 2q−1|m−1 hoặc 2q−1|m+1, mà m< 2q nên trong trường hợp này hoặc m= 2q−1+1 hoặc m= 2q−1−1. Tóm lại những m < pq thỏa mãn m2 ≡ 1 (mod pq) là 1 và pq− 1 trừ phi pq = 2 (trong trường hợp này ta chỉ có m = 1) và p = 2,q ≥ 3 mà ta có thêm các nghiệm là 2q−1+1 và m= 2q−1−1. Từ đó ta có (pq!)p hoặc đồng dư với 1 nếu p = 2,q ≥ 3 hoặc đồng dư với −1 trong các trường hợp còn lại. Ví dụ 2.1.4. Ví dụ lấy p= 3, q= 2, ta thấy (32!)3 = 1.2.4.5.7.8. Để ý rằng 2 = 5−1 (mod32) còn 4 = 7−1 (mod32) nên ta có thể ghép cặp (32!)3 = 1.8.(2.5).(4.7)≡ 1.(−1).1.1= 1 (mod32). 2.2 Một mở rộng của định lý Lucas Định lý Lucas cho ta biết (n m )≡∏i≥0 (nimi) (mod p). Nếu pk là lũy thừa cao nhất của p chia hết (n m ) thì ta có thể quan tâm tới 1 pk (n m ) (mod p). Câu trả lời là một kết quả của Anton (1869), Stickelberger (1890) và Hensel (1902), phát biểu như sau. Định lý 2.2.1. Cho p là một số nguyên tố, n ≥ m là hai số tự nhiên, r = n−m. Giả sử m,n,r có biểu diễn theo cơ số p dưới dạng m= m0+m1p+ · · ·+msps, n= n0+n1p+ · · ·+nsps, r = r0+ r1p+ · · ·+ rsps. Gọi k = vp( (n m ) ). Khi đó ta có 1 pk ( n m ) ≡ (−1)k ( n0! m0!r0! )( n1! m1!r1! ) ... ( ns! ms!rs! ) (mod p). Trước khi chứng minh Định lý, ta cần một bổ đề đơn giản sau. 19 Bổ đề 2.2.2. Cho a≡ b(mod p), và c≡ d(mod p). Giả sử thêm rằng c | a, d | b, và p - c. Khi đó a c ≡ b d (mod p). Chứng minh. Vì p - c và c≡ d(mod p), nên ta cũng có p - d. Do vậy gcd(p,cd)= 1. Từ giả thiết ta suy ra p | ad − bc. Kết hợp với gcd(p,cd) = 1, ta có p | (ad−bc)/cd. Từ đó suy ra điều phải chứng minh. Chứng minh Định lý 2.2.1. Bằng cách áp dụng Định lý 2.1.2 cho n, m và r, ta được n! pvp(n!) ≡ (−1)vp(n!)n0!n1! · · ·ns!(mod p), m! pvp(m!) ≡ (−1)vp(m!)m0!m1! · · ·ms!(mod p), r! pvp(r!) ≡ (−1)vp(r!)r0!r1! · · ·rs!(mod p). Hiển nhiên rằng m! pvp(m!) và r! pvp(r!) không chia hết cho p. Áp dụng Bổ đề trên (hai lần), ta suy ra pvp(m!)pvp(r!) vp(n!) n! m!r! ≡ (−1) vp(n!) (−1)vp(m!)(−1)vp(r!) n0! m0!r0! n1 m1!r1! · · · ns! ms!rs! (mod p). Rõ ràng rằng k = vp(n!)− vp(m!)− vp(r!). Do vậy, ta có 1 pk ( n m ) ≡ (−1)k ( n0! m0!r0! )( n1! m1!r1! ) · · · ( ns! ms!rs! ) (mod p). Ví dụ 2.2.3. Cho p= 3, n= 13 và m= 5. Khi đó r= n−m= 8. Viết trong cơ số 3, ta có 13= 1+1 ·3+1 ·32 = 1113 5= 2+1 ·3= 123 8= 2+2 ·3= 223 Số các nhớ khi cộng m = 5 = 123 và n−m = 8 = 223 trong cơ số 3 là 2. (Nhớ đầu xuất hiện ở việc cộng hàng đơn vị 2+2=4, ghi kết quả là 1 và nhớ 1 cho phép cộng hàng chục. Ta có cũng có “nhớ” khi cộng hàng chục, vì phép cộng hàng chục là 1+2+1=4 bằng 113.) Do đó lũy thừa cao nhất của 3 20 mà chia hết (13 5 ) là 32.Vì thế k = 2 và công thức (2) trở thành 1 32 ( 13 5 ) ≡ (−1)2 ( 1! 2!2! )( 1! 1!2! )( 1! 0!0! ) (mod3). Cái này đúng vì vế trái của nó là 1 32 13 ·12 ·11 ·10 ·9 1 ·2 ·3 ·4 ·5 = 13 ·11≡ 2(mod3); và vế phải là 1 2 ·2 1 2 ≡ 2(mod3). Ví dụ 2.2.4. (Ví dụ này lấy trong [2, page 230].) Xét p = 7, và n và k trong cơ số 7 cho bởi n = 24136057 và k = 12016327. Khi đó r = n− k = 12116437. Theo Định lý Kummer l = vp (n k ) = 2. Theo Định lý trên ta có (−1)l 72 ( n k ) ≡ ( 2! 1!1! )( 4! 2!2! )( 1! 0!1! )( 3! 1!1! )( 6! 6!6! ) ×( 0! 3!4! )( 5! 2!3! ) (mod 7) ≡ 2 (mod 7). Suy ra (n k )≡ 98(mod343). Mệnh đề 2.2.5. Cho p là số nguyên tố và 0≤ m< n< p. Khi đó( np+m mp+n ) ≡ (−1)m+n+1p(mod p2). Chứng minh. Ta viết N := np+m,M :=mp+n và R := N−M trong cơ số p, ta có N = nm, M = mn, R= (n−m−1)(p+m−n). Số phép nhớ khi cộngM với R trong cơ số p chính là 1. Theo Định lý 2.2.1, 21 ta có 1 p ( N M ) ≡ (−1) n! m!(n−m−1)! m! n!(p+m−n)!(mod p) ≡ (p−1)! (n−m−1)!(p+m−n)! = ( p−1 n−m−1 ) (mod p), ở đây ta đã sử dụng Định lý Wilson nói rằng −1≡ (p−1)!(mod p). Ta đã biết rằng (p−1 k )≡= (−1)k(mod p), với mọi 0≤ k < p. Do vậy( np+m mp+n ) ≡ p ( p−1 n−m−1 ) ≡ (−1)n−m−1p≡ (−1)n+m+1p(mod p2). 2.3 Hệ số nhị thức modulo lũy thừa nguyên tố Một câu hỏi tự nhiên đặt ra sau khi ta chứng minh xong Định lý 2.2.1 là có hay không một công thức tương tự modulo pq với q≥ 1 bất kỳ. Trong mục này chúng ta sẽ trình bày một kết quả tương tự của Granwille, phép chứng minh và một số ví dụ minh họa cho kết quả tổng quát đó. Trước tiên ta sẽ mở rộng Định lý 2.1.1 và Định lý 2.1.2 cho modulo lũy thừa nguyên tố. Định lý 2.3.1. Cho pq là một lũy thừa của số nguyên tố p và n là một số tự nhiên. Gọi N0 là số dư của n khi chia cho pq. Khi đó ta có δ [n/p q](n!)p ≡ (N0!)p(mod pq), trong đó δ =−1 nếu p= 2,q≥ 3, và δ =−1 trong các trường hợp còn lại. Chứng minh. Ký hiệu ∏′ là tích trên các số nguyên không chia hết cho p. 22 Ta có δ [n/p q](n!)p = δ [n/p q] ( [n/pq]−1 ∏ i=0 ′ ∏ 1≤ j<pq (ipq+ j) )( ′ ∏ 1≤ j≤N0 (b n pq cpq+ j) ) ≡ δ [n/pq] ( [n/pq]−1 ∏ i=0 ′ ∏ 1≤ j<pq j )( ′ ∏ 1≤ j≤N0 j ) (mod pq) ≡ δ [n/pq]((pq!)p)[n/pq](N0!)p (mod pq) ≡ (N0!)p(mod pq). Ở đây, đồng dư cuối cùng suy ra từ Định lý 2.1.3 nói rằng ta có (pq!)p ≡ δ (mod pq). Định lý 2.3.2. Cho pq là một lũy thừa của số nguyên tố p và n là một số tự nhiên. Với mỗi i≥ 0, ta gọi Ni là số dư của [n/pi] khi chia cho pq. Khi đó n! pvp(n!) ≡ δ∑i≥q[n/pi]∏ i≥0 (Ni!)p(mod pq). Chứng minh. Ta có n!= (n!)p · p[n/p] · ([n/p])!. Do vậy, ta có 1 p[n/p] n!= (n!)p[n/p]!. Do đó theo Định lý 2.3.1, ta có 1 p[n/p] n!≡ δ [n/pq](N0!)p([n/p])!(mod pq). Thay n bởi [n/p] trong công thức trên, ta suy ra 1 p[n/p 2] [n/p]!≡ δ [n/pq+1](N1!)p([n/p2]!)(mod pq). Cứ tiếp tục quá trình như vậy, ta suy ra với mọi i≥ 0 ta có 1 p[n/p i+1] [n/pi]!≡ δ [n/pq+i](Ni!)p([n/pi+1])!(mod pq). 23 Kết hợp các đẳng thức này, ta suy ra 1 p∑i≥1[n/pi] n!≡ δ∑i≥q[n/pi]∏ i≥0 (Ni!)p(mod pq). Theo Bổ đề 1.1.2, ta có vp(n!) = ∑i≥1[n/pi]. Do đó, n! pvp(n!) ≡ δ∑i≥q[n/pi]∏ i≥0 (Ni!)p(mod pq). Định lý 2.3.3. Cho pq là một lũy thừa của số nguyên tố p, n> m là hai số nguyên dương, và r = n−m. Giả sử n= n0+n1p+ · · ·+nsps là biểu diễn của n trong cơ số p. Với mỗi j ≥ 0, ta ký hiệu N j là số dư của b np j c (mod pq) (tức là N j = n j+ n j+1p+ · · ·+ n j+q−1pq−1). Định nghĩa tương tự cho m j,M j,r j,R j. Gọi e j là số các phép nhớ khi cộng m và r theo cơ số p, kể từ chỉ số thứ j trở đi. Khi đó ta có 1 pe0 ( n m ) ≡ (±1)eq−1 (N0!)p (M0!)p(R0!)p (N1!)p (M1!)p(R1!)p · · · (Nd!)p (Md!)p(Rd!)p (mod pq), với (±1) bằng −1 trừ khi p= 2 và q≥ 3. Chứng minh. Bằng cách áp dụng Định lý 2.3.1 cho n, m và r, ta được n! pvp(n!) = δ∑i≥q[n/p i]∏ i≥0 (Ni!)p(mod pq), m! pvp(m!) = δ∑i≥q[m/p i]∏ i≥0 (Mi!)p(mod pq), r! pvp(r!) = δ∑i≥q[r/p i]∏ i≥0 (Ri!)p(mod pq). Hiển nhiên rằng m! pvp(m!) và r! pvp(r!) không chia hết cho p. Áp dụng Bổ đề 2.2.2 (hai lần), ta suy ra pvp(m!)pvp(r!) vp(n!) n! m!r! ≡ δ ∑i≥q[n/pi] δ∑i≥q[m/pi]δ∑i≥q[n/pi] N0! M0!R0! N1 M1!R1! · · · Ns! Ms!Rs! (mod pq). Từ định nghĩa của ei và công thức Legendre, ta suy ra e0= vp(n!)−vp(m!)− 24 vp(r!) và eq−1 = ∑i≥q[n/pi]− [m/pi]− [r/pi]. Do vậy, ta có 1 pe0 ( n m ) ≡ δ eq−1 (N0!)p (M0!)p(R0!)p (N1!)p (M1!)p(R1!)p · · · (Nd!)p (Md!)p(Rd!)p (mod pq). 2.4 Ví dụ ứng dụng Định lý Lucas phát biểu rằng nếu p là một số nguyên, m,n,m0,n0 là các số nguyên không âm với m0,n0 ≤ p−1 thì ta có( np+n0 mp+m0 ) ≡ ( n m )( n0 m0 ) (mod p) (với quy ước rằng (0 0 ) = 1 và (l r ) = 0 nếu l< r). Năm 1990, Bailey [1][Theorem 3] chứng minh rằng với giả thiết như trên thì ta có thể thay p bởi p2, tức là ta có kết quả sau. Định lý 2.4.1. Cho p là một số nguyên tố, m≤ n và m0,n0 là các số nguyên không âm với m0,n0 ≤ p−1. Khi đó ta có( np2+n0 mp2+m0 ) ≡ ( n m )( n0 m0 ) (mod p2). Trong mục này chúng tôi sẽ trình bày chứng minh định lý này của Bailey ứng dụng một số kết quả trong các phần trước của luận văn. Chứng minh. Ta biểu diễn n,m, np2+n0, (mp2+m0) và np2+n0−(mp2+ m0) theo cơ số p: n= nsns−1 · · ·n2 m= msms−1 · · ·m2 N = np2+n0 = nsns−1 · · ·n20n0 M = mp2+m0 = msms−1 · · ·m20m0 R= np2+n0− (mp2+m0) = rsrs−1 · · ·r2r1r0. Ta xét các trường hợp sau. 25 TH1: n0 < m0. Khi đó (n0 m0 ) = 0. Ta cũng có phép cộng M và R trong cơ số p cấn ít nhất 2 phép nhớ (phép nhớ tại vị trí hàng đơn vị và hàng chục). Do đó theo Định lý Kummer ta có( N M ) ≡ 0= ( n m )( n0 m0 ) (mod p2). TH 2: n0≥m0. Khi đó a có r1= 0 và biểu diễn trong cơ số p của r := n−m chính là r = rsrs−1 · · ·r2. Gọi k là số phép nhớ khi cộng r với m trong cơ số p. Khi đó k cũng là số phép nhớ khi cộng trong cộng M với R trong cơ số p. Nếu k ≥ 2, thì theo Định lý Kummer ta có( N M ) ≡ 0≡ ( n m )( n0 m0 ) (mod p2). Nếu k= 1, thì theo Định lý 2.2.1 (áp dụng cho hai cặp (N,M) và (n,m)), ta có( N M ) ≡ (−1)p ( n0! m0!r0! )( 0! 0!0! )( n2! m2!r2! ) · · · ( ns! ms!rs! ) (mod p2) ≡ ( n0! m0!r0! ) (−1)p ( n2! m2!r2! ) · · · ( ns! ms!rs! ) (mod p2) ≡ ( n0 m0 )( n m ) (mod p2). Nếu k = 0, thì Định lý 2.3.3 (áp dụng hai lần), ta có( N M ) ≡ (0ns!)p (0ms!)p(0rs!)p (nsns−1!)p (msms−1!)p(rsrs−1!)p · · · (n3n2!)p (m3m2!)p(r3r2!)p (n20!)p (m20!)p(r20!)p (0n0!)p (0m0!)p(0r0!)p (mod p2) ≡ ( n m ) (pn2!)p (pm2!)p(pr2!)p ( n0 m0 ) (mod p2). 26 Như vậy ta chỉ cần chứng minh ((pn2)!)p ((pm2)!)p((pr2)!)p ≡ 1(mod p2). Ta có (pn2)!= ((pn2)!)ppn2n2!. Ta có các đẳng thức tương tự cho m2 và r2. Chú ý rẳng n2 = m2+ r2 vì k = 0. Do vậy( pn2 pm2 ) = ((pn2)!)p ((pm2)!)p((pr2)!)p ( n2 m2 ) . Từ Bài tập 8 (Chương 1), ta có 0≡ ( pn2 pm2 ) − ( n2 m2 ) = ( ((pn2)!)p ((pm2)!)p((pr2)!)p −1 )( n2 m2 ) (mod p2). Rõ ràng (n2 m2 ) và p nguyên tố cùng nhau (vì 0 ≤ m2 ≤ n2 ≤ p−1). Do vậy ((pn2)!)p ((pm2)!)p((pr2)!)p ≡ 1(mod p2), điều phải chứng minh. 27 Chương 3 Định lý Wolstenholme Trong chương này chúng tôi trình bày về Định lý Babbage, Định lý Wol- stenholme và Định lý Jacobsthal. Các định lý phát biểu sau là các mở rộng của định lý phát biểu trước đó. Tuy nhiên chúng tôi không chỉ trình bày chứng minh cho định lý tổng quát nhất (Định lý Jacobsthal), mà sẽ trình bày chứng minh chứng minh của tất cả các định lý này. Có hai lý do chính cho việc này. Thứ nhất chúng tôi nghĩ rằng nếu bạn đọc chỉ quan tâm đến một định lý cụ thể trong những định lý trên, thì có thể đọc trực tiếp chứng minh định lý này mà không cần quan tâm đến định lý sau đó. Thứ hai, các chứng minh định lý sau sẽ là việc làm mịn hơn các kỹ thuật của chứng minh định lý dễ hơn trước đó. Chúng tôi hy vọng việc trình bày các chứng minh định lý yếu hơn sẽ làm cho việc đọc hiểu chứng minh của các định lý tổng quát hơn (chẳng hạn Định lý Jacobsthal) một cách dễ dàng hơn. 3.1 Định lý Wolstenholme Với mọi số nguyên dương n = n0+ n1p+ · · ·+ ndpd, 0 ≤ ni ≤ p− 1, theo Định lý Lucas ta có (np p )≡ n0 ≡ n(mod p). Nói riêng, ta có (2pp )≡ 1(mod p). Năm 1819, Babbage chỉ ra rằng (2p p ) ≡ 2(mod p2) với mọi số nguyên tố p≥ 3. Định lý 3.1.1 (Babbage). Cho p≥ 3 là một số nguyên tố. Khi đó( 2p p ) ≡ 2(mod p2). 28 Ta sẽ chứng minh định lý này. Định nghĩa 3.1.2. Cho hai số hữu tỷ a và b. Ta nói a ≡ b(mod ps) nếu số hữu tỷ a−b ps ở dạng thu gọn có tử số không chia hết cho p. Với mỗi n≥ 1, đặt H(n) = 1+ 1 2 + · · ·+ 1 n . Bổ đề 3.1.3. Cho p≥ 3 là một số nguyên tố. Khi đó H(p−1) = 1+ 1 2 + · · ·+ 1 p−1 ≡ 0(mod p). Chứng minh. Ta có 2H(p−1) = p−1 ∑ i=1 ( 1 i + 1 p− i ) = p−1 ∑ i=1 ( p i(p− i) ) = p p−1 ∑ i=1 1 i(p− i) = p A (p−1)! , ở đây A là một số tự nhiên. Ta viết H(p−1) = M N ở dạng tối giản. Khi đó pAN = 2(p−1)!M. Do đó p chia hêt 2(p−1)!M, nhưng (p,2(p−1)!) = 1. Suy ra M ≡ 0(mod p), điều phải chứng minh. Chứng minh Định lý Babbage. Điều cần phải chứng minh tương đương với khẳng định ( 2p−1 p−1 ) ≡ 1(mod p2). 29 Ta sẽ chứng minh khẳng định này. Ta có( 2p−1 p−1 ) = (p+1)(p+2) · · ·(2p−1) 1 ·2 · · ·(p−1) = p+1 1 p+2 2 · · · 2p−1 p−1 = (1+ p) ( 1+ p 2 ) · · · ( 1+ p p−1 ) = 1+ p p−1 ∑ i=1 1 i (mod p2) Theo Bổ đề 3.1.3, ta có H(p−1) = p−1 ∑ i=1 1 i ≡ 0(mod p). Do đó ( 2p−1 p−1 ) ≡ 1(mod p2), điều phải chứng minh. Năm 1862, Wolstenholme đưa ra kết quả sau. Định lý 3.1.4 (Wolstenholme). Cho p≥ 5 là một số nguyên tố. Khi đó( 2p p ) ≡ 2(mod p3). Ta sẽ chứng minh Định lý này. Ta cần một số bổ đề sau. Bổ đề 3.1.5. Cho p≥ 5 là số nguyên tố. Khi đó 1+ 1 22 + 1 32 + · · ·+ 1 (p−1)2 ≡ 0(mod p). Chứng minh. Vì p 6= 2, nên hai tập sau là trùng nhau {số dư của 2i cho p | i= 1,2, . . . , p−1}= {1,2, . . . ,