Định nghĩa 1: Một số nguyên a được gọi là thặng dư bình phương mod n nếu tồn tại số nguyên x sao cho
$x^2 \equiv a (mod n)$
Ta cũng có thể gọi a là số chính phương mod p
Định nghĩa 2: Giả sử p là một số nguyên tố lẻ, a là một số nguyên, Kí hiệu Legendre $\left ( \frac{a}{p} \right )$được xác định như sau:
$\left ( \frac{a}{p} \right )=1$ Khi (a,p)=1 và a là thặng dư bình phương mod p
$\left ( \frac{a}{p} \right )=-1$ Khi (a,p)=1 và a không là số chính phương mod p
$\left ( \frac{a}{p} \right )=0$ nếu $a \vdots p$
Định lý:
1) (Tiêu chuẩn Euler) Cho p là một số nguyên tố và a là một số nguyên. Khi đó ta có $a^{\frac{p-1}{2}}\equiv \left ( \frac{a}{p} \right ) (mod p)$
Chứng minh:
Gọi g là một căn nguyên thủy của p (có nghĩa là g là một số nguyên sao cho p-1 là số mũ lớn nhất để $g^{p-1} \equiv 1 (mod p)$ Khi đó ta được hệ thặng dư thu gọn mod p {$1,g,g^2,..g^{p-2}$}.
Giả sử $a=g^i$ Ta cần chứng minh:
$a^{\frac{p-1}{2}} \equiv (g^i)^{\frac{p-1}{2}} \Rightarrow i.\frac{p-1}{2}\equiv 0 (mod p-1)$
$\Rightarrow$ i là số chẵn
Suy ra tồn tại j sao cho i=2j $\Rightarrow a=(g^j)^2 \Rightarrow \left ( \frac{a}{p} \right )=1 $
Ngược lại $\left ( \frac{a}{p} \right )=1 \Rightarrow $ tồn tại j sao cho $a \equiv (g^j)^2 (mod p) \Rightarrow g^i\equiv (g^j)^2 (mod p) \Rightarrow i \equiv 2j(mod p-1) \Rightarrow i\equiv 0(mod 2) $
Do đó $a^{\frac{p-1}{2}}\equiv (g^i)^{\frac{p-1}{2}}=g^{(p-1)k}\equiv 1 (mod p)$
Bài tập áp dụng:
Cho $f_n$ là số Fermat chứng minh rằng ước nguyên tố p của $f_n$ có dạng $p=s.2^{n+2}+1$ với s là số tự nhiên.
Giải
Gọi $m=ord_2(p)$ suy ra m có dang $2^k$ rõ ràng k không thể $\le n$
Vậy $k=n+1$, áp dụng định lý Fermat bé ta có $p=h.2^{n+1}+1$
Ta xét $p=8t+1$ khi đó theo tiêu chuẩn euler thì 2 là số chính phương mod p.
Suy ra $2^{n+1} | (p-1)/2$ suy ra điều phải chứng minh
Định lí 2: Luật tương hỗ Gauss;
$\left ( \frac{p}{q} \right )\left ( \frac{q}{p} \right )=(-1)^{\frac{(p-1)(q-1)}{4}}$
Chứng minh
Đặt A={a|(a,pq)=1,$1 \le a \le \frac{pq-1}{2}$}, $B=\prod_{x \in A}x$
Còn tiếp ...
