Tài liệu Một số tính chất số học của hệ số nhị thức (Luận văn thạc sĩ)

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC BÙI THỊ THỦY MỘT SỐ TÍNH CHẤT SỐ HỌC CỦA HỆ SỐ NHỊ THỨC LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2016 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC BÙI THỊ THỦY MỘT SỐ TÍNH CHẤT SỐ HỌC CỦA HỆ SỐ NHỊ THỨC LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60 46 01 13 NGƯỜI HƯỚNG DẪN KHOA HỌC TS. NGUYỄN DUY TÂN Thái Nguyên - 2016 i Mục lục Lời nói đầu 1 1 Định lý Kummer và Định lý Lucas 4 1.1 Định lý Kummer . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Hệ quả . . . . . . . . . . . . . . . . . . . . . . . 4 6 1.2 Định lý Lucas . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Hệ quả . . . . . . . . . . . . . . . . . . . . . . . 6 8 2 3 Hệ số nhị thức modulo lũy thừa nguyên tố 15 2.1 Mở rộng của định lý Wilson . . . . . . . . . . . . . . . . 15 2.2 2.3 Một mở rộng của định lý Lucas . . . . . . . . . . . . . . . Hệ số nhị thức modulo lũy thừa nguyên tố . . . . . . . . . 18 21 2.4 Ví dụ ứng dụng . . . . . . . . . . . . . . . . . . . . . . . 24 Định lý Wolstenholme 3.1 Định lý Wolstenholme . . . . . . . . . . . . . . . . . . . 27 27 3.2 31 Mở rộng của Định lý Wolstenholme . . . . . . . . . . . . Kết luận 38 Tài liệu tham khảo 39 1 Lời nói đầu Đồng dư số học là một chủ đề cổ điển nhưng vẫn luôn ẩn chứa nhiều kết quả đẹp đẽ và sâu sắc, thu hút nghiên cứu của các nhà toán học. Tính chất đồng dư của hệ số nhị thức là một trong số đó. Khởi đầu từ phát biểu của nhà toán học người Đức Ernst Kummer trong bài báo "Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen" công bố năm 1852, người ta bắt đầu quan tâm đến đồng dư theo modulo nguyên tố của hệ số nhị thức, và ý nghĩa của nó theo biểu diễn trong cơ số nguyên tố đó. Nếu như phát biểu của Kummer nghe còn tương đối mơ hồ thì đến năm 1878, nhà toán học Pháp Édouard Lucas trong serie bài báo đăng trên American Journal of Mathematics, Théorie des Fonctions Numériques Simplement Périodiques, đã phát biểu một cách tường minh cho mối liên hệ đồng dư theo modulo nguyên tố của hệ số nhị thức với tích các hệ số nhị thức tạo thành từ các chữ số trong biểu diễn của các thành phần trong hệ số nhị thức theo cơ số của chính số nguyên tố ấy. Không chỉ dừng lại ở việc là một phát biểu tường minh, kết quả của Lucas còn làm tiền đề và tạo cảm hứng cho những mở rộng đầu tiên của Anton (1969), Stickelberger (1890) và Hensel (1902). Vẫn dựa trên biểu diễn của các thành phần trong hệ số nhị thức theo cơ số nguyên tố, họ xem xét tính chất đồng dư theo cơ số nguyên tố của hệ số nhị thức sau khi chia cho lũy thừa bậc cao nhất của số nguyên tố chia hết nó. Đây là một kết quả đặc sắc, nhưng trong suốt hơn 112 năm từ sau Định lý Lucas, không có thêm một mở rộng nào nữa, cho tới khi Granville nâng modulo từ số nguyên tố thành lũy thừa của nó. Một hướng mở rộng khác của Định lý Lucas đó là loại bỏ biểu diễn theo cơ số nguyên tố mà liên kết trực tiếp số nguyên tố, các số thành phần trong hệ số nhị thức và bậc lũy thừa cao nhất chia hết hệ số nhị thức của 2 số nguyên tố đó. Bắt đầu từ kết quả của Charles Babbage (1819) - một mở rộng lên lũy thừa bậc hai cho một hệ quả đặc biệt của Định lý Lucas - sau đó Joseph Wolstenholme đã mở rộng chính kết quả này lên bậc ba. Được gợi ý từ những kết quả này, Ljunggren (1949) đã chứng minh một kết quả kiểu Lucas, rằng hệ số nhị thức của hai bội của một số nguyên tố sẽ đồng dư với chính hệ số nhị thức gồm hai thành phần thu được sau khi chia các bội cho số nguyên tố kia, theo modulo lũy thừa bậc ba của số nguyên tố đó. Kết quả cuối cùng của E. Jacobsthal mở rộng chính kết quả của Ljunggren lên lũy thừa bậc cao hơn. Luận văn có cấu trúc như sau: Mở đầu, ba chương, Kết luận và Tài liệu tham khảo Chương 1: Định lý Kummer và Định lý Lucas Chương này phát biểu và chứng minh hai định lý trên, kèm theo các hệ quả, chứng minh của chúng và một số bài tập ứng dụng. Chương 2: Hệ số nhị thức modulo lũy thừa nguyên tố Chương này trình bày hai mở rộng của Định lý Wilson, một mở rộng của Định lý Lucas và cuối cùng là kết quả của Granville về hệ số nhị thức modulo lũy thừa nguyên tố. Chương 3: Định lý Wolstenholme Trình bày các kết quả về đồng dư của hệ số nhị thức với thành phần nguyên tố modulo lũy thừa nguyên tố, từ kết quả của Charles Babbage, tới Định lý Wolstenholme và mở rộng của nó là Định lý Ljunggren. Luận văn này được thực hiện và hoàn thành vào tháng 6 năm 2016 tại trường Đại học Khoa học- Đại học Thái Nguyên. Qua đây, tác giả xin bày tỏ lòng biết ơn sâu sắc tới TS Nguyễn Duy Tân, người đã tận tình hướng dẫn trong suốt quá trình làm việc để hoàn thành luận văn này. Tác giả xin gửi lời cảm ơn chân thành đến Khoa Toán, Trường Đại học Khoa học- Đại học Thái Nguyên, đã tạo mọi điều kiện để giúp tác giả học tập và hoàn thành luận văn cũng như chương trình thạc sĩ.Tác giả cũng xin gửi lời cảm ơn tới tập thể lớp cao học YB, khóa 06/2014 - 06/2016 đã động viên giúp đỡ tác giả trong quá trình học tập và hoàn thành luận văn này.Đồng thời tác giả 3 xin gửi lời cảm ơn tới Sở GD-ĐT tỉnh Yên Bái, Ban giám hiệu và các đồng nghiệp tại trường THPT Sơn Thịnh đã tạo điều kiện cho tác giả trong suốt quá trình học tập và hoàn thành luận văn. Tác giả Bùi Thị Thủy 4 Chương 1 Định lý Kummer và Định lý Lucas Trong chương này chúng ta sẽ giới thiệu Định lý Kummer và Định lý Lucas, các phép chứng minh cùng với các ví dụ minh họa và một số bài tập ứng dụng của hai định lý. 1.1 Định lý Kummer Năm 1852, nhà toán học Đức Ernst Kummer trong bài báo "Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen" đã chỉ ra rằng Định lý 1.1.1 (Kummer). Cho p là một số nguyên tố, m ≤ n là hai số tự nhiên. Khi đó, số tự nhiên k lớn nhất sao cho pk là ước của hệ số nhị thức n
m là số các lần nhớ khi cộng m và n − m theo cơ số p. Gọi bxc là phần nguyên của số thực x. Cho p là số nguyên tố. Ta ký hiệu v p (n) cho số mũ của lũy thừa cao nhất của p chia hết n, σ p (n) là tổng các chữ số của n khi viết theo cơ số p. Bổ đề 1.1.2 (Legendre). Cho n ≥ 1 là số tự nhiên và p là số nguyên tố. Khi đó n − σ p (n) n . v p (n!) = ∑ b i c = p p − 1 i≥1 Chứng minh. Vì n! là tích tất cả các số tự nhiên từ 1 đến n nên với mỗi bội n của p trong các số từ 1 đến n ta được một thừa số p và do vậy có đúng b c. p n 2 Tương tự, từ mỗi bội của p , ta có thêm b 2 c thừa số p... Do đó lũy thừa p n cao nhất của p chia hết n! sẽ bằng ∑i≥1 b i c. p 5 Giả sử n = n0 + n1 p + ... + nt pt là biểu diễn của n theo cơ số p. Khi đó ta có   t n v p (n!) = ∑ b i c = ∑ (nt pt−i + · · · + ni+1 p + ni ) p i=1 i≥1 t t t = ∑ ∑ njp = j−i i=1 j=i t pj −1 ∑ nj p−1 = = j=1 = 1 p−1 j ∑ ∑ n j p j−i j=1 i=1 t pj −1 ∑ nj p−1 j=0 t ∑ (n j p j − n j ) = j=0 n − σ p (n) . p−1 Chứng minh Định lý Kummer. Giả sử rằng n = m+r. Ta viết ba số này theo cơ số p: n = n0 + n1 p + · · · + nt pt , tương tự cho m và r . Đặt ε j = 1 nếu khi cộng m và r theo cơ số p có nhớ ở chữ số thứ j, và ε j = 0 nếu không có nhớ. Dễ thấy rằng n0 = m0 + r0 − pε0 và n j = m j + r j + ε j−1 − pε j với mỗi j ≥ 1. Khi đó, theo công thức trên ta có   n vp = v p (n!) − v p (m!) − v p (r!) m n − σ p (n) m − σ p (m) r − σ p (r) = − − p−1 p−1 p−1 t mj +rj −nj σ p (m) + σ p (r) − σ p (n) = =∑ p−1 p−1 j=0 = pε0 + ∑tj=1 pε j − ε j−1 p−1 t = ∑ ε j. j=0 chính là số các phép nhớ khi cộng m và n − m theo cơ số p. Chứng minh hoàn tất. Ví dụ 1.1.3. Lấy n = 32, m = 18. Biểu diễn theo cơ số p = 5 ta có 32 = 1125 , 18 = 335 , 14 = 245 Dễ thấy rằng phép cộng 335 + 245 có hai lần nhớ. 6 Mặt khác 32
2 18 = 471435600 = 5 .18877424, do vậy v p   32
18 = 2, cũng chính bằng số lần nhớ ở trên. 1.1.1 Hệ quả Dưới đây là một số hệ quả của Định lý Kummer.
Hệ quả 1.1.4. Với n là một số nguyên dương, khi đó nk ≡ 0 ( mod n) nếu và chỉ với mọi ước nguyên tố p là một ước nguyên tố của n mà v p (n) = a, thì phép trừ n − k theo cơ số p cần ít nhất a phép mượn.
Chứng minh. Chú ý rằng nk ≡ 0 ( mod n) khi và chỉ khi n
k ≡0 ( mod pa ),
với mọi ước nguyên tố p của n với v p (n) = a. Theo Định lý Kummer, nk ≡ 0( mod pa ) khi và chỉ khi phép trừ n cho k trong cơ số p cần ít nhất a phép mượn. Hệ quả 1.1.5. Nếu m, n, k là các số nguyên dương thỏa mãn gcd(n, k) = 1
thì mn k ≡ 0 ( mod n). Chứng minh. Giả sử p là một ước nguyên tố bất kỳ của n với v p (n) = a. Ta viết k = k0 + k1 p + ... + kt pt trong cơ số p. Vì gcd(n, k) = 1 nên k0 6= 0. Chú ý rằng mn = mn0 pa với số nguyên n0 nào đó. Do đó phép trừ mn cho k theo
cơ số p phải có ít nhất là a phép nhớ. Theo Định lý Kummer ta có mn k ≡
mn 0 ( mod pa ). Vì p là ước nguyên tố bất kỳ của n nên k ≡ 0 ( mod n). 1.2 Định lý Lucas Năm 1878, Lucas đã đưa ra một phương pháp để tính Lucas phát biểu như sau n
m ( mod p). Định lý Định lý 1.2.1. Cho m, n là hai số tự nhiên, p là một số nguyên tố. Giả sử m, n có biểu diễn theo cơ số p dưới dạng m = m0 + m1 p + · · · + ms ps , n = n0 + n1 p + · · · + ns ps với 0 ≤ mi , ni ≤ p − 1, khi đó   s   n ni ≡∏ ( mod p) m i=0 mi 7 Ta 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 + a1 X + · · · + an X n ∈ 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). i i Bổ đề 1.2.3. Với i ≥ 0, ta có (1 + X) p ≡ 1 + X p ( 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) pi+1  p pi ≡ 1+X ( mod p) p−1   i+1 p pi k ≡ 1+ ∑ X + X p ( mod p) k=1 k ≡ 1+Xp vì ta có p | p
k i+1 ( mod p), với mọi k = 1, . . . , p − 1. Chứng minh Định lý Lucas. Ta có n   n s  n m n pi i X = (1 + X) = (1 + X) ∑ ∏ i=0 m=0 m ! ni   s s i i n i ≡ ∏(1 + X p )ni = ∏ ∑ X mi p ( mod p) i=0 mi =0 mi i=0 ! p−1   s i ni =∏ ∑ X mi p i=0 mi =0 mi ! n s   ni = ∑ ∏ X m ( mod p) m=0 i=0 mi Đồng nhất hệ số ở hai vế ta được n
ni
s ≡ ∏ i=0 mi m ( mod p). Ví dụ 1.2.4. Với n = 57, m = 32, p = 5, ta có n = 57 = 2125 , m = 32 = 1125 .
2
1
2
Dễ thấy 57 = 9929472283517787 ≡ 2 ( mod 5), còn 32 1 1 2 =2≡ 57
2
1
2
2 ( mod 5), do đó 32 ≡ 1 1 2 ( mod 5). 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 n r ≡ (mod p) mp + s m s Kết quả này ngay lập tức cho ta np
n
≡ mp m (mod p). Dễ dàng thấy rằng nếu n = n0 + n1 p + · · · + ns ps thì với mỗi k = 1, s, ta có   n n c ≡ nk (mod p). ≡ b pk pk
n Trong trường hợp đặc biệt với k = 1 ta có np ≡ b c (mod p). 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 ≡ (mod p). m
np
Chứng minh. Ta đã biết mp ≡ mn (mod p). npk
n
Giả sử mp ≡ k m (mod p) đúng với k nguyên dương nào đó. Ta sẽ chứng minh  k+1    np n ≡ (mod p). mpk+1 m Thật vậy, theo Định lý Lucas ta có   k npk+1 np ≡ (mod p). k+1 mp mpk  Kết hợp với giả thiết quy nạp, ta có điều phải chứng minh. 9 Mộ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 là 70 = 1. 500
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 1 1 0 0 0 1 1 ≡ ≡ 0( mod 2). 0 0 1 0 0 1 1 19 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 3 4 4 ≡ = 4( mod 5). 19 0 3 4 Do đó 99
19 ≡ 4( mod 10) và chữ số tận cùng của 99
19 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 - nk 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
p - n+1 k . n
k và p - n + 1, thì Chứng minh. Giả sử n = n0 + n1 p + · · · và k = k0 + k1 p + · · · 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 - nk 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 =
1 2n n+1 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ó   2n v p (n + 1) ≤ v p ( ). n Gọi l = v p (n + 1). Khi đó trong cơ số p, n + 1 có biểu diễn là n + 1 = as · · · a1 a0 0 · · · 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   2n v p( ) ≥ l = v p (n + 1). n 1 2k
. Chứng minh rằng ∑nk=1 Ck ≡ 1 ( mod 3) khi k+1 k 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. Bài tập 6. Đặt Ck = Chứng minh. Chú ý rằng         2n + 2 2n 2n + 1 2n 2n −4 =2 −4 = −2Cn . n+1 n n+1 n n Do đó Cn ≡ 2n+2
2n
− n+1 n ( mod 3). Bởi vậy n         2n + 2 2n 2n 2n − 2 ∑ Ck ≡ n + 1 − n + n − n − 1 + · · · k=1   2n + 2 = + 1 ( mod 3). n+1 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. n Giải. Ta có (1 + x)n = ∑ k=0 n
n k x . Do vậy  2   n 2n Sn = ∑ = . n k=0 k 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 = id id−1 · · · i0 3 và 2n = jd jd−1 · · · j0 3 . Theo 12 Định lý Lucas, ta có        id i1 4n i0 ··· (mod 3). = jd j1 2n j0 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ì d 2n = ∑ (ik − jk )3k = ∑ 3k k=0 k∈S là một số chẵn, nên số phần tử s của tập S là chẵn. Do vậy    k−s  s 4n 0 2 ≡ = 2s ≡ 1 2n 0 1 (mod 3).
Suy ra 4n 2n + 1 chia cho 3 dư 2. Như vậy ta đã chỉ ra rằng 3 luôn dư 1 hoặc 2. Đây là điều phải chứng minh. 4n
2n + 1 chia cho 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
n minh rằng p k−1 ≡ (−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−1
≡ (−1)k 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 p−1 ≡∏ ( mod p). k ki 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 ≡ ∏(−1)ki = (−1)∑ ki . Vì vậy k i pn −1
≡ (−1)σ p (k) ( mod p). k 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
2p−1
2q−1
≡ 1 ( mod pq) khi và chỉ khi ≡ 1 ( mod q) và pq−1 p−1 q−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 2q − 1 p−1 2q − 1 ≡ ≡ ( mod p). pq − 1 q−1 p−1 q−1 Tương tự ta có        2pq − 1 2p − 1 q − 1 2p − 1 ≡ ≡ ( mod q). pq − 1 p−1 q−1 p−1
2pq−1
Ta có 2pq−1 ≡ 1 (mod pq) khi và chỉ khi pq−1 pq−1
≡ 1 (mod p) và 2pq−1
2q−1 pq−1
≡ 1 (mod q), điều này lại tương đương với q−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
pn
minh rằng p2 | pm − mn . 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 p(n − 1) p p(n − 1) p = + pm pm 0 pm − 1 1       p(n − 1) p p(n − 1) p +···+ + . pm − p + 1 p−1 pm − 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 p(n − 1) p(n − 1) ≡ + ( mod p2 ). pm pm p(m − 1) Lùi vô hạn, ta có           p(n − 1) p(n − 1) n−1 n−1 n + ≡ + ≡ ( mod p2 ). pm p(m − 1) m m−1 m 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 + n1 p + · · · + ns ps . Khi đó n c (−1) p (n!) p ≡ n0 ! ( mod p). b Chứng minh. Ta thấy b np c−1 (n!) p = (kp + 1)(kp + 2) · · · (kp + p − 1)× k=0     n n n b cp + 1 b cp + 2 · · · b cp + n0 . p p p ∏ 16 Dễ thấy rằng (kp + 1)(kp + 2)...(kp + p − 1) ≡ (p − 1)! ( mod p), còn      n n n b cp + 1 b cp + 2 ... b cp + n0 ≡ n0 ! ( mod p). p p p Từ nhận xét này kết hợp với Định lý Wilson, ta có n c (−1) p (n!) p ≡ n0 ! ( mod p) b Định lý 2.1.2. Cho p là số nguyên tố, và n là số tự nhiên. Ta viết n = n0 + n1 p + · · · + ns ps trong cơ số p. Khi đó, ta có n! pv p (n!) = (−1)v p (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/p2 2 ] [n/p]! ≡ (−1)[n/p ] 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/pi+1 ] [n/pi ]! ≡ (−1)[n/p i+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 i [n/pi ] n! ≡ (−1)∑i≥1 [n/p ] n0 !n1 ! · · · ns !( mod p). Theo Bổ đề 1.1.2, ta có v p (n!) = ∑i≥1 [n/pi ]. Do đó, n! pv p (n!) ≡ (−1)v p (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 )  1, nếu p = 2, q ≥ 3. trong đó δ = −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.