Luận Văn Thạc Sĩ: Ứng Dụng Cấp và Chỉ Số Cho Số Nguyên Theo Modulo

Số nguyên a đồng dư với b theo modulo m nếu a và b có cùng số dư khi chia cho m. Kí hiệu: a ≡ b (mod m). Ví dụ: 3 ≡ 10 (mod 7), −25 ≡ 23 (mod 8). Điều này tương đương với việc m chia hết a - b, hay tồn tại số nguyên t sao cho a = b + mt. Đồng dư thức có nhiều tính chất quan trọng như cộng, trừ, nhân từng vế theo cùng một modulo. Các tính chất này tạo nên nền tảng cho việc giải quyết các bài toán liên quan đến chia hết và số dư.

Quan hệ đồng dư theo modulo m là một quan hệ tương đương trong tập số nguyên Z, tạo ra tập thương Zm, gọi là tập các lớp thặng dư modulo m. Mỗi phần tử A của Zm là một lớp thặng dư modulo m, kí hiệu a = {x ∈ Z | x ≡ a (mod m)}. Tập Zm có m phần tử. Hệ thặng dư đầy đủ modulo m là tập hợp các số nguyên lấy ra ở mỗi lớp thặng dư của Zm một và chỉ một số. Ví dụ, {0, 1, 2, 3, 4, 5, 6, 7} là một hệ thặng dư đầy đủ modulo 8.

Cấp của a modulo m (ordm a) là số mũ e nhỏ nhất sao cho ae ≡ 1 (mod m), với ƯCLN(a, m) = 1. Cấp luôn tồn tại vì theo định lý Euler, a^(ϕ(m)) ≡ 1 (mod m). Cấp đóng vai trò quan trọng trong việc nghiên cứu cấu trúc của nhóm nhân các số nguyên modulo n (Zn*). Việc tìm cấp của một số modulo m có thể được thực hiện bằng cách thử các ước của ϕ(m).

Cấp của a modulo m luôn là ước của ϕ(m). Đây là một kết quả quan trọng giúp giới hạn phạm vi tìm kiếm cấp. Ví dụ, nếu m là số nguyên tố p, thì ϕ(p) = p-1, do đó cấp của a modulo p phải là ước của p-1. Điều này có ứng dụng trong việc kiểm tra tính nguyên tố.

Để tính cấp của a modulo m, ta cần phân tích ϕ(m) thành thừa số nguyên tố. Sau đó, kiểm tra xem a^(ϕ(m)/p) ≡ 1 (mod m) với mọi ước nguyên tố p của ϕ(m). Nếu không thỏa mãn với bất kỳ p nào, thì cấp của a modulo m là ϕ(m). Ngược lại, cấp sẽ là một ước của ϕ(m)/p, và ta tiếp tục quá trình này cho đến khi tìm ra giá trị nhỏ nhất thỏa mãn.

Định lý Lucas cung cấp một tiêu chuẩn để kiểm tra tính nguyên tố của một số n dựa trên việc tìm một số a sao cho a^(n-1) ≡ 1 (mod n) và a^((n-1)/q) ≠ 1 (mod n) với mọi ước nguyên tố q của n-1. Nếu tồn tại một số a như vậy, thì n là số nguyên tố. Ứng dụng này dựa trên mối quan hệ giữa cấp và định lý Fermat nhỏ.

Để chứng minh một số n là số nguyên tố bằng cách sử dụng cấp, ta cần tìm một số a sao cho cấp của a modulo n là n-1. Điều này có nghĩa là a là căn nguyên thủy modulo n, và theo một định lý, nếu n có căn nguyên thủy thì n phải là số nguyên tố. Quá trình tìm kiếm a có thể tốn thời gian, nhưng đây là một phương pháp hiệu quả khi các phương pháp khác khó áp dụng.

Xét số n = 7. Ta cần tìm a sao cho cấp của a modulo 7 là 6. Chọn a = 3. Ta có 3^1 ≡ 3 (mod 7), 3^2 ≡ 2 (mod 7), 3^3 ≡ 6 (mod 7), 3^4 ≡ 4 (mod 7), 3^5 ≡ 5 (mod 7), và 3^6 ≡ 1 (mod 7). Do đó, cấp của 3 modulo 7 là 6, và 7 là số nguyên tố. Ví dụ này minh họa cách áp dụng cấp để chứng minh tính nguyên tố.

