3. Thặng dư chính phương

Định nghĩa 3.17 (Số chính phương modulo \(p\))

Xét số nguyên tố lẻ \(p\). Số \(a\) được gọi là số chính phương modulo \(p\) nếu \((a, m) = 1\) và tồn tại số \(x\) sao cho \(x^2 = a \pmod p\).

Nói cách khác phương trình đồng dư \(x^2 \equiv a \pmod p\) có nghiệm.

Chúng ta sử dụng kí hiệu Legendre (Legendre symbol) để thể hiện một số \(a\) có phải là số chính phương modulo nguyên tố \(p\) không.

Định nghĩa 3.18 (Legendre symbol)

Xét \(p\) là số nguyên tố, \(a\) là số nguyên không chia hết cho \(p\). Khi đó kí hiệu Legendre được định nghĩa là

\[\begin{split}\left(\frac{a}{p}\right) = \begin{cases} 1, & \text{ nếu } a \text{ là số chính phương modulo } p. \\ -1, & \text{ nếu ngược lại}. \end{cases}\end{split}\]

Một trường hợp tổng quát hơn của kí hiệu Legendre là kí hiệu Jacobi áp dụng cho số nguyên dương bất kì.

Định nghĩa 3.19 (Jacobi symbol)

Xét \(n\) là số nguyên dương, \(a\) là số nguyên không chia hết cho \(n\). Khi đó kí hiệu Jacobi được định nghĩa là

\[\begin{split}\left(\frac{a}{n}\right) = \begin{cases} 1, & \text{ nếu } a \text{ là số chính phương modulo } n \\ -1, & \text{ nếu ngược lại.} \end{cases}\end{split}\]

3.1. Bài tập sưu tầm

Câu 1 (đề kiểm tra, ITMO). Số \(3\) có là số chính phương modulo \(323\) không?

Vì \(323 = 17 \cdot 19\), ta sử dụng tiêu chuẩn Euler cho từng modulo \(17\) và \(19\):

\[\begin{split}\left(\frac{3}{17}\right) = 3^{\frac{17 - 1}{2}} \equiv -1 \pmod{17}, \\ \left(\frac{3}{19}\right) = 3^{\frac{19 - 1}{2}} \equiv -1 \pmod{19}.\end{split}\]

Như vậy \(3\) không là số chính phương trong modulo \(17\) và \(19\).

Kết luận: \(3\) không là số chính phương modulo \(323\).