Ký hiệu Legendre

Ký hiệu Legendre là một khái niệm trong lý thuyết số. 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.

Định nghĩa

Ký hiệu Legendre được định nghĩa như sau:

Nếu p là số nguyên tố lẻ và a là một số tự nhiên, thì ký hiệu Legendre

$\left({\frac {a}{p}}\right)$

là:

• 0 nếu p chia hết a;,
• 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à bình phương modulo p.

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{cases}1{\mbox{ khi }}p\equiv 1{\pmod {4}}\\-1{\mbox{ khi }}p\equiv 3{\pmod {4}}\end{cases}}$
5. $\left({\frac {2}{p}}\right)=(-1)^{(p^{2}-1)/8}={\begin{cases}1{\mbox{ khi }}p\equiv 1{\mbox{ hoac }}7{\pmod {8}}\\-1{\mbox{ khi }}p\equiv 3{\mbox{ hoac }}5{\pmod {8}}\end{cases}}$
6. Với số nguyên tố lẻ p bất kỳ, $\left({\frac {3}{p}}\right)=(-1)^{\left\lceil {\frac {p+1}{6}}\right\rceil }={\begin{cases}1{\mbox{ khi }}p\equiv 1{\mbox{ hoac }}11{\pmod {12}}\\-1{\mbox{ khi }}p\equiv 5{\mbox{ hoac }}7{\pmod {12}}\end{cases}}$
7. Với số nguyên tố lẻ p bất kỳ, $\left({\frac {5}{p}}\right)=(-1)^{\left\lfloor {\frac {p-2}{5}}\right\rfloor }={\begin{cases}1{\mbox{ khi }}p\equiv 1{\mbox{ hoac }}4{\pmod {5}}\\-1{\mbox{ khi }}p\equiv 2{\mbox{ hoac }}3{\pmod {5}}\end{cases}}$
8. Với số nguyên tố lẻ p bất kỳ, $\left({\frac {7}{p}}\right)={\begin{cases}1{\mbox{ khi }}p\equiv 1,3,9,19,25,{\mbox{ hoac }}27{\pmod {28}}\\-1{\mbox{ khi }}p\equiv 5,11,13,15,17,{\mbox{ hoac }}23{\pmod {28}}\end{cases}}$
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}{\pmod {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.