NCGVuong201303pdf

<span class='text_page_counter'>(1)</span>Số học của hệ số nhị thức Nguyễn Chu Gia Vượng Viện Toán học. Bài giảng Trường xuân Toán học 3/2013. Ta sẽ trình bày một số kết quả đáng lưu ý về số học của các hệ số nhị thức.. 1. Lũy thừa của một số nguyên tố trong hệ số nhị thức. Ta bắt đầu bằng một kết quả quen thuộc sau đây. Định lý 1 (De Polignac). Cho p là một số nguyên tố. Lũy thừa (cao nhất) của p trong n! được cho bởi X n  vp (n!) = . (1) pk k≥1. Chứng minh. Đây là một bài toán đơn giản về việc đếm các lũy thừa của p không vượt quá n. Ta lưu ý rằng các hạng tử của vế phải trong đẳng thức trên gợi ý một mối liên quan tới biểu diễn theo cơ số p của n. Thật vậy, Định lý 2 (Legendre, 1808). Ta viết n = n0 + n1 p + · · · + ns ps , 0 ≤ ni ≤ p − 1, ∀i. Khi đó, vp (n!) =. n − (n0 + · · · + ns ) . p−1. Chứng minh. Vì n = n0 + n1 p + · · · + ns ps ,   n p   n p2  · ·· n ps. = ns ps−1 + · · · + n1 = ns ps−2 + · · · + n2 = ··· = ns .. Như vậy, theo công thức De Polignac ta có. 1. (2).

<span class='text_page_counter'>(2)</span>     n n + ··· + s vp (n!) = p p = ns (ps−1 + · · · + 1) + ns−1 (ps−2 + ps−3 + · · · + 1) + · · · + n1 ps − 1 p−1 = ns + · · · + n1 p−1 p−1 s s−1 ns p + ns−1 p + · · · + n1 − ns − ns−1 − · · · − n1 = p−1 s s−1 ns p + ns−1 p + · · · + n1 + n0 − ns − ns−1 − · · · − n1 − n0 = p−1 n − (n0 + n1 + · · · + ns ) = . p−1. Một câu hỏi tự nhiên được đặt ra là tìm công thức tính vp ( được cho bởi kết quả sau.. m n.
. ) với m, n bất kì. Câu trả lời. Định lý 3 (Kummer,
1852). Cho m ≥ n là hai số nguyên dương và p là một số nguyên tố. Lũy thừa của p trong m n bằng số lần nhớ khi thực hiện phép cộng m − n và n trong hệ cơ số p. Ta sẽ lưu ý phát biểu tương đương sau đây của Định lý Kummer, đôi khi khá thuận tiện trong các áp dụng về sau.
Hệ quả 4. Lũy thừa của p trong m n bằng số lần nhớ khi thực hiện phép trừ m cho n trong hệ cơ số p. Chứng minh. Ta dựa vào công thức Legendre ở trên. Đặt k = m−n và viết n = n0 +n1 p+· · ·+ns ps , k = k0 + k1 + · · · + ks ps trong đó 0 ≤ ni , ki ≤ p − 1, ns + ks > 0. Gọi σ(n) là tổng các hệ số trong cách viết p-phân của n, như vậy σ(n) = n1 + · · · + ns và định nghĩa tương tự cho σ(k), σ(m). Ta mã hóa các phép nhớ bằng cách định nghĩa các số 0 , . . . , s ∈ {0, 1} như sau. n0 + k0 = 0 p + m0 0 + n1 + k1 = 1 p + m1 ··· = ··· s−1 + ns + ks = s p + ms .. Lưu ý rằng ta không khẳng định m = m0 + m1 p + · · · + ms ps . Thật ra, nhân hai vế của mỗi đẳng thức trên với 1, p, . . . , ps tương ứng rồi cộng lại ta được n + k + 0 p + 1 p2 + · · · + s−1 ps = 0 p + 1 p2 + · · · + s−1 ps + s ps+1 + m0 + m1 p + · · · + ms ps ⇔ m = n + k = m0 + m1 p + · · · + ms ps + s ps+1 . Nói riêng σ(m) = m1 + · · · + ms + s . Mặt khác, cộng tất cả các đẳng thức trên lại ta được. 2.

