Luận văn Một số chứng minh định lý fermat nhỏ và định lý wilson

2p−1p = 1+ha−1p 1p−0p = 1+hap với hi là số nguyên. Bằng cách cộng các phần tử từ mỗi bên, ta có ap = a+hp với h= h1+h2+ . . .+ha. Do đó ta có thể kết luận rằng p | (ap−a). 1.3 Chứng minh ban đầu Định lý Wilson Định lí 2. (Định lý Wilson) Nếu p là số nguyên tố khi đó (p−1)!≡−1 (mod p). 16 Những tuyên bố về Định lý Wilson lần đầu tiên xuất hiện trongMeditationes Algebraicae vào năm 1770 trong một tác phẩm của nhà toán học người Anh Edward Waring. John Wilson, một cựu sinh viên của Waring, công bố định lý nhưng không cung cấp chứng minh, giống như Fermat đã làm với Định lý nhỏ Fermat. Vào năm 1771, Lagrange đã cung cấp chứng minh đầu tiên. Tương tự như trường hợp của Định lý nhỏ Fermat, lưu ý rằng đã có bằng chứng Leibniz nhận đã chứng minh Định lý này, nhưng không bao giờ công bố [5, P.97]. Trừ khi có ghi chú khác, các chứng minh trong chương này là từ [4, chương 3]. Các chứng minh dưới đây xuất hiện trong cuốn Beginning Number Theory của Robbin và rất nhiều sách khác. Chứng minh dưới đây là một trường hợp đặc biệt của một chứng minh tổng quát được đưa ra bởi Dirichlet vào năm 1828. Chứng minh 2.1. Nếu p= 2 khi đó (2−1)!= 1≡−1 (mod 2) và nếu p= 3 khi đó (3−1)!= 2≡ −1 (mod 3). Do đó giả sử p là số nguyên tố lớn hơn 3. Vì (p−1)≡−1 (mod p) nó cũng đủ để cho thấy rằng (p−2)!≡ 1 (mod p). Theo như bổ đề 7, với mỗi số j sao cho 1≤ j ≤ p−1 sẽ tồn tại một số nguyên k sao cho 1≤ k≤ p−1 với jk≡ 1 (mod p). Nếu k= j, khi đó j2 ≡ 1 (mod p) với j= 1 hoặc j= p−1. Do đó nếu 2≤ j ≤ p−2, khi đó tồn tại số nguyên k sao cho j 6= k và 2≤ k≤ p−2 và jk ≡ 1 (mod p). Vì có 12(p− 3) cặp như thế nhân chúng với nhau được (p−2)!≡ 1 (mod p). Khi đó (p−1)(p−2)!≡ (−1)(1) (mod p)⇒ (p−1)!≡−1 (mod p). Một trong những chứng minh sớm nhất về định lý Wilson đến từ Lagrange. Bây giờ ta sẽ cùng tìm hiểu. Chứng minh 2.2 (Lagrange, 1773) Cho (x+1)(x+2) · · ·(x+ p−1) = xp−1+A1xp−2+ · · ·+Ap−1. (1.2) Thay x bởi x+1, sau đó nhân với x+1 ta có (x+1)(x+2) · · ·(x+ p) 17 = (x+1)p+A1(x+1)p−1+A2(x+1)p−2+ · · ·+Ap−1(x+1). Nhân (1.2) với (x+ p), từ hai biểu thức trên ta có (x+ p)[xp−1+A1xp−2+ · · ·+Ap−1] = (x+1)p+A1(x+1)p−1+A2(x+1)p−2+ · · ·+Ap−1(x+1). Sau đó đồng nhất hệ số hai vế ta được A1 = ( p 2 ) 2A2 = ( p 3 ) +A1 ( p−1 2 ) 3A3 = ( p 4 ) +A1 ( p−1 3 ) +A2 ( p−2 2 ) ... (p−2)Ap−2 = p+(p−1)A1+(p−2)A2+ · · ·+3Ap−3 (p−1)Ap−1 = Ap−2+ . . .+A3+A2+A1+1. Do đó tổng quát với 1≤ k ≤ p−1 kAk = ( p k+1 ) +A1 ( p−1 k ) +A2 ( p−2 k−1 ) + · · ·+Ak−1 ( p− k+1 2 ) . Cho p là số nguyên tố. Khi đó với 0< k< p, ( p k ) là số nguyên chia hết cho p. Do đó tất cả A1,2A2, . . . ,(p−2)Ap−2 đều chia hết cho p. (p−1)Ap−1 = ( p p ) + ( p−1 p−1 ) A1+ ( p−2 p−2 ) A2+ · · ·+ ( 2 2 ) Ap−2 = 1+A1+A2+ · · ·+Ap−2 18 Do đó (p−1)Ap−1 ≡ 1 (mod p) (−1)Ap−1 ≡ 1 (mod p), tức là Ap−1+1≡ 0 (mod p). Do đó 1+Ap−1 chia hết cho p. Nhắc lại phương trình ban đầu (x+1)(x+2)(x+3) · · ·(x+ p−1) = xp−1+A1xp−2+A2xp−3+ · · ·+Ap−1. Vì từ (1.2) Ap−1 = (p−1)!, suy ra Ap−1+1≡ 0 (mod p). Do đó (p−1)!≡ (−1) (mod p). Lagrange cũng cung cấp một chứng minh khác về định lý Fermat nhỏ: Chứng minh 1.9. Cho x là số nguyên cố định. Vì x,x+1, . . . ,x+ p−1 là một dãy p các số nguyên liên tiếp, một trong số chúng chia hết cho p. Ngoài ra A1,A2, . . . ,Ap−2 tất cả đều chia hết cho p và Ap−1 = (p−1)!≡−1 (mod p). Do đó, biểu thức x(x+1) · · ·(x+ p−1) = xp+A1xp−1+ · · ·+Ap−2x2+Ap−1x cho ta 0≡ xp− x (mod p), đó chính là định lý Fermat nhỏ. Số Ak ngày nay được biết là số Stirling. Một kí hiệu phổ biến là Ak = s(p, p− k) với k = 1, . . . , p. Lagrange lần đầu chứng minh s(p,k) ≡ 0 (mod p) với 1 ≤ 19 k ≤ p−1. Tham khảo [6, Chương 5] để hiểu thêm về số Stirling. Lagrange cũng cung cấp chứng minh thứ hai, điều đó sử dụng công thức Euler (tham khảo thêm Chương 2): Chứng minh 2.3 (Lagrange, 1773) Đọc lại công thức Euler (Bổ đề 11): x!= ax− x(a−1)x+ ( x 2 ) (a−2)x− ( x 3 ) (a−3)x+ · · · Thay x= p−1 và a= p ta có (p−1)! = pp−1− (p−1)(p−1)p−1+ ( p−1 2 ) (p−2)p−1 − ( p−1 3 ) (p−3)p−1+ · · ·− ( p−1 p−2 ) (2p−1)+(−1)p−1. Sử dụng Định lý Ferma nhỏ, ta có (p−1)!≡ 0−(p−1)+ ( p−1 2 ) − ( p−1 3 ) +· · ·− ( p−1 p−2 ) +(−1)p−1(mod p). Chú ý rằng (1−1)p−1= ( p−1 0 ) 1p−1−(p−1)1p−2+ ( p−1 2 ) 1p−3(−1)2−·· ·+(−1)p−1. Do đó (p−1)!≡ (1−1)p−1−1≡−1 (mod p). Euler cung cấp chứng minh Định lý Wilson có sử dụng căn nguyên thủy: Chứng minh 2.4 (Euler, 1783) Cho a là một căn nguyên thủy của p. Khi đó gcd(a, p) = 1, bậc của a là ϕ(p) = p−1 và ap−1 ≡ 1 (mod p). Xét tập {1,a,a2, . . . ,ap−2}. Vì p−1 là bậc của a, 20 khi đó đồng dư với hệ {1,2,3, . . . , p− 1}. Khi đó tích của hệ các phần tử phải đồng dư, do đó ap−2 ·ap−1 · · ·a2 ·a ·1 ≡ (p−1)! (mod p) a (p−1)(p−2) 2 ≡ (p−1)! (mod p). Giả sử p> 2, và cho p= 2n+1 với mỗi số nguyên dương n. Khi đó an = a p−1 2 . Vì ap−1≡ 1= (a p−12 −1)(a p−22 +1), từ Định lý Fermat nhỏ ta thấy p | (a p−12 −1) hoặc p | (a p−22 + 1). Vì a là một căn nguyên thủy, p phải chia hết (a p−12 + 1). Tức là a p−1 2 ≡−1 (mod p). Khi đó a (p−1)(p−2) 2 = a 2n(2n−1) 2 = an(2n−1) = (an)2n−1 ≡ (−1)2n−1 (mod p). Vì 2n−1 là lẻ, suy ra (p−1)!≡−1 (mod p). Chứng minh tiếp theo của Định lý Wilson là của Dirichlet. Chứng minh 2.5 (Dirichlet, 1828) Hai sốm,n gọi là tương ứng nếum,n< p vàmn≡ a (mod p), với p là số nguyên tố, a là số nguyên cố định, và a, p là nguyên tố cùng nhau. Bây giờ, với mỗi số 1,2, . . . , p− 1 có duy nhất một số tương ứng. Bất kì một đồng dư tuyến tính nào với d = gcd(a,n),ax≡ b (mod n) có d nghiệm nếu d | b. Trong trường hợp này, ax≡ b (mod p) có 1 nghiệm vì gcd(a, p) = 1. Do vậy có duy nhất một số nguyên n với 1≤ n≤ p−1 sao cho mn≡ a (mod p). Trường hợp 1: Nếu x2 ≡ a(mod p) không có nghiệm nguyên, số tương ứng là phân biệt và 1 ·2 ·3 · · ·(p−1) = (p−1)!≡ a p−12 (mod p) vì p−12 là bậc của a. Trường hợp 2:Nếu k là một số nguyên dương nhỏ hơn p sao cho k2≡ a (mod p), 21 khi đó (p− k)2 = p2−2pk+ k2 ≡ a (mod p). Bỏ k và p− k từ tích, ta được (1)(2) · · ·(k−1)(k+1) · · ·(p− k−1)(p− k+1) · · ·(p−1)≡ a p−32 (mod p). Do đó (p−1)! ≡ k(p− k) ·a p−32 (mod p) ≡ (pk− k2) ·a p−32 (mod p) ≡ −a ·a p−32 (mod p) ≡ −(a p−12 ) (mod p). Cho a= 1. Định lý Wilson sau trường hợp 2: (p−1)!≡−(1 p−12 )≡−1 (mod p). Nếu p là số nguyên tố lẻ, khi đó tiêu chuẩn Euler thỏa mãn. Nếu a là số dư bậc hai (mod p), i.e nếu đồng dư x2 ≡ a (mod p) có nghiệm, khi đó theo Định lý Wilson và trường hợp 2 ta được a p−1 2 ≡ 1 (mod p). Nếu a là số không dư bậc hai (mod p), khi đó theo trường hợp 1 và Định lý Wilson ta có a p−1 2 ≡−1 (mod p). Vì a p−1 2 ≡±1 (mod p), bình phương ta sẽ thu được Định lý Fermat nhỏ ap−1 ≡ 1 (mod p). Stern cũng đã cung cấp một chứng minh thú vị, sử dụng chuỗi Maclaurin của log( 11−x). Chứng minh 2.6 (Stern, 1860) Cho f là hàm giá trị thực. Tổng quát, nếu f khả vi tại x0, khi đó chuỗi Taylor 22 của hàm f tại x= x0 là ∞ ∑ k=0 f (k)(x0) k! (x−x0)k= f (x0)+ f ′(x0)(x−x0)+ f ′′(x0) 2! (x−x0)2+· · ·+ f k(x0) k! (x−x0)k+· · · Khi x0 = 0, ta có chuỗi Maclaurin của f : ∞ ∑ k=0 f (k)(0) k! (x)k = f (0)+ f ′(0)(x)+ f ′′(0) 2! (x)2+ · · ·+ f k(0) k! (x)k+ · · · Xét log( 11−x) =− log(1− x). Chuỗi Maclaurin của − log(1− x) là 0+ x+ x2 2 + x3 3 + · · · Chú ý ta có ex+ x2 2 + x3 3 +··· = elog( 1 1−x ) = 1 1− x Mà 1+ x+ x2+ . . .= 1 1− x . Do đó ta có ex+ x2 2 + x3 3 +··· = 1+ x+ x2+ · · · (1.3) Bây giờ khai triển vế trái của (1.3) ta có ex = 1+ x+ x2 2! + x3 3! + · · · e x2 2 = 1+ x2 2! 1! + (x 2 2 ) 2 2! + (x 2 2 ) 3 3! + · · · ... e xp p = 1+ xp p 1! + (x p p ) 2 2! + (x p p ) 3 3! + · · · ... 23 Do đó ex+ x2 2 + x3 3 +··· = (1+ x+ x2 2! + x3 3! + · · ·)(1+ x2 2! 1! + (x 2 2 ) 2 2! + (x 2 2 ) 3 3! + · · ·) . . . (1+ xp p 1! + (x p p ) 2 2! + (x p p ) 3 3! + · · ·) . . . = 1+ x 1! + x2 ( 1 2! + 1 2 ) + x3( 1 3! + 1 1! · 1 2 1! + 1 3 1! )+ · · · xp ( 1 p! + 1 (p−2)! · 1 2 1! + . . .+ 1 p 1 ) + · · · Hạng tử xp là tổng của các hạng tử trong công thức sau xa1 a1! · ( x2 2 ) a2 a2! · ( x3 3 ) a3 a3! · · · (x p p ) ap ap! = xa1+2a2+3a3+···+pap a1!a2!a3! · · ·ap!2a23a3 · · · pap trong đó a1+2a2+3a3+ · · ·+ pap = p. Trường hợp 1. a1 = p,ai = 0 với mọi i> 1. Ta sẽ được xp p! . Trường hợp 2. ap = 1,ai = 0 với mọi i< p. Cho ta xp p 1! = xp p . Trường hợp 3. a1 6= p,ai = 0. Trong trường hợp ai < p, khi đó p sẽ không chia hết cho mẫu thức a1!a2!a3! · · ·ap!2a23a3 · · · pap. Do đó hệ số của xp là 1 p! + 1 p = r s với p không chia hết s và r,s là nguyên tố cùng nhau. Khi đó hệ số ở biểu thức 1.3 sẽ tương đương với hệ sau 1 p! + 1 p + r s = 1 p!s 1 ( 1 p! + 1 p ) = p!s 1 (1− r s ) s(1+(p−1)!) = p!s− p!r = p!(s− r) = p(p−1)!(s− r). 24 Vì p - s suy ra p | (1+(p−1)!) nên ta có (p−1)!≡−1 (mod p). Chứng minh tiếp theo có liên quan đến "toán tử sai phân" ∆, được định nghĩa như sau ∆ f (x) = f (x+1)− f (x) với bất kì hàm f nào. Chú ý rằng ∆( f (x)+g(x)) = ( f (x+1)+g(x+1))− ( f (x)+g(x)) = ( f (x+1)− f (x))+(g(x+1)−g(x)) = ∆ f (x)+∆g(x). Ta định nghĩa ∆k f (x) = ∆k−1(∆ f (x)) = ∆(∆k−1 f (x)). Ta sẽ chỉ ra rằng ∆k f (x) = f (x+ k)− ( k k−1 ) f (x+ k−1)+ ( k k+2 ) f (x+ k−2) −·· ·+(−1)k f (x) = k ∑ j=0 (−1)k− j ( k j ) f (x+ j). (1.4) Bây giờ ta sử dụng quy nạp để chứng minh rằng ∆k f (x) = k ∑ j=0 (−1)k− j ( k j ) f (x+ j) với mọi số nguyên k. Và khi đó ta sẽ chứng minh Định lý Wilson. Chứng minh 2.7 (Thue, 1893) 25 Cho S= {k|∆k f (x) = k ∑ j=0 (−1)k− j ( k j ) f (x+ j)} (1) 1 ∈ S : ∆1 f (x) = f (x+1)− f (x) = (−1)1−0 ( 1 0 ) f (x+0)+(−1)0 ( 1 1 ) f (x+1) = − f (x)+ f (x+1) 2 ∈ S : ∆2 f (x) = ∆1(∆ f (x)) = ∆( f (x+1)− f (x)) = ( f (x+2)− f (x+1))− ( f (x+1)− f (x)) = f (x+2)− ( 2 1 ) f (x+1)+ f (x) (2) Giả sử đúng với k−1 có nghĩa là ∆k−1 f (x) = k−1 ∑ j=0 (−1)k−1− j ( k−1 j ) f (x+ j). 26 Khi đó ∆k f (x) = ∆(∆k−1 f (x)) = ∆( k−1 ∑ j=0 (−1)k−1− j ( k−1 j ) f (x+ j)) = ∆[(−1)k−1−0 ( k−1 0 ) f (x+0)]+∆[(−1)k−1−1 ( k−1 1 ) f (x+1)]+ · · ·+∆[(−1)k−1−(k−1) ( k−1 k−1 ) f (x+ k−1)] = (−1)k−1 ( k−1 0 ) ( f (x+1)− f (x))+(−1)k−2 ( k−1 1 ) ( f (x+2)− f (x+1))+ · · ·+(−1)0 ( k−1 k−1 ) ( f (x+ k)− f (x+ k−1)) = k−1 ∑ j=0 (−1)k−1− j ( k−1 j ) ( f (x+ j+1)− f (x+ j)). Với 1≤ j ≤ k−1, theo đồng nhất thức Pascal hệ số của f (x+ j) là (−1)k− j [( k−1 j ) + ( k−1 j−1 )] = (−1)k− j ( k j ) . Dễ dàng thấy rằng hệ số của f (x+ k) là 1: (−1)k−k ( k k ) = 1, và hệ số của f (x) là (−1)k: (−1)k−0 ( k 0 ) = (−1)k. 27 Nếu f (x) = xn thì ∆kxn = k ∑ j=0 (−1)k− j ( k j ) (x+ j)n. Khi x= 0 ta được ∆k0n = k ∑ j=0 (−1)k− j ( k j ) ( j)n. Ở đây ta chú ý rằng ∆k0n = k!S(n,k). [6,p.14] Cho f (x) = xp−1, với p là số nguyên tố. Từ (1.4), áp dụng Định lý Fermat nhỏ và Định lý Binomial, với k = 1,2,3, . . . , p−2. Ta có k = 1,2,3, . . . , p−2: ∆k f (1)= k ∑ j=1 (−1)k− j ( k j ) (1+ j)p−1≡ k ∑ j=1 (−1)k− j ( k j ) ≡ (1−1)k≡ 0 (mod p). Bây giờ ta chú ý rằng ∆2 f (0) = ∆ f (1)−∆ f (0) ∆3 f (0) = ∆2 f (1)−∆2 f (0) ∆4 f (0) = ∆3 f (1)−∆3 f (0) ... ∆p−2 f (0) = ∆p−3 f (1)−∆p−3 f (0) (1.5) ∆p−1 f (0) = ∆p−2 f (1)−∆p−2 f (0). 28 Sử dụng (1.5) ta tìm được ∆p−1 f (0) = ∆p−2 f (1)−∆p−3 f (1)+∆p−4 f (1)−·· · + ∆3 f (1)−∆2 f (1)+∆ f (1)−∆ f (0) ≡ −∆ f (0) = − f (1)+ f (0) = −1p−1 ≡ −1 (mod p). Thay vào (1.4) ta được ∆p−1 f (0) = ∆p−10p−1 = p−1 ∑ j=0 (−1)p−1− j ( p−1 j ) jp−1 = (p−1)p−1− ( p−1 1 ) (p−2)p−1+ ( p−1 2 ) (p−3)p−1 − ·· ·− ( p−1 p−2 ) 1p−1 Theo công thức Euler thì nó bằng (p−1)!. Do đó (p−1)!≡ 1 (mod p). 1.4 Ứng dụng giải một số bài tập Bài tập 1. Tìm tất cả các số nguyên dương x,y thỏa mãn x2017−1= (x−1)(y2015−1). Giải. Rõ ràng cặp số (1,y) với y nguyên dương tùy ý là nghiệm của phương trình. Xét trường hợp x> 1. Khi đó, ta có thể viết lại phương trình dưới dạng x2016+ x2015+ . . .+ x+1= x2017−1 x−1 = y 2015−1. (1) 29 Gọi p là một ước nguyên tố bất kì của A= x2017−1 x−1 , ta sẽ chứng minh p≡ 1(mod 2017) hoặc p= 2017. Thật vậy, nếu (p−1,2017) = 1 thì theo Định lí Bezout, tồn tại các số nguyên dương a,b để 2017a− (p−1)b= 1. Do x2017 ≡ 1(mod p) nên x2017a ≡ 1(mod p). từ đó sử dụng Định lý Fermat nhỏ, ta có 1≡ x2017a ≡ x(p−1)b+1 ≡ x(mod p). Điều này chứng tỏ x≡ 1(mod p), suy ra x2016+ x2015+ . . .+ x+1≡ 2017(mod p). Do đó, ta có p = 2017. Tóm lại, nếu p là một ước nguyên tố của A thì hoặc p ≡ 1(mod 2017) hoặc p = 2017. Bây giờ, gọi d là ước dương bất kì của A, ta cũng dễ thấy d ≡ 1(mod 2017) hoặc d ≡ 0(mod 2017) (2). Theo (1), ta có y−1 là một ước dương của A, do đó y−1≡ 0,1(mod 2017), tức y ≡ 1,2(mod 2017). Mặt khác, ta cũng có B = y2014+ y2013+ . . .+ y+1 cũng là ước của A. Nếu y ≡ 1(mod 2017) thì B ≡ 2015(mod 2017), mâu thuẫn với (2). Do đó y≡ 2(mod 2017). Tuy nhiên, trong trường hợp này, ta lại có B≡ 22014+22013+ . . .+2+1= 22015−1≡ 1009(mod 2017) cũng mâu thuẫn với (2). Do đó, nếu x> 1 thì không tồn tại cặp số nào thỏa mãn yêu cầu. Vậy chỉ có một cặp số duy nhất như đã nêu ở trên. Bài tập 2. Tìm tất cả các số nguyên tố p sao cho 3p−1−1 p là số chính phương. Giải. Rõ ràng p= 2 thỏa mãn yêu cầu đề bài. Xét trường hợp p> 2, lúc này p 30 lẻ nên ta có thể đặt p= 2k+1 với k ∈ Z+. Khi đó, ta có (3k−1)(3k+1) p = a2 với a ∈ Z+. Rõ ràng a chẵn và (3k−1,3k+1) = 2 nên ta có thể đặt a= 2b với b ∈ Z+ và viết phương trình trên thành 3k−1 2 · 3 k+1 2 p = b2. (1) Xét hai trường hợp sau: Trường hợp 1. 3k−1 chia hết cho p. Ta có( 3k−1 2p , 3k+1 2 ) = 1 nên theo (1) thì 3k−1= 2px2 3k+1= 2y2 với x,y ∈ Z+ và (x,y) = 1. Dẫn đến y2 ≡ 2(mod 3) (vô lí). Trường hợp 2. 3k+1 chia hết cho p. Tương tự như trên, ta cũng có 3k−1= 2x2, 3k+1= 2py2 với x,y ∈ Z+ và (x,y) = 1. Nếu k lẻ thì ta có 3k+1= 0(mod 4) nên y chia hết cho 2, từ đó suy ra 2py2 chia hết cho 8. Điều này vô lí vì 3k+1≡ 4(mod 8). Do đó k chẵn, k = 2t(t ∈ Z+). Ta có 2x2 = 32t−1= (3t−1)(3t+1). 31 Chú ý rằng (3t−1)(3t+1) = 2 nên một trong hai số 3t−1 và 3t+1 phải là số chính phương. Tuy nhiên, 3t − 1 ≡ 2(mod 3) nên 3t − 1 không thể là số chính phương, suy ra 3t+1= c2 với c ∈ Z+, hay 3t = (c−1)(c+1). Từ đây, ta suy ra c−1= 3m và c+1= 3n với m,n ∈ N,m< n và m+n= t. Do đó 2= 3n−3m = 3m(3n−m−1). Suy ra m= 0,n= 1 và t = 1. Ta tính được k = 2 và p= 5. Thử lại, ta thấy thỏa mãn. Bài tập 3. Tìm nghiệm nguyên của phương trình x2004− y3003 = 7. Giải. Đặt X = x1002,Y = y1001, khi đó đưa phương trình đã cho về dạng: X2−Y 3 = 7. Ta sẽ chứng minh rằng phương trình không có nghiệm nguyên dương. Thật vậy, giả sử phương trình có nghiệm nguyên dương X0,Y0. Khi đó: X20 −Y 30 = 7 → X20 +1= Y 30 +8 → X20 +1= (Y0+2)(Y 20 −2Y0+4). Chỉ có 2 khả năng xảy ra: 1) Nếu Y0 chẵn, tức là Y0 = 2k, ta có Y 20 −2Y0+4= 4k2−4k+4 → (Y 20 −2Y0+4)...4 → (X20 +1)...4 → X20 ≡−1(mod 4). Ta biết rằng nếu X0 là số nguyên thì hoặc là X20 ...4 hoặc là X20 ≡ 1(mod 4), vậy từ phương trình trên suy ra điều vô lí. Vậy trường hợp 1 không thể xảy ra. 32 2) Nếu Y0 lẻ, tức là Y0 = 4k+1 hoặc Y0 = 4k−1. a) Nếu Y0≡−1(mod 4). Lúc này ta có (Y0+2)≡ 1(mod 4) và (Y 20 −2Y0+4)≡ −1(mod 4). Ta suy ra X20 +1≡−1(mod 4)→ X20 +1≡−2(mod 4). Từ lập luận trên suy ra điều vô lí. Vậy trường hợp a) không thể xảy ra. b) Nếu Y0 ≡ 1(mod 4). Khi đó (Y0+2)≡ 3(mod 4), suy ra Y0+2 có ít nhất một ước nguyên tố p có dạng 4k+3. Suy ra (X20 +1) ...p → X20 ≡−1(mod p)→ (X20 )2k+1 ≡−1(mod p) → X (4k+3)−10 ≡−1(mod p)→ X p−10 ≡−1(mod p). Do p là số nguyên tố, nên theo Định lý Fermat nhỏ, ta có (X p0 −X0) ...p→ X0(X p−10 −1) ...p. Vì X20 ≡ 1(mod p)→ X0 6 ...p và vì p nguyên tố nên (X0, p) = 1, do vậy đi đến (X p−10 −1) ...p→ X p−10 ≡ 1(mod p). Dẫn đến điều vô lí. Vậy trong mọi trường hợp ta đề gặp mâu thuẫn, do đó giả thiết có nghiệm nguyên dương là sai, tức là phương trình không có nghiệm nguyên dương. Vì lẽ ấy phương trình đã cho không có nghiệm nguyên dương. Bài tập 4. Tìm nghiệm nguyên dương của phương trình: x41+ x 4 2+ · · ·+ x414 = 1599. Giải. Để ý rằng nếu a chẵn thì a4 = (2k)4 = 16k4, suy ra a4 ≡ 0(mod 16). 33 Nếu a lẻ thì a4 = (2k+1)4 = 16k4+32k2+8k(3k+1)+1. Dễ thấy với mọi k ∈Z, thì k(3k+1)...2, do đó suy ra khi a lẻ thì a4≡ 1(mod 16). Vì lẽ đó, với mọi a ∈ Z thì a4 ≡ 0(mod 16)a4 ≡ 1(mod 16). Từ đó suy ra với mọi xi ∈ Z, i= 1,2, . . . ,14, thì x41+ x 4 2+ · · ·+ x414 ≡ m(mod 16), trong đó m ∈ {0,1,2, . . . ,14}. Mặt khác: 1599≡ 15(mod 16). Vì lẽ ấy phương trình x41+ x 4 2+ · · ·+ x414 = 1599 không có nghiệm nguyên. Bài tập 5. Cho n≥ 5 là số tự nhiên. Chứng minh rằng[ (n−1)! n ] ...(n−1) Lời giải. a) Trường hợp 1: n là số nguyên tố. Theo Định lí Wilson, ta có (n−1)!≡−1(mod n). Suy ra ((n−1)!+1)...n. Ta có[ (n−1)! n ] = [ (n−1)!+1 n − 1 n ] = (n−1)!+1 n −1 (Vì 0< 1 n < 1) = (n−1)!− (n−1) n . Nên [ (n−1)! n ] ...(n−1).(Vì gcd(n,n−1) = 1) 34 b) Trường hợp 2: n là hợp số. +/ Nếu n không là bình phương của một số nguyên tố. Khi đó n= rs với 1< r < s< n. Do gcd(n,n−1) = 1, nên s< n−1→ (n−1)!= kn(n−1) suy ra [ (n−1)! n ] = k(n−1)...(n−1). +/ Nếu n không là bình phương của một số nguyên tố. Khi đó n= p2 với p là một số nguyên tố. Do p2 = n,n≥ 5, suy ra p≥ 3→ p2 ≥ 3p> 2p+1→ 2p< p2−1, hay 2p< n−1. Nên 1< p< 2p< n−1. Từ đó suy ra [ (n−1)! n ] ...(n−1). Vậy ta được điều phải chứng minh. 35 Chương 2 Mở rộng Định lý Fermat nhỏ và Định lý Wilson Mục đích của chương này là trình bày một dạng mở rộng của Định lý Fermat nhỏ và Định lý Wilson và ứng dụng của hai định lý đó. 2.1 Một dạng tổng quát của Định lý Fermat nhỏ Trước tiên ta cần nắm vững một số vấn đề sau làm cơ sở nghiên cứu dạng mở rộng của Định lý Fermat nhỏ và Định lý Wilson. Định nghĩa 2.1.1. Phi hàm Euler ϕ(n) được định nghĩa là số các số nguyên k sao cho 1≤ k ≤ n và nguyên tố cùng nhau với n. Euler định nghĩa phi hàm Euler vào năm 1970. Bổ đề 2.1.2. Với mỗi số nguyên a,d,n, nếu gcd(d,n) = 1 thì khi đó n hạng tử a,a+ d,a+ 2d, . . . ,a+ (n− 1)d khi chia cho n sẽ có số dư lần lượt là 0,1, . . . ,n−1, phần dư nhỏ nhất (mod n) là 0,1, . . . ,n−1 theo thứ tự. Chứng minh. Xét tập {a,a+d,a+2d, . . . ,a+(n−1)d}. Giả sử rằng a+ kd ≡ a+ jd (mod n) 36 với k,d ∈ Z sao cho 0≤ k < j < n. Khi đó kd ≡ jd (mod n). Vì gcd(d,n) = 1 khi đó giản ước ta được k ≡ j (mod n), mâu thuẫn. Do đó các số trong dãy là đồng dư với {0,1, . . . ,n−1} theo thứ tự. Bổ đề 2.1.3. Φ(pm) = pm−1(p−1). Chứng minh. Chú ý rằng gcd(n, pm) = 1 khi và chỉ khi p - n. Sẽ có pm−1 số nguyên giữa 1 và pm chia hết cho p : {p,2p,3p, . . . ,(pm−1)p}. Do đó sẽ có pm− pm−1 số nguyên giữa 1 và pm mà chúng nguyên tố cùng nhau với pm. Như vậy ϕ(pm) = pm− pm−1 = pm−1(p−1). Bổ đề 2.1.4. Phi hàm Euler là hàm nhân tính. Chứng minh. Một hàm số học được định nghĩa là hàm nhân tính nếu f (mn) = f (m) f (n) khi m,n nguyên tố cùng nhau [7, p.15]. Để chỉ ra phi hàm Euler là hàm nhân tính ta cần chỉ ra rằng với m và n là nguyên tố cùng nhau thì ϕ(mn) = ϕ(m)ϕ(n). Vì ϕ(1) = 1, kết quả sẽ được giữ nguyên nếu m hoặc n bằng 1. Do đó ta sẽ giả sử m,n> 1. Tiếp theo sắp xếp các số nguyên từ 1 tới mn vào m cột như sau: 1 2 · · · r · · · m m+1 m+2 · · · m+ r · · · 2m 2m+1 2m+2 · · · 2m+ r · · · 3m ... ... ... ... (n−1)m+1 (n−1)m+2 · · · (n−1)m+ r · · · nm Vì gcd(a,bc) = 1⇔ gcd(a,b) = 1 và gcd(a,c) = 1, ϕ(mn) không chỉ bằng với các phần tử bên trên mà nguyên tố cùng nhau với mn mà ϕ(mn) còn bằng với số nguyên tố cùng nhau với cả m và n. Chú ý rằng gcd(qm+ nr) = gcd(r,m), như vậy cho một cột r nhất định, phần tử trong cột nguyên tố cùng nhau với m khi và chỉ khi r nguyên tố cùng nhau với m. Có ϕ(m) cột như vậy. Bây giờ cho gcd(r,m) = 1 với một số cột r. Các phần tử trong cột thứ r là: r,m+ r,2m+ r, . . . ,(n−1)m+ r 37 Có n số nguyên trong dãy trên và không có hai số nào đồng dư với nhau. Rõ ràng hơn, ta giả sử sm+ r ≡ tm+ r (mod n). Khi đó sm ≡ tm (mod n). Suy ra cột thứ r chứa các số nguyên mà chúng nguyên tố cùng nhau với n như tập {0,1,2, . . . ,n− 1}, gọi là số nguyên ϕ(n). Do đó tổng các số nguyên tố cùng nhau với cả m và n là ϕ(m)ϕ(n). Ví dụ 1. ϕ(945) = ϕ(33 ·5 ·7) = 32 ·50 ·70 · (3−1) · (5−1) · (7−1) = 432 Ví dụ 2. 13433 ≡? (mod 945) Chú ý rằng gcd(13,945) = 1 và theo như bên trên, ϕ(945) = 432. Do đó 13433 = 13432 ·13≡ 13 (mod 945). Định lý 3. (Tổng quát về Định lý Fermat nhỏ) Nếu n= ϕ(N) là số các số nguyên dương không vượt quá N và nguyên tố cùng nhau với N, khi đó xn−1 chia hết cho N với bất kì số nguyên x nào nguyên tố cùng nhau với N. Đầu tiên chúng ta nghiên cứu chứng minh của Euler [4, p.61] Chứng minh 3.1 (Euler, 1760) Cho v là bậc của x. Khi đó theo bổ đề 2.2.2, hệ {1,x,x2, . . . ,xn−1} là phân biệt (mod N) và nguyên tố cùng nhau với N. Do đó v≤ ϕ(N). (Chứng minh bằng phản chứng. Giả sử v> ϕ(N). Khi đó có nhiều hơn ϕ(N) số nguyên mà chúng nguyên tố cùng nhau với N, mâu thuẫn). Nếu v = ϕ(N), chứng minh hoàn tất. Nếu v < ϕ(N) khi đó có một số nguyên dương a nhỏ hơnN và nguyên tố cùng nhau vớiN. Khi đó {a,ax,ax2, . . . ,axv−1} là phân biệt với bất kì lũy thừa nào của x: (Chứng minh bằng phản chứng. Giả sử axm ≡ axn(mod N) với n < m. Khi đó xm−n ≡ 1 (mod N), mâu thuẫn. Nếu axm ≡ xn (mod N), khi đó a≡ 1 (mod N) và ta biết rằng {1,x,x2, . . . ,xv−1} là phân biệt). Do đó 2v ≤ n. Nếu 2v = n. chứng minh hoàn tất. Nếu không thì xét 3v ≤ n. Tiếp tục tính toán, ta thấy rằng v chia hết ϕ(N) suy ra Φ(N) = vm với một số 38 số nguyên m. Khi đó xn = xvm = (xv)m ≡ 1m ≡ 1 (mod N). Lapace cũng cung cấp một chứng minh dạng tổng quát [4, p.63], đó là: Nếu gcd(a,n) = 1 thì khi đó aϕ(n) ≡ 1 (mod n). Chứng minh 3.2 (Laplace, 1776) Cho s = pe11 · · · pekk với pi 6= p j với i 6= j với mỗi pi là nguyên tố. Cho a ∈ Z và gcd(a,s) = 1. Cho v = ϕ(s) = (pe1−11 ) · · ·(pek−1k )(p1−1) · · ·(pk−1) q = ϕ(pe11 ) = (p e1−1 1 )(p1−1) r = (pe2−12 )(p2−1) · · ·(pek−1k )(pk−1). Khi đó v= qr = s( p1−1 p1 )( p2−1 p2 ) · · ·( pk−1 pk ). Cho x= aq. Khi đó av−1= aqr−1= xr−1 chia hết cho x−1 bởi vì (x−1)(xr−1+ xr−2+ · · ·+ x+1) = xr−1. Nghĩa là, aϕ(s)−1 chia hết cho aϕ(pe11 )−1. Bây giờ bằng quy nạp ta chỉ ra x−1 chia hết cho pe11 . Đầu tiên, cho e1 = 1. Khi đó x− 1 = aq− 1 = ap (1−1) 1 (p1−1)− 1 = ap1−1− 1 ≡ 0 (mod p1) theo như Định lý Fermat nhỏ. bây giờ ta giả sử nó đúng với e1−1≡ 1 (mod pe1−11 ) và a(p e1−2 1 (p1−1)) = aϕ(p e1−1 1 ) = 1+mpe1−11 39 với m ∈ Z. Khi đó aΦ(p e1 1 ) = a(p e1−1 1 )(p1−1) = (a(p e1−2 1 )(p1−1))p1 = (1+mpe−1−11 ) p1 = 1+ ( p1 1 ) mpe1−11 +mp e1 1 Q = 1+mpe11 +mp e1 1 Q = 1+ pe11 (m+mQ). Khi đó x− 1 chia hết cho pe11 . Vì pe11 | (x− 1) và (x− 1) | (xr − 1), suy rra pe11 | (xr− 1). Tương tự, mỗi pe22 , pe33 , · · · , pekk chia hết (xr− 1). Vì mỗi peii là nguyên tố cùng nhau, tích của chúng s cũng chia hết (xr−1). Do đó aϕ(s) = av = xr ≡ 1 (mod s). 2.2 Một dạng tổng quát của Gauss về Định lý Wilson Gauss [4, p.65] là người đầu tiên công bố một cách khái quát nhất Định lý Wilson: Định lý 4. Cho P là tích của Φ(A) số nguyên n1,n2, . . . ,nΦ(A), tất cả đều nhỏ hơn A và gcd(ni,A) = 1 với mọi i. Cho A = 2 jp e1 1 p e2 2 · · · pekk với pi là các số nguyên tố lẻ phân biệt và ϕ(A) > 0. Nếu A = 4 hoặc A = 2 jpm với j = 0 hoặc j = 1, khi đó P≡−1 (mod A). Nếu không thì P≡ 1 (mod A). Chứng minh 4.1. (Minding, 1832) Bình phương t của p1 và sử dụng Định lý phần dư Trung Hoa để xác định số a sao cho a ≡ t (mod p1) and a ≡ 1 (mod 2p2p3 · · · pk). Khi đó a là một căn bậc lẻ không dư của A. Cho n1x ≡ a (mod A) và n2y ≡ a (mod A) sao cho n1 6= n2 và n2 6= a. Khi đó y 6= n1,x,n2. Theo cách này ϕ(A) số nguyên n1,n2, . . . ,nϕ(A) có thể kết hợp với nhau n1x,n2y, . . . sao cho tích của của hai trong bất kì cặp nào đồng dư với a (mod A). Vì thế sẽ có ϕ(A)/2 cặp, P≡ aϕ(A)/2 (mod A). 40 Trường hợp 1. A= 2 jpm với j = 0 hoặc j = 1. Khi đó ϕ(A) = ϕ(2 jpm) = ϕ(2 j)ϕ(pm) = (pm−1)(p−1), và aΦ(A)= a(p m−1)(p−1)= aϕ(pm)≡ 1 (mod pm) vì gcd(a, pm) = 1 theo như Định lý Fermat nhỏ. Do đó theo tiêu chuẩn Euler aϕ(A)/2 = ( a p−1 2 )pm−1 ≡ (−1)pm−1 ≡−1 (mod p). Do đó pm chia hết aϕ(A)/2−1 hoặc aϕ(A)/2+1. Ta biết rằng p chia hết aϕ(A)/2+ 1. Nếu p|(aϕ(A)/2− 1 khi đó p|[(aϕ(A)/2+ 1)− (aϕ(A)/2− 1)], suy ra p|2, mâu thuẫn vì p là số lẻ. Do đó p|(aϕ(A)/2+1) suy ra pm|(aϕ(A)/2+1). Do đó aϕ(A)/2 ≡−1 (mod pm)≡−1 (mod A). Nếu A= 2pm khi đó vì a là số lẻ, aϕ(A)/2 ≡ (−1) (mod 2). Do đó P= aϕ(A)/2 ≡ −1 (mod A). Trường hợp 2. A= 2 jpm với j ≥ 2. Khi đó ϕ(A) = 2 j−1(pm−1)(p−1), và aϕ(A)/2 = a(2 j−1)(pm−1)(p−1)/2 = ( a pm−1(p−1) 2 )2 j−1 ≡ (−1)2 j−1 ≡ 1 (mod pm, và aϕ(A)/2 = (a2 j−1 )(p m−1)(p−1)/2 ≡ 1pm−1(p−1)/2 ≡ 1