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

( a p ) {\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 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:

  1. ( a b p ) = ( a p ) ( b p ) {\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ì ( a p ) = ( b p ) {\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)}
  3. ( 1 p ) = 1 {\displaystyle \left({\frac {1}{p}}\right)=1}
  4. ( − 1 p ) = ( − 1 ) ( p − 1 ) / 2 = { 1  khi  p ≡ 1 ( mod 4 ) − 1  khi  p ≡ 3 ( mod 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. ( 2 p ) = ( − 1 ) ( p 2 − 1 ) / 8 = { 1  khi  p ≡ 1  hoac  7 ( mod 8 ) − 1  khi  p ≡ 3  hoac  5 ( mod 8 ) {\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ỳ, ( 3 p ) = ( − 1 ) ⌈ p + 1 6 ⌉ = { 1  khi  p ≡ 1  hoac  11 ( mod 12 ) − 1  khi  p ≡ 5  hoac  7 ( mod 12 ) {\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ỳ, ( 5 p ) = ( − 1 ) ⌊ p − 2 5 ⌋ = { 1  khi  p ≡ 1  hoac  4 ( mod 5 ) − 1  khi  p ≡ 2  hoac  3 ( mod 5 ) {\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ỳ, ( 7 p ) = { 1  khi  p ≡ 1 , 3 , 9 , 19 , 25 ,  hoac  27 ( mod 28 ) − 1  khi  p ≡ 5 , 11 , 13 , 15 , 17 ,  hoac  23 ( mod 28 ) {\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ì ( q p ) = ( p q ) ( − 1 ) ( ( p − 1 ) / 2 ) ( ( q − 1 ) / 2 ) {\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

( a p ) ≡ a ( p − 1 ) / 2 ( mod p ) . {\displaystyle \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:

( 12345 331 ) {\displaystyle \left({\frac {12345}{331}}\right)}
= ( 3 331 ) ( 5 331 ) ( 823 331 ) {\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {823}{331}}\right)}
= ( 3 331 ) ( 5 331 ) ( 161 331 ) {\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {161}{331}}\right)}
= ( 3 331 ) ( 5 331 ) ( 7 331 ) ( 23 331 ) {\displaystyle =\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {7}{331}}\right)\left({\frac {23}{331}}\right)}
= ( − 1 ) ( 331 3 ) ( 331 5 ) ( − 1 ) ( 331 7 ) ( − 1 ) ( 331 23 ) {\displaystyle =(-1)\left({\frac {331}{3}}\right)\left({\frac {331}{5}}\right)(-1)\left({\frac {331}{7}}\right)(-1)\left({\frac {331}{23}}\right)}
= − ( 1 3 ) ( 1 5 ) ( 2 7 ) ( 9 23 ) {\displaystyle =-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {9}{23}}\right)}
= − ( 1 3 ) ( 1 5 ) ( 2 7 ) ( 3 23 ) 2 {\displaystyle =-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {3}{23}}\right)^{2}}
= − ( 1 ) ( 1 ) ( 1 ) ( 1 ) = − 1 {\displaystyle =-\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.

Tham khảo