Ngày đăng: 21/08/2014, 14:22
PRIMITIVE ROOT Nguyễn Thanh Trà K42 Trường THPT Chuyên ĐHSP HN [email protected] Ngày 27 tháng 11 năm 2009 1 Nguyễn Thanh Trà Mục lục 1 Một số khái niệm và tính chất 3 2 Căn nguyên thuỷ-những ứng dụng 5 2.1 Bài tập về tính chất căn nguyên thuỷ . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Một số ứng dụng của căn nguyên thuỷ . . . . . . . . . . . . . . . . . . . . . 6 3 Một số bài tập 17 Seminar Trường THPT chuyên ĐHSP HN Page 2 Nguyễn Thanh Trà 1 Một số khái niệm và tính chất Khái niệm 1.1. Cấp của một số nguyên. Giả sử a và m là các số nguyên dương nguyên tố cùng nhau. Khi đó số nguyên dương x nhỏ nhất sao cho a x ≡ 1 (mod p) được gọi là cấp của a modulo m. Ta kí hiệu bậc của a modulo m b ở i ord m a Như vậy, dễ dàng suy ra ord m a là ước của φ(m) với mọi a. Khái niệm 1.2. Căn nguyên thuỷ. Nếu số nguyên dương g có cấp là φ(p) mod p thì g được gọi là căn nguyên thuỷ mod p Từ khái niệm căn nguyên thuỷ, ta có các tính chất Tính chất 1. Nếu g là căn nguyên thuỷ mod p thì ta có thể trình diễn hệ thặng dư thu gọn mod p dưới dạng sau: {1, g, g 2 , , g φ(p) } Tính chất 2. Nếu p là số nguyên tố thì p có đúng φ(p −1) căn nguyên thuỷ. Tính chất 3. Giả sử p là một số nguyên tố lẻ, có căn nguyên thuỷ g. Khi đó, hoặc g hoặc g + p là một căn nguyên thuỷ mod p 2 . Tính chất 4. Giả sử p là một số nguyên tố lẻ. Khi đó p k có căn nguyên thuỷ với mọi số nguyên dương k. Hơn nữa nếu g là một căn nguyên thuỷ mod p 2 thì g là căn nguyên thuỷ mod p k với mọi số nguyên k. Tính chất 5. Nếu n = 2p t , p là số nguyên tố lẻ, t nguyên dương thì n có căn nguyên thuỷ. Cụ thể là, nếu g là căn nguyên thuỷ mod p t và r lẻ thì nó là căn nguyên thuỷ mod 2p t , còn nếu r chẵn thì r + p t là căn nguyên thuỷ mod 2p t . Tính chất 6. Số nguyên dương n có căn nguyên thuỷ khi và chỉ khi: n = 2, 4, p t , 2p t Seminar Trường THPT chuyên ĐHSP HN Page 3 Nguyễn Thanh Trà trong đó, p là số nguyên tố lẻ, t là số nguyên dương. Seminar Trường THPT chuyên ĐHSP HN Page 4 Nguyễn Thanh Trà 2 Căn nguyên thuỷ-những ứng dụng 2.1 Bài tập về tính chất căn nguyên thuỷ Như ta đã biết, căn nguyên thuỷ là một khái niệm trọng yếu, có nhiều ứng dụng mạnh trong giải toán. Trong mục này tôi xin giới thiệu một số bài tập về tính chất của căn nguyên thuỷ. Ví dụ 1. Cho p = 2 n + 1 là một số nguyên tố. Minh chứng rằng 3 là căn nguyên thuỷ mod p. Lời giải. Đặt p = 2 n + 1 Trước nhất, ta sẽ minh chứng 3 không là bình phương mod p. Thật vậy, ta lưu ý rằng p ≡ 1 (mod 4) và 2 n + 1 ≡ −1 (mod 3) (do n phải là luỹ thừa của 2). Khi đó, ta có: 3 p = p 3 = −1 3 = −1. Như vậy, 3 không là bình phương mod 3. Do φ(p) = 2 n nên ord p 3 = 2 k (do ord p 3 = 2 k |φ(p)). Giả sử k < n ta có 3 2 n−1 ≡ 1 (mod p). Mà 3 không là bình phương mod 3 nên 3 p ≡ 3 2 n−1 (mod p) suy ra 3 2 n−1 ≡ −1 (mod p). Do đó, p|1 −(−1) = 2, điều này vô lí. Ví dụ 2. Cho p là một số nguyên tố có dạng 4k + 3 và g là một căn nguyên thuỷ mod p thoả mãn g 2 ≡ g + 1 (mod p). Minh chứng rằng g −2 cũng là một căn nguyên thủy mod p Lời giải. Để minh chứng bài toán, trước hết, ta cần một bổ đề. Bổ đề 1. Cho p là một số nguyên tố và g là một căn nguyên thuỷ mod p. Gọi g là số nghịch đảo của g mod p. Minh chứng rằng g cũng là một căn nguyên thuỷ mod p. Lời giải của bổ đề 1. Giả sử g không là căn nguyên thuỷ mod p. Khi đó, tồn tại số nguyên dương j sao cho g p−1 j ≡ 1 (mod p) Do g là nghịch đảo của g mod p nên gg ≡ 1 (mod p) ⇒ (gg ) p−1 j ≡ 1 (mod p) ⇒ g p−1 j ≡ 1 (mod p) Điều này trái với giả thiết g là căn nguyên thuỷ mod p. Seminar Trường THPT chuyên ĐHSP HN Page 5 Nguyễn Thanh Trà Trở lại bài toán, trước nhất, ta sẽ minh chứng p − 1 là một căn nguyên thuỷ mod p. Thật vậy, ta có g 2 ≡ g + 1 (mod p) ⇒ g(g − 1) ≡ 1 (mod p) Theo bổ đề 1, ta có g −1 là căn nguyên thuỷ mod p. Do đó (g −1) p−1 2 ≡ −1 (mod p) hay (g − 1) 2k+1 ≡ −1 (mod p) Mặt khác, từ giả thiết, ta có: g 2 ≡ g + 1 (mod p) ⇒ (g − 1) 2 ≡ 2 −g (mod p) Suy ra (g −1) 2k+3 ≡ (g − 1) 2 · (g − 1) 2k+1 ≡ −1 ·(2 −g) (mod p) Như vậy, để minh chứng g − 2 là căn nguyên thuỷ mod p ta chỉ cần minh chứng (2k + 3, p −1) = 1. Thật vậy, ta có (2k + 3, p −1) = (2k + 3, 4k + 2) = 1. Tóm lại g − 2 là căn nguyên thuỷ mod p. 2.2 Một số ứng dụng của căn nguyên t huỷ Để mở màn cho những ứng dụng của căn nguyên thuỷ, ta hãy đến với một số ví dụ đơn giản. Ví dụ 3. Tìm các số nguyên n > 1 sao cho: n|a 25 − a với mọi a ∈ N Lời giải. Đặt N = p−1|24 p∈P p = 2 ·3 ·5 ·7 ·13 Ta sẽ minh chứng n thoả mãn điều kiện của đề bài khi và chỉ khi n là một ước số của N . Theo định lí F ermat, ta có: a 25 − a = a(a 24 − 1) ≡ 0 (mod N ) với mọi a ∈ Z + Do đó, mọi ước số nguyên của N đều thoả mãn đề bài. Giả sử tồn tại một số nguyên dương n không là ước số của N thoả mãn điều kiện đề bài. Nếu n có một ước số nguyên p không là ước của N, thì tồn tại một số a là căn nguyên thuỷ của p. Khi đó, a 25 − a = a(a 24 − 1) ≡ 0 (mod p) khi và chỉ khi 24 ≡ 0 (mod p −1). Vô lí. Nếu n có một ước số chính phương dạng p 2 , với a = p, ta có: p 25 − p ≡ 0 (mod p 2 ) như vậy, không tồn tại p thoả mãn. Như vậy, n là một ước của N. Seminar Trường THPT chuyên ĐHSP HN Page 6 Nguyễn Thanh Trà Trong bài toán trên, ta nhận thấy rằng giả thiết với mọi a ∈ N làm cho bài toán yếu đi. Ta hãy tư duy theo một hướng khác. Ta có bài toán: Ví dụ 4. Tìm ước chung lớn nhất của các số: a 561 − a, với a = 2, 3, 4, , 561 Lời giải. Tương tự như trên, ta sẽ minh chứng rằng: N = p−1|560 p∈P p = 2 ·3 ·5 ·7 ·11 ·13 ·17 ·29 ·41 ·71 ·281 là ước chúng lớn nhất của toàn bộ các số nói trên. Giả sử ước chúng lớn nhất của a 561 − a, với a = 2, 3, 4, , 561 là d. Ta xét hai trường hợp: Trường hợp 1. Nếu d không có ước nguyên tố to hơn 561. Gọi p là một ước nguyên tố bất kì của d, ta có p < 561. Gọi g là một căn nguyên thuỷ của p, suy ra g < 561 nên g 560 − 1 ≡ 0 (mod p). Do g là că n nguyên thuỷ của p nên p −1|560. Mặt khác, dễ dàng minh chứng được nếu p − 1|560 thì a 561 − a ≡ 0 (mod p) với a = 2, 3, 4, , 561. Giả sử n có một ước số dạng p 2 với p là số nguyên tố. Khi đó p 561 − p ≡ 0 (mod p 2 ), vô lí. Trường hợp 2. Nếu d có một ước nguyên tố to hơn 561. Ta xét đa thức f(x) = x 560 − 1 là một đa thức bậ c 560 có 560 nghiệm mod p. Mặt khác đa thức (x −2)(x −3) ···(x −561) cũng là một đa thức bậv 560 và có 560 nghiệm mod p. Đồng nhất hệ số của x 559 , ta có: 2 + 3 + 4 + ··· + 561 ≡ 0 (mod p) ⇔ 561 ·562 2 − 1 ≡ 0 (mod p) ⇔ 561 ·561 ·281 ≡ 1 (mod p) ⇔ p|2 5 · 5 · 7 · 563 ⇒ p = 563 Seminar Trường THPT chuyên ĐHSP HN Page 7 Nguyễn Thanh Trà Mặt khác, tro ng trường hợp a = 2, ta có 2 561 ≡ 282 = 2 (mod 563). Tóm lại, từ hai trường hợp 1 và 2, ta có N = p−1|560 p∈P p = 2 ·3 ·5 ·7 ·11 ·13 ·17 ·29 ·41 ·71 ·281 là ước chung lớn nhất của a 561 − a, với a = 2, 3, 4, , 561 Nhận xét. Từ ví dụ trên, ta nhận thấy số 561 không có vai trò trọng yếu trong bài toán. Ta hãy tổng quát bài toán: Bài toán 3.1. Tìm ước chung lớn nhất của các số: a k − a, với a = 2, 3, 4, , k Từ một hướng nhìn nhận khác, ta có một bài toán Ví dụ 5 (SP TST 2008). Tìm các số nguyên tố p, q thoả mãn: α 3pq ≡ α (mod 3pq) ∀α ∈ Z Lời giải. Giả sử p ≤ q là các số nguyên tố thoả mãn đề bài. Do α 3pq ≡ α (mod 3) ∀α ∈ Z nên nếu chọn a = −1 suy ra p, q đều là các số lẻ. Do α 3pq ≡ α (mod 3p) ∀α ∈ Z nên nếu chọn α là một căn nguyên thuỷ của p, ta sẽ có 3pq − 1 ≡ 0 (mod p −1) ⇒ 3q − 1 . . . p − 1. Do α 3pq ≡ α (mod 3q) ∀α ∈ Z nên nếu chọn α là một căn nguyên thuỷ của q, ta sẽ có 3pq − 1 ≡ 0 (mod q −1) ⇒ 3q − 1 . . . p − 1. Nếu p = q thì 3p − 1 . . . p − 1 nên suy ra p = q = 3. Thay vào không thoả mãn vì 4 27 ≡ 1 (mod 27). Nếu q ≥ p + 2 thì 3p − 1 q − 1 < 3 nên 3p −1 = 2(q − 1) hay 2q = 3p + 1, do đó: 3q − 1 = 9p + 1 2 . . . p − 1 và (9p + 1) − (9p −1) = 10 . . . p − 1 suy ra p = 11, q = 17. Thay vào, ta thấy thoả mãn điều kiện đề bài. Seminar Trường THPT chuyên ĐHSP HN Page 8 Nguyễn Thanh Trà Nhận xét. Ta thấy trong bài toán trên, số 3 cũng là một số nguyên tố. Như vậy, ta hãy nghĩ cách tổng quát bài toán. Và ta có được kết quả sau. Ví dụ 6. Tìm các số nguyên tố p, q, r thoả mãn: α pqr ≡ α (mod pqr) ∀α ∈ Z Lời giải. Tương tự cách minh chứng bài toán trên, ta cũng có kết quả sau: pq − 1 . . . r −1 qr − 1 . . . p − 1 sp − 1 . . . q − 1 (1) Như vậy bài toán đã cho được mang trở về dạng giải phương trình nghiệm nguyên với các số nguyên tố p, q, r thoả mãn điều kiện (1) Ta hãy nghĩ một cách mở rộng mới cho ví dụ 5 Ví dụ 7. Tìm các số β sao cho tồn tại các số nguyên tố p, q thoả mãn: α 3pq ≡ αβ (mod 3pq) ∀α ∈ Z Lời giải. Trước hết, ta lưu ý tới bổ đề sau: Bổ đề 1. Cho p là một số nguyên tố, a, n là các số nguyên dương, (a, n) = 1. Khi đó phương trình x n ≡ a (mod p) hoặc có (n, p − 1) nghiệm hoặc vô nghiệm, tuỳ theo: a p−1 (n,p−1) ≡ 1 (mod p) có thoả mãn hay không. Cách minh chứng bổ trên là khá dễ dàng , xin không nêu ra ở đây. Trở lại bài toán, ta có: α 3pq ≡ αβ (mod 3pq) ∀α ∈ Z khi và chỉ khi phương trình x 3pq−1 ≡ β (mod 3p) có p − 1 nghiệm mod p và phương trình x 3pq−1 ≡ β (mod 3q) có q − 1 nghiệm mod q. Suy ra: (3pq − 1, p − 1) = p −1 (3pq − 1, q − 1) = q − 1 và β p−1 (3pq−1,p−1) ≡ 1 (mod p) β q−1 (3pq−1,q−1) ≡ 1 (mod q) Seminar Trường THPT chuyên ĐHSP HN Page 9 Nguyễn Thanh Trà Từ (3pq −1, p −1) = p −1, (3pq −1, q −1) = q −1, ta có p = 11, q = 17. Thay vào, ta được: β 1 ≡ 1 (mod 17) β 1 ≡ 1 (mod 11) Ta thấy β = 1 là số duy nhất thoả mãn. Như vậy, các số β thoả mãn đề bài là β = 1 Ta nhận thấy rằng bài toán trên còn nhiều hướng mở rộng, ví dụ với ba biến p, q, r. Tất nhiên là tất cả chúng ta vẫn giải được các bà i toán theo phương pháp trên. Tuy nhiên, trong các trường hợp này tính toán tương đối phức tạp, tôi không tiện nêu ra. Tất cả chúng ta xét thêm một số ví dụ khác. Ví dụ 8. Tìm số nguyên dương n thoả mãn: 2 n − 1 . . . n Lời giải. Bài toán trên có thể giải rất dễ dàng nhờ phương pháp cấp của số nguyên. Gọi p là ước nguyên tố nhỏ nhất của n. Ta có: 2 n − 1 ≡ 0 (mod n) ⇒ 2 n − 1 ≡ 0 (mod p) Mặt khác do p là số nguyên tố nên 2 p−1 − 1 ≡ 0 (mod p) Suy và 2 n − 1 ≡ 0 (mod p) và 2 p−1 − 1 ≡ 0 (mod p) suy ra 2 (n,p−1) − 1 ≡ 0 (mod p). Nếu (n, p − 1) = 1 ta có p|1, suy ra n = 1. Nếu (n − 1, p) = 1 thì n sẽ chia hết cho một số nguyên tố nhỏ hơn p (trái với giả thiết p là ước số nguyên tố nhỏ nhất của n. Như vậy, n = 1 thoả mãn đề bài. Ta hãy nghĩ mở rộng ví dụ 9. Ta có được ta có bài toán: Ví dụ 9. Tìm các số nguyên n thoả mãn: n 2 |2 n + 1 Seminar Trường THPT chuyên ĐHSP HN Page 10 […]… dụng căn nguyên thuỷ một cách thành thục Bài tập 1 Cho n = 2h + 1 Minh chứng rằng n là số nguyên tố nếu và chỉ nếu 3 (mod p) n−1 2 ≡ −1 φ(p − 1) số g thoả mãn 2 0 < g < p và g là một căn nguyên thủy của pk với mọi số tự nhiên k Bài tập 2 Cho p là một số nguyên tố Minh chứng rằng có ít nhất Bài tập 3 Giả sử rằng 4n + 2n + 1 là một số nguyên tố Minh chứng rằng n là luỹ thừa của 3 Bài tập 4 Cho p là số nguyên. .. 1) 2 22k , với k là số các ước nguyên tố của p − 1 M là một số nguyên bất kì Minh chứng rằng trong tập hợp {M + 1, M + 2, , M + p−1 √ 2 2k p − 1} tồn tại ít nhất một căn nguyên thuỷ mod p φ(p − 1) Bài tập 5 Tìm các bộ ba số nguyên tố (p, q, r) thoả mãn: p|q r + 1 q|rp + 1 r|pq + 1 Bài tập 6 Cho p là một số nguyên tố và k ≥ 2 là một số nguyên dương Giả sử q là ước số nguyên tố nhỏ nhất của k Minh chứng… nghiệm Tóm lại n là số nguyên tố thoả mãn đề bài Ta hãy xét các bài toán có dạng khác Seminar Trường THPT chuyên ĐHSP HN Page 12 Nguyễn Thanh Trà Ví dụ 11 (Balkan 1999) Cho p là một số nguyên tố có dạng 3n + 2 Đặt: S = x, y là các số nguyên, 0 < x, y < p − 1 Minh chứng rằng có nhiều nhất p phần tử trong S chia hết cho p Minh chứng Ta có nhận xét: Nếu p là một số nguyên tố Khi đó các số… nhất cần tìm là k m Lời kết Căn nguyên thuỷ là một lí thuyết rất mạnh, có tính ứng dụng cao trong giải toán số học Nhưng vì dung tích của nội dung không nhiều nên tôi chưa thể giới thiệu hết các ứng dụng của nó Cácvấn đề còn lại sẽ được trình bày trong thời gian sớm nhất có thể Seminar Trường THPT chuyên ĐHSP HN Page 16 Nguyễn Thanh Trà 3 Một số bài tập Để kết thúc chuyên mục, tôi xin giới thiệu một… (−1)i ai là số lẻ nên ta có a + 1 ≡ 0 (mod 2k ) i=0 Kí hiệu số mũ của p trong phân tích thành thừa số nguyên tố của n! là vp (n!) Ta xét hai trường hợp: Trường hợp 1 n ≥ 3, n là một số nguyên tố Ta có vp (n!) = 1 Gọi p ≥ 3 là một ước số nguyên tố của của n!, p = n và gọi k = vp (n!) Gọi g là một căn nguyên thuỷ mod pk φ(pk ) Suy ra g 2 ≡ −1 (mod pk ) Do (a, n) = 1 nên tồn tại x ∈ {1, 2, , φ(pk )} thoả… nên d = 1 và n = 3 Thử lại thấy n = 3 đúng Vậy số nguyên dương n thoả mãn đề bài là n = 3 Như ta đã thấy, việc biến hoá số chia cho ta một bài toán rất thú vị Tiếp tục mở rộng, ta được bài toán: Ví dụ 10 Tìm toàn bộ các số nguyên n > 1 sao cho tồn tại duy nhất số nguyên dương a với 0 < a < n! thoả mãn: an + 1 ≡ 0 (mod n!) trong đó n! là tích của các số nguyên dương từ 1 đến n Lời giải Ta thấy n = 2 thoả… giải Gọi ai là các số nguyên dương phân biêt 1 ≤ ai ≤ 2001 thoả mãn ai + aj = 2001 Xét: n a3 + (2001 − a1 )3 i i=1 n 20013 − 3 · 20012 ai + 3 · 2001a2 i = i=1 n a2 i ≡ 2001 (mod 20012 ) i=1 Seminar Trường THPT chuyên ĐHSP HN Page 13 Nguyễn Thanh Trà Suy ra n (a3 + (2001 − a1 )3 ) ≡ 0 (mod 20012 ) ⇔ n a2 ≡ 0 (mod 667) i i=1 i=1 i Gọi p là một số nguyên tố bất kì, đặt g là một căn nguyên thuỷ của p và… = gcd n, pk−1 (p − 1) = 1 nên x có nghiệm duy nhất mod φ(pk ) Suy ra a có nghiệm duy nhất mod n! với n ≥ 3 là số nguyên tố Trường hợp 2 n là hợp số, n ≥ 3 Gọi p là một ước số nguyên tố phân biệt với n, p ≥ 3 (p luôn tồn tại do n là một hợp số lẻ) Suy ra k = vp (n!) ≥ 2 Gọi g là một căn nguyên thuỷ mod pk φ(pk ) Suy ra g 2 ≡ −1 (mod pk ) Do (a, n) = 1 nên tồn tại x ∈ {1, 2, , φ(pk )} thoả mãn a ≡ g… thoả mãn n2 |2n + 1, khi đó 2n + 1 n2 nên n là một số lẻ Gọi p là ước nguyên tố nhỏ nhất của n Gọi p là ước nguyên tố nhỏ nhất của n Ta có: 2n − 1 ≡ 0 (mod n) ⇒ 2n − 1 ≡ 0 (mod p) Mặt khác do p là số nguyên tố nên 2p−1 − 1 ≡ 0 (mod p) Suy và 22n − 1 ≡ 0 (mod p) và 2p−1 − 1 ≡ 0 (mod p) suy ra 2(2n,p−1) − 1 ≡ 0 (mod p) Do p là ước nguyên tố nhỏ nhất của n nên (2n, p − 1) = 2 Như vậy, ta có p|3 Suy ra… Seminar Trường THPT chuyên ĐHSP HN Page 14 Nguyễn Thanh Trà Mà: 2001 i = i=1 2 2001 3 i = i=1 2001 · 2001 2 2 ≡0 (mod p) Như vậy ta có cách chia tập hợp A = {13 , 23 , , 20003 } thành 25 tập hợp con thoả mãn tổng toàn bộ các phần tử trong một tập hợp con chia hết cho 20012 Ví dụ 13 Cho p là một số nguyên tố lẻ và đặt S = {n1 , n2 , nk } là một tập hợp bất kì của các số chính phương nguyên tố cùng nhau . PRIMITIVE ROOT Nguyễn Thanh Trà K42 Trường THPT Chuyên ĐHSP HN [email protected] Ngày 27 tháng. tương tự như trên, ta có số k nhỏ nhất cần tìm là k p − 1 m Lời kết. Căn nguyên thuỷ là một lí thuy t rất mạnh, có tính ứng dụng cao trong giải toán số học. Nhưng vì dung tích của nội dung khô
