Bách khoa toàn thư mở Wikipedia
Ký hiệu Jacobi là tổng quát hóa của ký hiệu Legendre . Nó được sử dụng trong lý thuyết số và được đặt theo tên nhà toán học Carl Gustav Jakob Jacobi .
Ký hiệu Jacobi
(
a
n
)
{\displaystyle \left({\frac {a}{n}}\right)}
dạng phân tích tiêu chuẩn của số đứng dưới. Nó được định nghĩa như sau:
Giả sử n > 0 là số tự nhiên lẻ và
p
1
α
1
p
2
α
2
⋯
p
k
α
k
{\displaystyle p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}}
n . Với số nguyên a bất kỳ, ký hiệu Jacobi
(
a
n
)
=
(
a
p
1
)
α
1
(
a
p
2
)
α
2
⋯
(
a
p
k
)
α
k
{\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)^{\alpha _{1}}\left({\frac {a}{p_{2}}}\right)^{\alpha _{2}}\cdots \left({\frac {a}{p_{k}}}\right)^{\alpha _{k}}}
Ký hiệu Legendre .
Các tính chất của ký hiệu Jacobi [ sửa | sửa mã nguồn ] Các tính chất sau thường dùng để tính nhanh ký hiệu Jacobi:
Nếu n là số nguyên tố thì ký hiệu Jacobi là ký hiệu Legendre.
(
a
n
)
∈
{
0
,
1
,
−
1
}
{\displaystyle \left({\frac {a}{n}}\right)\in \{0,1,-1\}}
(
a
n
)
=
0
{\displaystyle \left({\frac {a}{n}}\right)=0}
gcd
(
a
,
n
)
≠
1
{\displaystyle \gcd(a,n)\neq 1}
(
a
b
n
)
=
(
a
n
)
(
b
n
)
{\displaystyle \left({\frac {ab}{n}}\right)={\Bigg (}{\frac {a}{n}}{\Bigg )}\left({\frac {b}{n}}\right)}
(
a
m
n
)
=
(
a
m
)
(
a
n
)
{\displaystyle \left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right)}
(
a
n
2
)
{\displaystyle \left({\frac {a}{n^{2}}}\right)}
a bất kỳ và số tự nhiên lẻ n bất kỳ.Nếu a ≡ b (mod n ), thì
(
a
n
)
=
(
b
n
)
{\displaystyle {\Bigg (}{\frac {a}{n}}{\Bigg )}=\left({\frac {b}{n}}\right)}
(
1
n
)
=
1
{\displaystyle \left({\frac {1}{n}}\right)=1}
(
−
1
n
)
=
(
−
1
)
(
n
−
1
)
2
=
{
1
khi
n
≡
1
mod
4
−
1
khi
n
≡
3
mod
4
{\displaystyle \left({\frac {-1}{n}}\right)=(-1)^{\frac {(n-1)}{2}}=\left\{{\begin{array}{cl}1&{\textrm {khi}}\;n\equiv 1\mod 4\\-1&{\textrm {khi}}\;n\equiv 3\mod 4\end{array}}\right.}
(
2
n
)
=
(
−
1
)
(
n
2
−
1
)
8
=
{
1
if
n
≡
1
hoac
7
mod
8
−
1
if
n
≡
3
hoac
5
mod
8
{\displaystyle {\left({\frac {2}{n}}\right)=(-1)^{\frac {(n^{2}-1)}{8}}=\left\{{\begin{array}{cl}1&{\textrm {if}}\;n\equiv 1\;{\textrm {hoac}}\;7\mod 8\\-1&{\textrm {if}}\;n\equiv 3\;{\textrm {hoac}}\;5\mod 8\end{array}}\right.}}
(
m
n
)
(
n
m
)
=
(
−
1
)
(
m
−
1
)
(
n
−
1
)
4
{\displaystyle \left({\frac {m}{n}}\right)\left({\frac {n}{m}}\right)=(-1)^{\frac {(m-1)(n-1)}{4}}}
m vàd n là các số tự nhiên lẻ.Tính chất sau cùng thường được biết với tên giống như trong ký hiệu Legendre: luật thuận nghịch bình phương .
Có hai tính chất đúng với ký hiệu Legendre nhưng không thể mở rộng cho ký hiệu Jacobi.
Thứ nhất, nếu
(
a
n
)
=
−
1
{\displaystyle \left({\frac {a}{n}}\right)=-1}
a không là thặng dư bậc hai của n vì a không là thặng dư bậc hai của một số thừa số của n . Tuy nhiên, ngược lại khi
(
a
n
)
=
1
{\displaystyle \left({\frac {a}{n}}\right)=1}
a chưa chắc chắn là thặng dư bậc hai của n . Bởi vì ký hiệu Jacobi là tích của các ký hiệu Legendre, nên có thể có hai ký hiệu Legendre bằng −1 và khi đó ký hiệu Jacobi bằng 1.
Tính chất thứ hai không thể mở rộng gắn với đồng dư thức Euler
(
a
p
)
≡
a
(
p
−
1
)
/
2
{\displaystyle \left({\frac {a}{p}}\right)\equiv a^{(p-1)/2}}
p với số nguyên tố p và số nguyên a bất kỳ. Một cách tự nhiên đồng dư thức Euler mở rộng từ ký hiệu Legendre sang ký hiệu Jacobi là:
(
a
n
)
≡
a
(
n
−
1
)
/
2
{\displaystyle \left({\frac {a}{n}}\right)\equiv a^{(n-1)/2}}
n với hợp số lẻ dương n . Tuy nhiên đồng dư thức này là sai với ít nhất một nửa của các a mod n khi n là hợp số. Tỷ lệ này là cơ sở của thuật toán kiểm tra Solovay-Strassen kiểm tra tính nguyên tố theo xác suất.
(
37035
331
)
{\displaystyle \left({\frac {37035}{331}}\right)}
=
(
294
331
)
{\displaystyle =\left({\frac {294}{331}}\right)}
=
1
⋅
(
2
331
)
(
147
331
)
{\displaystyle =1\cdot \left({\frac {2}{331}}\right)\left({\frac {147}{331}}\right)}
=
−
(
147
331
)
{\displaystyle =-\left({\frac {147}{331}}\right)}
=
(
331
147
)
{\displaystyle =\left({\frac {331}{147}}\right)}
=
(
37
147
)
{\displaystyle =\left({\frac {37}{147}}\right)}
=
(
147
37
)
{\displaystyle =\left({\frac {147}{37}}\right)}
=
(
36
37
)
{\displaystyle =\left({\frac {36}{37}}\right)}
=
(
2
37
)
2
(
9
37
)
{\displaystyle =\left({\frac {2}{37}}\right)^{2}\left({\frac {9}{37}}\right)}
=
(
37
9
)
{\displaystyle =\left({\frac {37}{9}}\right)}
=
(
1
9
)
=
1.
{\displaystyle =\left({\frac {1}{9}}\right)=1.}
Vì 331 là số nguyên tố nên từ đó 37035 là thặng dư bậc hai mod 331.