<span class='text_page_counter'>(3)</span> σ(n) + σ(k) + (0 + · · · + s−1 ) = (0 + · · · + s )p + (m0 + m1 + · · · + ms ) ⇔ σ(n) + σ(k) + (0 + · · · + s−1 ) = (0 + · · · + s )p + σ(m) − s ⇔ σ(n) + σ(k) − σ(s) = (p − 1)(0 + · · · + s ) Cuối cùng, công thức Legendre ở trên ta có   m m − σ(m) − (n − σ(n) + k − σ(k)) (p − 1)(0 + . . . + s ) = vp = = 0 + · · · + s . n p−1 p−1 Đây chính là điều cần chứng minh. Nhận xét 1. Với cùng chứng minh trên ta có thể mở rộng Định lý Kummer cho các đa hệ số: lũy r )! thừa của p trong (n1n+···+n bằng số các nhớ khi thực hiện phép cộng n1 + · · · + nr qua cách viết 1 !···nr ! p-phân.. 2. Phần dư của hệ số nhị thức modulo một số nguyên tố.
Khi p - m n , định lý Kummer không cho ta giá trị cụ thể của phần dư của này được giải quyết qua kết quả sau.. m n.
. khi chia cho p. Điều. Định lý 5 (Lucas, 1878). Cho m, n là hai số nguyên dương và p là một số nguyên tố. Gọi m0 , n0 tương ứng là các số dư của m, n khi chia cho p. Ta có      m [m/p] m0 ≡ (mod p). (3) n [n/p] n0
Nhận xét 2. Ta qui ước m n = 0 nếu m < n. Bằng cách viết m = m0 + m1 p + · · · + ms ps , n = n0 + n1 p + · · · + ns ps , Định lý Lucas được phát biểu một cách tương đương như sau. Định lý 6 (Lucas). Ta có       m ms m0 ≡ ··· (mod p). n ns n0. (4). Có khá nhiều chứng minh định lý Lucas được biết đến, nói chung gồm hai loại: đại số và tổ hợp. Ta trình bày ở đây một chứng minh đại số và hai tổ hợp. Chứng minh đại số của Định lý Lucas. Chú ý rằng r. r. (X + 1)p ≡ X p + 1 Như vậy, nếu ta viết m = m0 + m1 p + · · · + ms ps thì. 3. (mod p).

<span class='text_page_counter'>(4)</span> m   s X Y m r n m X = (X + 1) ≡ (X + 1)p mr n. n=0. ≡. r=0 s Y. r. (X p + 1)mr. r=0 s Y. !  mr  X mr r X mr p ≡ nr r=0 nr =0  n Y s  X mr X n (mod p) ≡ nr m=0 r=0. Và ta suy ra điều phải chứng minh. Chứng minh tổ hợp thứ nhất của Định lý Lucas. Trường hợp n > m là hiển nhiên. Ta xét m ≥ n. Ta bỏ m quả bóng vào σ(m) = m0 + m1 + · · · + ms chiếc hộp: bỏ một quả bóng vào mỗi hộp trong m0 hộp đầu tiên, p quả bóng vào mỗi hộp trong m1 hộp tiếp theo, v.v, bỏ ps quả bóng vào mỗi hộp trong ms hộp cuối cùng. Ta xét
các cách lấy n quả bóng từ m quả bóng này. Tổng số cách chọn ra n quả bóng rõ ràng bằng m n . Mặt khác, do m quả bóng được xếp trong σ(m) hộp, mỗi cách chọn ra n quả bóng tương ứng một với một cách viết n = k1 + · · · + kσ(m) sao cho với mỗi i, 0 ≤ ki ≤ pi . Ở đây, ta yêu cầu chọn ra ki quả bóng từ hộp thứ i. s
Bổ đề 1. Cho s ≥ 1. Ta có p | pk khi và chỉ khi 1 < k < ps . s. s. Chứng minh Bổ đề. Điều này đơn giản được suy ra từ đẳng thức (1 + X)p ≡ 1 + X p mod p. Ta cố định một cách viết n = k1 + · · · + kσ(m) như trên. Theo bổ đề trên, với mọi i, nếu 0 < ki < pi thì số cách chọn ra ki quả bóng từ hộp thứ i chia hết của p. Như vậy, số dư khi chia cho p của các cách chọn n quả bóng trong số m quả bóng bằng số dư khi chia cho p của các cách chọn có dạng như sau: n = k1 + · · · + kσi thỏa mãn với mỗi i, ki = 0 hoặc pi . Mỗi cách chọn như vậy thật ra tương ứng với các cách chọn các hộp: ta cho tương ứng một cách chọn với ni = pi với cách chọn ra hộp thứ i. Nghĩa là mỗi cách chọn n bóng có dạng như đã miêu tả ở trên tương ứng với một cách chọn ra h0 hộp trong số m0 hộp đầu tiên, h1 hộp trong số m1 hộp tiếp theo, v.v. Nhưng khi đó n = h0 + h1 p + · · · + hs ps và do 0 ≤ hi ≤ mi ≤ p −
1 nên
h0 = n0 , . . . , hs = ns . Ta suy ra số các cách chọn n bóng có dạng m0 s như vậy chính bằng m · · · ns n0 và ta có điều phải chứng minh. Một chứng minh tổ hợp khác của Định lý Lucas. Ta bắt đầu bằng một bổ đề đơn giản. Bổ đề 2. Cho p là một số nguyên tố, S là một tập hữu hạn và f : S → S là một ánh xạ thỏa mãn f p (x) = x với mọi x ∈ S (ở đây f p = f ◦ f ◦ · · · ◦ f là hợp thành p lần của f ). Khi đó ta có |S| ≡ |S f | (mod p) với S f là tập các điểm bất động của f .. 4.

<span class='text_page_counter'>(5)</span> Chứng minh Bổ đề. Thật vậy ta có S = ∪x∈S {x, f (x), . . . , f p−1 (x)}. Bởi vì p là nguyên tố, mỗi tập {x, f (x), . . . , f p−1 (x)} hoặc có một (nếu x ∈ S f ) hoặc có p phần tử (nếu x ∈ / S f ) và ta suy ra điều cần chứng minh. Chứng minh Định lý 5. Để thuận tiện, ta đặt q = [m/p], r = [n/p] sao cho m = qp+m0 , n = rp+n0 . Gọi S là tập các cặp (A, v) trong đó A là một ma trận p × q với hệ số 0 hoặc 1 và v là một vector m0 × 1 với hệ số 0 hoặc 1 sao cho trong m = pq + m0 hệ số của A, v có đúng n = rp + n0 hệ số bằng 1. Như vậy   m |S| = . n Gọi M = (mi,j )1≤i,j≤p là ma trận hoán vị cấp p định nghĩa bởi m1,p = m2,1 = m3,2 = · · · = mp,p−1 = 1 còn tất cả các hệ số khác đều bằng 0. Định nghĩa f : S → S bằng công thức f (A, v) = (M A, v). Chú ý rằng M A chính là ma trận nhận được từ A bằng cách đẩy mỗi hàng xuống ngay dưới (hàng 1 của M A bằng hàng p của A, hàng 2 của M A bằng hàng 1 của A, v.v.). Ta suy ra f p = f . Xét các điểm bất động của f . Một phần tử (A, v) ∈ S f khi và chỉ khi tất cả các hàng của A đều giống nhau và gồm r hệ số 1 và v chứa đúng n0 hệ số 1. Như vậy,    q m0 f |S | = . r n0 Cuối cùng, ta có thể kết luận dựa vào Bổ đề ở trên.. 3. Hệ số nhị thức modulo một lũy thừa của một số nguyên tố. Việc xác định đồng dư của một hệ số nhị thức modulo một số nguyên bất kì là một vấn đề khó. Dựa vào Định lý thặng dư Trung Hoa, điều này được đưa về trường hợp xác định modulo các lũy thừa của các số nguyên tố. Ta lưu ý một số kết quả sau liên quan đến việc xác định công thức cho phần dư của một hệ số nhị thức modulo pk với k > 1. Định lý 7 (Wolstenholme, 1862). Với mọi số nguyên tố p ≥ 5,   2p − 1 ≡ 1 (mod p3 ). p−1
Nhận xét 3. 1. Chú ý rằng đẳng thức 2p−1 ≡ 1 (mod p) là một hệ quả của định lý Wilson, p−1
2p−1 2 trong khi đó đẳng thức p−1 ≡ 1 (mod p ) (với mọi p ≥ 3) đã được thiết lập bởi Babbage (1818).
3 2. Kết quả trên còn có thể được phát biểu một cách tương đương thành 2p p ≡ 2 (mod p ). 3. Định lý Wolstenholme còn có thể phát biểu một cách tương đương dưới dạng các chuỗi điều 1 ) ≥ 2. Nói một cách khác tử số của phân hòa: với mọi p ≥ 5 nguyên tố vp (1 + p1 + · · · + p−1 1 1 2 thức 1 + p + · · · + p−1 luôn chia hết cho p . Định lý Wolstenholme có thể được mở rộng như sau. 5.

<span class='text_page_counter'>(6)</span> Định lý 8 (Ljunggren, 1952). Với mọi p nguyên tố ≥ 5, với mọi m, n nguyên dương,     mp m ≡ (mod p3 ). np n Hoặc dưới dạng phức tạp hơn một chút như sau. Định lý 9 (Jacobstal, 1952). Với mọi p nguyên tố ≥ 5, với mọi m > n nguyên dương,
mp np
m n. ≡ 1 (mod pt ),. trong đó t là lũy thừa của p trong p3 mn(m − n). Cuối cùng, ta lưu ý kết quả sau đây. Định lý 10 (Morley 1895.). Với mọi số nguyên tố p ≥ 5,   p−1 p−1 (−1) 2 ≡ 4p−1 (mod p3 ). p−1 2. 6.

<span class='text_page_counter'>(7)</span> Số học của hệ số nhị thức 1 Ngày 29/3/2013 Trường Xuân Toán học 2013. NCG. Vượng.
1. Cho p là một số nguyên tố. Chứng minh rằng với mọi 0 ≤ n ≤ p − 1, p−1 ≡ (−1)n n
s (mod p). Một cách tổng quát hơn, nếu 0 ≤ n ≤ ps − 1 thì p n−1 ≡ (−1)n (mod p). 2. Cho p là một số nguyên tố, và 0 ≤ n ≤ m ≤ p − 1 là hai số nguyên dương. Chứng minh rằng     m m+n p − n − 1 ≡ (−1) (mod p). n p−m−1 3. Cho p là một số nguyên tố lẻ. Chứng minh rằng với mọi 0 ≤ n ≤. p−1 2. thì.    p−1  2n n 2 ≡ (−4) (mod p). n n 4. Chứng minh rằng             n−1 n n+1 n−1 n n+1 , , = , , . k k−1 k+1 k−1 k+1 k ((a, b, c) kí hiệu ước chung lớn nhất của a, b, c). 5. Cho p là một số nguyên tố. Chứng minh rằng  p   X p p+k k=0. k. k. ≡ 2p + 1. (mod p2 ).. 6. Cho các số nguyên dương a1 , a2 , . . . , ak , (k ≥ 1). Gọi d là ước số chung lớn nhất của chúng và n = a1 + · · · + ak . Chứng minh rằng d. (n − 1)! a1 ! · · · ak !. là một số nguyên. 7. Chứng minh rằng với mọi số nguyên tố p ≥ 5, X p ≡1 k 2p. 0≤k<. 3. 1. (mod p2 )..

<span class='text_page_counter'>(8)</span> 8. Cho m, n là các số nguyên dương với m lẻ. Chứng minh rằng m. 3 n|.  m  X 3m 3k. k=0. (3n − 1)k. 9. Chứng minh rằng với mọi số nguyên dương m,  2|.    3m 3m ⇔4| . m m. 10. (VN TST 10) Gọi Sn là tổng các bình phương các hệ số của biểu thức (1 + x)n . Chứng minh rằng S2n + 1 không chia hết cho 3.. 2.

<span class='text_page_counter'>(9)</span> Số học của hệ số nhị thức 2 Ngày 31/3/2013 Trường Xuân Toán học 2013. NCG. Vượng. 1. Chứng minh rằng với mọi p nguyên tố ≥ 3 ta có   2p − 1 ≡1 p−1. (mod p2 ).. 2. Cho p là một số nguyên tố ≥ 3. Chứng minh rằng với mọi số nguyên dương m ≥ n ta luôn có     mp m ≡ (mod p2 ). np n 3. Cho p là một số nguyên tố ≥ 5. Chứng minh rằng   2p − 1 ≡1 p−1. (mod p3 ).. 4. Cho số nguyên tố p ≥ 5 và các số nguyên dương m, n . Chứng minh rằng
(a) mp ≡ m (mod p3 ); p

m (b) mp ≡ (mod p3 ). np n 5. Chứng minh rằng với mọi số nguyên n ≥ 2, ta có . 2n+1 2n. .  ≡. 2n 2n−1. . (mod 22n+2 ).. 6. Cho p là một số nguyên tố và m là một số nguyên dương. Chứng minh rằng X 1≤n≤m;p−1|n.   m ≡0 n. (mod p).. 7. Cho p là một số nguyên tố và các số nguyên dương m, m0 , n0 thỏa mãn m0 , n0 ≤ p − 1, m ≡ m0 (mod p − 1). Chứng minh rằng X 1≤n≤m;n≡n0. (mod p−1).     m m0 ≡ (mod p). n n0. 8. (IMO 08-Shortlist) Cho số nguyên n > 1. Chứng minh rằng các số 0, . . . , 2n−1 − 1 có số dư đôi một khác nhau khi chia cho 2n . 1. 2n −1 k.
,k =.

<span class='text_page_counter'>(10)</span>