Ký hiệu Jacobi

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.

Định nghĩa

Ký hiệu Jacobi ( a n ) {\displaystyle \left({\frac {a}{n}}\right)} sử dụng 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}}} là dạng phân tích tiêu chuẩn của 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}}} trong đó tất cả các ký hiệu bên vế phải là Ký hiệu Legendre.

Các tính chất của ký hiệu Jacobi

Các tính chất sau thường dùng để tính nhanh ký hiệu Jacobi:

  1. Nếu n là số nguyên tố thì ký hiệu Jacobi là ký hiệu Legendre.
  2. ( a n ) ∈ { 0 , 1 , − 1 } {\displaystyle \left({\frac {a}{n}}\right)\in \{0,1,-1\}}
  3. ( a n ) = 0 {\displaystyle \left({\frac {a}{n}}\right)=0} nếu gcd ( a , n ) ≠ 1 {\displaystyle \gcd(a,n)\neq 1}
  4. ( a b n ) = ( a n ) ( b n ) {\displaystyle \left({\frac {ab}{n}}\right)={\Bigg (}{\frac {a}{n}}{\Bigg )}\left({\frac {b}{n}}\right)}
  5. ( a m n ) = ( a m ) ( a n ) {\displaystyle \left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right)} . Điều này dẫn tới ( a n 2 ) {\displaystyle \left({\frac {a}{n^{2}}}\right)} là 0 hoặc 1 với số nguyên a bất kỳ và số tự nhiên lẻ n bất kỳ.
  6. Nếu a ≡ b (mod n), thì ( a n ) = ( b n ) {\displaystyle {\Bigg (}{\frac {a}{n}}{\Bigg )}=\left({\frac {b}{n}}\right)}
  7. ( 1 n ) = 1 {\displaystyle \left({\frac {1}{n}}\right)=1}
  8. ( − 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.}
  9. ( 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.}}
  10. ( 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}}} nếu 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.

Lưu ý

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} thì 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}} mod 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}} mod 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.

Ví dụ

( 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.

Các hàm liên quan

  • Ký hiệu Kronecker là tổng quát hóa của ký hiệu Jacobi cho tất cả các số nguyên.

Tham khảo

Liên kết ngoài

  • Calculate Jacobi symbol Lưu trữ 2008-07-20 tại Wayback Machine