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
![{\displaystyle \left({\frac {a}{p}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aad4dd123bb7bc0da377dec595d91761753ba294)
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 k2 ≡ 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:
(Nó là hàm có tính chất nhân đối với đối số trên. - Nếu a ≡ b (mod p), thì
![{\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22c53d660aed6373e99b8e0feb7d9801186b2d41)
![{\displaystyle \left({\frac {1}{p}}\right)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df1bc66bb06845bb4d2d3908f9ab3d72493874ce)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89addc9ab786405547089c8e0de75a42896a6701)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6d9896ce86742cc091630fcc25026be211e4bdd)
- 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b1e588b24263014ebf010621a2fb2ac06781188)
- 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd814ce3d98004348526e36283aed5fbc76c2636)
- 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d71069d97cf138ea006f8e550f2df7fe1926073)
- 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)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3546345c8f00b666986c22445ae21c234ddaaae8)
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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/873423142ba8132e892e0e12aa898b5df55ffe9e)
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:
![{\displaystyle \left({\frac {12345}{331}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/827ce8eb12cd064d538fba78851cdcf32f5237e9)
![{\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {823}{331}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/239c0bd33998501f6f040a0a53f0757f665b1cb8)
![{\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {161}{331}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e27dfd260354631933b8f1a96998af6093847c45)
![{\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {7}{331}}\right)\left({\frac {23}{331}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/827eecd5ac37c8bb9f0e1708f0752d2741785690)
![{\displaystyle =(-1)\left({\frac {331}{3}}\right)\left({\frac {331}{5}}\right)(-1)\left({\frac {331}{7}}\right)(-1)\left({\frac {331}{23}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e15893c92c8e69189b6dbe3fc84878f80016cf56)
![{\displaystyle =-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {9}{23}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d9f3d05e8faa1196ae844ff490e380543cf4cd9d)
![{\displaystyle =-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {3}{23}}\right)^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ab36b474cf5d1e547a7c818815d1588f528dcff)
![{\displaystyle =-\left(1\right)\left(1\right)\left(1\right)\left(1\right)=-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df1522040774dcd25c96c036128a0f5b319c697f)
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.
Tham khảo