3.1 Thặng dư chính phương và Kí hiệu Legendre
Cho \(p\) là một số nguyên tố lẻ và \(a\) là một lớp đồng dư khả nghịch (hay \(\gcd(a, p) = 1\)). Một câu hỏi hoàn toàn tự nhiên là liệu có tồn tại \(x \bmod p\) là nghiệm của phương trình \(x^2 \equiv a \pmod p\) hay không?
Trong bài giảng trước, bằng việc xét đồng cấu nhóm:
\[ \iota : \mathbb{F}_p^* \to \mathbb{F}_p^*, \quad x \mapsto x^2 \]ta thu được \(|\text{Im}(\iota)| = \frac{p-1}{2}\). Hay nói một cách khác, có đúng \(\frac{p-1}{2}\) lớp thặng dư chính phương (các lớp thặng dư mà phương trình trên có nghiệm) và \(\frac{p-1}{2}\) lớp thặng dư không chính phương.
Định nghĩa 3.1 (Kí hiệu Legendre). Cho \(p\) là một số nguyên tố lẻ, \(a\) là một số nguyên thỏa mãn tính chất \(\gcd(a, p) = 1\). Khi đó kí hiệu Legendre \(\left(\frac{a}{p}\right)\) được định nghĩa như sau:
\[ \left(\frac{a}{p}\right) = \begin{cases} 1 & \text{nếu } a \text{ là một thặng dư chính phương} \\ -1 & \text{nếu } a \text{ không là một thặng dư chính phương} \end{cases} \]Mệnh đề 3.2. Cho \(p\) là một số nguyên tố lẻ và \(a\) là một số nguyên thỏa mãn tính chất \(\gcd(a, p) = 1\). Khi đó ta có:
\[ \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p \]Chứng minh Mệnh đề 3.2:
- Nếu \(a\) là một thặng dư chính phương, thì khi đó tồn tại \(x \in \mathbb{F}_p^*\) sao cho \(a \equiv x^2 \pmod p\). Lấy lũy thừa \(\frac{p-1}{2}\) cả hai vế của đẳng thức ta có:\[ a^{\frac{p-1}{2}} \equiv (x^2)^{\frac{p-1}{2}} = x^{p-1} \equiv 1 \pmod p \]Đẳng thức cuối là hệ quả trực tiếp của định lý Fermat nhỏ.
- Nếu \(a\) không là một thặng dư chính phương, ta sẽ đi chứng minh rằng \(a^{\frac{p-1}{2}} \not\equiv 1 \pmod p\). (Theo định lý Fermat nhỏ ta có \(a^{p-1} \equiv 1 \pmod p\), nên điều này tương đương với \(a^{\frac{p-1}{2}} \equiv -1 \pmod p\).)
Ta có nhận xét rằng \(x^{\frac{p-1}{2}} - 1\) là một đa thức bậc \(\frac{p-1}{2}\) với hệ số trên trường \(\mathbb{F}_p\). Đa thức này đã có \(\frac{p-1}{2}\) nghiệm phân biệt là các lớp thặng dư chính phương trong \(\mathbb{F}_p^*\). Do đó điều phải chứng minh là hệ quả trực tiếp của Hệ quả 3.4 dưới đây.
Định lý Bézout cho Đa thức và Hệ quả
Định lý 3.3 (Định lý Bezout). Cho \(P(X) \in \mathbb{F}_p[X]\). Khi đó \(a \in \mathbb{F}_p\) là nghiệm của đa thức \(P\) khi và chỉ khi tồn tại một đa thức \(Q(X) \in \mathbb{F}_p[X]\) sao cho:
\[ P(X) = (X - a) \cdot Q(X) \]Chứng minh Định lý 3.3:
Áp dụng thuật toán chia Euclid cho đa thức \(P(X)\) và \(X - a\), khi đó ta có tồn tại duy nhất một đa thức \(Q(X) \in \mathbb{F}_p[X]\) và một hằng số \(c \in \mathbb{F}_p\) (do bậc của đa thức \(X - a\) là \(1\)) sao cho:
\[ P(X) = (X - a) \cdot Q(X) + c \]- Nếu \(a\) là nghiệm của \(P\), thay \(X = a\) vào phương trình trên ta thu được \(c = 0\).
- Nếu \(c = 0\), khi đó thay \(X = a\) vào phương trình trên ta thu được \(P(a) = 0\). Hay nói cách khác \(a\) là nghiệm của đa thức \(P(X)\).
Hệ quả 3.4. Cho \(P(X) \in \mathbb{F}_p[X]\) là một đa thức có bậc là \(n\). Khi đó \(P(X)\) có không quá \(n\) nghiệm (tính cả bội) trong \(\mathbb{F}_p\).