Một số g là căn nguyên thủy modulo p nếu cấp của g modulo p là p-1, tức là ordp(g) = p-1. Điều này có nghĩa là g^(p-1) ≡ 1 (mod p), và g^((p-1)/q) ≠ 1 (mod p) với mọi ước nguyên tố q của p-1. Để kiểm tra xem một số có phải là căn nguyên thủy hay không, ta cần kiểm tra tất cả các ước nguyên tố của p-1.

Nếu p là số nguyên tố, thì số lượng căn nguyên thủy modulo p là ϕ(p-1). Điều này có nghĩa là số lượng các số mà cấp của chúng modulo p là p-1 là ϕ(p-1). Ví dụ, nếu p = 7, thì p-1 = 6, và ϕ(6) = 2. Do đó, có 2 căn nguyên thủy modulo 7. (Chúng là 3 và 5).

Việc tìm căn nguyên thủy có thể tốn thời gian. Một phương pháp là chọn ngẫu nhiên các số từ 2 đến p-1 và kiểm tra xem chúng có phải là căn nguyên thủy hay không. Khi tìm thấy một căn nguyên thủy g, ta có thể tạo ra tất cả các căn nguyên thủy khác bằng cách tính g^k (mod p), với ƯCLN(k, p-1) = 1. (Các số k này thuộc hệ thặng dư thu gọn modulo (p-1))

Định lý quan trọng xác định rằng chỉ các số có dạng 1, 2, 4, pk, hoặc 2pk (với p là số nguyên tố lẻ và k ≥ 1) mới có căn nguyên thủy. Các số khác, ví dụ như 8 hoặc 12, không có căn nguyên thủy. Chứng minh định lý này sử dụng các kết quả về cấu trúc nhóm nhân các số nguyên modulo n.

Ví dụ, số 7 (là số nguyên tố) có căn nguyên thủy (ví dụ: 3). Số 9 (3^2) cũng có căn nguyên thủy (ví dụ: 2). Tuy nhiên, số 8 (2^3) không có căn nguyên thủy. Số 15 (3 * 5) cũng không có căn nguyên thủy. Các ví dụ này minh họa định lý về các số có và không có căn nguyên thủy.

Điều kiện cần và đủ giúp ta nhanh chóng xác định xem một số có căn nguyên thủy hay không. Nếu số đó không thuộc dạng 1, 2, 4, pk, hoặc 2pk, thì ta biết ngay là nó không có căn nguyên thủy, và không cần phải tìm kiếm. Điều này tiết kiệm thời gian và công sức trong các bài toán liên quan đến lý thuyết số.

Nếu r là căn nguyên thủy modulo m, thì chỉ số của a modulo m (với cơ số r) là số k sao cho r^k ≡ a (mod m). Kí hiệu: indr(a) = k. Chỉ số có các tính chất tương tự như logarit, ví dụ: indr(ab) ≡ indr(a) + indr(b) (mod ϕ(m)).

Chỉ số có thể được sử dụng để giải các phương trình đồng dư dạng x^n ≡ a (mod m). Bằng cách lấy chỉ số của cả hai vế, ta có n * indr(x) ≡ indr(a) (mod ϕ(m)). Phương trình này là một phương trình tuyến tính, có thể giải được bằng các phương pháp thông thường.

Xét phương trình x^3 ≡ 2 (mod 7). Ta biết 3 là căn nguyên thủy modulo 7. Bảng chỉ số (với cơ số 3) là: ind3(1) = 0, ind3(2) = 2, ind3(3) = 1, ind3(4) = 4, ind3(5) = 5, ind3(6) = 3. Phương trình trở thành 3 * ind3(x) ≡ 2 (mod 6). Giải phương trình này, ta được ind3(x) ≡ 4 (mod 6). Do đó, x ≡ 3^4 ≡ 4 (mod 7). Vậy nghiệm của phương trình là x ≡ 4 (mod 7).