Cách Sử Dụng “Legendre symbol”

Trong bài viết này, chúng ta sẽ khám phá “Legendre symbol” – một khái niệm quan trọng trong lý thuyết số. Bài viết cung cấp 20 ví dụ sử dụng trong các bài toán và chứng minh, cùng hướng dẫn chi tiết về ý nghĩa, cách dùng, bảng ký hiệu, và các lưu ý quan trọng.

Phần 1: Hướng dẫn sử dụng “Legendre symbol” và các lưu ý

1. Ý nghĩa cơ bản của “Legendre symbol”

“Legendre symbol” là một hàm số trong lý thuyết số, được sử dụng để xác định xem một số nguyên có phải là thặng dư bậc hai modulo một số nguyên tố lẻ hay không. Nó thường được ký hiệu là (a/p), trong đó a là một số nguyên và p là một số nguyên tố lẻ.

• Ý nghĩa:
• (a/p) = 0 nếu a chia hết cho p.
• (a/p) = 1 nếu a là một thặng dư bậc hai modulo p (tức là tồn tại một số nguyên x sao cho x² ≡ a (mod p)).
• (a/p) = -1 nếu a không phải là một thặng dư bậc hai modulo p.

Ví dụ:

• (2/7) = 1 vì 3² ≡ 2 (mod 7).
• (3/7) = -1 vì không có số nguyên x nào mà x² ≡ 3 (mod 7).

2. Cách sử dụng “Legendre symbol”

a. Tính toán “Legendre symbol”

1. Sử dụng tiêu chuẩn Euler:
   Công thức: (a/p) ≡ a^(p-1)/2 (mod p).
   Ví dụ: (2/7) ≡ 2^(7-1)/2 ≡ 2³ ≡ 8 ≡ 1 (mod 7).
2. Sử dụng tính chất:
   Tính chất: (ab/p) = (a/p)(b/p).
   Ví dụ: (6/7) = (2/7)(3/7) = (1)(-1) = -1.

b. Định lý tương hỗ bậc hai (Quadratic Reciprocity)

1. Định lý: Nếu p và q là hai số nguyên tố lẻ phân biệt, thì (p/q)(q/p) = (-1)^((p-1)(q-1)/4).
   Ví dụ: Để tính (7/11), ta có (7/11)(11/7) = (-1)^((7-1)(11-1)/4) = (-1)^(60/4) = (-1)^15 = -1. Do đó, (7/11) = -(11/7). Vì 11 ≡ 4 (mod 7), (11/7) = (4/7) = 1. Vậy (7/11) = -1.

c. Các trường hợp đặc biệt

1. (1/p) = 1
   Ví dụ: (1/7) = 1
2. (-1/p) = 1 nếu p ≡ 1 (mod 4), -1 nếu p ≡ 3 (mod 4)
   Ví dụ: (-1/5) = 1, (-1/7) = -1
3. (2/p) = 1 nếu p ≡ 1 hoặc 7 (mod 8), -1 nếu p ≡ 3 hoặc 5 (mod 8)
   Ví dụ: (2/7) = 1, (2/5) = -1

d. Ký hiệu và cách dùng trong câu

Ký hiệu	Ý nghĩa	Ví dụ
(a/p)	Legendre symbol của a modulo p	(3/7) = -1 (3 không phải là thặng dư bậc hai modulo 7)

3. Một số ứng dụng của “Legendre symbol”

• Kiểm tra tính giải được của phương trình bậc hai:
  Ví dụ: Phương trình x² ≡ a (mod p) có nghiệm khi và chỉ khi (a/p) = 1 hoặc a chia hết cho p.
• Phân tích số nguyên tố:
  Ví dụ: Sử dụng trong các thuật toán kiểm tra tính nguyên tố.
• Mật mã học:
  Ví dụ: Sử dụng trong các lược đồ mã hóa dựa trên độ khó của bài toán thặng dư bậc hai.

4. Lưu ý khi sử dụng “Legendre symbol”

a. Điều kiện sử dụng

• p phải là số nguyên tố lẻ: Legendre symbol không được định nghĩa cho p không phải là số nguyên tố lẻ.
• a là số nguyên: a phải là một số nguyên.

b. Phân biệt với các ký hiệu khác

• “Legendre symbol” vs “Jacobi symbol”:
  – “Legendre symbol”: p phải là số nguyên tố.
  – “Jacobi symbol”: p có thể là hợp số lẻ.

5. Những lỗi cần tránh

1. Sử dụng Legendre symbol cho p không phải là số nguyên tố:
   – Sai: *(3/4)* (4 không phải là số nguyên tố)
   – Đúng: (3/5) = -1
2. Nhầm lẫn với Jacobi symbol: Nếu p không phải là số nguyên tố, phải sử dụng Jacobi symbol thay vì Legendre symbol.

6. Mẹo để ghi nhớ và sử dụng hiệu quả

• Nắm vững tiêu chuẩn Euler: (a/p) ≡ a^(p-1)/2 (mod p)
• Hiểu rõ định lý tương hỗ bậc hai: (p/q)(q/p) = (-1)^((p-1)(q-1)/4)
• Thực hành tính toán: Giải nhiều bài tập để làm quen với các tính chất và ứng dụng của Legendre symbol.

Phần 2: Ví dụ sử dụng “Legendre symbol” và các dạng liên quan

Ví dụ minh họa

1. Calculate (3/11). (Tính (3/11).)
2. Determine if 7 is a quadratic residue modulo 13 using the Legendre symbol. (Xác định xem 7 có phải là thặng dư bậc hai modulo 13 bằng cách sử dụng Legendre symbol.)
3. Compute the value of (5/17). (Tính giá trị của (5/17).)
4. Find (2/19). (Tìm (2/19).)
5. Evaluate (11/3). (Đánh giá (11/3).)
6. Use Legendre symbol to check if x² ≡ 5 (mod 11) has a solution. (Sử dụng Legendre symbol để kiểm tra xem x² ≡ 5 (mod 11) có nghiệm hay không.)
7. Determine (6/13) using the properties of Legendre symbol. (Xác định (6/13) bằng cách sử dụng các thuộc tính của Legendre symbol.)
8. Find the Legendre symbol of (8/11). (Tìm Legendre symbol của (8/11).)
9. Calculate (7/19). (Tính (7/19).)
10. Evaluate the Legendre symbol (10/17). (Đánh giá Legendre symbol (10/17).)
11. Compute (12/13). (Tính (12/13).)
12. Determine the value of Legendre symbol (14/19). (Xác định giá trị của Legendre symbol (14/19).)
13. Calculate the Legendre symbol (15/7). (Tính Legendre symbol (15/7).)
14. Find the value of (16/17). (Tìm giá trị của (16/17).)
15. Evaluate (17/5). (Đánh giá (17/5).)
16. Compute the Legendre symbol (18/19). (Tính Legendre symbol (18/19).)
17. Determine the value of Legendre symbol (19/3). (Xác định giá trị của Legendre symbol (19/3).)
18. Calculate Legendre symbol (20/7). (Tính Legendre symbol (20/7).)
19. Find the value of the expression (21/11). (Tìm giá trị của biểu thức (21/11).)
20. Evaluate the Legendre symbol (22/5). (Đánh giá Legendre symbol (22/5).)