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.

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

${\displaystyle \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 sau thường sử dụng để có thể tính nhanh ký hiệu Legendre:

1. ${\displaystyle \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ì ${\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)}$
3. ${\displaystyle \left({\frac {1}{p}}\right)=1}$
4. ${\displaystyle \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. ${\displaystyle \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ỳ, ${\displaystyle \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ỳ, ${\displaystyle \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ỳ, ${\displaystyle \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ì ${\displaystyle \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

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

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

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

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

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

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

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

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

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

${\displaystyle =-\left(1\right)\left(1\right)\left(1\right)\left(1\right)=-1}$

• 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.