Ký hiệu Legendre

Giá trị của kí hiệu Legendre (Bản mẫu:Sfrac) với a (theo hàng) và p (theo cột).

Bản mẫu:Diagonal split header	0	1	2	3	4	5	6	7	8	9	10
3	0	1	−1
5	0	1	−1	−1	1
7	0	1	1	−1	1	−1	−1
11	Bản mẫu:00	Bản mẫu:01	−1	1	Bản mẫu:01	1	−1	−1	−1	Bản mẫu:01	−1
Trong bảng này chỉ xét trường hợp 0 ≤ a < p, do nếu a lớn hơn p thì có thể rút gọn về trường hợp nhỏ hơn. Các thặng dư bậc hai được làm nổi bật bằng ô màu vàng, với các giá trị 0 và 1.

Trong lí thuyết số, kí hiệu Legendre là một hàm nhân tính nhận ba giá trị 1, -1 và 0. Nó được đặt theo tên của nhà toán học Pháp Adrien-Marie Legendre và gắn liền với khái niệm thặng dư bậc hai.

Kí hiệu này được Legendre giới thiệu vào năm 1798 trong các bài giảng hướng đến việc chứng minh luật thuận nghịch bậc hai của ông. Tổng quát hóa của kí hiệu Legendre có kí hiệu Jacobi và đặc trưng Dirichlet bậc cao. Sự tiện dụng của kí hiệu này đã tạo cảm hứng cho những kí hiệu khác xuất hiện trong lí thuyết số đại số như kí hiệu Hilbert hay kí hiệu Artin.

Định nghĩa

Nếu p là số nguyên tố lẻ và a là một số nguyên, thì ký hiệu Legendre $\left(\frac{a}{p}\right)$ có thể nhận các giá trị:

• 0 nếu p chia hết a, hay a là bội của p.
• 1 nếu a là thặng dư bậc hai modulo p — nghĩa là tồn tại số nguyên k sao cho k² ≡ a (mod p);
• −1 nếu a không là thặng dư bậc hai modulo p, hay ta gọi a là bất thặng dư bậc hai modulo p.

Tuy nhiên, ban đầu Legendre lại định nghĩa như sau: $\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}(\mathrm{mod}p)\text{ và }\left(\frac{a}{p}\right)\in \{-1,0,1\}.$

Các tính chất của ký hiệu Legendre

Các tính chất sau thường sử dụng để có thể tính nhanh ký hiệu Legendre:

1. $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$ (Nó là hàm có tính chất nhân đối với đối số trên.
2. Nếu a ≡ b (mod p), thì $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$
3. $\left(\frac{1}{p}\right)=1$
4. $\left(\frac{-1}{p}\right)=(-1{)}^{(p-1)/2}=\{\begin{array}{c}1\text{ khi }p\equiv 1(\mathrm{mod}4)\\ -1\text{ khi }p\equiv 3(\mathrm{mod}4)\end{array}$
5. $\left(\frac{2}{p}\right)=(-1{)}^{(p^2-1)/8}=\{\begin{array}{c}1\text{ khi }p\equiv 1\text{ hoac }7(\mathrm{mod}8)\\ -1\text{ khi }p\equiv 3\text{ hoac }5(\mathrm{mod}8)\end{array}$
6. Với số nguyên tố lẻ p bất kỳ, $\left(\frac{3}{p}\right)=(-1{)}^{\lceil \frac{p+1}{6}\rceil }=\{\begin{array}{c}1\text{ khi }p\equiv 1\text{ hoac }11(\mathrm{mod}12)\\ -1\text{ khi }p\equiv 5\text{ hoac }7(\mathrm{mod}12)\end{array}$
7. Với số nguyên tố lẻ p bất kỳ, $\left(\frac{5}{p}\right)=(-1{)}^{\lfloor \frac{p-2}{5}\rfloor }=\{\begin{array}{c}1\text{ khi }p\equiv 1\text{ hoac }4(\mathrm{mod}5)\\ -1\text{ khi }p\equiv 2\text{ hoac }3(\mathrm{mod}5)\end{array}$
8. Với số nguyên tố lẻ p bất kỳ, $\left(\frac{7}{p}\right)=\{\begin{array}{c}1\text{ khi }p\equiv 1,3,9,19,25,\text{ hoac }27(\mathrm{mod}28)\\ -1\text{ khi }p\equiv 5,11,13,15,17,\text{ hoac }23(\mathrm{mod}28)\end{array}$
9. Nếu p và q là các số nguyên tố lẻ thì $\left(\frac{q}{p}\right)=\left(\frac{p}{q}\right)(-1{)}^{((p-1)/2)((q-1)/2)}$

Tính chất sau cùng thường được gọi là luật thuận nghịch bình phương. Các tính chất 4 và 5 là các trường hợp riêng của luật trên. Cả hai được chứng minh từ Bổ đề Gauss.

Ký hiệu Legendre được sử dụng trong tiêu chuẩn Euler do Euler chứng minh

$\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}(\mathrm{mod}p).$

Ví dụ

Có thể sử dụng các tính chất trên để tính ký hiệu Legendre. Chẳng hạn:

$\left(\frac{12345}{331}\right)$

$=\left(\frac{3}{331}\right)\left(\frac{5}{331}\right)\left(\frac{823}{331}\right)$

$=\left(\frac{3}{331}\right)\left(\frac{5}{331}\right)\left(\frac{161}{331}\right)$

$=\left(\frac{3}{331}\right)\left(\frac{5}{331}\right)\left(\frac{7}{331}\right)\left(\frac{23}{331}\right)$

$=(-1)\left(\frac{331}{3}\right)\left(\frac{331}{5}\right)(-1)\left(\frac{331}{7}\right)(-1)\left(\frac{331}{23}\right)$

$=-\left(\frac{1}{3}\right)\left(\frac{1}{5}\right)\left(\frac{2}{7}\right)\left(\frac{9}{23}\right)$

$=-\left(\frac{1}{3}\right)\left(\frac{1}{5}\right)\left(\frac{2}{7}\right){\left(\frac{3}{23}\right)}^2$

$=-\left(1\right)\left(1\right)\left(1\right)\left(1\right)=-1$

Tổng quát hóa

• Ký hiệu Jacobi là tổng quát của ký hiệu Legendre cho các số dưới là các hợp số dương lẻ.
• Một dạng tổng quát hoa khác là Ký hiệu Kronecker, mở rộng cho các số dưới là các số nguyên tổng quát.