Bách khoa toàn thư mở Wikipedia
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 k 2 ≡ 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)}
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.
