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 ( 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 sau thường sử dụng để có thể tính nhanh ký hiệu Legendre: ( 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. Nếu a ≡ b (mod p), thì ( a p ) = ( b p ) {\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)} ( 1 p ) = 1 {\displaystyle \left({\frac {1}{p}}\right)=1} ( − 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}}} ( 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}}} 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}}} 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}}} 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}}} 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}}.} 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} 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.