Ký hiệu Legendre

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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[sửa | sửa mã nguồn]

Ký hiệu Legendre được định nghĩa như sau:

Nếu psố nguyên tố lẻ và a là một số tự nhiên, thì kí hiệu Legendre

\left(\frac{a}{p}\right)

là:

  • 0 nếu p chia hết a;,
  • 1 nếu athặng dư bậc hai modulo p — nghĩa là tồn tại số nguyên k sao cho k2a (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[sửa | sửa mã nguồn]

Các tính chất sau thường sử dụng để có thể tính nhanh ký hiệu Legendre:

  1. 
\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 ab (mod p), thì 
\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)
  3. 
\left(\frac{1}{p}\right) = 1
  4. 
\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. 
\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ỳ, 
\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ỳ, 
\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 \pmod5 \\-1\mbox{ khi }p \equiv 2\mbox{ hoac }3 \pmod5  \end{cases}
  8. Với số nguyên tố lẻ p bất kỳ, 
\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 pq là các số nguyên tố lẻ thì 
\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


\left(\frac{a}{p}\right) \equiv a^{(p-1)/2}\pmod p.

Ví dụ[sửa | sửa mã nguồn]

Có thể sử dụng các tính chất trên để tính ký hiệu Legendre. Chẳng hạn:

\left (\frac{12345}{331}\right)
=\left (\frac{3}{331}\right) \left (\frac{5}{331}\right) \left (\frac{823}{331}\right)
=\left (\frac{3}{331}\right) \left (\frac{5}{331}\right) \left (\frac{161}{331}\right)
=\left (\frac{3}{331}\right) \left (\frac{5}{331}\right) \left (\frac{7}{331}\right) \left (\frac{23}{331}\right)
= (-1) \left (\frac{331}{3}\right) \left (\frac{331}{5}\right) (-1) \left (\frac{331}{7}\right) (-1) \left (\frac{331}{23}\right)
=-\left (\frac{1}{3}\right) \left (\frac{1}{5}\right) \left (\frac{2}{7}\right) \left (\frac{9}{23}\right)
=-\left (\frac{1}{3}\right) \left (\frac{1}{5}\right) \left (\frac{2}{7}\right) \left (\frac{3}{23}\right)^2
= - \left (1\right) \left (1\right) \left (1\right) \left (1\right) = -1

Tổng quát hóa[sửa | sửa mã nguồn]

  • 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[sửa | sửa mã nguồn]