Luận văn Thạc sĩ Toán học: Ứng dụng của cấp và chỉ số cho số nguyên theo Modulo

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:51

Thêm vào BST

Báo xấu

18
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung luận văn nghiên cứu về khái niệm và tính chất của cấp và chỉ số cho số nguyên theo modulo m, đồng thời xét một số ứng dụng điển hình của chúng trong các bài toán số học có liên quan. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Ứng dụng của cấp và chỉ số cho số nguyên theo Modulo

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– PHẠM THỊ ĐỊNH ỨNG DỤNG CỦA CẤP VÀ CHỈ SỐ CHO SỐ NGUYÊN THEO MODULO THÁI NGUYÊN, 5/2019
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– PHẠM THỊ ĐỊNH ỨNG DỤNG CỦA CẤP VÀ CHỈ SỐ CHO SỐ NGUYÊN THEO MODULO Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 8460113 LUẬN VĂN THẠC SĨ TOÁN HỌC GIÁO VIÊN HƯỚNG DẪN TS. NGÔ THỊ NGOAN THÁI NGUYÊN, 5/2019
Mục lục Lời cảm ơn 2 Mở đầu 3 1 Kiến thức chuẩn bị 5 1.1 Lý thuyết chia hết trong tập số nguyên . . . . . . . . . . . 5 1.2 Đồng dư thức và phương trình đồng dư . . . . . . . . . . . 9 2 Ứng dụng của cấp và chỉ số của số nguyên 16 2.1 Khái niệm, ví dụ, tính chất cơ bản về cấp cho số nguyên theo modulo . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2 Khái niệm và tính chất của căn nguyên thủy modulo . . . . 21 2.3 Cấp cho số nguyên theo modulo và ứng dụng để kiểm tra tính nguyên tố . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.4 Cấp cho số nguyên theo modulo và ứng dụng nhận diện các căn nguyên thủy của số nguyên tố . . . . . . . . . . . . . . 27 2.5 Cấp cho số nguyên theo modulo và áp dụng nhận diện số nguyên có căn nguyên thủy . . . . . . . . . . . . . . . . . . 34 2.6 Chỉ số cho số nguyên theo modulo và ứng dụng . . . . . . . 43 Kết luận 48 Tài liệu tham khảo 49 1
Lời cảm ơn Trước tiên tôi xin gửi lời cảm ơn chân thành và sâu sắc nhất tới TS. Ngô Thị Ngoan với lòng nhiệt huyết đã luôn chỉ bảo tận tình cho tôi từ những ngày đầu tiên, đồng thời đưa ra những lời khuyên bổ ích giúp tôi hoàn thiện luận văn này. Tôi cũng xin gửi lời cảm ơn tới các thầy cô, tập thể cán bộ khoa Toán - Tin, Trường Đại học Khoa học - Đại học Thái Nguyên, Ban lãnh đạo và các đồng nghiệp trường Trung học phổ thông Hoành Bồ - tỉnh Quảng Ninh, cùng các bạn học viên lớp cao học toán K11D, đã không chỉ trang bị cho tôi những kiến thức bổ ích mà còn luôn giúp đỡ, tạo điều kiện thuận lợi trong quá trình tôi học tập tại trường. Cuối cùng tôi xin cảm ơn gia đình, bạn bè người thân là những người luôn ủng hộ, động viên tôi vượt qua những khó khăn để em hoàn thành tốt luận văn. Thái Nguyên, ngày 25 tháng 5 năm 2019 2
Mở đầu Nội dung luận văn nghiên cứu về khái niệm và tính chất của cấp và chỉ số cho số nguyên theo modulo m, đồng thời xét một số ứng dụng điển hình của chúng trong các bài toán số học có liên quan. Luận văn bao gồm hai chương. Chương 1 của luận văn trình bày các kiến thức chuẩn bị về lý thuyết chia hết trong tập số nguyên, đồng dư thức, các lớp thặng dư đầy đủ, hệ thặng dư đầy đủ, hệ thặng dư thu gọn . . .. Các kiến thức này được tham khảo chủ yếu từ tài liệu [1]. Nội dung của Chương 2 gồm 6 mục, từ Mục 2.1 đến Mục 2.6, đề cập đến các khái niệm và ứng dụng của cấp cho số nguyên theo modulo, căn nguyên thủy modulo, chỉ số cho số nguyên theo modulo. Trước tiên luận văn trình bày về khái niệm cấp cho số nguyên a theo modulo m (với điều kiện a nguyên tố với modulo m), đó là số mũ nguyên dương nhỏ nhất e sao cho ae ≡ 1 (mod m), kí hiệu e = ordm a. Sau đó luận văn giới thiệu khái niệm và tính chất của căn nguyên thủy cho số nguyên theo modulo m, đó là thặng dư không âm nhỏ nhất α modulo m thỏa mãn ordm α = ϕ(m). Khái niệm căn nguyên thủy modulo m có nhiều ứng dụng trong số học, chẳng hạn nó sẽ sinh ra đủ ϕ(m) thặng dư nguyên tố với modulo m,... Tiếp đến luận văn khảo sát tiêu chuẩn để kiểm tra tính nguyên tố của một số số nguyên dương bằng cách ứng dụng các tính chất của cấp cho số nguyên theo modulo và căn nguyên thủy modulo (Định lý 2.3.1). Vì vai trò quan trọng của căn nguyên thủy trong số học và những bài toán liên quan nên, luận văn khảo sát kĩ hơn về bài toán nhận diện các căn nguyên thủy modulo số nguyên tố (Định lý 2.4.7), đó cũng là áp dụng hiệu quả của cấp cho số nguyên theo modulo. Lưu ý rằng có những số nguyên dương không có căn nguyên thủy, chẳng hạn: số 8, số 12 đều không có căn nguyên thủy,. . . Do đó, tiếp đến luận văn trình bày ứng dụng của cấp cho 3
số nguyên theo modulo vào bài toán nhận diện lớp các số nguyên dương có các căn nguyên thủy đó là các số nguyên 1, 2, 4, pk , 2pk với p là số nguyên tố lẻ (Định lý 2.5.19). Phần cuối của luận văn giới thiệu khái niệm chỉ số cho số nguyên theo modulo đối với một cơ số, và xét một số ứng dụng vào phương trình đồng dư. Ngoài ra luận văn cũng trình bày nhiều ví dụ minh họa giúp cho người đọc dễ theo dõi, và đó cũng là những bài tập thích hợp cho phổ thông. Dưới đây là tóm lược nội dung các mục của Chương 2. • Mục 2.1 sẽ đề cập đến các khái niệm và tính chất cơ bản về cấp cho số nguyên theo modulo và các ví dụ minh họa. • Mục 2.2 trình bày về khái niệm và tính chất của căn nguyên thủy modulo. • Mục 2.3 trình bày ứng dụng của cấp cho số nguyên theo modulo vào bài toán kiểm tra tính nguyên tố dựa trên định lý Lucas và các hệ quả của nó. • Mục 2.4 trình bày ứng dụng của cấp cho số nguyên theo modulo vào nhận diện các căn nguyên thuỷ của số nguyên tố. • Mục 2.5 khảo sát ứng dụng của cấp cho số nguyên theo modulo vào bài toán nhận diện các số nguyên có căn nguyên thủy. • Mục 2.6 dành để trình bày về một khái niệm tương tự khái niệm lôgarit, đó là khái niệm chỉ số cho số nguyên theo modulo đối với một cơ sở, và xét một vài ứng dụng của nó vào phương trình đồng dư. Thái Nguyên, ngày 25 tháng 5 năm 2019 Tác giả luận văn Phạm Thị Định 4
Chương 1 Kiến thức chuẩn bị Nội dung Chương 1 được tham khảo chủ yếu từ tài liệu [1] và một phần nhỏ trong tài liệu [3]. Các kiến thức ở chương này nhằm chuẩn bị những kiến thức cơ bản giúp cho việc trình bày chương sau được hệ thống và dễ theo dõi hơn. Mục 1.1 sẽ nhắc lại về lý thuyết chia hết trong tập số nguyên; đồng thời mục này cũng nhắc lại khái niệm hệ số nhị thức và định lý nhị thức. Mục 1.2 nhắc lại các khái niệm cơ bản về đồng dư thức thức, hệ thặng dư đầy đủ, định lý Euler, định lý Fermat nhỏ, phương trình đồng dư. 1.1 Lý thuyết chia hết trong tập số nguyên Trong tập hợp số nguyên Z, các phép toán cộng, trừ và nhân luôn thực hiện được, tuy nhiên phép chia cho một số nguyên khác 0 không phải bao giờ cũng thực hiện được, nghĩa là phương trình ax = b, trong đó a, b ∈ Z; a 6= 0 không phải lúc nào cũng có nghiệm trong Z. Trong trường hợp ax = b có nghiệm trong Z, chúng ta đi đến khái niệm chia hết. Định nghĩa 1.1.1. Giả sử a, b là hai số nguyên, b 6= 0. Ta nói b chia hết a hay b là một ước của a và kí hiệu b | a nếu như có một số nguyên q sao cho a = bq. Khi đó ta cũng nói a chia hết cho b hay a là bội của b và viết . a..b. Khi b không chia hết a ta kí hiệu là b - a. Ví dụ 1.1.2. Trong tập số nguyên Z, ta có (i) −5 chia hết 10 hay 10 chia hết cho −5, vì 10 = (−2).(−5). 5
(ii) 1 và −1 là ước của mọi số nguyên a vì a = 1.a = (−1).(−a). (iii) 0 là bội của mọi số nguyên b 6= 0 vì 0 = b.0. Chú ý 1.1.3. Nếu b | a và a 6= 0 thì từ a = bq ta có q 6= 0 do đó |q| ≥ 1 cho nên |a| = |b|.|q| ≥ |b|. Các tính chất chia hết sẽ được trình bày vắn tắt dưới đây. (i) Số nguyên a là ước của 1 khi và chỉ khi a = ±1. (ii) Nếu b | a thì ±b | ±a. (iii) Nếu a | b và b | a thì a = ±b. (iv) Nếu b | a1 , b | a2 , . . . , b | an , với b, a1 , a2 , . . . , an ∈ Z thì b | (a1 x1 + a2 x2 + · · · + an xn ), ∀x1 , x2 , . . . , xn ∈ Z. Định lý 1.1.4. Với mỗi cặp số nguyên a, b cho trước (b 6= 0), tồn tại duy nhất cặp số nguyên q, r thỏa mãn hệ thức a = bq + r, 0 ≤ r < |b|. Chứng minh. Sự tồn tại cặp số nguyên q, r: Xét tập hợp M gồm các bội của b không vượt quá a M = {bx : x ∈ Z, bx ≤ a}. Ta thấy −|b|.|a| là một bội của b không vượt quá a nên M 6= ∅. Hơn nữa, M là một bộ phận của Z và bị chặn trên bởi a do đó trong M có số lớn nhất, chẳng hạn là bq, q ∈ Z. Vì |b| ≥ 1 nên ba + |b| > bq , do đó bq + |b| ∈ / M cũng là bội của b cho nên ta có bq ≤ a < bq + |b| hay 0 ≤ a − bq < |b|. Đặt r = a − bq ta được r ∈ Z, a = bq + r và 0 ≤ r < |b|. Để chứng minh tính duy nhất của cặp q, r ta giả sử có cặp số nguyên q1 , r1 cùng thỏa mãn hệ thức a = bq + r, 0 ≤ r < |b|; a = bq1 + r1 , 0 ≤ r1 < |b|. 6
Từ đây ta có b(q − q1 ) = −(r − r1 ) và |r − r1 | < |b|. Khi đó do |b| > 0 và |b||q − q1 | = |r − r1 | < |b| ta được |q − q1 | < 1. Do đó |q − q1 | = 0 hay q = q1 kéo theo r = r1 . Định nghĩa 1.1.5. Cho a, b là các số nguyên cho trước, b 6= 0. Khi có đẳng thức a = bq + r, trong đó q là một số nguyên, 0 ≤ r < |b|, thì ta nói a chia cho b được thương là q và số dư r. Kí hiệu a ≡ r (mod b). Chú ý 1.1.6. Trong trường hợp số dư r = 0, ta có a = bq, nghĩa là a chia hết cho b. Như vậy, phép chia hết là một trường hợp riêng của phép chia có dư. Số nguyên d được gọi là một ước chung của các số nguyên a1 , a2 , . . . , an nếu d là ước đồng thời của mỗi số nguyên đó. Một ước chung d của các số nguyên a1 , a2 , . . . , an sao cho mọi ước chung của a1 , a2 , . . . , an đều là ước của d được gọi là ước chung lớn nhất (viết tắt là ƯCLN) của các số đó. Các số nguyên a1 , a2 , . . . , an được gọi là nguyên tố cùng nhau nếu như ƯCLN của các số đó là 1. Số tự nhiên lớn hơn 1 không có ước nào khác ngoài 1 và chính nó được gọi là số nguyên tố. Chúng ta sẽ nhắc lại định lý cơ bản nhưng không đề cập đến chứng minh của nó. Định lý 1.1.7 (Định lý cơ bản). Mỗi số tự nhiên lớn hơn 1 đều phân tích được thành tích những thừa số nguyên tố và sự phân tích đó là duy nhất nếu không kể đến thứ tự của các thừa số. Nội dung định lý cơ bản đã nói lên vai trò quan trọng của số nguyên tố trong tập các số tự nhiên: mỗi số tự nhiên lớn hơn 1 đều được “cấu tạo” từ những số nguyên tố bởi phép nhân, mà chúng ta biết số nguyên tố là những số có ít ước nhất. Từ định lý cơ bản, các nhà toán học đã đi đến các ứng dụng của nó như: tiêu chuẩn chia hết, ước chung lớn nhất - bội chung nhỏ nhất. Các ứng dụng của định lý cơ bản đã được đề cập trong chương trình học đại học, trong luận văn này ta bỏ qua không nhắc lại. 7
Phần cuối của mục này ta nhắc lại khái niệm và tính chất của hệ số nhị thức. Định nghĩa 1.1.8. Cho n, r là các số nguyên không âm, hệ số nhị thức được kí hiệu là nr = r!(n−r)! n! nếu r ≤ n và bằng 0 nếu ngược lại; ta cũng thường kí hiệu hệ số nhị thức bởi Cnr . Từ định nghĩa, ta có n0 = 1 = nn và nr = n−r n . Định lý 1.1.9 (Đồng nhất thức Pascal). Cho n và r là hai số nguyên dương, trong đó r ≤ n. Khi đó nr = n−1 n−1 r−1 + r . Chứng minh. Ta sẽ biến đổi vế phải và đưa dần dần về vế trái: ! ! n−1 n−1 (n − 1)! (n − 1)! + = + r−1 r (r − 1)!(n − r)! r!(n − r − 1)! r(n − 1)! (n − r)(n − 1)! = + r(r − 1)!(n − r)! r!(n − r)(n − r − 1)! r(n − 1)! (n − r)(n − 1)! = + r!(n − r)! r!(n − r)! (n − 1)![r + (n − r)] (n − 1)!n = = r!(n − r)! r!(n − r)! ! n! n = = . r!(n − r)! r Định lý sau đây chỉ ra rằng ta có thể sử dụng các hệ số nhị thức để tìm khai triển của (x + y)n . Định lý 1.1.10 (Định lý nhị thức). Cho x, y là hai số thực bất kỳ và n là số nguyên không âm. Khi đó (x + y)n = nr=0 nr xn−r y r . P Chứng minh. Chứng minh bằng phương pháp quy nạp. Với n = 0, ta có (x + y)0 = 1 và 0r=0 0r x0−r y r = x0 y 0 = 1. Do đó giả thiết đúng với P n = 0. Giả sử định lý đúng với số k ≥ 0 nào đó, tức là k ! X k k−r r (x + y)k = x y . (1.1) r=0 r 8
Khi đó " k ! # X k k−r r (x + y)k+1 = (x + y)k (x + y) = x y (x + y) theo công thức 1.1 r=0 r k ! k ! X k X k = xk+1−r y r + xk−r y r+1 r=0 r r=0 r " ! k ! # " k−1 ! ! # k k+1 X k k+1−r r X k k−r r+1 k k+1 = x + x y + x y + y 0 r=1 r r=0 r k ! k ! k ! ! k + 1 k+1 X k k+1−r r X k k + 1 k+1 = x + x y + xk+1−r y r + y 0 r=1 r r=1 r − 1 r + 1 ! k " ! !# ! k + 1 k+1 X k k k + 1 k+1 = x + + xk+1−r y r + y 0 r=1 r r − 1 r + 1 ! k ! ! k + 1 k+1 X k + 1 k+1−r r k + 1 k+1 = x + x y + y (theo định lý 1.1.9) 0 r=1 r r + 1 k+1 ! X k+1 = xk+1−r y r . r=0 r Do vậy theo quy nạp, giả thiết trên đúng với mọi số nguyên n ≥ 0. 1.2 Đồng dư thức và phương trình đồng dư Đồng dư là một phương pháp có tính chất bổ trợ về mặt kỹ thuật để giải quyết vẫn đề chia hết trong vành số nguyên. Chúng ta đã biết tập hợp các số dư trong phép chia các số nguyên cho một số tự nhiên cho trước là tập hữu hạn phần tử, trong khi tập hợp số nguyên Z là một tập vô hạn phần tử. Vì thế ta có thể chuyển việc nghiên cứu trên Z về nghiên cứu trên một tập hợp hữu hạn. Định nghĩa 1.2.1. Cho 0 < m ∈ Z và a, b ∈ Z. Ta nói a đồng dư với b theo modulo m, kí hiệu a ≡ b (mod m), nếu trong các phép chia a và b cho m ta được cùng một số dư, nghĩa là có các số nguyên q1 , q2 , r với 0 ≤ r < m, sao cho a = mq1 + r và b = mq2 + r. Chú ý khi a ≡ b (mod m), ta cũng nói a, b đồng dư với nhau theo 9
modulo m). Trong trường hợp không xảy ra a đồng dư với b theo modulo m ta viết a 6≡ b (mod m). Ví dụ 1.2.2. Ta có 3 ≡ 10 (mod 7); −25 ≡ 23 (mod 8) Để thấy được ý nghĩa của đồng dư thức, ta nhắc lại các điều kiện tương đương với định nghĩa của nó ở định lý sau. Định lý 1.2.3. Các mệnh đề sau đây là tương đương (i) a, b đồng dư với nhau theo modulo m; (ii) m chia hết a − b; (iii) Tồn tại số nguyên t sao cho a = b + mt. Từ định nghĩa và định lý trên, chúng ta có thể dễ dàng suy ra các tính chất của đồng dư thức sau đây: Chú ý 1.2.4. [(i)] Quan hệ đồng dư là một quan hệ tương đương trên tập Z, nghĩa là nó có các tính chất đơn giản như sau: • ∀a ∈ Z : a ≡ a (mod m); • ∀a, b ∈ Z : a ≡ b (mod m) ⇒ b ≡ a (mod m); • ∀a, b, c ∈ Z : a ≡ b (mod m) và b ≡ c (mod m) ⇒ a ≡ c (mod m). (ii) Ta có thể cộng, trừ hoặc nhân từng vế của nhiều đồng dư thức theo cùng một modulo. Cụ thể là • a1 ≡ b1 (mod m) và a2 ≡ b2 (mod m) ⇒ a1 ± a2 ≡ b1 ± b2 (mod m). Thật vậy, từ a1 ≡ b1 (mod m) và a2 ≡ b2 (mod m) ta có t1 , t2 ∈ Z sao cho a1 = b1 + mt1 , a2 = b2 + mt2 . Do đó a1 ± a2 = b1 ± b2 + m(t1 ± t2 ) ⇒ a1 ± a2 ≡ b1 ± b2 (mod m). • a1 ≡ b1 (mod m) và a2 ≡ b2 (mod m) ⇒ a1 .a2 ≡ b1 .b2 (mod m). Thật vậy, a1 a2 = b1 b2 + m(b2 t1 + b1 t2 + mt1 t2 ) ⇒ a1 .a2 ≡ b1 .b2 (mod m). (iii) a ≡ b (mod m) ⇒ an ≡ bn (mod m), ∀n ∈ N. (iv) Ta có thể chia hai vế của một đồng dư thức cho một ước chung của chúng nguyên tố với modulo. 10
(v) Ta có thể nhân hai vế và modulo của một đồng dư thức với cùng một số nguyên dương. Nghĩa là a ≡ b (mod m) ⇒ ac ≡ bc (mod mc), ∀c ∈ Z, c > 0. Tương tự, ta có thể chia hai vế và modulo của một đồng dư thức cho một ước chung dương của chúng. Cụ thể là a b m a ≡ b (mod m), 0 < δ ∈ Z, δ | ƯCLN(a,b,m) ⇒ ≡ (mod ). δ δ δ Ta biết rằng quan hệ đồng dư theo modulo m là một quan hệ tương đương trong tập số nguyên Z cho nên tồn tại tập thương Z trên quan hệ tương đương này. Định nghĩa 1.2.5. Tập thương của Z trên quan hệ đồng dư theo modulo m gọi là tập các lớp thặng dư modulo m và kí hiệu là Zm . Mỗi phần tử A của Zm được gọi là một lớp thặng dư modulo m. Với A ∈ Zm và a ∈ A, ta kí hiệu a = {x ∈ Z | x ≡ a (mod m)} thì a = A. Như vậy, mỗi lớp thặng dư A modulo m có dạng a (mod m), với a là một phần tử tùy ý của A. Phần tử a như thế được gọi là một đại diện của lớp A và cũng gọi là một thặng dư modulo m. Ta dễ thấy tập hợp Zm có m phần tử. Ví dụ 1.2.6. Trong Z8 , lớp thặng dư 1 (mod 8) là 1 = {x ∈ Z : x ≡ 1 (mod 8)} = {. . . − 15, −7, 1, 9, 17, . . .} Nhận xét 1.2.7. (i) ƯCLN của một lớp thặng dư A với modulo m được xác định là ƯCLN của một thặng dư tùy ý của lớp đó với modulo m, kí hiệu ƯCLN(A, m). Nói cách khác ƯCLN(A, m) = ƯCLN(a, m) với a ∈ A. (ii) Trong Zm , tập hợp các lớp thặng dư nguyên tố với modulo m được kí hiệu bởi Z∗m . Như vậy Z∗m = {A ∈ Zm : ƯCLN(A, m) = 1}. Số các phần tử của tập hợp Z∗m được kí hiệu là ϕ(m) (ta gọi là hàm Euler). 11
Chú ý 1.2.8. Vì vậy, có thể nói ϕ(m) là các số tự nhiên không vượt quá m − 1 và nguyên tố với m. Ta cũng biết rằng Zm = {1, 2, . . . , m}, nên Z∗m = {a ∈ Zm : 1 ≤ a ≤ m, ƯCLN(a, m) = 1}. Ví dụ 1.2.9. Trong Z8 = {0, 1, 2, 3, 4, 5, 6, 7} ta có ƯCLN(0, 8) = 8, ƯCLN(1, 8) = 1, ƯCLN(2, 8) = 2, ƯCLN(3, 8) = 1, ƯCLN(4, 8) = 4, ƯCLN(5, 8) = 1, ƯCLN(6, 8) = 2, ƯCLN(7, 8) = 1. Các lớp nguyên tố với modulo 8 là 1, 3, 5, 7. Ví dụ 1.2.10. Ta có ϕ(1) = 1, ϕ(5) = 4, ϕ(9) = 6, . . . Tổng quát hơn ta có ϕ(p) = p − 1 với p là số nguyên tố. Định nghĩa 1.2.11. Cho 0 < m ∈ N. Tập hợp H gồm những số nguyên lấy ra ở mỗi lớp thặng dư của Zm một và chỉ một số được gọi là hệ thặng dư đầy đủ modulo m. Như vậy, tập hợp H bao gồm những số nguyên là một hệ thặng dư đầy đủ modulo m khi và chỉ khi • Các phần tử của H đôi một không đồng dư với nhau theo modulo m; • Mỗi số nguyên tùy ý đều đồng dư theo modulo m với một số nào đó thuộc H . Ví dụ 1.2.12. Với m = 8 ta có {0, 1, 2, 3, 4, 5, 6, 7} là một hệ thặng dư đầy đủ modulo 8, nó được gọi là hệ thặng dư đầy đủ không âm nhỏ nhất. {−3, −2, −1, 0, 1, 2, 3, 4} là một hệ thặng dư đầy đủ modulo 8, hệ này được gọi là hệ thặng dư đầy đủ giá trị tuyệt đối nhỏ nhất. Tổng quát hơn, ta có: H = {0, 1, . . . , m − 1} là một hệ thặng dư đầy đủ modulo m và nóđược gọi là hệ thặng dư đầy đủ không âm nhỏ nhất. Với m−1 m−1 m−1 m là số lẻ, H = − ,− + 1, . . . , là một hệ thặng dư 2 2 2 đầy đủ modulo m, gọi lànhệ thặng dư đầy đủ giá trị o tuyệt đối nhỏ nhất. m m m Với m là số chẵn, H = − , − + 1, . . . , − 1 là hệ thặng dư đầy 2 2 2 đủ giá trị tuyệt đối nhỏ nhất. Định nghĩa 1.2.13. Cho m là một số nguyên dương. Tập hợp K gồm những số nguyên được lấy ra ở mỗi lớp nguyên tố với modulo m của Z∗m một và chỉ một số được gọi là một hệ thặng dư thu gọn modulo m. 12
Vậy, một tập hợp K gồm những số nguyên được gọi là một hệ thặng dư thu gọn modulo m khi và chỉ khi • Các phần tử thuộc K đôi một không đồng dư với nhau theo modulo m; • Các phần tử thuộc K nguyên tố với modulo m; • Mỗi số nguyên tùy ý nguyên tố với modulo m đều đồng dư với một số nào đó thuộc K . Ví dụ 1.2.14. Với m = 8 ta có {1, 3, 5, 7} là hệ thặng dư thu gọn không âm nhỏ nhất và {−3, −1, 1, 3} là hệ thặng dư thu gọn giá trị tuyệt đối nhỏ nhất. Nếu m = p là số nguyên tố thì {1,2, . . . , p − 1} là hệ thặng dư thu gọn p−1 p−1 không âm nhỏ nhất và nếu p > 2 thì − , . . . , −2, −1, 1, 2, . . . , 2 2 là hệ thặng dư thu gọn giá trị tuyệt đối nhỏ nhất. Định lý 1.2.15 (Định lý Euler). Giả sử 1 < m ∈ N và a ∈ Z thỏa mãn ƯCLN(a, m) = 1. Khi đó ta có aϕ(m) ≡ 1 (mod m). Chứng minh. Cho x chạy qua hệ thặng dư thu gọn modulo m không âm nhỏ nhất {r1 , r2 , . . . , rϕ(m) }. Khi đó, tập hợp {ar1 , ar2 , . . . , arϕ(m) } cũng là một hệ thặng dư thu gọn modulo m. Gọi s1 , s2 , . . . , sϕ(m) là các thặng dư không âm nhỏ nhất tương ứng cùng lớp với ar1 , ar2 , . . . , arϕ(m) thì ta có ar1 ≡ s1 (mod m), ar2 ≡ s2 (mod m), ... arϕ(m) ≡ sϕ(m) (mod m), ta sẽ được {s1 , s2 , . . . , sϕ(m) } cũng là hệ thặng dư thu gọn modulo m không âm nhỏ nhất. Bằng cách nhân vế với vế của ϕ(m) đồng dư trên ta được aϕ(m) .r1 r2 . . . rϕ(m) ≡ s1 s2 . . . sϕ(m) (mod m). Bởi vì {r1 , r2 , . . . , rϕ(m) } và {s1 , s2 , . . . , sϕ(m) } cùng là hệ thặng dư thu gọn modulo m không âm nhỏ nhất nên ta có r1 r2 . . . rϕ(m) = s1 s2 . . . sϕ(m) , 13
từ đó aϕ(m) .r1 r2 . . . rϕ(m) ≡ r1 r2 . . . rϕ(m) (mod m). Nhưng tích r1 r2 . . . rϕ(m) nguyên tố với m (vì từng thừa số của nó nguyên tố với m), nên có thể chia hai vế của đồng dư thức trên đây cho r1 r2 . . . rϕ(m) ta được aϕ(m) ≡ 1 (mod m). Hệ quả 1.2.16 (Định lý Fermat nhỏ). Cho p là một số nguyên tố và a là một số nguyên không chia hết cho p. Khi đó ta có ap−1 ≡ 1 (mod p). Chứng minh. Theo giả thiết ta có ϕ(p) = p − 1 và a nguyên tố với p nên theo định lý Euler ta được ap−1 ≡ 1 (mod p). Sử dụng hệ quả trên ta có công thức khác của định lý Fermat sau đây. Định lý 1.2.17. Cho p là một số nguyên tố và a là một số nguyên. Khi đó ta có ap ≡ a (mod p). Tiếp theo ta nhắc lại những kiến thức cơ bản về phương trình đồng dư. Định nghĩa 1.2.18. Giả sử g(x), h(x) ∈ Z[x] và 1 < m ∈ N. Khi đó đồng dư thức g(x) ≡ h(x) (mod m) hoặc f (x) = g(x) − h(x) ≡ 0 (mod m) được gọi là phương trình đồng dư một ẩn. Định nghĩa 1.2.19. Cho f (x) = a0 + a1 x + a2 x2 + · · · + an xn ∈ Z[x]. Nếu với x = x0 ∈ Z thỏa mãn f (x0 ) ≡ 0 (mod m) (1.2) thì ta nói x0 nghiệm đúng của phương trình f (x) ≡ 0 (mod m). Giải một phương trình đồng dư là tìm tập hợp các giá trị nghiệm đúng phương trình đồng dư đó. Giả sử g(x), h(x) ∈ Z[x]. Hai phương trình đồng dư g(x) ≡ 0 (mod m1 ), h(x) ≡ 0 (mod m2 ) tương đương với nhau nếu như tập hợp các giá trị nghiệm đúng phương trình này bằng tập hợp các giá trị nghiệm đúng phương trình kia. Khi đó ta viết g(x) ≡ 0 (mod m1 ) ⇔ h(x) ≡ 0 (mod m2 ). Sử dụng các tính chất của đồng dư thức ta có nhiều phép biến đổi tương đương các phương trình đồng dư. 14
Định nghĩa 1.2.20. Trong phương trình (1.2) nếu an 6≡ 0 (mod m) thì ta nói rằng n là bậc của phương trình đồng dư (1.2). Tập hợp các giá trị nghiệm đúng phương trình f (x) ≡ 0 (mod m) được phân chia thành những lớp theo modulo m và được gọi là những nghiệm của phương trình đó. Định lý sau đây là cơ sở cho việc định nghĩa nghiệm của một phương trình đồng dư. Định lý 1.2.21. Nếu x = α nghiệm đúng phương trình (1.2) thì mọi số nguyên thuộc lớp thặng dư α (mod m) đều nghiệm đúng phương trình (1.2). Định nghĩa 1.2.22. Khi số nguyên α nghiệm đúng phương trình (1.2) thì ta gọi lớp thặng dư α (mod m) là một nghiệm của phương trình (1.2). Khi α (mod m) là một nghiệm của phương trình (1.2) thì ta cũng có thể viết x ≡ α (mod m) là một nghiệm của phương trình (1.2). Vì Zm có m phần tử nên số nghiệm của một phương trình đồng dư theo modulo m không vượt quá m. Đối với phương trình bậc 1 ta có kết quả sau đây. Định lý 1.2.23. Phương trình đồng dư bậc nhất ax + b ≡ 0 (mod m) có nghiệm duy nhất nếu (a, m) = 1. 15
Chương 2 Ứng dụng của cấp và chỉ số của số nguyên Nội dung của Chương 2 đề cập đến các khái niệm và ứng dụng của cấp cho số nguyên theo modulo, căn nguyên thủy modulo, chỉ số cho số nguyên theo modulo. Mục 2.1 sẽ đề cập đến các khái niệm và tính chất cơ bản về cấp cho số nguyên theo modulo và các ví dụ minh họa. Mục 2.2 trình bày về khái niệm và tính chất của căn nguyên thủy modulo. Mục 2.3 trình bày ứng dụng của cấp cho số nguyên theo modulo vào bài toán kiểm tra tính nguyên tố dựa trên định lý Lucas và các hệ quả của nó. Mục 2.4 trình bày ứng dụng của cấp cho số nguyên theo modulo vào nhận diện các căn nguyên thuỷ cho số nguyên tố. Mục 2.5 khảo sát ứng dụng của cấp cho số nguyên modulo vào bài toán nhận diện các số nguyên có căn nguyên thủy. Mục cuối cùng dành để trình bày về một khái niệm tương tự khái niệm lôgarit, đó là khái niệm chỉ số cho số nguyên theo modulo đối với một cơ sở, và xét một vài ứng dụng của nó vào phương trình đồng dư. Nội dung chi tiết của chương 2 được tham khảo chủ yếu trong tài liệu [3]. 2.1 Khái niệm, ví dụ, tính chất cơ bản về cấp cho số nguyên theo modulo Cho m là số nguyên dương cố định, và a là số nguyên dương sao cho (a, m) = 1. Khi đó theo định lý Euler, tồn tại số mũ dương e sao cho ae ≡ 1 (mod m) (ở đây e = ϕ(m)). Nhìn chung số ϕ(m) không nhất thiết 16
là số mũ nhỏ nhất có tính chất như vậy. Theo tính chất sắp thứ tự tốt của tập các số nguyên dương, ta luôn chọn được số mũ dương nhỏ nhất có tính chất đã nêu. Chẳng hạn, nếu chúng ta tính toán đối với các thặng dư dương a nhỏ nhất và nguyên tố với modulo 9, tức là 1 ≤ a ≤ 8, (a, 9) = 1. Ta có ϕ(9) = 6 và a6 ≡ 1 (mod 9). Tìm sẽ cần số mũ nhỏ nhất trong mỗi trường hợp của a. Để thuận tiện ta sẽ tổng hợp các số mũ dương e nhỏ nhất sao cho ae ≡ 1 (mod 9) trong bảng 2.1 dưới đây (số mũ nhỏ nhất ứng với số có ô vuông). a a2 a3 a4 a5 a6 1 1 1 1 1 1 2 4 8 7 5 1 4 7 1 4 7 1 5 7 8 4 2 1 7 4 1 7 4 1 8 1 8 1 8 1 Bảng 2.1: Giá trị thặng dư của a theo modulo 9 Khái niệm cấp một số theo modulo m đã được nhà toán học Carl Friedrich Gauss (1777 − 1855) xuất bản vào năm 1801 trong cuốn sách “Disquisitiones Arithmeticae”. Định nghĩa 2.1.1. Cho m, a là các số nguyên dương sao cho (a, m) = 1. Khi đó số mũ dương e nhỏ nhất sao cho ae ≡ 1 (mod m) được gọi là cấp của a theo modulo m, kí hiệu bởi ordm a (hoặc ord a, nếu việc bỏ qua modulo m mà không dẫn đến nhầm lẫn). Theo định nghĩa trên và nhìn vào Bảng 2.1 ta có ord9 1 = 1, ord9 2 = ord9 5 = 6, ord9 4 = ord9 7 = 3 và ord9 8 = 2. Ví dụ 2.1.2. Tìm ord13 5 và ord13 7. Giải. Ta có (5, 13) = 1 = (7, 13). Ta tìm số mũ e nhỏ nhất của 5 và 7 theo modulo 13 sao cho 5e ≡ 1 (mod 13) và 7e ≡ 1 (mod 13). Ta có 52 ≡ −1 (mod 13), 53 ≡ −5 (mod 13), 54 ≡ 1 (mod 13) 17
Do vậy, ord13 5 = 4. Tương tự ta tính được 72 ≡ −3 (mod 13), 73 ≡ 5 (mod 13), 74 ≡ −4 (mod 13) 75 ≡ −2 (mod 13), 76 ≡ −1 (mod 13), 77 ≡ 6 (mod 13) 78 ≡ 3 (mod 13), 79 ≡ −5 (mod 13), 710 ≡ 4 (mod 13) 711 ≡ 2 (mod 13), 712 ≡ 1 (mod 13). Do vậy, ord13 7 = 12. Vậy, để tính ordm a, chúng ta cần tính ak theo modulo m với mọi số nguyên dương k ≤ ϕ(m). Việc tính toán này tốn khá nhiều thời gian nếu như các số nguyên dương đã cho có giá trị lớn. Định lý dưới đây giúp chúng ta loại trừ khá nhiều ứng cử viên để tính ordm a. Định lý 2.1.3. Cho a, m là số nguyên dương sao cho (a, m) = 1 và ordm a = e. Khi đó an ≡ 1 (mod m) khi và chỉ khi e | n. Chứng minh. Giả sử an ≡ 1 (mod m) nhưng e - n, vậy ta có n = qe + r trong đó 0 ≤ r < e. Khi đó an =aqe+r = (ae )q .ar ≡1q .ar ≡ ar (mod m). Nhưng theo giả thiết an ≡ 1 (mod m) nên ar ≡ 1 (mod m) trong đó 0 ≤ r < e. Vì e là số mũ bé nhất thỏa mãn ae ≡ 1 (mod m) và r < e suy ra r = 0. Do đó, n = qe và suy ra e | n. Để chứng minh chiều ngược lại, giả sử e | n. Khi đó n = be với b là số nguyên dương. Do đó an =abe = (ae )b ≡1b ≡ 1 (mod m). Hệ quả của Định lý 2.1.3 cung cấp cho ta một công cụ hiệu quả để tính ordm a. Hệ quả 2.1.4. Cho a, m là các số nguyên dương sao cho (a, m) = 1. Khi đó ordm a | ϕ(m). Trong trường hợp đặc biệt, nếu p là một số nguyên tố và p - a thì ordp a | (p − 1). 18